資源描述：
《算法與數(shù)據(jù)結(jié)構講義三(搜索算法).doc》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、第十三課搜索算法12.0搜索樹12.1搜索算法的基本原理12.2廣度優(yōu)先搜索12.3深度優(yōu)先搜索12.4練習12.0搜索樹引例：在一個4*4的棋盤上的左下角有一個馬，按照國際象棋的規(guī)則，將這個馬跳到右*上角。分析：首先建立棋盤的坐標，我們以左下角為(1,1)，以右上角、為(4,4)。按照馬的移動規(guī)則，假定當前馬的位置坐標為(x,y)，則移動方法有：（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
2、;（6）x’=x-1;y’=y-2;（7）x’=x-2;y’=y+1;（8）x’=x-2;y’=y-1113223122113314424114244112332232343233234123243213244可以建立搜索樹如下：圖中表示：由(1,1)可以跳到(2,3)和(3,2)兩個點(其它移動規(guī)則由于邊界限制無法到達)；(2,3)又可以跳到(1,1)、(4,4)、(4,2)、(3,1)四個點，(3,2)可以跳達(1,1)、(1,3)、(2,4)、(4,4)四個點，……。搜索樹：按照數(shù)據(jù)元素的產(chǎn)生式規(guī)則建立起
3、來的數(shù)據(jù)元素邏輯關系。特點：（1）數(shù)據(jù)之間的邏輯關系為一對多。（2）每個結(jié)點數(shù)據(jù)的下一級子結(jié)點是由該結(jié)點的產(chǎn)生式規(guī)則生成。（3）目標結(jié)點（答案數(shù)據(jù)）一定在搜索樹中能夠出現(xiàn)。（4）對于數(shù)據(jù)規(guī)模較大的問題，搜索樹的結(jié)點將是海量的。（5）搜索樹可能是無窮無盡的（因為很多結(jié)點回重復出現(xiàn)）。12.1搜索算法的基本原理：從搜索樹中可以看出，一個問題從起始狀態(tài)，通過窮舉的方式建立起搜索樹后，目標狀態(tài)一定能在搜索樹中出現(xiàn)。因此，只要建立起搜索樹，就可以在其中搜索到目標狀態(tài)（數(shù)據(jù)、路徑、位置等）。搜索算法要解決的問題：產(chǎn)生式規(guī)則
4、：由當前狀態(tài)按照問題的需求和限制，生成新的狀態(tài)的方法集合。搜索樹的生成和存儲：一般采用一邊生成，一邊搜索；存儲方法有：集合、棧。搜索的方法：按行搜索：即從上到下，逐層搜索雙向按行搜索：一邊從上往下（起始狀態(tài)到中間狀態(tài)），一邊從下往上逐層搜索（從目標狀態(tài)到中間狀態(tài)），找到相同的中間狀態(tài)即可。回朔法搜索：優(yōu)先向更深層結(jié)點查找，走不通則換一條路，無法換則退回到上一層。搜索狀態(tài)的減少：在生成搜索樹時，對于已搜過的中間狀態(tài)的再次出現(xiàn)，是否需要再次加入到樹中重新搜索。12.2廣度優(yōu)先搜索（bfs）又稱寬度優(yōu)先搜索，是一種從
5、搜索樹的根結(jié)點開始，沿著樹的寬度遍歷樹的結(jié)點。如果所有節(jié)點均被訪問，則算法中止。一般用于求從起始狀態(tài)到目標狀態(tài)所需的最少步驟數(shù)。算法過程：1、首先將根結(jié)點放入隊列中。2、從隊首取出一個結(jié)點，按照產(chǎn)生式規(guī)則逐個生成新的結(jié)點數(shù)據(jù)，對新數(shù)據(jù)：如果如果是目標結(jié)點，則結(jié)束算法并返回結(jié)果。如果不是目標結(jié)點，則檢查它是否已在搜索樹中出現(xiàn)過，未出現(xiàn)就將它作為尚未檢查過的子結(jié)點加入到隊列的隊尾（特殊情況下，也有已出現(xiàn)過的結(jié)點重新入隊的）。3、重復步驟2。4、若隊列為空，表示整張圖都檢查過了，即目標無法達到，結(jié)束算法并返回“找不到
6、目標”的信息。算法細化：1、用哈希數(shù)組判斷新生成的結(jié)點數(shù)據(jù)是否已出現(xiàn)過。2、隊列經(jīng)常要多開一行，記錄新結(jié)點的父親（即該結(jié)點由上一層的哪個結(jié)點擴展而來），用于最后輸出過程。3、如數(shù)據(jù)規(guī)模過大，需要使用循環(huán)隊列（后果是無法記錄父親）。算法框架：functioncreat(i)begincaseiof1:creat:=按照第一產(chǎn)生式規(guī)則生成新狀態(tài)數(shù)據(jù)；2:creat:=按照第二產(chǎn)生式規(guī)則生成新狀態(tài)數(shù)據(jù)；...end;end;///////////////////////////////////////////////
7、/////////////////procedurebfs;beginjoin(起始狀態(tài));whilenot(隊空)dobegin當前處理狀態(tài):=deq;fori:=第一產(chǎn)生式規(guī)則to最大產(chǎn)生式規(guī)則dobegin新狀態(tài):=creat(i);if新狀態(tài)=目標狀態(tài)thenbeginprint;exit;endelseifnot(haxi[新狀態(tài)])thenbeginjoin(新狀態(tài));haxi[新狀態(tài)]:=true;end;end;end;end;空間復雜度：線性隊列：O(最大可能狀態(tài)數(shù))循環(huán)隊列：O(最大可能狀態(tài)
8、數(shù)/2)時間復雜度：最差情形下，BFS必須尋找所有到可能結(jié)點的所有路徑。O(最大可能狀態(tài)數(shù))完全性：廣度優(yōu)先搜索算法具有完全性。只要目標存在，則BFS一定會找到。但是，若目標不存在，且問題規(guī)模為無限大，則BFS將不收斂（不會結(jié)束）。適用范圍：廣度優(yōu)先搜索是找到第一個解的算法，即距離根結(jié)點的邊數(shù)最少的解。如果所有邊的權值都相等（即所有產(chǎn)生新狀態(tài)的代價相同），則這個解也是最優(yōu)解。例一：將一
