在開始寫關(guān)于集束搜索的文章之前，我發(fā)現(xiàn)我對很多相關(guān)的算法都不是很熟悉，這嚴重影響到了我對集束搜索的理解，為了能讓自己更好的理解集束搜索，我又回顧了一些基礎(chǔ)。

我的回顧之旅:

BFS算法中，我總結(jié)了兩篇二叉樹的BFS搜索和無向圖的BFS搜索，在理解BFS搜索算法的過程中又額外涉及到了通過樹的中序和先序遍歷生成二叉樹和存儲無向圖的鄰接矩陣和鄰接鏈表這兩個知識點，有興趣的朋友可以查看我的文集“算法之旅”。

好了，閑話不多說，我們先開始說一說什么是集束搜索吧。

Beam Search

盡管廣度優(yōu)先搜索BFS能夠保證在無權(quán)無向圖中找到起點與終點之間的最短路徑，但是由于該算法對存儲的消耗是指數(shù)級別的，因此對于搜索空間較大的問題，廣度優(yōu)先搜索算法幾乎無用武之地，因為往往在找到最優(yōu)解之前，存儲內(nèi)存就已經(jīng)消耗完了，但是如果我們不得不去在一個搜素空間較大的圖中尋找兩點之間的路徑時，我們該怎么辦呢？前人給了我們這樣一個解決方法：那就是放寬對路徑的要求，不再要求路徑一定是最短路徑，退而求其次，尋找一個相對較短的路徑，這個相對值是可以在我們能接受的范圍之內(nèi)的，這種解決方案就是集束搜索的算法思想了。

集束搜索Beam Search借助了一個啟發(fā)式代價函數(shù)henuristic cost function,h用來預(yù)測當前節(jié)點到目標節(jié)點的代價的大小，這個啟發(fā)式代價函數(shù)我們不是第一次接觸了，在上一篇文章A*搜索算法中我們已經(jīng)詳細介紹了，除此之外，集束搜索還是用了一個束寬度beam width,B來限制在每一層的遍歷時存儲該層的節(jié)點數(shù)量。

在BFS算法中，我們是將每一層的所有節(jié)點都存儲到隊列queue中，而集束搜索是根據(jù)h的值，只選擇B個節(jié)點存儲到隊列中，這樣的話我們就能保證在得到結(jié)果之前將存儲耗盡的情況了。

現(xiàn)在我們來分析一下集束搜索：

通過考慮四個特征來分析圖搜索算法通常是有效的：

? ? 完整性：如果搜索算法在解決方案存在時找到解決方案（目標節(jié)點），則搜索算法已完成。

? ? 最優(yōu)性：如果找到最優(yōu)解，搜索算法是最優(yōu)的。在波束搜索算法的情況下，這意味著算法必須找到從起始節(jié)點到目標節(jié)點的最短路徑。

? ? ?時間復(fù)雜度：這是算法速度的數(shù)量級估計。通過分析算法執(zhí)行期間生成的節(jié)點數(shù)來確定時間復(fù)雜度。

? ? 空間復(fù)雜度：這是算法的內(nèi)存消耗的數(shù)量級估計?？臻g復(fù)雜度由算法執(zhí)行期間任何時候必須存儲的最大節(jié)點數(shù)決定。

完整性

通常，光束搜索算法不完整。這在上面的跟蹤1中說明。即使內(nèi)存沒有耗盡，算法也無法找到目標，因為它無法向BEAM添加任何節(jié)點。因此，即使給定無限的時間和存儲器，當存在從起始節(jié)點到目標節(jié)點的路徑時，波束搜索算法也可能錯過目標節(jié)點。更準確的啟發(fā)式功能和更大的波束寬度可以提高Beam Search找到目標的機會。然而，這種完整性的缺乏是光束搜索算法的最重要的弱點之一。

最優(yōu)

正如光束搜索算法不完整一樣，它也不能保證是最佳的。這由上面的跟蹤2顯示。在此示例中，Beam Search找到了目標節(jié)點，但未能找到目標的最佳路徑，即使圖1中的啟發(fā)式是可接受的（低估了每個節(jié)點的目標成本）和一致性（低估了相鄰節(jié)點之間的成本） ）。這是因為波束寬度和不準確的啟發(fā)函數(shù)導(dǎo)致算法錯過擴展最短路徑。更精確的啟發(fā)式功能和更大的波束寬度可以使Beam Search更有可能找到達到目標的最佳路徑。

時間復(fù)雜性

光束搜索算法完成的時間往往取決于啟發(fā)式函數(shù)的準確性。不準確的啟發(fā)式函數(shù)通常會強制算法擴展更多節(jié)點以找到目標，甚至可能導(dǎo)致它無法找到目標。在最壞的情況下，啟發(fā)式函數(shù)將Beam Search一直引導(dǎo)到搜索樹中最深的層次。因此，最壞情況時間是?O（Bm），其中B是波束寬度，m是搜索樹中任何路徑的最大深度。這種時間復(fù)雜度是線性的，因為波束搜索算法僅擴展B每個級別的節(jié)點;?它不會像許多具有指數(shù)時間復(fù)雜性的搜索算法那樣在每個級別上進行更廣泛的分支。該算法執(zhí)行的速度是其最大優(yōu)勢之一。

空間復(fù)雜性

Beam Search的內(nèi)存消耗是其最理想的特性。因為該算法僅在搜索樹中的每個級別存儲B個節(jié)點，所以最壞情況的空間復(fù)雜度為?O（Bm），其中B是波束寬度，m是搜索樹中任何路徑的最大深度。這種線性內(nèi)存消耗允許Beam Search深入探測大型搜索空間，并可能找到其他算法無法達到的解決方案。

集束搜索算法的偽碼：

/ *初始化* /

g = 0;

hash_table = {start};

BEAM = {start};

/ *主循環(huán)* /

while（BEAM≠?）{//循環(huán)，直到BEAM不包含節(jié)點

? SET =?; //空集

? / *生成SET節(jié)點* /

? for（each state in BEAM）{

? ? for（each successor of state）{

? ? ? if（successor == goal）返回g + 1;

? ? ? SET =SET∪{successor}; //添加SET的后繼者

? ? }

? }

? BEAM =?; //空集

? g = g + 1;

? / *為下一個循環(huán)填充BEAM * /

? while（（SET≠?）AND（B> | BEAM |））{// set不為空且BEAM中的節(jié)點數(shù)小于B

? ? state =具有最小h值的SET中的后繼者;

? ? SET = SET \ {state}; //從SET中刪除狀態(tài)

? ? if（state?hash_table）{//狀態(tài)不在hash_table中

? ? ? if（hash_table為full）返回∞;

? ? ? hash_table = hash_table∪{state}; //將狀態(tài)添加到hash_table

? ? ? BEAM = BEAM∪{state}; //將狀態(tài)添加到BEAM

? ? }

? }

}

//未找到目標，BEAM為空 -? Beam Search未能找到目標

返回∞;