1
我已经实施并使用过几次A *，并且认为我知道关于A *的所有知识。直到我遇到这个例子：A * - 简单的图表示例 - 错误的结果
该图由4个节点和6向加权边缘。启发式按每个节点H=…表示。启发式显然是可以接受的，所以我没有看到任何问题。
问题是找到从开始到目标的路线，而且总成本最小。正确的解决方案是采取边缘与成本的路径36和18
我的A *的实现执行以下步骤（省略有关封闭列表的任何操作）：
- 所述的StartNode是{ G = 0，H = 200， - > F = 200}并被选为'当前节点'
- 所有邻居都被添加到打开列表
= {{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的路由被选中。
所以实现会产生错误的结果。这些步骤中应该发生什么？
那么，这当然不是一个图（因为有成对的节点共享两个边而不是一个或零），但这不是A *在这里不起作用的原因。通过用较低的代价替换每个双边，可以很容易地制作一个图表。 –
@Doc Brown - 如果您采用适当的图形定义，这当然是一个图表。具体来说，它是一个没有循环的定向多图。从[维基百科]（http://en.wikipedia.org/wiki/Multigraph）（当然，这对任何事情都是正确的：〜））：“在数学中，多图或伪图是允许有多条边......“ –
@Ted Hopp：如果你详细阅读了维基百科的文章，你会发现它给出了术语”图“的不同定义，而”多图“与最常见的定义不符。然而，这里重要的问题是“A *适用于多图？”答案是 - “不是直接的，而是通过将多图转化为经典图，它可以被应用。” –