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

搜索理論

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

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

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

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

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

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

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

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回溯往往會(huì)超時(shí)，一般與剪枝聯(lián)系在一起

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

（1）可行性剪枝， 剪去不能到達(dá)終點(diǎn)的路徑

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

 迭代加深搜索

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

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

使用是要注意：

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

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

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

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

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

A*算法

A*類似貪心的BFS 

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

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

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

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

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

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

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

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

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

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

A*必須滿足兩點(diǎn)：

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

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

2) 問題域是有限的。

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

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

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

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

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

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


當(dāng)然，估值函數(shù)的設(shè)計(jì)也就就僅僅是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)針對(duì)不同的具體問題亦會(huì)有不同的效果。

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

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

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

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

偽代碼

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

posted on

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