8

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

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

但我遇到的主要问题是如何将转数转化为部分路径成本（g）。如果我将 g 乘以所经过的圈数 (t)，就会发生奇怪的事情，例如：一条较长的路径接近终点 N 圈优于较短的路径 N 圈靠近起点。

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

4

3 回答 3

7

搜索的当前“状态”实际上由两件事表示：您所在的节点，以及您所面对的方向。您想要的是将这些状态中的每一个分离到不同的节点中。

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

  • 如果边缘不代表转弯，则也制作新的权w重
  • 如果边确实代表一个转弯，则制作新的权重w + ε，其中ε某个数字明显小于最小权重。

然后进行正常的 A* 搜索。由于没有任何权重减少，因此您的启发式仍然可以接受，因此您仍然可以使用相同的启发式。

于 2013-10-17T21:16:05.740 回答
0

如果你真的想最小化转弯的数量（而不是在转弯和路径长度之间找到一个很好的折衷），为什么不通过为通过无障碍直线连接的每对节点添加一条边来转换你的问题空间呢？这些是您可以在没有转弯的情况下穿行的对。每个节点有 O(n) 个这样的边，因此新图的边数为 O(n 3 )。这使得 A* 解决方案在时间上与 O(n 3 ) 一样多。

曼哈顿距离可能是 A* 的一个很好的启发式方法。

于 2016-07-10T16:39:22.020 回答
0

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

这很可能是不可能的。原因是它是权重约束最短路径问题的一个例子。因此，它是 NP 完全的，无法有效求解。

您可以找到讨论解决此问题的论文，例如http://web.stanford.edu/~shushman/math15_report.pdf

于 2020-03-28T16:52:04.827 回答