Допустимая модификация Heuristi c

Question

В настоящее время я работаю над проектом, включающим головоломку и различные алгоритмы поиска пути. Головоломка представлена ​​в виде двухмерного массива с заданным c форм-фактором. Каждая ячейка в массиве 2d имеет значение перехода, то есть количество пробелов, которое вы можете переместить вверх, вниз, влево или вправо от ячейки.

В настоящее время я работаю над реализацией поиска A * по этой головоломке. Я думал об использовании манхэттенского расстояния в качестве допустимого heuristi c для этой проблемы, но я не думаю, что обычное манхэттенское расстояние будет работать, поскольку движение ограничено определенным c числом ходов.

Например:

2   2   2   1   1
1   1   1   2   2
3   1   2   1   1
3   1   2   1   1
2   1   1   1   0

Возможная сетка. Вы начинаете с 2 в верхней левой ячейке и пытаетесь добраться до 0 в нижней правой ячейке. Из начальной ячейки вы можете перейти вправо на два или вниз 2 к новым пробелам, которые имеют разные значения прыжка. Этот процесс повторяется до тех пор, пока цель не будет достигнута, если головоломка разрешима.

Как я могу изменить манхэттенское расстояние abs(x1-x2) + abs(y1-y2), чтобы включить перемещение определенного c количества пробелов?

Answer 1

Как вы заметили, манхэттенское расстояние не является допустимым heuristi c, например, начиная с P = (3,2), у вас есть:

Manhattan(P, Target) = abs(3 - 4) + abs(2 - 4) = 1 + 2 = 3

, но real расстояние всего 2.

Допустимое значение heuristi c:

h(P) = (P_x != Target_x) + (P_y != Target_y)

, где

           | 1    if x == y
(x != y) = |
           | 0    otherwise

Это работает, поскольку для каждого компонента current-position-vector , который не соответствует соответствующему компоненту в целевом векторе, вы должны сделать хотя бы 1 ход.