algorithm - 如何使用A*算法找到所有最短路径？

Question

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

如果我能得到所有的最短路径，我就能得到我想要的那个(顺时针优先)。

Answer 1

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

那是因为 A* 使用的启发式函数必须是 admissible heuristic; that is, it must not overestimate the distance to the goal.

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

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

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

因此，总结一下:在找到第一个 最佳解决方案后，您只需继续前进，并且您接受所有距离相同的解决方案。第一条距离较差(较长)的路径，您丢弃并停止搜索。

---

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

如果您不明确想要使用数值，您可以采用另一种比较方式，即让成本成为一对值。如果该对的第一个组件在两个路径成本上不同，您只需比较它们。如果第一个组件相同，则只有比较成对的第二个值。

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