algorithm - 启发式和 A* 算法

Question

我正在阅读有关 dijkstra 算法和 A* 星算法的信息。我知道区别在于使用的启发式方法。但是什么是启发式方法以及它如何影响算法？启发式只是一种测量距离的方法？但是dijkstra也考虑距离吗？抱歉，但我的问题是关于启发式及其含义以及为什么要使用它们......（我已经阅读过它，但不明白） 其他问题：每个人应该什么时候使用？

谢谢

Answer 1

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

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

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

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

Answer 2

启发式基本上意味着一个想法或直觉！您用来解决难题的任何策略都是启发式的！在某些领域（如组合问题），它指的是可以帮助您在多项式时间内以次优方式解决NP难题的策略。

Answer 3

Dijkstra 解决了单源路由问题，即它为您提供了从单个点到空间中任何其他点的成本。

A* 解决了单源单目标问题。它为您提供了从给定点到另一个给定点的最小距离路径。

A* 通常比 Dijkstra 快，只要你给它一个可接受的启发式方法，这是对目标距离的估计，从不高估所述距离。与此处给出的先前答案相反，如果使用的启发式是可接受的，则 A* 是完整的，将为您提供最佳答案。