3

我知道 A* 算法可以找到最短路径。但我工作中的问题是我需要找到所有最短路径。更准确地说，可能存在多条最短路径，但我需要选择顺时针优先级的最短路径。

如果我能得到所有最短路径，我就能得到我想要的（顺时针优先）。

4

3 回答 3

8

A*算法的特点是它是完整的和最优的。这意味着如果存在路径，它将找到解决方案的路径，而且保证首先找到最短路径。

这是因为 A* 使用的启发式函数必须是可接受的启发式；也就是说，它不能高估到目标的距离。

这反过来确保一旦您找到解决方案的路径，您就会知道在搜索空间的其余部分中没有比该路径更短的路径。

假设到您的第一个解决方案的距离是d(problem)。现在，我的最后一句话实际上意味着，如果您在找到第一个解决方案d(problem)之后继续前进，并找到另一个解决方案d2(problem)，则有两种可能性：

  • d2(problem) = d(problem)：你想保留那个，因为你想要所有的最佳路径。此外，所有新路径都可以等于或大于d2 = d
  • d2(problem) > d(problem)：现在，我上面写的同样的事情是有效的：没有比d2短的路径了。而且，d2已经比您正在寻找的解决方案更长。因此，您可以丢弃d2并完成搜索
  • 请注意，没有第三个选项，d2(problem)永远不会比您已经找到的最佳d(problem)短，因为这是算法的基本属性之一。

所以，总结一下：在找到第一个最优解之后，你就继续前进，并且接受所有距离相同的解。第一条距离更远（更长）的路径，您丢弃并停止搜索。

我刚刚看到问题的“顺时针”部分。您可以通过以某种方式将顺时针插入到您的启发式或成本函数中来避免搜索所有最佳解决方案。例如，我有时使用的一个技巧是：你的成本是一个整数，从 0 到inf。然后，添加顺时针分量，它可以具有区间[0, 1)中的实数值。这样，无论以前是否正确，它都会保持不变，但如果顺时针分量不同，则关系可能会改变。a > ba == b

如果您不明确希望使用数值，则可以比较的另一种方法是将成本设为一对值。如果该对的第一个组件在两个路径成本中不同，您只需比较它们。如果第一个组件相同，则仅比较成对中的第二个值。

也就是说，在我脑海中，我不确定我是否会建议您修改成本或启发式函数（或两者）。另外，我不确定这个精确的技巧是否能解决你的问题，但我相信你应该能够通过修改这些函数之一来将算法推向最顺时针的解决方案，如果你只是玩一点。

于 2012-05-24T14:05:34.490 回答
1

澄清@penelope 的意思：“......在找到第一个最佳解决方案后继续...... ”

要从 A* 获得一组等效成本最优路径：

一旦 A* 找到最短路径（成本 = C*），您可以通过继续从 OPEN 列表中弹出解决方案来获得其他等长路径，直到遇到成本超过 C* 的解决方案。（有一个警告，如果您的启发式方法不完美，您可能需要做一些额外的工作。）请注意，这将为您提供一组最佳路径，但不一定是所有最佳路径的集合 - 这取决于您如何'已经设置了重复检测。

要从 A* 获得顺时针路径：

至于更喜欢顺时针路径，请考虑在比较方法中使用平局来对 OPEN 列表进行排序。如果两个候选人具有相同的 f 成本，则选择最顺时针方向的候选人。（我认为你可以通过查看你的候选人相对于​​开始/目标节点来获得顺时针的概念。）如果你以这种方式打破平局，顺时针解决方案将被推到 OPEN 列表的前面，你会从 A* 中得到最顺时针的解。

于 2017-08-30T16:41:51.000 回答
-6

Dijkstra 的算法为您提供所有最短路径。A* 是作为改进的 Dijkstra 制作的，带有额外的约束。改进是您不需要访问所有节点。如果你想探索所有节点（这是确保你检查了所有最短路径所必需的），那么使用 A* 没有意义，只需坚持通用祖先

于 2012-05-24T13:38:54.770 回答