algorithm - 具有 Chebyshev 距离的 Dijkstra 算法

Question

我一直在使用 Dijkstra 算法在 Princeton University Algorithm Part 2 给出的 Graph API 中找到最短路径，并且我已经弄清楚如何使用 Chebyshev 距离找到路径。

虽然Chebyshev可以移动到节点的任意一边，cost仅为1，但对Total Cost没有影响，但是根据图，红圈，为什么寻路线是zigzag的，没有移动直的？

如果我使用 A* 算法，同样的事情会重复吗？

Answer 1

如果您想优先考虑“直线”，您应该考虑上一步的方向。一种可能的方法是创建一个图 G'(V', E')，其中 V' 由所有相邻顶点对组成。例如，顶点 v = (v_prev, v_cur) 将在路径中定义一个顶点，其中 v_cur 是路径的最后一个顶点，v_prev是前一个顶点。然后在最短路径算法的“更新距离”步骤中，您可以选择具有最佳(不变)方向的最佳距离。

此外，我们还可以向等于改变方向的次数的距离添加附加属性，并找到方向改变次数最少的最小距离方式。