PopularSearchAlgorithms

Unit

2Contents

NewWords

Abbreviations

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

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