星星总是 return 成本最低的路径吗？
will a star always return the least cost path?
我最近在我的一个寻路可视化器上实现了一颗星。我注意到的一个常见问题是，虽然它 return 最短 路径，但它有时无法 return 最低成本 路径。现在我不确定这是否是由于某些实现错误造成的，或者这是否不是整个算法的特征。作为参考，这些分别是 a star 和 dijkstras 算法的输出：
那么，为什么会这样呢？ （PS：权重为10，任意方向的正常成本为1，灰色块为墙）
A* 最佳。它总是 return least-cost 路径。但是启发值必须是可以接受的。
A* 给出了正确的结果，前提是启发式给出了真实成本的下限。每条可能路径的成本必须高于或等于启发式提供的值。
如果您使用始终给出值 0 的简单启发式算法，该算法将与 Dijkstra 的算法相同。
A 可能不是 return 成本最低的路径，这是正确的。不过，这是 A* 的一个特点，而不是缺点。回答你的问题，
Why is it the case?
A 具有启发式功能，允许算法通过 显着减少搜索区域 牺牲准确性以获得更高的性能。这也可以在您的图片中看到，其中 Dijkstra 的搜索范围要广得多。 A* 通常在 real-time 游戏中更有用，您不一定需要 lowest-cost 路径，只要它“足够好”即可。有关更多示例，请参阅此 article。我发现它用简单的语言非常清楚地解释了 A*。
至于什么是“足够好”，您可以使用启发式函数来定义。使用不同的函数会导致不同的行为，让您可以根据您的需要调整算法以达到最佳效果（取决于您的竞争环境和准确性要求）。您也可以删除启发式算法，在这种情况下它就变成了简单的 Dijkstra 算法。请参阅同一站点的 this article 以获取一些启发式示例。
通过 and 添加正确答案：
If the heuristic function is admissible, then A* tree search will
always find the least cost path.
(source)
一个可接受的启发式是乐观的是一个乐观的：启发式成本应该小于或等于实际成本。
换句话说，如果您的实施不是 return 成本最低的路径，请考虑将启发式更改为可接受的。
我最近在我的一个寻路可视化器上实现了一颗星。我注意到的一个常见问题是，虽然它 return 最短 路径，但它有时无法 return 最低成本 路径。现在我不确定这是否是由于某些实现错误造成的，或者这是否不是整个算法的特征。作为参考，这些分别是 a star 和 dijkstras 算法的输出：
那么，为什么会这样呢？ （PS：权重为10，任意方向的正常成本为1，灰色块为墙）
A* 最佳。它总是 return least-cost 路径。但是启发值必须是可以接受的。
A* 给出了正确的结果，前提是启发式给出了真实成本的下限。每条可能路径的成本必须高于或等于启发式提供的值。 如果您使用始终给出值 0 的简单启发式算法，该算法将与 Dijkstra 的算法相同。
A 可能不是 return 成本最低的路径，这是正确的。不过，这是 A* 的一个特点，而不是缺点。回答你的问题，
Why is it the case?
A 具有启发式功能，允许算法通过 显着减少搜索区域 牺牲准确性以获得更高的性能。这也可以在您的图片中看到，其中 Dijkstra 的搜索范围要广得多。 A* 通常在 real-time 游戏中更有用，您不一定需要 lowest-cost 路径，只要它“足够好”即可。有关更多示例，请参阅此 article。我发现它用简单的语言非常清楚地解释了 A*。
至于什么是“足够好”，您可以使用启发式函数来定义。使用不同的函数会导致不同的行为，让您可以根据您的需要调整算法以达到最佳效果（取决于您的竞争环境和准确性要求）。您也可以删除启发式算法，在这种情况下它就变成了简单的 Dijkstra 算法。请参阅同一站点的 this article 以获取一些启发式示例。
通过
If the heuristic function is admissible, then A* tree search will always find the least cost path.
(source)
一个可接受的启发式是乐观的是一个乐观的：启发式成本应该小于或等于实际成本。
换句话说，如果您的实施不是 return 成本最低的路径，请考虑将启发式更改为可接受的。