PopularSearchAlgorithms

Unit

2Contents

NewWords

Abbreviations

PhrasesNotes參考譯文NewWordsNewWordsNewWordsNewWordsNewWordsPhrasesPhrasesPhrasesAbbreviationsListeningtoTextA熱門搜索算法搜索是人工智能中解決問(wèn)題的通用技術(shù)。有一些單人游戲，如智力拼圖、數(shù)獨(dú)游戲、填字游戲等。搜索算法可以幫助你搜索此類游戲中的特定位置。1.搜索術(shù)語(yǔ)問(wèn)題空間——這是搜索發(fā)生的環(huán)境。（一組狀態(tài)和一組運(yùn)算符來(lái)改變這些狀態(tài)。）問(wèn)題實(shí)例——它是初始狀態(tài)+目標(biāo)狀態(tài)。問(wèn)題空間圖——它代表問(wèn)題狀態(tài)。狀態(tài)由節(jié)點(diǎn)顯示，運(yùn)算符由邊顯示。問(wèn)題的深度——從初始狀態(tài)到目標(biāo)狀態(tài)的最短路徑或最短操作符序列的長(zhǎng)度?？臻g復(fù)雜度——存儲(chǔ)在內(nèi)存中的最大節(jié)點(diǎn)數(shù)。時(shí)間復(fù)雜度——?jiǎng)?chuàng)建的最大節(jié)點(diǎn)數(shù)?？扇菰S性——總是找到最優(yōu)解的算法的屬性。分支因子——問(wèn)題空間圖中的平均子節(jié)點(diǎn)數(shù)。深度——從初始狀態(tài)到目標(biāo)狀態(tài)的最短路徑的長(zhǎng)度。參考譯文1.蠻力搜索策略它們很簡(jiǎn)單，因?yàn)樗鼈儾恍枰魏翁囟I(lǐng)域的知識(shí)。在很少的可能狀態(tài)下，這些策略頗為適用。要求：?狀態(tài)描述?一組有效的運(yùn)算符?初始狀態(tài)?目標(biāo)狀態(tài)描述2.1廣度優(yōu)先搜索它從根節(jié)點(diǎn)開始，首先探索相鄰節(jié)點(diǎn)并向下一級(jí)鄰居移動(dòng)。它一次生成一個(gè)樹，直到找到解決方案。它可以使用FIFO隊(duì)列數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。該方法提供了解決問(wèn)題的最短路徑。如果分支因子（給定節(jié)點(diǎn)的子節(jié)點(diǎn)的平均數(shù)量）=b且深度=d，則該級(jí)別的節(jié)點(diǎn)數(shù)是bd。參考譯文在最壞情況下創(chuàng)建的節(jié)點(diǎn)總數(shù)是b+b2+b3+...+bd。缺點(diǎn)：由于保存了每個(gè)級(jí)別的節(jié)點(diǎn)以創(chuàng)建下一個(gè)節(jié)點(diǎn)，因此會(huì)消耗大量?jī)?nèi)存空間。存儲(chǔ)節(jié)點(diǎn)的空間要求是指數(shù)級(jí)的。其復(fù)雜性取決于節(jié)點(diǎn)數(shù)量。它可以檢查重復(fù)的節(jié)點(diǎn)。2.2深度優(yōu)先搜索它用LIFO堆棧數(shù)據(jù)結(jié)構(gòu)以遞歸方式實(shí)現(xiàn)。它創(chuàng)建與廣度優(yōu)先方法相同的節(jié)點(diǎn)集，只是順序不同。由于單個(gè)路徑上的節(jié)點(diǎn)存儲(chǔ)在從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每次迭代中，因此存儲(chǔ)節(jié)點(diǎn)的空間要求是線性的。當(dāng)分支因子帶深度為m時(shí)，存儲(chǔ)空間為bm。缺點(diǎn)：此算法可能無(wú)法終止并在一條路徑上無(wú)限循環(huán)。解決這一問(wèn)題的方法是選擇截止深度。如果理想截止值為d且當(dāng)選擇的截止值小于d，則該算法可能失敗。當(dāng)選擇的截止值大于d，則會(huì)增加執(zhí)行時(shí)間。其復(fù)雜性取決于路徑的數(shù)量。它無(wú)法檢查重復(fù)的節(jié)點(diǎn)。參考譯文參考譯文2.3雙向搜索它從初始狀態(tài)向前搜索，從目標(biāo)狀態(tài)向后搜索，直到兩者相遇以識(shí)別共同狀態(tài)。從初始狀態(tài)開始的路徑與來(lái)自目標(biāo)狀態(tài)的反向路徑相關(guān)聯(lián)。每次搜索僅完成總路徑的一半。2.4等代價(jià)搜索排序是通過(guò)增加節(jié)點(diǎn)路徑的代價(jià)來(lái)完成的。它總是擴(kuò)展最低代價(jià)節(jié)點(diǎn)。如果每個(gè)轉(zhuǎn)換具有相同的代價(jià)，則與廣度優(yōu)先搜索相同。它以代價(jià)增加的順序探索路徑。缺點(diǎn)：可能有多個(gè)長(zhǎng)路徑。等代價(jià)搜索必須全部探索。2.5迭代深化深度優(yōu)先搜索它執(zhí)行深度優(yōu)先搜索到級(jí)別1，重新開始，執(zhí)行完整的深度優(yōu)先搜索到級(jí)別2，并繼續(xù)以這種方式直到找到解決方案。直到生成所有較低節(jié)點(diǎn)，它才會(huì)創(chuàng)建一個(gè)節(jié)點(diǎn)。它只保存節(jié)點(diǎn)堆棧。算法在深度d處找到解時(shí)結(jié)束。在深度d處創(chuàng)建的節(jié)點(diǎn)的數(shù)量是bd，且在深度d-1處是bd-1。參考譯文

參考譯文3.知情（啟發(fā)式）搜索策略為了解決具有大量可能狀態(tài)的大問(wèn)題，需要添加針對(duì)問(wèn)題的知識(shí)以提高搜索算法的效率。3.1啟發(fā)式評(píng)估函數(shù)其計(jì)算兩個(gè)狀態(tài)之間最佳路徑的代價(jià)?；瑒?dòng)拼圖游戲的啟發(fā)式函數(shù)由計(jì)算移動(dòng)滑塊的數(shù)量來(lái)完成，每個(gè)滑塊都來(lái)自其目標(biāo)狀態(tài)，還要加上全部滑塊的移動(dòng)數(shù)。3.2純啟發(fā)式搜索它按照啟發(fā)式值的順序擴(kuò)展節(jié)點(diǎn)。它創(chuàng)建了兩個(gè)列表，一個(gè)是已經(jīng)展開的節(jié)點(diǎn)的閉合列表，另一個(gè)是已創(chuàng)建但未展開的節(jié)點(diǎn)的開放列表。在每次迭代中，擴(kuò)展具有最小啟發(fā)式值的節(jié)點(diǎn)，創(chuàng)建其所有子節(jié)點(diǎn)并將其放置在閉合列表中。然后，將啟發(fā)式函數(shù)應(yīng)用于子節(jié)點(diǎn)，并根據(jù)它們的啟發(fā)式值將它們放置在打開列表中。保存較短的路徑，并處理較長(zhǎng)的路徑。參考譯文3.3A*搜索它是最佳優(yōu)先搜索的最知名形式。它避免擴(kuò)展那些很昂貴的路徑，而是首先擴(kuò)展最有希望的路徑。f(n)=g(n)+h(n)，其中?g(n)到達(dá)節(jié)點(diǎn)的成本（到目前為止）?h(n)從節(jié)點(diǎn)到目標(biāo)的估計(jì)成本?f(n)估計(jì)從n到目標(biāo)的路徑總成本。它通過(guò)增加f(n)使用優(yōu)先級(jí)隊(duì)列來(lái)實(shí)現(xiàn)。3.4貪婪最佳優(yōu)先搜索它擴(kuò)展估計(jì)最接近目標(biāo)的節(jié)點(diǎn)。它基于f(n)=h(n)擴(kuò)展節(jié)點(diǎn)。它使用優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)。缺點(diǎn)：它可能卡在循環(huán)中。這不是最佳的。參考譯文4.本地搜索算法它們從一個(gè)預(yù)期的解決方案開始，然后轉(zhuǎn)移到鄰近的解決方案。即使它們?cè)诮Y(jié)束之前的任何時(shí)間被中斷，它們也可以返回一個(gè)有效的解決方案。4.1爬山搜索它是一種迭代算法，從問(wèn)題的任意解決方案開始，并嘗試通過(guò)逐步更改解決方案的單個(gè)元素來(lái)找到更好的解決方案。如果更改產(chǎn)生更好的解決方案，則將新增更改視為新解決方案。重復(fù)該過(guò)程直到?jīng)]有進(jìn)一步的改進(jìn)。函數(shù)Hill-Climbing(problem)返回一個(gè)局部最大值的狀態(tài)。缺點(diǎn)：該算法既不完整也不優(yōu)化。參考譯文4.2局部集束搜索在該算法中，它在任何給定時(shí)間保持k個(gè)狀態(tài)。一開始，這些狀態(tài)是隨機(jī)生成的。這些k個(gè)狀態(tài)的后繼者是在目標(biāo)函數(shù)的幫助下計(jì)算出來(lái)的。如果這些后繼者中的任何一個(gè)是目標(biāo)函數(shù)的最大值，則算法停止。否則，（初始k狀態(tài)和k個(gè)狀態(tài)的后繼者=2k）狀態(tài)被放置在池中。然后按數(shù)字對(duì)池進(jìn)行排序。選擇最高的k個(gè)狀態(tài)作為新的初始狀態(tài)。此過(guò)程持續(xù)進(jìn)行直到達(dá)到最大值。函數(shù)BeamSearch(problem,k)返回一個(gè)解狀態(tài)。參考譯文參考譯文4.3模擬退火退火是加熱和冷卻金屬而改變其內(nèi)部結(jié)構(gòu)以改變其物理性質(zhì)的過(guò)程。當(dāng)金屬冷卻時(shí)，就形成了其新結(jié)構(gòu)，而且金屬保留其新獲得的性能。在模擬退火過(guò)程中，溫度一直可變。我們最初將溫度設(shè)置為高，然后在算法進(jìn)行時(shí)讓它慢慢“冷卻”。當(dāng)溫度高時(shí)，算法允許接受具有高頻率的更差的解決方案。開始?初始化k=0;L=整數(shù)變量;?從i→j，搜索性能差異Δ。?如果Δ<=0，則接受；否則，如果exp(-Δ/T(k))>random(0,1)則接受；?對(duì)L(k)步驟重復(fù)步驟1和2。?k=k+1;重復(fù)步驟1到4，