我目前正在做一个涉及谜题和各种寻路算法的项目。拼图使用 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)以合并移动特定数量的空间？
正如你所观察到的，曼哈顿距离不是一个可接受的启发式方法，例如，从你拥有P = (3,2)开始：
Manhattan(P, Target) = abs(3 - 4) + abs(2 - 4) = 1 + 2 = 3
但真正的距离只是2.
可接受的启发式方法是：
h(P) = (P_x != Target_x) + (P_y != Target_y)
哪里
| 1 if x == y
(x != y) = |
| 0 otherwise
这是有效的，因为对于当前位置矢量的每个组件，如果与目标矢量中的相应组件不匹配，您必须至少移动1。