Пример применения алгоритма А*

Рассмотрим игру «Восемь», для которой следует из начального состояния 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.