A* - 简单图表示例 - 错误结果
我已经实现并使用了 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的节点，即图像中的上节点。 - 该节点的邻居被添加到打开列表中，然后该列表具有元素 { {G=36, H=100,F=136}, {G=58,H=0,F=58}}。
- 再次选择一个新的当前节点，即目标节点，因此算法终止并选择成本为 5 和 53 的路由。
所以执行会产生错误的结果。这些步骤中有哪些不应该发生的事情？
I’ve implemented and used A* several times and thought I knew everything there was to know about A*…. Until I encountered this example:
The graph consists of 4 nodes and 6 directed weighted edges. The heuristic is denoted per node by H=…. The heuristic is clearly admissible, so I don't see any problems with that.
The problem is to find the route from start to goal with the minimal total cost. The correct solution is the route taking the edges with the costs 36 and 18.
My implementation of A* performs the following steps(omitting any operations related to the closed list):
- The startnode is {G = 0, H = 200, -> F = 200} and is selected as ‘current node’
- All its neighbours are added to the openlist
= {{G=5, H=100, F=105}, {G=36, H=100, F=136}}. - The new ‘current node’ is selected, which is the node in the open list with smallest F, which is the node with
F = 105, the upper node in the image. - The neighbours of that node are added to the openlist, which then has the elements { {G=36, H=100,F=136}, {G=58,H=0,F=58}}.
- Again a new current node is selected, which is the goal node, so the algorithm terminates and the route with the costs 5 and 53 is selected.
So the implementation produces the wrong result. What in these steps shouldn’t have happened?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
为了使启发式方法能够被接受，它必须以达到目标的实际成本为界限。你的启发式是不可接受的，这就是你得到错误答案的原因。例如，请参阅关于 A* 的维基百科文章。
For a heuristic to be admissible, it must be bounded from above by the actual cost to the goal. Your heuristic is not admissible and that's why you're getting the wrong answer. See, for instance, the Wikipedia article on A*.