允许的启发式修改

Question

我目前正在从事一个涉及难题和各种寻路算法的项目。拼图使用2d数组表示，并具有特定的形状因数。 2d数组中的每个单元格都有一个跳转值，即可以从该单元格上，下，左或右移动的空格数。

我目前正在努力对此难题实施A *搜索。我曾考虑将曼哈顿距离作为对此问题的可允许启发式方法，但由于移动仅限于特定数量的移动，因此我认为常规的曼哈顿距离不会起作用。

例如：

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)以合并移动特定数量的空格？

Answer 1

如您所见，曼哈顿距离不是admissible heuristic，例如从P = (3,2)开始，您有：

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

但是real距离仅为2。

可接受的启发式是：

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

where

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

这是有效的，因为对于current-position-vector的每个与目标向量中的对应分量都不匹配的分量，您至少必须采取1移动。