一颗星星是否总是会回到最小代价路径？

Question

最近我在我的路径可视化器中实现了A*算法。我注意到它确实返回了最短路径，但有时却未必是最小代价的路径。现在我不确定这是否由于实现错误，还是算法本身的特性。参考以下是A*和Dijkstra算法的输出结果: 那么，为什么会出现这种情况呢？（PS：权重为10，任何移动方向的正常代价为1，灰色区域表示墙壁）。

- aditya

---

你能详细说明一下成本是如何工作的，以及你的实现如何反映这一点吗？ - harold

如您所见，有六个移动方向，它们最初的代价都是1。但是，一旦放置了重量，任何一个邻居到达该（现在加权）节点的边缘将具有10的权重。紫色的哑铃表示权重，每个哑铃都有一个静态值为10。 - aditya

最好说A* :-) - user1196549

@YvesDaoust 抱歉！一直在说星号（A*），因为这是我在代码中的写法。 ） - aditya

亿万程序员都知道A*算法，并且赋予了星号不同的含义。 - user1196549

Answer 1

A*算法是最优的。它总是返回最小代价路径。但是启发式函数值必须是可接受的。

- Md Asaduzzaman

---

我认为如果启发式函数是可接受的，A*算法将始终返回最低成本路径。 - c0der

Answer 2

A*算法能够给出正确的结果，前提是启发式函数提供了一个比真实代价更低的下界。每一条可能的路径必须具有比启发式函数提供的值更高或相等的代价。如果使用一个总是返回0的简单启发式函数，该算法将变为Dijkstra算法。

- Henry

Answer 3

A*算法可能不会返回最小成本路径，这是A*算法的特性，而不是缺点。回答你的问题，A*算法具有启发式函数，可以通过显著减少搜索区域来折衷精度和高性能。您的图片中也可以看到这一点，Dijkstra的搜索区域要宽得多。在实时游戏中，A*算法通常更有用，因为您不一定需要最低成本路径，只要它足够好即可。请参考此文章了解更多示例，我认为它用简单的语言非常清楚地解释了A*算法。

至于什么是“足够好”，您可以使用启发式函数来定义。使用不同的函数将导致不同的行为，使您可以将算法调整为满足您的需求（取决于您的游戏场和精度要求）。您还可以删除启发式函数，这样它就变成了Dijkstra算法。请参考这篇文章以获取一些启发式函数的示例。

- Register Sole

---

谢谢，过去的4个小时我一直盯着电脑，试图理解我写错了什么。这些文章帮了很多忙。此外，我还学习了最佳优先搜索算法。它是根据从起点到当前节点的距离加权，还是只考虑当前节点到终点的距离？ - aditya

如果你指的是贪婪最佳优先搜索，它只考虑从目标到当前节点的距离。这就是为什么它在凹形障碍物上产生奇怪结果的原因。@aditya - Register Sole

顺便提一下，Dijkstra 中没有 ji 这个字母，它是一个 ij。 - harold

@哈罗德 谢谢！我是凭记忆打的。今天我才知道我的记忆是虚假的。 - Register Sole

Answer 4

为了补充 Md Asaduzzaman 和 Henry 的正确答案：

如果启发式函数是可接受的，那么A*树搜索将总是找到最小成本路径。

(来源)

可接受的启发式是一种乐观的启发式：启发式成本应该小于或等于实际成本。

换句话说，如果你的实现没有返回最低成本路径，请考虑将启发式更改为可接受的。

- c0der