Dijkstra算法与Chebyshev距离

Question

我一直在使用Dijkstra算法，在普林斯顿大学算法第二部分提供的图形API中寻找最短路径，我已经找到了如何使用切比雪夫距离找到路径。

尽管切比雪夫距离可以以1的代价移动到节点的任何一侧，但对总成本没有影响，但根据图表，红色圆圈，为什么寻路线路会曲折移动而不是直走？

如果我使用A *算法是否会重复相同的事情？

- Lakindu Gunasekara

Answer 1

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

此外，我们可以为距离添加附加属性，等于更改方向的次数，并找到具有最小方向更改数量的最小距离路径。

- DAle

Answer 2

根据Dijkstra或A*算法，它不应该是特别直的，正如你所说 它对总成本没有影响。我假设你想要避免无用的来回移动，并且在一般情况下没有特殊的方向偏好。

Dijkstra和A*算法并没有内置的"怪异路径"不喜欢，它们只关心成本，这意味着它们也关心如何处理相等的成本。有几件事情可以做：

1. 使用打破关系以使其优先选择直行移动，每当两个节点具有相等成本（G或F，具体取决于您正在执行Dijkstra还是A*）时。这在障碍物周围会有些麻烦，因为最终导致相等长度路径的两种选择不一定具有相同的F分数，因此它们可能不会被打破关系。但它永远不会给你一个次优路径。
2. 稍微增加对角线成本，不必太多，例如直行10、对角线11。这将避免任何不是快捷方式的对角线移动。但是显然：如果这与实际成本不匹配，则现在可以找到次优路径。成本差异越大，发生这种情况的可能性就越大。在实践中，这种情况相对较少，并且路径必须足够长（累积足够的成本差异），才会发生。

- harold