[科普中國(guó)]-爬山算法

爬山算法是一種局部擇優(yōu)的方法，采用啟發(fā)式方法，是對(duì)深度優(yōu)先搜索的一種改進(jìn)，它利用反饋信息幫助生成解的決策。 屬于人工智能算法的一種。

定義從當(dāng)前的節(jié)點(diǎn)開(kāi)始，和周圍的鄰居節(jié)點(diǎn)的值進(jìn)行比較。 如果當(dāng)前節(jié)點(diǎn)是最大的，那么返回當(dāng)前節(jié)點(diǎn)，作為最大值(既山峰最高點(diǎn))；反之就用最高的鄰居節(jié)點(diǎn)來(lái)，替換當(dāng)前節(jié)點(diǎn)，從而實(shí)現(xiàn)向山峰的高處攀爬的目的。如此循環(huán)直到達(dá)到最高點(diǎn)。1

算法優(yōu)缺點(diǎn)優(yōu)點(diǎn)避免遍歷，通過(guò)啟發(fā)選擇部分節(jié)點(diǎn)，從而達(dá)到提高效率的目的。

缺點(diǎn)因?yàn)椴皇侨嫠阉?，所以結(jié)果可能不是最佳。

爬山算法一般存在以下問(wèn)題：

1）局部最大：某個(gè)節(jié)點(diǎn)比周圍任何一個(gè)鄰居都高，但是它卻不是整個(gè)問(wèn)題的最高點(diǎn)。

2）高地：也稱為平頂，搜索一旦到達(dá)高地，就無(wú)法確定搜索最佳方向，會(huì)產(chǎn)生隨機(jī)走動(dòng)，使得搜索效率降低。

3）山脊：搜索可能會(huì)在山脊的兩面來(lái)回震蕩，前進(jìn)步伐很小。

解決方法：隨機(jī)重啟爬山算法

深度優(yōu)先搜索算法深度優(yōu)先搜索算法（英語(yǔ)：Depth-First-Search，DFS）是一種用于遍歷或搜索樹(shù)或圖的算法。沿著樹(shù)的深度遍歷樹(shù)的節(jié)點(diǎn)，盡可能深的搜索樹(shù)的分支。當(dāng)節(jié)點(diǎn)v的所在邊都己被探尋過(guò)，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)。這一過(guò)程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)，則選擇其中一個(gè)作為源節(jié)點(diǎn)并重復(fù)以上過(guò)程，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問(wèn)為止。屬于盲目搜索。

深度優(yōu)先搜索是圖論中的經(jīng)典算法，利用深度優(yōu)先搜索算法可以產(chǎn)生目標(biāo)圖的相應(yīng)拓?fù)渑判虮?，利用拓?fù)渑判虮砜梢苑奖愕慕鉀Q很多相關(guān)的圖論問(wèn)題，如最大路徑問(wèn)題等等。2

其他相關(guān)算法stochastic hill climbing

First-choice hill climbing

Random-restart hill climbing

Simulated annealing search

Local beam search

本詞條內(nèi)容貢獻(xiàn)者為:

黃倫先 - 副教授 - 西南大學(xué)