logo标签列表

寻路算法 - A*最少拐弯法

path-findinga-star
8
能否修改A*算法以返回具有最少拐弯的最短路径？
一个复杂性在于，节点不再仅由其位置区分，因为它们的父节点与确定未来拐弯方向相关，所以它们必须有一个方向与之关联。
但我遇到的主要问题是如何将拐弯次数转化为部分路径成本(g)。如果我将g乘以所采取的拐弯次数(t)，则会出现奇怪的情况，例如：末尾附近具有N个拐弯的较长路径优于开头附近具有N个拐弯的较短路径。
我正在考虑的另一个不太理想的解决方案是：在计算出最短路径后，我可以运行第二个A*迭代（使用不同的路径成本公式），这次在最短路径的x/y范围内限定，并返回具有最少拐弯的路径。还有其他想法吗？
3个回答
7
当前搜索的“状态”实际上由两个部分表示：您所在的节点和您面对的方向。您需要将每个状态分离为不同的节点。
因此，对于初始图中的每个节点，请将其分成E个单独的节点，其中E是传入边的数量。这些新节点中的每一个代表旧节点，但面向不同的方向。这些新节点的出边都与旧的出边相同，但具有不同的权重。如果旧权重为w，则...
  • 如果边不是表示转弯，请将新权重设置为w
  • 如果边表示转弯，请将新权重设置为w + ε，其中ε是比最小权重小得多的数字。
然后只需进行常规的A *搜索即可。由于没有任何权重降低，因此您的启发式仍然是可接受的，因此您仍然可以使用相同的启发式。
0

能否修改A*算法以返回最少转弯的最短路径？

很可能不行。原因是这是一个权重限制下的最短路径问题，因此是NP-完全问题，无法高效地解决。

您可以找到一些论文来讨论解决这个问题，例如http://web.stanford.edu/~shushman/math15_report.pdf。

0
如果你真的想要最小化转弯次数（而不是在转弯次数和路径长度之间找到一个好的折衷方案），为什么不通过为每对由无阻挡直线连接的节点添加一条边来变换你的问题空间； 这些是你可以在没有拐弯的情况下行进的节点对。每个节点有O(n)个这样的边，因此新图在边的方面是O(n^3)。这使得A*解决方案在时间上高达O(n^3)。
曼哈顿距离可能是A*的一个很好的启发式方法。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接