algorithm - 启发式算法如何工作？

Question

我最近正在学习一些启发式算法，例如 A* 搜索算法。我知道一些关于启发式搜索算法的基本事实，例如 f(n)=g(n)+h(n)，并且我也知道每个可接受和一致的含义。但是让我困惑的是启发式算法是如何工作的？为什么启发式值更接近成本的实际值会更好？谢谢！

Answer 1

启发式只是一个很好的有根据的猜测。近似值保证在一定范围内。christofides 算法是一种近似算法，但仅适用于满足三角形不等式（度量 tsp）的图。资料来源：https ://cs.stackexchange.com/questions/10182/difference-between-heuristic-and-approximation-algorithm

Answer 2

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

启发式函数越接近，搜索越快。想想极端的情况，h(n) = 0你将有一个 A 搜索，而如果h(n)正好是剩余成本，这意味着f(n)是实际成本，那么搜索就完成了。

Answer 3

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

因此，最短路径上每个节点 s 的成本函数 f(s) 将相同，并且等于最短路径的长度：到目前为止行进的距离加上到目标的确切最短距离。

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

现在想一想 A* 算法在这种启发式下会如何表现：在每个节点上，选择的下一个展开到队列中的节点也将是最短路径上的下一个节点，因为它必须具有最小的 f 值。因此，该算法将沿着最短路径直接从起点移动到目标节点，没有任何失误！

如果您没有完美的启发式算法，那么该算法显然会出错，因为 f(n) < f(s) 是可能的，因此该算法可以沿着不必要的分支“走出最短路径”。

该算法的美妙之处在于，只要启发式是可以接受的，它仍然会找到最短路径，只是比完美路径慢。