-
爬山算法
鎖定
- 中文名
- 爬山算法
- 外文名
- Hill Climbing
爬山算法定義
從當前的節點開始,和周圍的鄰居節點的值進行比較。 如果當前節點是最大的,那麼返回當前節點,作為最大值(既山峯最高點);反之就用最高的鄰居節點來,替換當前節點,從而實現向山峯的高處攀爬的目的。如此循環直到達到最高點。
[1]
爬山算法算法優缺點
爬山算法優點
避免遍歷,通過啓發選擇部分節點,從而達到提高效率的目的。
爬山算法缺點
因為不是全面搜索,所以結果可能不是最佳。
爬山算法一般存在以下問題:
1)局部最大:某個節點比周圍任何一個鄰居都高,但是它卻不是整個問題的最高點。
2)高地:也稱為平頂,搜索一旦到達高地,就無法確定搜索最佳方向,會產生隨機走動,使得搜索效率降低。
3)山脊:搜索可能會在山脊的兩面來回震盪,前進步伐很小。
解決方法:隨機重啓爬山算法
爬山算法深度優先搜索算法
深度優先搜索算法(英語:Depth-First-Search,DFS)是一種用於遍歷或搜索樹或圖的算法。沿着樹的深度遍歷樹的節點,儘可能深的搜索樹的分支。當節點v的所在邊都己被探尋過,搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點,則選擇其中一個作為源節點並重復以上過程,整個進程反覆進行直到所有節點都被訪問為止。屬於盲目搜索。
深度優先搜索是圖論中的經典算法,利用深度優先搜索算法可以產生目標圖的相應拓撲排序表,利用拓撲排序表可以方便的解決很多相關的圖論問題,如最大路徑問題等等。
[2]
爬山算法其他相關算法
- stochastic hill climbing
- First-choice hill climbing
- Random-restart hill climbing
- Simulated annealing search
- Local beam search