具有Chebyshev距离的Dijkstra算法
Lak*_*ara 6 algorithm a-star dijkstra shortest-path graph-algorithm
我一直在使用Dijkstra算法来寻找普林斯顿大学算法第2部分给出的图谱API中的最短路径,并且我已经找到了如何找到Chebyshev距离的路径.
即使Chebyshev只能以1的成本移动到节点的任何一侧,但对总成本没有影响,但根据图表,红色圆圈,为什么路径寻找线在没有直线移动的情况下移动曲折？
如果我使用A*算法会重复同样的事情吗？
如果要优先考虑"直线",则应考虑上一步的方向.一种可能的方法是创建一个图形G'(V', E'),其中V'包含所有邻居顶点对.例如,顶点v = (v_prev, v_cur)将在路径中定义顶点,该顶点是路径v_cur的最后一个顶点,并且v_prev是前一个顶点.然后在最短路径算法的"更新距离"步骤中,您可以选择具有最佳(不变化)方向的最佳距离.
此外,我们可以添加额外的属性到等于改变方向的数量的距离,并找到最小的方向变化的最小距离方式.