一颗星星会总是返回最低的成本路径吗？
我最近在我的一位探索视觉者上实施了一颗星星。我注意到的一件常见的事情是，尽管它确实返回了最短路径，但有时它不会返回最低成本路径。现在，我不确定是否是由于某些实现错误，或者这不是整体算法的特征。作为参考，这些是A星和Dijkstras algo的输出：
那么，为什么这样？ （PS：重量为10，任何运动方向的正常成本为1，灰色斑块是墙壁）
I have been implementing a star recently on one of my pathfinding visualisers. A common thing that i have noticed is that while it does return the shortest path, it sometimes fails to return the least cost path. Now i am unsure as to if, this is due to some implementation error or if this is not a characteristic of the algorithm on a whole. For reference, these are the outputs of the a star and dijkstras algo respectively:
So, why is this the case? (PS:the weights are 10, normal cost is 1 for any direction of movement and, the grey patches are walls)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
A*是最佳的。它将始终返回成本最小的路径。但是启发式价值必须可以接受。
A* is optimal. It will always return the least-cost path. But the heuristic value must be admissible.
A*可能不会返回最低的成本路径，这是正确的。这是A*的一个功能，而不是劣势。要回答你的问题，
A*具有启发式函数，可以通过显着降低搜索范围来牺牲更高性能的精度。这也可以在您的图像中看到，Dijkstra的搜索区域更宽。 A*通常在实时游戏中更有用，只要它足够好，您就不一定需要最低成本的路径。请参阅此文章 更多示例。我发现它用简单的语言解释了一个*。
至于“足够好”，您可以使用启发式功能来定义此功能。使用不同的功能将导致不同的行为，从而使您可以调整算法最适合您的需求（取决于您的竞争环境和准确性要求）。您还可以删除启发式方法，在这种情况下，它就变成了Dijkstra的算法。请参阅本文来自同一站点以获取一些启发性的示例。
A* may not return the least cost path, that is correct. This is a feature of A* though, not a disadvantage. To answer your question,
A* has a heuristics function that allows the algorithm to sacrifice accuracy for much higher performance by significantly reducing the area of search. This can be seen in your image too, where the Dijkstra's area of search is much wider. A* is often more useful in real-time games, where you don't necessarily need the lowest-cost path, as long as it is "good enough". Refer to this article for more examples. I find it explains A* very clearly in simple language.
As to what is "good enough", you define this using the heuristics function. Using different function will result in different behavior, allowing you to tune the algorithm to be optimal for your needs (depending on your playing field and accuracy requirement). You can also remove the heuristics, in which case it becomes simply the Dijkstra's algorithm. Refer to this article from the same site for some examples of heuristics.
A*给出了正确的结果，只要启发式剂给出了真实成本的下限。每条可能的路径必须具有更高或等于启发式的价值。
如果您使用始终赋予值0的微不足道的启发式，则该算法与Dijkstra相同。
A* gives a correct result provided the heuristic gives a lower bound to the true cost. Every possible path must have cost higher or equal to the value provided by the heuristic.
The algorithm becomes identical to Dijkstra's if you use a trivial heuristic that always gives the value 0.
要添加正确的答案，请 md asaduzzaman 和亨利：
（ source ）
可接受的启发式启发式是乐观的，这是一种乐观主义者：启发式成本应小于或等于实际成本。
换句话说，如果您的实施不返回最低的成本路径，请考虑将启发式方法更改为可允许的启发式。
To add to the correct answers by Md Asaduzzaman and Henry:
(source)
An admissible heuristic is optimistic is an optimistic one: the heuristic cost should be less than or equal to the actual cost.
In other words, if your implementation does not return the lowest cost path, consider changing the heuristic to an admissible one.