算法與數(shù)據(jù)結(jié)構(gòu)講義三(搜索算法)

《算法與數(shù)據(jù)結(jié)構(gòu)講義三(搜索算法)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第十三課搜索算法12.0搜索樹12.1搜索算法的基本原理12.2廣度優(yōu)先搜索12.3深度優(yōu)先搜索12.4練習(xí)12.0搜索樹引例：在一個(gè)4*4的棋盤上的左下角有一個(gè)馬，按照國(guó)際象棋的規(guī)則，將這個(gè)馬跳到右*上角。分析：首先建立棋盤的坐標(biāo)，我們以左下角為(1,1)，以右上角、為(4,4)。按照馬的移動(dòng)規(guī)則，假定當(dāng)前馬的位置坐標(biāo)為(x,y)，則移動(dòng)方法有：（1）x’=x+1;y’=y+2（2）x’=x+1;y’=y-2;（3）x’=x+2;y’=y+1;（4）x’=x+2;y’=y-1;（5）x’=x-1;y’=y+2;（6）x’=x-1;y’=y-2;（7）x’=x-2;y’=y+

2、1;（8）x’=x-2;y’=y-1113223122113314424114244112332232343233234123243213244可以建立搜索樹如下：圖中表示：由(1,1)可以跳到(2,3)和(3,2)兩個(gè)點(diǎn)(其它移動(dòng)規(guī)則由于邊界限制無(wú)法到達(dá))；(2,3)又可以跳到(1,1)、(4,4)、(4,2)、(3,1)四個(gè)點(diǎn)，(3,2)可以跳達(dá)(1,1)、(1,3)、(2,4)、(4,4)四個(gè)點(diǎn)，……。搜索樹：按照數(shù)據(jù)元素的產(chǎn)生式規(guī)則建立起來(lái)的數(shù)據(jù)元素邏輯關(guān)系。特點(diǎn)：（1）數(shù)據(jù)之間的邏輯關(guān)系為一對(duì)多。（2）每個(gè)結(jié)點(diǎn)數(shù)據(jù)的下一級(jí)子結(jié)點(diǎn)是由該結(jié)點(diǎn)的產(chǎn)生式規(guī)則生成。（3）目標(biāo)

3、結(jié)點(diǎn)（答案數(shù)據(jù)）一定在搜索樹中能夠出現(xiàn)。（4）對(duì)于數(shù)據(jù)規(guī)模較大的問題，搜索樹的結(jié)點(diǎn)將是海量的。（5）搜索樹可能是無(wú)窮無(wú)盡的（因?yàn)楹芏嘟Y(jié)點(diǎn)回重復(fù)出現(xiàn)）。12.1搜索算法的基本原理：從搜索樹中可以看出，一個(gè)問題從起始狀態(tài)，通過窮舉的方式建立起搜索樹后，目標(biāo)狀態(tài)一定能在搜索樹中出現(xiàn)。因此，只要建立起搜索樹，就可以在其中搜索到目標(biāo)狀態(tài)（數(shù)據(jù)、路徑、位置等）。搜索算法要解決的問題：產(chǎn)生式規(guī)則：由當(dāng)前狀態(tài)按照問題的需求和限制，生成新的狀態(tài)的方法集合。搜索樹的生成和存儲(chǔ)：一般采用一邊生成，一邊搜索；存儲(chǔ)方法有：集合、棧。搜索的方法：按行搜索：即從上到下，逐層搜索雙向按行搜索：一邊從上往下（

4、起始狀態(tài)到中間狀態(tài)），一邊從下往上逐層搜索（從目標(biāo)狀態(tài)到中間狀態(tài)），找到相同的中間狀態(tài)即可?；厮贩ㄋ阉鳎簝?yōu)先向更深層結(jié)點(diǎn)查找，走不通則換一條路，無(wú)法換則退回到上一層。搜索狀態(tài)的減少：在生成搜索樹時(shí)，對(duì)于已搜過的中間狀態(tài)的再次出現(xiàn)，是否需要再次加入到樹中重新搜索。12.2廣度優(yōu)先搜索（bfs）又稱寬度優(yōu)先搜索，是一種從搜索樹的根結(jié)點(diǎn)開始，沿著樹的寬度遍歷樹的結(jié)點(diǎn)。如果所有節(jié)點(diǎn)均被訪問，則算法中止。一般用于求從起始狀態(tài)到目標(biāo)狀態(tài)所需的最少步驟數(shù)。算法過程：1、首先將根結(jié)點(diǎn)放入隊(duì)列中。2、從隊(duì)首取出一個(gè)結(jié)點(diǎn)，按照產(chǎn)生式規(guī)則逐個(gè)生成新的結(jié)點(diǎn)數(shù)據(jù)，對(duì)新數(shù)據(jù)：如果如果是目標(biāo)結(jié)點(diǎn)，則結(jié)束算

5、法并返回結(jié)果。如果不是目標(biāo)結(jié)點(diǎn)，則檢查它是否已在搜索樹中出現(xiàn)過，未出現(xiàn)就將它作為尚未檢查過的子結(jié)點(diǎn)加入到隊(duì)列的隊(duì)尾（特殊情況下，也有已出現(xiàn)過的結(jié)點(diǎn)重新入隊(duì)的）。3、重復(fù)步驟2。4、若隊(duì)列為空，表示整張圖都檢查過了，即目標(biāo)無(wú)法達(dá)到，結(jié)束算法并返回“找不到目標(biāo)”的信息。算法細(xì)化：1、用哈希數(shù)組判斷新生成的結(jié)點(diǎn)數(shù)據(jù)是否已出現(xiàn)過。2、隊(duì)列經(jīng)常要多開一行，記錄新結(jié)點(diǎn)的父親（即該結(jié)點(diǎn)由上一層的哪個(gè)結(jié)點(diǎn)擴(kuò)展而來(lái)），用于最后輸出過程。3、如數(shù)據(jù)規(guī)模過大，需要使用循環(huán)隊(duì)列（后果是無(wú)法記錄父親）。算法框架：functioncreat(i)begincaseiof1:creat:=按照第一產(chǎn)生式規(guī)

6、則生成新狀態(tài)數(shù)據(jù)；2:creat:=按照第二產(chǎn)生式規(guī)則生成新狀態(tài)數(shù)據(jù)；...end;end;////////////////////////////////////////////////////////////////procedurebfs;beginjoin(起始狀態(tài));whilenot(隊(duì)空)dobegin當(dāng)前處理狀態(tài):=deq;fori:=第一產(chǎn)生式規(guī)則to最大產(chǎn)生式規(guī)則dobegin新狀態(tài):=creat(i);if新狀態(tài)=目標(biāo)狀態(tài)thenbeginprint;exit;endelseifnot(haxi[新狀態(tài)])thenbeginjoin(新狀態(tài));haxi[新

7、狀態(tài)]:=true;end;end;end;end;空間復(fù)雜度：線性隊(duì)列：O(最大可能狀態(tài)數(shù))循環(huán)隊(duì)列：O(最大可能狀態(tài)數(shù)/2)時(shí)間復(fù)雜度：最差情形下，BFS必須尋找所有到可能結(jié)點(diǎn)的所有路徑。O(最大可能狀態(tài)數(shù))完全性：廣度優(yōu)先搜索算法具有完全性。只要目標(biāo)存在，則BFS一定會(huì)找到。但是，若目標(biāo)不存在，且問題規(guī)模為無(wú)限大，則BFS將不收斂（不會(huì)結(jié)束）。適用范圍：廣度優(yōu)先搜索是找到第一個(gè)解的算法，即距離根結(jié)點(diǎn)的邊數(shù)最少的解。如果所有邊的權(quán)值都相等（即所有產(chǎn)生新狀態(tài)的代價(jià)相同），則這個(gè)解也是最優(yōu)解。例一：將一