PopularSearchAlgorithms

Unit

2Contents

NewWords

Abbreviations

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

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