启发式算法

计算机科学中所謂的heuristic，除了有經驗法則的意思外（見啟發式），它還有另外兩個技術上的意義。

啟發式演算法[编辑]

電腦科學的兩大基礎目標，就是發現可證明其執行效率良好且可得最佳解或次佳解的演算法。而啟發式演算法則試圖一次提供一个或全部目標。例如它常能發現很不錯的解，但也沒辦法證明它不會得到較壞的解；它通常可在合理時間解出答案，但也沒辦法知道它是否每次都可以這樣的速度求解。

有時候人們會發現在某些特殊情況下，啟發式演算法會得到很壞的答案或效率極差，然而造成那些特殊情況的資料結構，也許永遠不會在現實世界出現。因此現實世界中啟發式演算法很常用來解決問題。啟發式演算法處理許多實際問題時通常可以在合理時間內得到不錯的答案。

有一類的通用啟發式策略稱為元启发算法（metaheuristic），通常使用亂數搜尋技巧。他們可以應用在非常廣泛的問題上，但不能保證效率。

啟發式演算法與最短路徑問題[编辑]

所謂的最短路径問題有很多種意思，在這裡啟發式指的是在一個搜尋樹的節點上定義的函数 $h(n)$ ，用於評估從此節點到目標節點成本最小的路徑。啟發式通常用於資訊充份的搜尋演算法，例如最好优先貪婪演算法與A*。最好优先貪婪演算法會為啟發式函數選擇最低代價的節點；A*則會為 $g(n)+h(n)$ 選擇最低代價的節點，此 $g(n)$ 是從起始節點到目前節點的路徑的確實代價。如果 $h(n)$ 是可接受的（admissible）意即 $h(n)$ 未曾付出超過達到目標的代價，則A*一定會找出最佳解。

最能感受到啟發式演算法好處的經典問題是n-puzzle。此問題在計算錯誤的拼圖圖形，與計算任兩塊拼圖的曼哈頓距離的總和以及它距離目的有多遠時，使用了本演算法。注意，上述兩條件都必須在可接受的範圍內。

啟發式演算法對運算效能的影響[编辑]

任何的搜尋問題中，每個節點都有 $b$ 個選擇以及到達目標的深度 $d$ ，一個毫無技巧的演算法通常都要搜尋 $b^{d}$ 個節點才能找到答案。啟發式演算法藉由使用某種切割機制降低了分支因子（branching factor）以改進搜尋效率，由 $b^{d}$ 降到較低的 $b'$ 。分叉率可以用來定義啟發式演算法的偏序关系，例如：若在一個 $n$ 節點的搜尋樹上， $h_{1}(n)$ 的分叉率較 $h_{2}(n)$ 低，則 $h_{1}(n)<h_{2}(n)$ 。啟發式為每個要解決特定問題的搜尋樹的每個節點提供了較低的分叉率，因此它們擁有較佳效率的計算能力。