啓發式算法如何工作？

Question

我正在學習最近的一種啓發式算法，如A *搜索算法。我知道關於啓發式搜索算法的一些基本事實，如f（n）= g（n）+ h（n），我也知道每種方法的可接受性和一致性。但令我困惑的是啓發式算法如何工作？爲什麼啓發式價值更接近成本的實際價值會更好？謝謝！

Answer 1

想想一個完美的啓發式h（n）。它給出從n到目標的確切最短距離。

因此，最短路徑上每個節點的成本函數f（s）將相同並等於最短路徑的長度：到目前爲止行進的距離加上到目標的確切最短距離。因此不難看出，對於所有的最短路徑節點和任何給定的非最短路徑節點n，我們都有f（s）< f（n）。

現在考慮A *算法如何以這樣一種啓發式行爲：在每個節點上，選定的下一個要擴展到隊列中的節點也將是最短路徑上的下一個節點，因爲它必須具有最小的可能值f。因此，該算法將沿着最短路徑從開始直接移動到目標節點，而不會出現任何失誤！

如果你沒有完美的啓發式算法，算法顯然可能會造成失誤，因爲f（n）< f（s）是可能的，所以算法可以沿着不必要的分支「走出最短路徑」。

該算法的優點是，只要啓發式是可接受的，它仍然會找到最短路徑，只比完美路徑慢。

Answer 2

啓發式只是一個良好的教育猜測。近似值有保證在一定範圍內。 Christofides算法是一種近似算法，但僅適用於滿足三角不等式（度量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)是真正的成本，那麼搜索就完成了。