我已经多次实现和使用 A*，并认为我知道关于 A* 的一切……。直到遇到这个例子:
该图由 4 个节点和 6 个有向加权边组成。启发式由 H=... 表示每个节点。启发式显然是可以接受的，所以我看不出有任何问题。
问题是找到从开始 到目标 的总成本最小的路线。正确的解决方案是采用成本为 36 和 18 的边的路线。
我的 A* 实现执行以下步骤(省略任何与封闭列表相关的操作):
- 起始节点为{G = 0, H = 200, -> F = 200}，被选为“当前节点”
- 它的所有邻居都被添加到 openlist
= {{G=5, H=100, F=105}, {G=36, H=100, F=136}}。 - 选择新的“当前节点”，它是开放列表中具有最小 F 的节点，即
F = 105的节点，图像中的上部节点。 - 该节点的邻居被添加到 openlist，然后有元素 {{G=36, H=100,F=136}, {G=58,H=0,F=58}}。
- 再次选择一个新的当前节点，即目标节点，因此算法终止并选择成本为 5 和 53 的路径。
所以执行产生了错误的结果。这些步骤中有什么是不应该发生的？
最佳答案
对于可接受的启发式，它必须从以上到目标的实际成本。你的启发式是 Not Acceptable ，这就是你得到错误答案的原因。参见，例如，Wikipedia article on A* .
关于algorithm - A* - 简单图形示例 - 错误结果，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7112767/