Стратегия поиска

Опишем оценочную функцию f(u)=g(u)+h(u).

Очевидно, что g(u) — число ходов, сделанных от начальной конфигурации до текущей конфигурации u.

«Малой» эвристикой h(u) будет являться суммарное расстояние фишек в конфигурации u до их позиций в целевой конфигурации (рис. 12):

Рисунок 12. Целевая конфигурация игры в «8»

Tot_dist=1+1+2=4

Если бы фишкам разрешалось двигаться через занятые клетки, то каждая фишка добралась бы до своей целевой позиции за число ходов, равное расстоянию.

Поскольку фишки могут перемещаться только через пустую клетку, их пути будут длиннее.

Таким образом, h(u)≤h*(u) для всех u.

Если мы сумеем за реальное время найти решение с помощью h(u), оно будет минимальным.

Но для третьей стартовой конфигурации такой эвристики будет недостаточно. Введем «большую» эвристику

h(u) = «суммарное расстояние» + С * «степень упорядоченности»

C — константа, которая подбирается опытным путем при прогоне программы. Из всех возможных значений C выбирается то, которое дает минимальное число ходов. Степень упорядоченности соответствует расположению фишек 1..8 по часовой стрелке.

За отклонение текущей конфигурации от такого расположения будем начислять штрафные очки.

Начисление штрафных очков:

фишка, не равная «0» в центре поля — 1 очко;

для фишки «i» (не в центре поля) по часовой стрелке не «i+1», i=1..7 — 2 очка;

для фишки «8» (не в центре поля) по часовой стрелке не фишка «1» — 2 очка.

Для первой стартовой позиции (рис. 11) степень упорядоченности равна 2+2+2=6 очков, где штрафные очки набирают фишки «1», «2» и «4».

Окончательно, наша эвристика имеет вид

h(u) = «суммарное расстояние» + C * «степень упорядоченности»

и при C=0 h(u) ≤ h*(u),

при C≥1 h(u) > h*(u).