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

Question

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

如果我可以获得所有最短的路径,我可以得到我想要的那个(顺时针优先).

Answer 1

随着事情A*算法是,它是完整的和最佳的.这意味着如果路径存在,它将找到解决方案的路径,但也保证首先找到最短路径.

这是因为启发函数A*使用必须是一个可接受的启发式算法; 也就是说,它不能高估到目标的距离.

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

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

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

总而言之:您只需在找到第一个最佳解决方案后继续前进,并接受所有相同距离的解决方案.距离较远(较长)的第一条路径,您丢弃并停止搜索.

我刚看到问题的"顺时针"部分.您可以通过以某种方式将顺时针方向插入启发式或成本函数来避免搜索所有最佳解决方案.例如,我有时使用的一个技巧是:你的成本是一个整数,从0到inf.然后,添加顺时针 - ness组件,该组件可以具有区间[0,1]中的实际值.这样,无论之前的哪个地方都是如此,它将保持如此,但如果顺时针方向的组件不同,则关系可能会改变.a > ba == b

如果您不明确要使用数值,则可以使用不同的方法比较成本是一对值.如果该对的第一个组件的两个路径成本不同,那么您只需比较它们.如果第一个组件相同,则只需比较对中的第二个值.

也就是说,我不知道是否会建议你修改费用或启发式功能(或两者兼而有之).此外,我不确定这个精确的技巧是否适用于你的问题,但我相信如果你只是玩一点,你应该能够通过修改其中一个功能来将算法推向最顺时针的解决方案.