啟發式演算法
此條目的語調或風格或許不適合百科全書。 (2019年8月24日) |
此條目沒有列出任何參考或來源。 (2013年9月30日) |
啟發式演算法
電腦科學的兩大基礎目標，就是發現可證明其執行效率良好且可得最佳解或次佳解的演算法。而啟發式演算法則試圖一次提供一個或全部目標。例如它常能發現很不錯的解，但也沒辦法證明它不會得到較壞的解；它通常可在合理時間解出答案，但也沒辦法知道它是否每次都可以這樣的速度求解。
有時候人們會發現在某些特殊情況下，啟發式演算法會得到很壞的答案或效率極差，然而造成那些特殊情況的資料結構，也許永遠不會在現實世界出現。因此現實世界中啟發式演算法很常用來解決問題。啟發式演算法處理許多實際問題時通常可以在合理時間內得到不錯的答案。
有一類的通用啟發式策略稱為元啟發演算法（metaheuristic），通常使用亂數搜尋技巧。他們可以應用在非常廣泛的問題上，但不能保證效率。
啟發式演算法與最短路徑問題
所謂的最短路徑問題有很多種意思，在這裡啟發式指的是在一個搜尋樹的節點上定義的函式 ，用於評估從此節點到目標節點成本最小的路徑。啟發式通常用於資訊充份的搜尋演算法，例如最好優先貪婪演算法與A*。最好優先貪婪演算法會為啟發式函式選擇最低代價的節點；A*則會為 選擇最低代價的節點，此 是從起始節點到目前節點的路徑的確實代價。如果 是可接受的（admissible）意即 未曾付出超過達到目標的代價，則A*一定會找出最佳解。
最能感受到啟發式演算法好處的經典問題是n-puzzle。此問題在計算錯誤的拼圖圖形，與計算任兩塊拼圖的曼哈頓距離的總和以及它距離目的有多遠時，使用了本演算法。注意，上述兩條件都必須在可接受的範圍內。
啟發式演算法對運算效能的影響
任何的搜尋問題中，每個節點都有 個選擇以及到達目標的深度 ，一個毫無技巧的演算法通常都要搜尋 個節點才能找到答案。啟發式演算法藉由使用某種切割機制降低了分支因子（branching factor）以改進搜尋效率，由 降到較低的 。分叉率可以用來定義啟發式演算法的偏序關係，例如：若在一個 節點的搜尋樹上， 的分叉率較 低，則 。啟發式為每個要解決特定問題的搜尋樹的每個節點提供了較低的分叉率，因此它們擁有較佳效率的計算能力。
找尋新的啟發式演算法
如何找到一個分叉率較少又通用的合理啟發式演算法，已被人工智慧社群[哪個／哪些？]深入探究過。他們使用幾種常見技術：
- 部分問題的解答的代價通常可以評估解決整個問題的代價，通常很合理。例如一個10-puzzle拼盤，解題的代價應該與將1到5的方塊移回正確位置的代價差不多。通常解題者會先建立一個儲存部份問題所需代價的模式資料庫（pattern database）以評估問題。
- 解決較易的近似問題通常可以拿來合理評估原先問題。例如曼哈頓距離是一個簡單版本的n-puzzle問題，因為我們假設可以獨立移動一個方塊到我們想要的位置，而暫不考慮會移到其他方塊的問題。
- 給我們一群合理的啟發式函式 ，而函式 則是個可預測這些函式的啟發式函式。
一個在1993年由A.E. Prieditis寫出的程式ABSOLVER就運用了這些技術，這程式可以自動為問題產生啟發式演算法。ABSOLVER為8-puzzle產生的啟發式演算法優於任何先前存在的！而且它也發現了第一個有用的解魔術方塊的啟發式程式。