版權(quán)歸原作者所有,如有侵權(quán),請(qǐng)聯(lián)系我們

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

科學(xué)百科
原創(chuàng)
科學(xué)百科為用戶提供權(quán)威科普內(nèi)容,打造知識(shí)科普陣地
收藏

爬山算法是一種局部擇優(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é)