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

Question

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

algorithmshortest-patha-star

3

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

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

- teloon

如果您可以测量路径“顺时针”走了多远（而不是与其他路径进行比较），则可以将长度的定义从N步替换为配对N步，M％顺时针，并使用相同的路径查找算法，但比较配对而不是长度。 - hamstergene

@hamstergene 是的，理想情况下我可以将优先级定义为将L2距离与顺时针优先级相结合。但在实践中很难，因为它们处于不同的比例尺上。 - teloon

3个回答

1

为了澄清@penelope的意思：“...在找到第一个最优解之后继续前进...”

从A*中获取一组等价成本最优路径：

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

从A*中获取顺时针路径：

至于优先选择顺时针路径，请考虑在排序OPEN列表的比较方法中使用打结方法。如果两个候选者具有相同的f-cost，请优先选择最顺时针的候选者。（我认为您可以通过查看候选者相对于起始/目标节点的位置来获得顺时针性质。）如果您以这种方式进行打结，则顺时针解决方案将被推到OPEN列表的前面，并且您将从A*获取最顺时针的解决方案。

- thayne

-6

Dijkstra算法可以给出所有最短路径。 A*算法是在改进Dijkstra算法的基础上产生的，增加了额外的约束条件。改进之处在于不需要访问所有节点。如果您想要探索所有节点（这是必须的，以确保您已经检查了所有最短路径），那么使用A*算法就没有意义，只需坚持使用通用的祖先算法即可。

- Pyra

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- penelope · Accepted Answer

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 > b都将保持不变，但如果顺时针性组件不同，则可能会改变a == b的关系。

如果你不想明确地使用数值，还有一种比较方法是将成本作为一对值。如果两个路径成本的第一个部分不同，则可以直接进行比较。如果第一个部分相同，则只需比较成对中的第二个值。

话虽如此，我暂时不确定是否建议您修改成本或启发式函数（或两者都修改）。而且，我不确定这个精确的技巧在您的问题中是否有效，但我相信如果您稍微尝试一下，就可以通过修改其中一个函数来激励算法朝向最顺时针的解决方案。