爬山算法

爬山算法是一種局部擇優的方法，採用啟發式方法，是對深度優先搜尋的一種改進，它利用反饋信息幫助生成解的決策。 屬於人工智慧算法的一種。

基本介紹

• 中文名：爬山算法
• 外文名：Hill Climbing
• 類型：一種局部擇優的方法
• 採用：啟發式方法
• 屬於：人工智慧算法的一種

定義

從當前的節點開始，和周圍的鄰居節點的值進行比較。 如果當前節點是最大的，那么返回當前節點，作為最大值(既山峰最高點)；反之就用最高的鄰居節點來，替換當前節點，從而實現向山峰的高處攀爬的目的。如此循環直到達到最高點。

算法優缺點

優點

避免遍歷，通過啟發選擇部分節點，從而達到提高效率的目的。

缺點

因為不是全面搜尋，所以結果可能不是最佳。

爬山算法一般存在以下問題：

1）局部最大：某個節點比周圍任何一個鄰居都高，但是它卻不是整個問題的最高點。

2）高地：也稱為平頂，搜尋一旦到達高地，就無法確定搜尋最佳方向，會產生隨機走動，使得搜尋效率降低。

3）山脊：搜尋可能會在山脊的兩面來回震盪，前進步伐很小。

解決方法：隨機重啟爬山算法

深度優先搜尋算法

深度優先搜尋算法（英語：Depth-First-Search，DFS）是一種用於遍歷或搜尋樹或圖的算法。沿著樹的深度遍歷樹的節點，儘可能深的搜尋樹的分支。當節點v的所在邊都己被探尋過，搜尋將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重複以上過程，整個進程反覆進行直到所有節點都被訪問為止。屬於盲目搜尋。

深度優先搜尋是圖論中的經典算法，利用深度優先搜尋算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。

其他相關算法

• stochastic hill climbing
  
• First-choice hill climbing
  
• Random-restart hill climbing
  
• Simulated annealing search
  
• Local beam search