具有 Chebyshev 距离的 Dijkstra 算法
Dijkstra Algorithm with Chebyshev Distance
我一直在使用 Dijkstra 算法在 Princeton University Algorithm Part 2 给出的 Graph API 中找到最短路径，并且我已经弄清楚如何使用 Chebyshev 距离找到路径。
虽然Chebyshev可以移动到节点的任一侧，cost仅为1，但对Total Cost没有影响，但是根据图中红圈，为什么寻路线是锯齿形移动不直接移动？
用A*算法会不会重复同样的事情？
如果您想确定优先级 "straight lines"，您应该考虑上一步的方向。一种可能的方法是创建一个图 G'(V', E')，其中 V' 由所有相邻顶点对组成。例如，顶点 v = (v_prev, v_cur) 将在路径中定义一个顶点，其中 v_cur 是路径的最后一个顶点，v_prev 是前一个顶点。然后在最短路径算法的 "updating distances" 步骤中，您可以选择具有最佳（不变）方向的最佳距离。
我们也可以将额外的属性添加到等于改变方向的次数的距离，并找到方向改变次数最少的最小距离方式。
应该不是特别直，按照你说的Dijkstra或者A*，对总成本没有影响。顺便说一下，我假设您特别想防止无用的锯齿形移动，并且通常没有特别偏好与前一移动方向相同的移动。
Dijkstra 和 A* 对 "weird paths" 没有天生的厌恶，他们只明确关心成本，这意味着他们也关心你如何处理同等成本。您可以为此做几件事：
- 只要两个节点的成本相等（G 或 F，取决于您使用的是 Dijkstra 还是 A*），使用打破平局让他们更喜欢直线移动。这给绕过障碍带来了一些麻烦，因为最终导致等长路径的两个选择不一定具有相同的 F 分数，因此它们可能不会平局。它永远不会给你一个次优的路径。
- 略微增加对角线成本，不一定要很多，比如直线为 10，对角线为 11。这只会避免任何不是捷径的对角线移动。但很明显：如果这与实际成本不符，您现在可以找到次优路径。成本差异越大，发生的情况就越多。在实践中它相对罕见，并且路径必须足够长（积累足够多的成本差异以使其值得整个额外的移动）在它发生之前。
我一直在使用 Dijkstra 算法在 Princeton University Algorithm Part 2 给出的 Graph API 中找到最短路径，并且我已经弄清楚如何使用 Chebyshev 距离找到路径。
虽然Chebyshev可以移动到节点的任一侧，cost仅为1，但对Total Cost没有影响，但是根据图中红圈，为什么寻路线是锯齿形移动不直接移动？
用A*算法会不会重复同样的事情？
如果您想确定优先级 "straight lines"，您应该考虑上一步的方向。一种可能的方法是创建一个图 G'(V', E')，其中 V' 由所有相邻顶点对组成。例如，顶点 v = (v_prev, v_cur) 将在路径中定义一个顶点，其中 v_cur 是路径的最后一个顶点，v_prev 是前一个顶点。然后在最短路径算法的 "updating distances" 步骤中，您可以选择具有最佳（不变）方向的最佳距离。
我们也可以将额外的属性添加到等于改变方向的次数的距离，并找到方向改变次数最少的最小距离方式。
应该不是特别直，按照你说的Dijkstra或者A*，对总成本没有影响。顺便说一下，我假设您特别想防止无用的锯齿形移动，并且通常没有特别偏好与前一移动方向相同的移动。
Dijkstra 和 A* 对 "weird paths" 没有天生的厌恶，他们只明确关心成本，这意味着他们也关心你如何处理同等成本。您可以为此做几件事：
- 只要两个节点的成本相等（G 或 F，取决于您使用的是 Dijkstra 还是 A*），使用打破平局让他们更喜欢直线移动。这给绕过障碍带来了一些麻烦，因为最终导致等长路径的两个选择不一定具有相同的 F 分数，因此它们可能不会平局。它永远不会给你一个次优的路径。
- 略微增加对角线成本，不一定要很多，比如直线为 10，对角线为 11。这只会避免任何不是捷径的对角线移动。但很明显：如果这与实际成本不符，您现在可以找到次优路径。成本差异越大，发生的情况就越多。在实践中它相对罕见，并且路径必须足够长（积累足够多的成本差异以使其值得整个额外的移动）在它发生之前。