algorithm - 明星总是会返回成本最低的路径吗？

Question

我最近在我的一个寻路可视化器上实现了一颗星。我注意到的一个共同点是，虽然它确实返回了 shortest 路径，但有时它无法返回 least cost 路径。现在我不确定这是否是由于某些实现错误，或者这不是整个算法的特征。作为引用，这些分别是 a star 和 dijkstras 算法的输出:

那么，为什么会这样呢？ (PS:权重为 10，任何运动方向的正常成本为 1，灰色 block 为墙壁)

Answer 1

A* 是最优的。它总是返回成本最低的路径。但启发式值必须是可接受的。