寻路-最少转弯的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屋！