没有对角线移动的最短路径

Question

我知道有很多最短路径算法，但我想问一下是否可以做任何修改，让一些算法像 a* 或 Dijkstra 选择最短路径但没有对角线移动所以向上

上下左右是允许的走法

Answer 1

您可能需要的算法是 A*（如果您想要在具有一些连贯障碍物的大地图上的短路径），尽管您可能只需要 Dijkstra 的（如果您必须具有数学上的最短路径，或者如果地图与任何物理事物都没有任何实际关系）。您只需禁止对角线移动，如果您使用曼哈顿距离作为 A* 的启发式方法，您可能会获得更好的结果。对于 Dijkstra，该图没有对角线链接。