啓發式搜索算法

何謂啓發式搜索算法

在説它之前先提狀態空間搜索。狀態空間搜索，如果按專業點的説法就是將問題求解過程表現為從初始狀態到目標狀態尋找這個路徑的過程。通俗點説，兩點之間求一線路，這兩點是求解的開始和問題的結果，而這一線路不一定是直線，可以是曲折的。由於求解問題的過程中分枝有很多，主要是求解過程中求解條件的不確定性，不完備性造成的，使得求解的路徑很多這就構成了一個圖，我們説這個圖就是狀態空間。問題的求解實際上就是在這個狀態空間圖中找到一條路徑可以從開始到結果。這個尋找的過程就是狀態空間搜索。

常用的狀態空間搜索有深度優先和廣度優先。廣度優先是從初始狀態一層一層向下找，直到找到目標為止。深度優先是按照一定的順序前查找完一個分支，再查找另一個分支，以至找到目標為止。這兩種算法在數據結構書中都有描述，可以參看這些書得到更詳細的解釋。

前面説的廣度和深度優先搜索有一個很大的缺陷就是他們都是在一個給定的狀態空間中窮舉。這在狀態空間不大的情況下是很合適的算法，可是當狀態空間十分大，且不預測的情況下就不可取了。他的效率實在太低，甚至不可完成。在這裏就要用到啓發式搜索了。

啓發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無謂的搜索路徑，提高了效率。在啓發式搜索中，對位置的估價是十分重要的。採用了不同的估價可以有不同的效果。

啓發中的估價是用估價函數表示的，如：f(n) = g(n) + h(n)

其中f(n) 是節點n的估價函數，g(n)是在狀態空間中從初始節點到n節點的實際代價，h(n)是從n到目標節點最佳路徑的估計代價。在這裏主要是h(n)體現了搜索的啓發信息，因為g(n)是已知的。如果説詳細點，g(n)代表了搜索的廣度的優先趨勢。但是當h(n) >> g(n)時，可以省略g(n)，而提高效率。

啓發算法有： 蟻羣算法，遺傳算法、模擬退火算法等 　蟻羣算法是一種來自大自然的隨機搜索尋優方法，是生物界的羣體啓發式行為，現己陸續應用到組合優化、人工智能、通訊等多個領域。蟻羣算法的正反饋性和協同性使其可用於分佈式系統，隱含的並行性更使之具有發展潛力。從數值仿真結果來看，它比風行一時的遺傳算法、模擬退火算法等有更好的適應性。