Dijkstra算法与切比雪夫距离

Question

我一直在使用Dijkstra算法来查找由普林斯顿大学算法第2部分给出的图形API中的最短路径，并且我已经找到了如何找到具有切比雪夫距离的路径。

尽管切比雪夫可以移动到节点的任何一侧，但成本只有1，但对总成本没有影响，但根据图表红圈，路径寻找线为什么没有移动曲折而没有直行？

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

Answer 1

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

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

Answer 2

根据Dijkstra或A *，它不应该是特别直的，如您所说的它对总成本没有影响。顺便说一下，我会假设你想特别防止无用的锯齿形锯齿，并且一般没有特别的偏好，因为它和前面的移动走向相同。 Dijkstra和A *没有对“怪异路径”的内置不喜欢，他们只是明确地关心成本，隐含地意味着他们也关心你如何处理同等成本。有一对夫妇的事情你可以做的：

1. 使用打破平局让他们更喜欢直线移动，只要两个节点具有相同的成本（G或F，这取决于你正在做的Dijkstra算法或A * ）。这给障碍带来了一些麻烦，因为最终导致等长路径的两个选择不一定具有相同的F分数，所以它们可能不会打破平局。它永远不会给你一个次优路径。
2. 有点增加你的对角线成本，它不一定非常多，比如直线10和对角线11。这将避免任何不是捷径的对角线移动。但显然：如果这不符合实际成本，现在可以找到次优路径。成本差异越大，发生的越多。在实践中，这是相对罕见的，路径必须足够长（积累足够的成本差异，以便在发生之前变得值得一整套额外的行动）。