4 Методологія розв’язування гри у вісімки
1. Вешина простору станів – деяка кофігурація з фішок на гральній дошці, наприклад, список поточного положення фішок.
2. Кожне розміщення визначається парою координат (х, у).
3. Елементи списку розміщені у такому порядку: поточне розміщення порожньої клітинки, поточне розміщення фішки 1, поточне розміщення фішки 2 і т.д.
4. .Довжина усіх дуг – 1.
5. Евристична функція h визначається як комбінація двох оцінок:
a) Sum – сумарна відстань восьми фішок, що знаходяться у поточній позиції Поз, від їх розміщення у цільвій позиції.
b) Sort – ступінь впорядкування фішок у поточній позиції по відношенню до того порядку, у якому вони повинні знахожитись у цільвій позиції. Цей показник визначається за таким правилом:
9Фішка у центральній позиції –1 очко,
9Фішка не у центральній позиції, і безпосередньо за нею слідує за годинниковою стрілкою та фішка, яка і повинна за нею слідувати у цільовій позиції – 0 очок,
9Те ж саме, але за фішкою слідує “не та” фішка – 2 очка.
6. Евристична оцінка визначається як сума
H= sum +3*sort.
Ця еврістична функція добре працює у тому розумінні, що ефективно скеровує пошук до кінцевої мети. У більшості випадків, якщо початкова комбінация фішок має розв`язок, кінцева комбінація знаходиться з мінімальною кількістю повернень. Проте введена еврістична функція не є допустимою, тобто нема гарантії, що коротший шлях знайдеться швидше, ніж довший. Справа у тому, що для функції h умова h £ h* виконується не для всіх вершин простору станів. Здругого боку, оцінка “сумарна відстань” допустима: для всіх позицій, Sum £ h*.
5
5 Приклад роботи алгоритму
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
1 |
2 |
|
4 |
5 |
3 |
7 |
8 |
6 |
1 |
2 |
3 |
4 |
8 |
5 |
7 |
|
6 |
1 |
2 |
3 |
4 |
5 |
|
7 |
8 |
6 |
1 |
|
3 |
4 |
2 |
5 |
7 |
8 |
6 |
1 |
2 |
3 |
7 |
4 |
5 |
|
8 |
6 |
2 |
4 |
3 |
1 |
5 |
6 |
7 |
|
8 |
1 |
2 |
3 |
|
4 |
5 |
7 |
8 |
6 |
2 |
4 |
3 |
1 |
5 |
6 |
7 |
8 |
|
2 |
4 |
|
1 |
5 |
3 |
7 |
8 |
6 |
2 |
3 |
|
1 |
4 |
5 |
7 |
8 |
6 |
2 |
4 |
3 |
7 |
1 |
5 |
|
8 |
6 |
|
4 |
3 |
2 |
1 |
5 |
7 |
8 |
6 |
2 |
4 |
3 |
1 |
5 |
|
7 |
8 |
6 |
2 |
|
3 |
1 |
4 |
5 |
7 |
8 |
6 |
2 |
4 |
3 |
|
1 |
5 |
7 |
8 |
6 |
2 |
4 |
3 |
1 |
8 |
5 |
7 |
6 |
|
2 |
4 |
3 |
1 |
8 |
5 |
|
7 |
6 |
1
2 4 3
6 1 8 5
7 6
2
2 4 3
8 6 1 5 7
7 8 6
5 6 3
7 7 6
7 4 8 2 3
9 7 1 4 5 9 8 6 7 8 6
8
7 8
9
7 9
9 7 9
9 7
6