寻路 - A* 最少转弯 [英] Pathfinding - A* with least turns

问题描述

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

Is it possible to modify A* to return the shortest path with the least number of turns?

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

One complication: Nodes can no longer be distinguished solely by their location, because their parent node is relevant in determining future turns, so they have to have a direction associated with them as well.

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

But the main problem I'm having, is how to work number of turns into the partial path cost (g). If I multiply g by the number of turns taken (t), weird things are happening like: A longer path with N turns near the end is favored over a shorter path with N turns near the beginning.

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

Another less optimal solution I'm considering is: After calculating the shortest path, I could run a second A* iteration (with a different path cost formula), this time bounded within the x/y range of the shortest path, and return the path with the least turns. Any other ideas?

推荐答案

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

The current "state" of the search is actually represented by two things: The node you're in, and the direction you're facing. What you want is to separate each of those states into different nodes.

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

So, for each node in the initial graph, split it into E separate nodes, where E is the number of incoming edges. Each of these new nodes represents the old node, but facing in different directions. The outgoing edges of these new nodes will all be the same as the old outgoing edges, but with a different weight. If the old weight was w, then...

• 如果边不代表一个转弯，那么也使新的权重w
• 如果边确实代表一个转弯，则使新的权重w + ε，其中ε是一些明显小于最小的数字重量.

• If the edge doesn't represent a turn, make the new weight w as well
• If the edge does represent a turn, make the new weight w + ε, where ε is some number significantly smaller than the smallest weight.

然后进行普通的 A* 搜索.由于没有任何权重降低，您的启发式仍然是可接受，因此您仍然可以使用同样的启发式.

Then just do a normal A* search. Since none of the weights have decreased, your heuristic will still be admissible, so you can still use the same heuristic.

这篇关于寻路 - A* 最少转弯的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！