本文關(guān)鍵詞：搜索理論，由筆耕文化傳播整理發(fā)布。

搜索理論

寬度優(yōu)先搜索bfs 

一、搜索的bfs，寬度優(yōu)先搜索，一般用于求最短的得到到目的地的距離，有個起始點，先把這個起始點入隊列，不要忘記將這個起始點標記為已經(jīng)利用，不然會走回來的，然后是與這個起始點的周圍的點的監(jiān)測，若可以行的通，我們一一檢測這些擴展出來的點，若是目的地就結(jié)束了，若不是目的地，將改點標記為已經(jīng)利用，并將該點入隊列。

 二、搜索的雙向bfs，雙向的bfs一般來說可以用單向解決，但是單向的效率上還是差了點，適合雙向bfs的題目有一些共同特點：給出起始和最終狀態(tài)，讓求出一條從初始到末狀態(tài)的最短路。

雙向bfs的實現(xiàn)過程： 從初始結(jié)點開始擴展，每擴展一層，在從目標節(jié)點按照產(chǎn)生系統(tǒng)相反的辦法來擴展結(jié)點，直到從兩端擴展出的某個結(jié)點相遇，那么中間的這條路徑一定就是從初始到終點最短的路徑。

注意： 雙向廣搜必須按層擴展，才能保證結(jié)果的正確性

無解狀態(tài)就和普通bfs無異, 所以判斷無解函數(shù)不可省略.  

     路徑的保存：有時候除了要找到一個目標狀態(tài)，還需要保存從初始結(jié)點到它的路徑。路徑可以隨狀態(tài)保存，也可以用鏈表穿起來。如果保存的所有結(jié)點或者路徑長度不定，推薦使用鏈表。

int DBFS() { Queue Q[2]; Map M[2]; int now=0; Q[0].push(start); Q[1].push(end); M[0][start]=M[1][end]=true; While( !Q[0].empty() || !Q[1].empty) { int nowg=now&1,count=Q[nowg].size(); while(count--) { curstate=Q[nowg].front(); Q[nowg].pop(); if( M[nowg^1].find(curstate) != M.end() )return now; for every extstate=extend(curstate) if(M[nowg].find(extstate) == M.end()) { Q[nowg].push(extstate); M[nowg][extstate] =true; } } ++now; } return -1; }

 深度優(yōu)先搜索dfs

一、深度優(yōu)先搜索一般是給定搜索的深度，或者沒有深度有結(jié)束條件的，可以用結(jié)束條件代替深度，都可以用dfs

二、dfs回溯用來解決搜索所有解的問題，但是純粹的dfs回溯往往會超時，一般與剪枝聯(lián)系在一起

三、剪枝一般分為可行性剪枝和最優(yōu)化剪枝 

（1）可行性剪枝， 剪去不能到達終點的路徑

（2）最優(yōu)化剪枝， 剪去不能到達終點和不可能是第一個到達終點的路徑

 迭代加深搜索

一、用于不知道最短轉(zhuǎn)移次數(shù)，為了彌補廣搜的空間不足的問題而產(chǎn)生的搜索方法

形式為：for( depth=init(); dfs() ; depth++ ) 

使用是要注意：

（1）由于不知道上界， 如果問題無解的情況下就不能用這個了

 （2）對深度較淺的層數(shù)會重復(fù)搜索，并不推薦使用

Procedure ID-dfs(dep:integer); Var J: integer; Begin If dep>深度的限界 then exit; // 如果搜索的深度大于限界，則返回上一層 For j:=1 to n do // 按照規(guī)則生成子結(jié)點 If 子結(jié)點安全 then Begin 入棧； If 子結(jié)點是目標結(jié)點 then 對目標結(jié)點進行處理，退出程序 Else id-dfs(dep+1); 退棧； End; End; For i:=1 to depmax do // 枚舉深度的限界 Begin Id-dfs(i); If 運行超時 then break; End;

從上述迭代加深搜索算法的實現(xiàn)過程和框架，我們可以看出，迭代加深搜索算法就是仿廣度優(yōu)先搜索的深度優(yōu)先搜索。

既能滿足深度優(yōu)先搜索的線性存儲要求，又能保證發(fā)現(xiàn)一個最小深度的目標結(jié)點。

A*算法

A*類似貪心的BFS 

BFS一般擴展最小消耗的點，A*算法在另一方面 擴展最有希望的點（估價函數(shù)返回值最優(yōu)）

狀態(tài)被保存在一個優(yōu)先級隊列中，按照cost*價值排列。對一個可容許的估價函數(shù)，第一個找到的狀態(tài)保證是最優(yōu)的。

一、A*算法屬于啟發(fā)式搜索，擴展結(jié)點的順序是基于廣度優(yōu)先搜索，但是不同之處在于每擴展一個子結(jié)點需要計算估價函數(shù)f（s），以估算起始結(jié)點，經(jīng)過該結(jié)點到達目標結(jié)點的最佳路徑代價，每當擴展結(jié)點時，總是希望在所有待擴展結(jié)點中選擇具有最小

f（s）值的結(jié)點作為擴展對象，以便使搜索盡量沿著最有希望的方向進行。 

假設(shè)s表示一個狀態(tài)，

f（s）：啟發(fā)式函數(shù)，表示從初始狀態(tài)開始，經(jīng)過狀態(tài)s的路徑上最少需要多少代價才可以找到終點之一。

g（s）：從初始狀態(tài)到當前狀態(tài)s的最小代價

h（s）：估價函數(shù)，從當前狀態(tài)s到達終點之一最少需要多少代價

有關(guān)系式f（s）=g（s）+h（s）

一種具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法的充分條件是：

A*必須滿足兩點：

h（s）<=h*(s) 和 f（s）必須是遞增的

1) 搜索樹上存在著從起始點到終了點的最優(yōu)路徑。

2) 問題域是有限的。

3）所有結(jié)點的子結(jié)點的搜索代價值>0。

4）h(n)=<h*(n) （h*(n)為實際問題的代價值）。

當此四個條件都滿足時，一個具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法，并一定能找到最優(yōu)解。

對于一個搜索問題，顯然，條件1,2,3都是很容易滿足的，而

條件4)： h(n)<=h*(n)是需要精心設(shè)計的，由于h*(n)顯然是無法知道的。

所以，一個滿足條件4）的啟發(fā)策略h(n)就來的難能可貴了。不過，對于圖的最優(yōu)路徑搜索和八數(shù)碼問題，有些相關(guān)策略h(n)不僅很好理解，而且已經(jīng)在理論上證明是滿足條件4)的，從而為這個算法的推廣起到了決定性的作用。不過h(n)距離h*(n)的程度不能過大，否則h(n)就沒有過強的區(qū)分能力，算法效率并不會很高。對一個好的h(n)的評價是：h(n)在h*(n)的下界之下，并且盡量接近h*(n).


當然，估值函數(shù)的設(shè)計也就就僅僅是f(n)=g(n)+h(n)一種，，另外的估值函數(shù)“變種”如：f(n)=w*g(n)+(1-w)*h(n) ，f(n)=g(n)+h(n)+h(n-1)針對不同的具體問題亦會有不同的效果。

        A*算法最為核心的過程，就在每次選擇下一個當前搜索點時，是從所有已探知的但未搜索過點中(可能是不同層，亦可不在同一條支路上)，選取f值最小的結(jié)點進行展開。而所有“已探知的但未搜索過點”可以通過一個按f值升序的隊列(即優(yōu)先隊列)進行排列。這樣，在整體的搜索過程中，只要按照類似廣度優(yōu)先的算法框架，從優(yōu)先隊列中彈出隊首元素（f值），對其可能子結(jié)點計算g、h和f值，直到優(yōu)先隊列為空(無解)或找到終止點為止。 

A*算法與廣度優(yōu)先和深度優(yōu)先的聯(lián)系就在于，當g(n)=0時，該算法類似于DFS，當h(n)=0時，該算法類似于BFS , 這一點，可以通過上面的A*搜索樹的具體過程中將h(n)設(shè)為0或?qū)(n)設(shè)為0而得到。 

       路徑最優(yōu)問題，簡單來說，就是在兩個結(jié)點之間找一條最短路徑。有的朋友不禁要問，這個問題不是已經(jīng)有Dijkstra算法可以解決了嗎？此話不假，但是不要忘了Dijkstra算法的復(fù)雜度是O(n^2)，一旦結(jié)點很多并且需要實時計算的話，Dijkstra就無法滿足要求了。而A*來處理這類有需要實時要求的問題則顯得游刃有余。

       在路徑最優(yōu)問題中，用來作為啟發(fā)函數(shù)關(guān)鍵部分的h(n)其實很容易選，那便是當前結(jié)點至最終結(jié)點的距離，這個距離既可以是曼哈頓距離(|x1-x2|+|y1-y2|)，亦可以是Euclid（歐幾里得或者歐式距離） 距離(直線距離)。都可以在較快的速度下達到問題的最優(yōu)解。 

偽代碼

主要搜索過程偽代碼如下：
　　創(chuàng)建兩個表，OPEN表保存所有已生成而未考察的節(jié)點，CLOSED表中記錄已訪問過的節(jié)點�！�
　　算起點的估價值;
　　將起點放入OPEN表;
　　while(OPEN!=NULL)　
　　{　
　　從OPEN表中取估價值f最小的節(jié)點n;　
　　if(n節(jié)點==目標節(jié)點){　
　　break;　
　　}　
　　for(當前節(jié)點n 的每個子節(jié)點X)　
　　{
　　算X的估價值;　
　　if(X in OPEN)
　　{　
　　if( X的估價值小于OPEN表的估價值 ){　
　　把n設(shè)置為X的父親;　
　　更新OPEN表中的估價值; //取最小路徑的估價值　
　　}
　　}
　　if(X inCLOSE) {　
　　if( X的估價值小于CLOSE表的估價值 ){　
　　把n設(shè)置為X的父親;　
　　更新CLOSE表中的估價值;　
　　把X節(jié)點放入OPEN //取最小路徑的估價值　
　　}　
　　}
　　if(X not inboth){　
　　把n設(shè)置為X的父親;
　　求X的估價值;　
　　并將X插入OPEN表中; //還沒有排序　
　　}
　　}//end for
　　將n節(jié)點插入CLOSE表中;　
　　按照估價值將OPEN表中的節(jié)點排序; //實際上是比較OPEN表內(nèi)節(jié)點f的大小，從最小路徑的節(jié)點向下進行。
　　}//end while(OPEN!=NULL)
　　保存路徑，即 從終點開始，每個節(jié)點沿著父節(jié)點移動直至起點，這就是你的路徑

posted on

  本文關(guān)鍵詞：搜索理論，由筆耕文化傳播整理發(fā)布。