Best-FirstSearch

Unit

3Contents

NewWords

Abbreviations

PhrasesNotes參考譯文NewWordsNewWordsNewWordsNewWordsPhrasesListeningtoTextA最佳優(yōu)先搜索1.序言本文介紹了最佳優(yōu)先搜索的一般形式。有許多特定的算法遵循最佳優(yōu)先搜索的基本形式但卻使用更復(fù)雜的評估函數(shù)。A*是最佳優(yōu)先搜索的一個流行變體。雖然此處包含的信息與這些搜索算法相關(guān)，但本文沒有專門討論A*或其它變體。2.定義最佳優(yōu)先搜索最常見形式是簡單的啟發(fā)式搜索算法。這里的“啟發(fā)式”是指一般的問題解決規(guī)則或一組規(guī)則，它們不能保證得到最佳解決方案甚至不能得到任何解決方案，但可以作為解決問題的有用指南。最佳優(yōu)先搜索是基于圖的搜索算法，這意味著搜索空間可以表示為由路徑連接的一系列節(jié)點。參考譯文3.它如何工作名稱“最佳優(yōu)先”指首先探索具有最佳“得分”的節(jié)點的方法。用評估函數(shù)為每個候選節(jié)點分配分?jǐn)?shù)。該算法含有兩個列表，一個列表包含尚待探索的候選節(jié)點（OPEN），另一個列表包含已訪問節(jié)點（CLOSED）。由于每個訪問節(jié)點的所有未訪問的后繼節(jié)點都包括在OPEN列表中，因此該算法不限于僅探索最近訪問的節(jié)點的后繼節(jié)點。換句話說，該算法總是選擇圖中所有未訪問節(jié)點中的最佳節(jié)點，而不是僅限于小的子集（例如直接鄰居）。其他搜索策略（例如深度優(yōu)先和廣度優(yōu)先）具有這樣的限制。該策略的優(yōu)點是，如果算法到達(dá)死角節(jié)點，它將繼續(xù)嘗試其它節(jié)點。參考譯文4.算法最佳優(yōu)先搜索最基本形式包括以下算法：第一步是使用單個節(jié)點（起始節(jié)點）定義OPEN列表。第二步是檢查OPEN是否為空。如果它為空，則算法返回失敗并退出。第三步是從OPEN中刪除具有最高分?jǐn)?shù)n的節(jié)點，并將其置于CLOSED中。第四步“擴(kuò)展”節(jié)點n，其中擴(kuò)展是n的后繼節(jié)點的標(biāo)識。然后，第五步檢查每個后繼節(jié)點，以查看它們中的一個是否是目標(biāo)節(jié)點。如果任何后繼者是目標(biāo)節(jié)點，則算法返回成功和解決方案，該解決方案包括從目標(biāo)向后追溯到起始節(jié)點的路徑。否則，算法前進(jìn)到第六步。對于每個后繼節(jié)點，算法將評估函數(shù)f應(yīng)用于它，然后檢查節(jié)點是否已處于OPEN或CLOSED狀態(tài)。如果該節(jié)點尚未進(jìn)入任一列表，則會將其添加到OPEN。最后，第七步通過將算法回送到第二步來建立循環(huán)結(jié)構(gòu)。如果算法在步驟5中返回成功或在步驟2中失敗，則該循環(huán)中斷。參考譯文參考譯文這里的算法用偽代碼表示為：1)定義一個列表，OPEN，僅由單個節(jié)點（即起始節(jié)點）組成。2)如果列表為空，則返回失敗。3)從列表中刪除具有最佳分?jǐn)?shù)的節(jié)點n（f為最小的節(jié)點），并將其移至列表CLOSED。4)展開節(jié)點n。5)如果n的任何后繼者是目標(biāo)節(jié)點，則返回成功和解決方案（通過跟蹤從目標(biāo)節(jié)點到開始節(jié)點的路徑）。6)對于每個后繼節(jié)點：A)將評估函數(shù)f應(yīng)用于節(jié)點。B)如果節(jié)點未在任何列表中，則將其添加到OPEN。7)通過將算法回送到第二步來建立循環(huán)結(jié)構(gòu)。Pearl為FOR循環(huán)添加了第三步，旨在防止重新擴(kuò)展已經(jīng)訪問過的節(jié)點。上面省略了該步驟，因為對于所有最佳優(yōu)先搜索算法這一步并不常見。5.評估函數(shù)用于確定節(jié)點得分的特定評估函數(shù)在上述算法中沒有精確定義，因為所使用的實際函數(shù)由程序員的確定，并且可以根據(jù)搜索空間的特性而變化。雖然評估函數(shù)可以在很大程度上確定搜索的有效性和效率，但是為了理解搜索算法，我們不需要關(guān)心函數(shù)的特性。

參考譯文6.應(yīng)用最佳搜索及其更高級的變體已用于游戲和網(wǎng)絡(luò)爬蟲等應(yīng)用程序。在網(wǎng)絡(luò)爬蟲程序中，每個網(wǎng)頁都被視為一個節(jié)點，頁面上的所有超鏈接都被視為未訪問的后繼節(jié)點。使用最佳優(yōu)先搜索的網(wǎng)絡(luò)爬蟲程序通常使用評估函數(shù)，該函數(shù)根據(jù)其父頁面的內(nèi)容與搜索查詢的相似程度為鏈接分配優(yōu)先級。在游戲中，最佳優(yōu)先搜索可以為游戲角色提供路徑搜索算法。例如，對手可以使用它來查找游戲世界中玩家的位置。有些游戲把地形分成可進(jìn)入或不可進(jìn)入的區(qū)塊。在這種情況下，搜索算法將每個區(qū)塊視為節(jié)點，其中