启发式算法是如何工作的？

Question

最近我正在学习一些启发式算法，比如A*搜索算法。我知道一些关于启发式搜索算法的基本事实，如f(n)=g(n)+h(n)，我也知道每种方法的可容许性和一致性。但让我困惑的是启发式算法是如何工作的？如果启发式值更接近成本的实际值，为什么会更好？谢谢!

Answer 1

考虑一个完美的启发式h(n)。它给出了从n到目标的精确最短距离。

因此，在最短路径上，每个节点的代价函数f(s)都是相同的，等于最短路径的长度:迄今所走的距离加上距离目标的精确最短距离。

因此不难看出，对于所有最短路径节点s和任意给定的非最短路径节点n，我们都有f(s) < f(n)。

现在想想A*算法在这样一个启发式的情况下的行为:在每个节点上，扩展到队列上的下一个节点也将是最短路径上的下一个节点，因为这必须有最小的f值。因此，该算法将沿着最短路径直接移动到目标节点，不会出现任何错误！

如果没有完美的启发式算法，由于f(n) < f(s)是可能的，因此该算法很明显会产生错误，因此该算法可以沿着一个不必要的分支“脱离最短路径”。

该算法的优点是，只要启发式是可接受的，它仍然会找到最短的路径，只是速度比完美的路径慢。

Answer 2

启发式只是一种受过良好教育的猜测。近似值保证在一定范围内。赫里斯托菲德算法是一种近似算法，但只适用于满足三角不等式(度量tsp)的图。来源：https://cs.stackexchange.com/questions/10182/difference-between-heuristic-and-approximation-algorithm

Answer 3

该启发式函数的作用类似于对完成端到端路径的最低剩余成本的估计。f(n) = g(n) + h(n)从底部有界，扩展和完成路径g(n)的成本最低。因此，对于可接受的启发式函数，可以保证搜索成功。

启发式函数越接近，搜索速度就越快。考虑到极端的情况，即h(n) = 0，您将得到一个A搜索，而如果h(n)恰好是剩余的成本--这意味着f(n)是真正的成本，那么搜索就完成了。