ПРИКЛАД ЗАСТОСУВАННЯ АЛГОРИТМУ А *

Розглянемо гру «Вісім», для якої випливає з початкового стану S ₀ перейти в кінцевий стан S, (рис. 9). Кожен хід в цій грі можна інтерпретувати як рух порожньої клітки - цифри 0 в відповідних матрицях.

Мал. 9

Метою цієї гри є пошук найкоротшої послідовності рухів 0, що переводить стан S ₀ в кінцевий стан S _r Поточний стан, отримане після декількох ходів, позначимо S.

Визначимо оціночну функцію f (S) = g (S) + h (S ), поклавши # ^ рівним фактичному числу ходів, що призвели до стану S зі стану S ₀ , а евристичну функцію h (S) покладемо рівною кількістю фішок, розташованих не на своїх місцях в стані S в порівнянні з цільовим станом S _r з умови задачі і визначення функції h (S) слід нерівність h (S) <h * (S) для всіх нецільових вершин. Дерево пошуку, отримане за допомогою алгоритму А*, Наведено на рис. 10. На ньому близько кожного стану справа внизу в квадратних дужках через кому представлені відповідні значення g (S) і h (S). Оптимальний вирішальний шлях виділений масними лініями. При цьому початковому стані S ₀ буде потрібно щонайменше п'ять рухів порожній клітини-цифри 0 для отримання цільового стану S ,.

Мал. 10

Зауважимо, що алгоритм А * з тієї ж оціночної функцією для двох інших початкових станів (див. Рис. 11) побудує оптимальні вирішальні шляхи відповідно в 4 і 18 ходів.

Мал. 11