path-finding - 寻路 - A* 最少转弯

Question

是否可以修改A*以返回最短路径匝数最少 ?

一个复杂的问题:节点不再能够仅仅通过它们的位置来区分，因为它们的父节点与确定 future 的转弯相关，所以它们也必须有一个与它们相关的方向。

但是我遇到的主要问题是如何将匝数转换为部分路径成本(g)。如果我将 g 乘以所用的匝数 (t)，就会发生一些奇怪的事情，例如:接近终点 N 匝的较长路径比接近起点 N 匝的较短路径更受欢迎。

我正在考虑的另一个不太理想的解决方案是:在计算最短路径后，我可以运行第二次 A* 迭代(使用不同的路径成本公式)，这次限制在最短路径的 x/y 范围内，并返回转弯最少的路径。还有其他想法吗？

Answer 1

搜索的当前“状态”实际上由两件事表示:您所在的节点和您面对的方向。您想要的是将每个状态分成不同的节点。

因此，对于初始图中的每个节点，将其拆分为 E 个单独的节点，其中 E 是传入边的数量。这些新节点中的每一个都代表旧节点，但面向不同的方向。这些新节点的出边都将与旧的出边相同，但具有不同的权重。如果旧重量是 w ， 然后...

如果边不代表转弯，则设置新权重 w还有

如果边确实代表转弯，则设置新权重 w + ε ，其中 ε是一些比最小权重小得多的数字。

然后就做一个普通的 A* 搜索。由于没有任何权重降低，您的启发式仍然是 admissible ，因此您仍然可以使用相同的启发式方法。