algorithm - 启发式和 A* 算法

Question

我正在阅读有关 dijkstra 算法和 A* 星算法的内容。我知道区别在于所使用的启发式方法。但什么是启发式以及它如何影响算法？启发式只是一种测量距离的方法？但是 dijkstra 也考虑了距离？抱歉，但我的问题是关于启发式及其含义以及为什么要使用它们......(我读过它，但不明白)其他问题:分别应该在什么时候使用？

谢谢

Answer 1

在此上下文中，启发式是一种为算法提供某种形式的额外评估信息的方式，以便算法可以找到“足够好”的解决方案，而无需穷尽搜索所有可能的解决方案。

Dijkstra 算法不使用启发式算法。它从起始节点向外扩展，并检查图中的每个节点以找到最短路径。虽然这是准确的，但计算量可能很大。

相比之下，A* 算法使用距离 + 成本启发式来指导算法选择下一个要探索的节点。这意味着该算法无需检查图上的每个节点即可找到可能的搜索解决方案。因此，它的运行成本要低得多，但会损失完全的准确性。它之所以有效，是因为结果通常足够接近最优解，而且被发现比对整个图进行详尽搜索成本更低。

至于什么时候应该使用它们，这实际上取决于应用程序。但是，使用 A* 算法需要一个可接受的启发式算法，因此这可能不适用于算法无法获得此类信息的情况。