最近我在我的路径可视化器中实现了A*算法。我注意到它确实返回了最短路径,但有时却未必是最小代价的路径。现在我不确定这是否由于实现错误,还是算法本身的特性。参考以下是A*和Dijkstra算法的输出结果: 那么,为什么会出现这种情况呢?(PS:权重为10,任何移动方向的正常代价为1,灰色区域表示墙壁)。
A*算法能够给出正确的结果,前提是启发式函数提供了一个比真实代价更低的下界。每一条可能的路径必须具有比启发式函数提供的值更高或相等的代价。如果使用一个总是返回0的简单启发式函数,该算法将变为Dijkstra算法。
A*算法可能不会返回最小成本路径,这是A*算法的特性,而不是缺点。回答你的问题,A*算法具有启发式函数,可以通过显著减少搜索区域来折衷精度和高性能。您的图片中也可以看到这一点,Dijkstra的搜索区域要宽得多。在实时游戏中,A*算法通常更有用,因为您不一定需要最低成本路径,只要它足够好即可。请参考此文章了解更多示例,我认为它用简单的语言非常清楚地解释了A*算法。至于什么是“足够好”,您可以使用启发式函数来定义。使用不同的函数将导致不同的行为,使您可以将算法调整为满足您的需求(取决于您的游戏场和精度要求)。您还可以删除启发式函数,这样它就变成了Dijkstra算法。请参考这篇文章以获取一些启发式函数的示例。
为了补充 Md Asaduzzaman 和 Henry 的正确答案: 如果启发式函数是可接受的,那么A*树搜索将总是找到最小成本路径。 (来源) 可接受的启发式是一种乐观的启发式:启发式成本应该小于或等于实际成本。 换句话说,如果你的实现没有返回最低成本路径,请考虑将启发式更改为可接受的。