Mandist ( SI, S2, D)

где D — манхэттенское расстояние между клетками S1 и S2; оно измеряется как сумма расстояний между S1 и S2 в горизонтальном и вертикальном направлениях. Необходимо найти путь к решению минимальной длины. Поэтому определим стоимость всех дуг в пространстве состояний как равную 1. В программе, заданы также три примера начальных позиций, которые составлены по диаграммам, показанным на рис. 5.3. Рис. 5.3 Три начальные позиции для головоломки "игра е восемь":

а) требует. 4 хода; б) требует. 5 ходов; в) требует 18 ходов

Эвристическая функция h определяется в программе следующим образом: