搜索算法基礎(chǔ)與提高教程

1、搜索算法搜索算法是利用計算機的高性能來有冃的的窮舉一個問題的部分 或所有的可能情況，從而求出問題的解的一種方法。搜索過程實際上是 根據(jù)初始條件和擴展規(guī)則構(gòu)造一棵解答樹并尋找符合目標狀態(tài)的節(jié)點 的過程。所有的搜索算法從其最終的算法實現(xiàn)上來看，都可以劃分成兩 個部分控制結(jié)構(gòu)和產(chǎn)生系統(tǒng)，而所有的算法的優(yōu)化和改進主要都是 通過修改其控制結(jié)構(gòu)來完成的?，F(xiàn)在主要對其控制結(jié)構(gòu)進行討論，因此 對其產(chǎn)生系統(tǒng)作如下約定：functionexpendnode(situation:tsituat ion:expendwayno:integer):tsituati on;表示對給出的節(jié)點狀態(tài)sitution采用第exp

2、endwayno種擴展規(guī)則 進行擴展，并且返回擴展后的狀態(tài)。(本文所采用的算法描述語言為類pascalo)第一部分基本搜索算法一、回溯算法冋溯算法是所有搜索算法中最為基本的一種算法，其采用了一種 “走不通就掉頭”思想作為其控制結(jié)構(gòu)，其相當于采用了先根遍歷的方 法來構(gòu)造解答樹，可用于找解或所有解以及最優(yōu)解。具體的算法描述如 下：非遞歸算法<type>node （節(jié)點類型）=recordsitutation:tsituation （當前節(jié)點狀態(tài)）;way-no: integer （已使用過的擴展規(guī)則的數(shù)目）;end<var>list （回溯表）:array1. max（最大

3、深度）of node;pos （當前擴展節(jié)點編號）:integer;<init>list-0;pos<-l;list1. situation-初始狀態(tài)；<main program>while （pos>0（有路可走）and （未達到目標）dobeginif pos>二max then （數(shù)據(jù)溢出，跳出主程序）;listpos way-n0:=listpos. way-no+1;if （list pos. way-no<=totalexpendmethod） then （如果還有沒 用過的擴展規(guī)則）beginif （可以使用當前擴展規(guī)則）thenb

4、egin(用第way條規(guī)則擴展當前節(jié)點)listpos+1 situation:二expendnode(listpos situation, list pos. way-no);listpos+1. way-no:二0;pos:=pos+l;end-if;end-ifelse beginpos:二post ;end-elseend-wh訂e;遞歸算法procedure backtrack(situation:tsituation;deepth:integer); var i :integer;beginif deepth>max then (空間達到極限，跳出本過程);if situat

5、ion二target then (找到目標);for i:=1 to totalexpendmethod dobeginbacktrack(expendnode(situation, i), deepth+1);endfor;end;范例：個m*m的棋盤上某一點上有一個馬，要求尋找一條從這一 點出發(fā)不重復(fù)的跳完棋盤上所有的點的路線。評價：冋溯算法對空間的消耗較少，當其與分枝定界法一起使用時, 對于所求解在解答樹中層次較深的問題有較好的效果。但應(yīng)避免在后繼 節(jié)點可能與前繼節(jié)點相同的問題中使用，以免產(chǎn)生循環(huán)。二、深度搜索與廣度搜索深度搜索與廣度搜索的控制結(jié)構(gòu)和產(chǎn)生系統(tǒng)很相似，唯一的區(qū)別在 丁對擴展

6、節(jié)點選取上。由丁其保留了所有的前繼節(jié)點，所以在產(chǎn)生后繼 節(jié)點時可以去掉一部分重復(fù)的節(jié)點，從而提高了搜索效率。這兩種算法 每次都擴展一個節(jié)點的所有子節(jié)點，而不同的是，深度搜索下一次擴展 的是本次擴展出來的子節(jié)點中的一個，而廣度搜索擴展的則是本次擴展 的節(jié)點的兄弟節(jié)點。在具體實現(xiàn)上為了提高效率，所以采用了不同的數(shù) 據(jù)結(jié)構(gòu).廣度搜索<type>node （節(jié)點類型）=recordsitutation:tsituation （當前節(jié)點狀態(tài)）;level: integer （當前節(jié)點深度）；last : integer （父節(jié)點）；end<var>list （節(jié)點表）:array

7、 1. . max（最多節(jié)點數(shù)）of node（節(jié)點類型）；open（總節(jié)點數(shù)）:integer;close（待擴展節(jié)點編號）:integer;new-s:tsituation;（新節(jié)點）<init>list<-0;open<-l;close<-0;list 1. situation- 初始狀態(tài)；list1 level:=1;list1. last:二0;<main program>while （close<open（還有未擴展節(jié)點）and（open<max （空間未用完）and（未找到目標節(jié)點）dobeginclose:=close+l;

8、for i:=1 to totalexpendmethod do （擴展一層子節(jié)點）beginnew-s:=expendnode （listclosesituation,i）;if not （new-s in list） then（擴展出的節(jié)點從未出現(xiàn)過）beginopen:二open+1;listopen situation:二new-s;list open level:=listclose level + 1;list open last:=close;end-ifend-for;end-while;深度搜索<var>open:array1. . max of node;（待擴

9、展節(jié)點表）close:array1. . max of node;（已擴展節(jié)點表） openl, closel: integer;（表的長度）new-s: ts i tuat ion;（新狀態(tài)）<init>0pen<-0; close<-0;openl<-l;closel<-0;openl situation- 初始狀態(tài)；open1 level<-1;openl. last<-0;<main program>while （openl>0） and （closel<max） and （openl<max） dobegi

10、nclosel:=closel+l;closeclosel:=0penopenl;openl:=openl-l;for i :=1 to totalexpendmethod do (擴展一層子節(jié)點)beginnews:=expendnode(closeclosel. situation, i);if not (new-s in list) then(擴展出的節(jié)點從未出現(xiàn)過)beginopenl:=openl+l;openopenl si tuat ion:=news:openopenl level:二closeclosel level+1;openopenl last:=closel;end-

11、ifend-for;end;范例：迷宮問題，求解最短路徑和可通路徑。評價：廣度搜索是求解最優(yōu)解的一種較好的方法，在后面將會 對其進行進一步的優(yōu)化。而深度搜索多用于只要求解，并且解答樹 中的重復(fù)節(jié)點較多并且重復(fù)較難判斷時使用，但往往可以用分支定 界或回溯算法代替。第二部分搜索算法的優(yōu)化一、雙向廣度搜索廣度搜索雖然可以得到最優(yōu)解，但是其空間消耗增長太快。但 如果從正反兩個方向進行廣度搜索，理想情況下可以減少二分之一的搜索量，從而提高搜索速度。范例：有n個黑口棋子排成一派，中間任意兩個位置有兩個連 續(xù)的空格。每次空格可以與序列屮的某兩個棋子交換位置，且兩子 的次序不變。要求出入長度為length的一

12、個初始狀態(tài)和一個目標 狀態(tài)，求出最少的轉(zhuǎn)化步數(shù)。問題分析：該題要求求出最少的轉(zhuǎn)化步數(shù)，但如果直接使用廣 度搜索，很容易產(chǎn)生數(shù)據(jù)溢出。但如果從初始狀態(tài)和口標狀態(tài)兩個 方向同時進行擴展，如果兩棵解答樹在某個節(jié)點第一次發(fā)牛重合， 則該節(jié)點所連接的兩條路徑所拼成的路徑就是最優(yōu)解。對廣度搜索算法 的改進：1 o添加一張節(jié)點表，作為反向擴展表。2。在while循環(huán)體中在正向擴展代碼后加入反向擴展代碼， 其擴展過程不能與正向過程共享一個for循環(huán)。3 o在正向擴展出一個節(jié)點后，需在反向表中查找是否有重合節(jié)點。反向擴展吋與之相同。對雙向廣度搜索算法的改進：略微修改一下控制結(jié)構(gòu)，每次wh訂e循環(huán)時只擴展正反兩個

13、方 向屮節(jié)點數(shù)目較少的一個，可以使兩邊的發(fā)展速度保持一定的平 衡，從而減少總擴展節(jié)點的個數(shù)，加快搜索速度。二、分支定界分支定界實際上是a*算法的一種雛形，其對于每個擴展出來的 節(jié)點給出一個預(yù)期值，如果這個預(yù)期值不如當前已經(jīng)搜索出來的結(jié) 果好的話，則將這個節(jié)點（包括其了節(jié)點）從解答樹中刪去，從而達 到加快搜索速度的目的。范例：在一個商店中購物，設(shè)第i種商品的價格為ci。但商店 提供一種折扣，即給出一組商品的組合，如果一次性購買了這一組 商品，則可以亨受較優(yōu)惠的價格?，F(xiàn)在給出一張購買清單和商店所 提供的折扣清單，要求利用這些折扣，使所付款最少。問題分析：顯然，折扣使用的順序與最終結(jié)果無關(guān)，所以可以

14、 先將所右的折扣按折扣率從大到小排序，然后采用回溯法的控制結(jié) 構(gòu)，對每個折扣從其最人可能使用次數(shù)向零遞減搜索，設(shè)a為以打 完折扣后優(yōu)惠的價格，c為當前未打折扣的商品零售價之和，則其預(yù)期值 為a+a*c,其中a為下一個折扣的折扣 率。如當前已是最后一個折扣,則a=l。對回溯算法的改進：1 o添加一個全局變量bestanswer,記錄當前最優(yōu)解。2 o在每次生成一個節(jié)點時，計算其預(yù)期值，并與bestanswer 比較。如果不好，則調(diào)用回溯過程。三、a*算法a*算法中更一般的引入了一個估價函數(shù)f,其肚義為f=g+ho其 中g(shù)為到達當前節(jié)點的耗費，而h表示對從當前節(jié)點到達目標節(jié)點 的耗費的估計。其必須

15、滿足兩個條件：1 o h必須小于等于實際的從當前節(jié)點到達目標節(jié)點的最小耗 費h*。2o f必須保持單調(diào)遞增。a*算法的控制結(jié)構(gòu)與廣度搜索的十分類似，只是每次擴展的都 是當前待擴展節(jié)點小f值最小的個，如果擴展出來的節(jié)點與已擴 展的節(jié)點重復(fù)，則刪去這個節(jié)點。如果與待擴展節(jié)點重復(fù)，如果這 個節(jié)點的估價函數(shù)值較小，則用其代替原待擴展節(jié)點，具體算法描 述如下：范例：一個3*3的棋盤中有1-8八個數(shù)字和一個空格，現(xiàn)給出 一個初始態(tài)和一個目標態(tài)，要求利用這個空格，用最少的步數(shù)，使 其到達冃標態(tài)。問題分析：預(yù)期值定義為h= | x-dx | +1 y-dy | o估價函數(shù)定義為f=g+ho<type&g

16、t;node （節(jié)點類型）=recordsitutation:tsituation （當前節(jié)點狀態(tài)）;g:integer;（到達當前狀態(tài)的耗費）h: integer;（預(yù)計的耗費）f:real;（估價函數(shù)值）last: integer;（父節(jié)點）end<var>list （節(jié)點表）:array 1. . max（最多節(jié)點數(shù)）of node（節(jié)點類 型）；open（總節(jié)點數(shù)）:integer;close（待擴展節(jié)點編號）:integer;new-s:tsituation;（新節(jié)點）<init>list-0;open<-l;close-0;list1 situatio

17、n- 初始狀態(tài)；<main program>while （close<open（還有未擴展節(jié)點）and（open<max（空間未用完）and（未找到目標節(jié)點）dobeginbeginclose:=close+l;for i:=close+l to open do （尋找估價函數(shù)值最小的節(jié)點）beginif listiflistclosef thenbegin交換 list i和 list close;end-if;end-for;end;for i :=1 to totalexpendmethod do （擴展一層子節(jié)點）beginnew-s:二expendnode（l

18、istclose situation, i）if not （new-s in list1.close） then（擴展出的節(jié)點未與已擴展的節(jié)點重復(fù)）beginif not （new-s in listclose+1open） then（擴展出的節(jié)點未與待擴展的節(jié)點重復(fù)）beginopen:=open+l;listopen situation:=news;listopen last:=close;listopen g:=listclose g+cost;listopen h:=geth(listopen situation);listopen f:二listopen h+listopen g;e

19、nd-ifelse beginif list close.g+cost+geth(new-s)<listsame f then(擴展出來的節(jié)點的估價函數(shù)值小于與其相同的節(jié)點)beginlistsame situations news:listsame last:=close;listsame g:=listclose g+cost;listsame h:=geth(listopen situation);listsame f:二listopen h+listopen g;end-if;end-else;end-ifend-for;end-while;對a*算法的改進一分階段a*：當a*算

20、法出現(xiàn)數(shù)據(jù)溢出時，從待擴展節(jié)點中取出若干個估價函數(shù)值較小的節(jié)點，然后放棄其余的待擴展節(jié)點，從而可以使搜索進一步的 進行下去。第三部分搜索與動態(tài)規(guī)劃的結(jié)合例1.有一個棋子，其1、6面2、4面3、5面相對?，F(xiàn)給出一個 m*n的棋盤，棋子起初處于（1,1）點，擺放狀態(tài)給定，現(xiàn)在要求用最少 的步數(shù)從（1,1）點翻滾到（m,n）點，并且1面向上。分析：這道題目用簡單的搜索很容易發(fā)/超時，特別當m、n較大 時。所以可以考慮使用動態(tài)規(guī)劃來解題。對于一個棋子，其總共只有 24種狀態(tài)。在（1,1）點時,其向右翻滾至（2, 1）點，向上翻滾至（1,2）點。 而任意（i, j）點的狀態(tài)是由（it, j）和（i,-1

21、）點狀態(tài)推導(dǎo)出來 的。所以如果規(guī)定棋了只能向上和向右翻滾，則可以用動態(tài)規(guī)劃的方法將到達（m, n）點的所有可能的 狀態(tài)推導(dǎo)出來。顯然，從（1,1）到達（n, m）這些狀態(tài)的路徑時最優(yōu)的。如果這些狀態(tài)中有1 面向上的，則已求出解。如果沒有，則可以從（m, n）點開始廣度搜索，以（m, n）點的狀態(tài)組作為初始狀 態(tài)，每擴展一步時，檢查當前所得的狀態(tài)組是否有狀態(tài)與到達格子的狀態(tài)組中的狀態(tài)相同，如果有， 則由動態(tài)規(guī)劃的最優(yōu)性和廣度搜索的最優(yōu)性可以保證已求出最優(yōu)解。例2.給出一個正整數(shù)n,有基本元素a,要求通過最少次數(shù)的乘法, 求出a"n。分析：思路一：這道題從題面上來看非常象一道動態(tài)規(guī)劃題，

22、 a"n=a"xl*a"x2。在保證a"xl和a"x2的最優(yōu)性之后，a"n的最優(yōu)性應(yīng)該得到保證。但是仔細分析后可以發(fā)現(xiàn)，all與*x2的乘法過程屮可 能有一部分的重復(fù)，所以在計算*n時耍減去其重復(fù)部分。由丁重復(fù)部分的 計算較繁瑣，所以可以將其化為一組展開計算。描述如下：i：=n;（拆分 a"n）split n :=xl;（分解方案）usedn:二true;（在乘法過程中出現(xiàn)的數(shù)字）repeat （不斷分解數(shù)字）usedi-spliti:=true;usedspl:二true;dec （i）;while （i>1） an

23、d （not usedi） do dec （i）;unt訂 i二1;for i :=n downto 1 do （計算總的乘法次數(shù)）if usedi then count:二count+1;result:=count;（返回乘法次數(shù)）思路二：通過對思路一的輸出結(jié)果的分析可以發(fā)現(xiàn)個規(guī)律： a/19 二 *1*18a/18二a"2*a"16a" 16 二 *8*8*8 二 *4*a"4a4=a2*a23 2二8*d對于一個n,先構(gòu)造一個最接近的2"k,然后利用在構(gòu)造過程 中產(chǎn)生的2"1,對n-2k進行二進制分解，可以得出解。對次數(shù)的計 算

24、的描述如下：count:=0;repeatif n mod 2=0 then count:二count+1else count:二count+2;n:=n div 2;until n=l;resuit:二count;反思：觀察下列數(shù)據(jù)：15 a 23 a"27cost:5 cost:6 cost:6a 2=a la 1 a 2=a la 1 a 2=a la 1a,二fl*2 *3二1*2二fl*2a 6=a 3a 3 a 5=a 2a 3 a 6=a 3a 3a 12=a 6*a 6 a 10=a 5*a"5 a 12=a 6*a 6*15二*3*a/12 a 20=al

25、0*al0 a 24=al2*al2a 23=a 3*a 20 a 27=a 3*a 24這些數(shù)據(jù)都沒有采用思路二種的分解方法，而都優(yōu)于思路二中所給出的解。但是經(jīng)過實測，思路一二的所有的解的情況相同，而卻得不出以上數(shù)據(jù)中的解。經(jīng)過對a"2 a"15的數(shù)據(jù)的完全分析，發(fā)現(xiàn)對于一個ab,存在多個分解方法都可以得出最優(yōu)解，而在思路一中只保留了一組分解方式。例如對于*6只保留了 a"2*a"4,從而使*3*3這條路中斷，以至采用思路一 的算法時無法得出正確的耗費值，從而丟失了最優(yōu)解。所以在計算 a"n=a"xl*a"x2的重復(fù)吋，要

26、引入一個搜索過程。例 如:a"15=a"3*a"12,a"12=a"6*a"6,而 a 6=a 3*a 3o 如果采用了 a"6=a"2*a"4, 則必須多用一步。<type>link=node;（使用鏈表結(jié)構(gòu)紀錄所有的可能解）node=recordsplit:integer;next :link;end;<var>solution:array1. . 1000 of link;（對于 a n 的所有可能 解）cost :array1. 1000 of integer;（解的代價）

27、max : integer;（推算的上界） <main program>procedure getsolution;var i, j :integer; min,c:integer;count:integer;temp, tail:link;plan :array1.500 of integer; nused:array1. 1000 of boolean;procedure getcost （from, cost: integer）;（搜索計算最優(yōu)解） var temp:link;a,b :boolean;i :integer;beginif cost>c then exi

28、t;（剪枝）if from=l then （遞歸終結(jié)條件）beginif costc then c:=cost;exit;end;temp:=solutionfrom;while temponil do （搜索主體）begina:=nusedtemp" split:if not a then inc (cost); nusedtemp split:=true; b:=nusedfrom - temp.split;if not b then inc (cost); nusedfrom-temp split:=true;i:=from-l;while (i>l) and (not

29、nusedi) do dec(i): getcost (i, cost);if not a then dec (cost);if not b then dec (cost); nusedfrom-temp split:二b; nusedtemp" split:=a;temp:二temp" next;end;end;beginfor i :=2 to max do (動態(tài)規(guī)劃計算所有解) begin count:=0;min:=32767;for j:=l to i div 2 do (將 i 分解為 i-j 和 j) beginc:二32767;fillchar(nused

30、, sizeof(nused), 0); nusedj:=true;nusedi-j:二true;if j=i-j then getcost (ij, 1)else getcost(ij, 2);if c<min thenbegincount:=1;min:=c;plancount:=j;endelse if c=min thenbegininc (count);plancount:=j;end;end;new(solutioni);(構(gòu)造解答鏈表) solutioni ； split:=planl;solutioni ： next:二nil;cost i:二min;tail:=solu

31、tioni;for j:=2 to count dobeginnew(temp);temp . split:=planj; temp" next:二nil;tail .next:=temp:tail:二temp;end;end;end;深度優(yōu)先搜索算法教程（1）例1有a、b、c、d、e五本書，要分給張、王、劉、趙、錢五位同 學(xué)，每人只能選一本。事先讓每個人將自己喜愛的書填寫在下表中。希 望你設(shè)計一個程序，打印分書的所有可能方案，當然是讓每個人都滿意。分析這個問題屮喜愛的書是隨機的，沒有什么規(guī)律，所以用窮舉法比 較合適。為編程方便，用1、2、3、4、5分別表示這五本書。這五本書的一種全

32、 排列就是五本書的一種分法。例如54321表示第5本書（即e）分給張, 第4本書（即d分給王，）第1本書（即a分給錢）?！跋矏蹠怼?可以用二維數(shù)組來表示，1表示喜愛，0表示不喜愛。算法設(shè)計:1、產(chǎn)生5個數(shù)字的一個全排列；2、檢查是否符合“喜愛書表”的條件，如果符合就打印出來。3、檢查是否所有排列都產(chǎn)生了，如果沒有產(chǎn)生完，則返回1。4、結(jié)束。算法改進:因為張只喜歡第3、4本書，這就是說，1* 一類的分 法都不符合條件。所以改進后的算法應(yīng)當是：在產(chǎn)生排列時，每增加一 個數(shù)，就檢查該數(shù)是否符合條件，不符合，就立即換一個，符合條件后, 再產(chǎn)生下一個數(shù)。因為從第i本書到第i+1本書的尋找過程是相同的，

33、 所以可以用遞歸算法。算法如下：procedure try（i）;beginfor j:=l to 5 dobeginif第i個同學(xué)分給第j本書符合條件thenbegin記錄第i個數(shù)；if i=5 then 打印一個解 else try（i+l）;刪去第i個數(shù)字endendend;具體如下：遞歸算法program zhaoshu;uses crt;constlike:array1.5,1.5 of 0.1=(0,0,1,1,0),(1,1,0,0,1 ),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1);name:array1.5 of string5=(,zhangvw

34、ang7hu,zhaovqian,);var book:array1.5 of 0.5;flag:set of 1.5;c:integer;procedure print;var【integer;begininc(c);writeln(,answer,c,7);for i:=l to 5 dowriteln(name i: 10, *: chr(64+book i);end;procedure try(i:integer);varj: integer;beginfor j:=l to 5 doif not(j in flag) and (likeij>0) then beginflag:

35、=flag+j; booki:=j;if i=5 then print else try(i+l); flag:=flag-j;end;end;=main=beginclrscr;flag:=;c:=0;try(l);readln;end.非遞歸算法:program path;dep:=0;dep為棧指針，也代表層次repeatdep:=dep+l; r:=0; p:=false;repeat r:=r+l;if子節(jié)點mr符合條件then 產(chǎn)生新節(jié)點并存于dep指向的棧頂；if子節(jié)點是日標then輸出并退出（或退棧）else p:=true;else if r>=maxr then 回溯

36、 else p:=flase;endif;until p:=true;until dep=0;其中回溯過程如下：procedure 回溯；dep:=dep 1;if dep=0 then p:=true else 取冋棧頂元素（出棧）;具體如下：非遞歸算法program zhaoshu2;uses crt;constlike:array1.5,l.,5 of 0.1=(0,0,1,1,0),( 1,1,0,0,1 ),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1);name:array1.5 of string5=('zhangtwangtliu',&#

37、39;zhaotqian)；var book:array0.5 of 0.5;flag:set of 1.5;c,dep,r:longint;p:boolean;f:text;procedure print;var i:integer;begininc(c);writeln(f/answerc,':');for i:=l to 5 dowriteln(f,namei: 10/:chr(64+booki);end;procedure back;begindep:=dep-l;if dep=0 then p:=trueelse begin r:=bookdep; flag:=fla

38、g-r; end;end;=main=beginassign(f/d:wuren.pasf);rewrite(f);clrscr;flag:=; c:=0;dep:=o;repeatdep:=dep+l; r:=0; p:=false;repeatr:=r+l;if not(r in flag) and (likedep,r>0)and (r<=5)thenbeginflag:=flag+r; bookdep:=r;if dep=5 then begin print;inc(dep);back; endelse p:=true;endelseif r>=5 then back

39、 else p:=falseuntil p=true;until dep=o;close(f);end.上述程序運行產(chǎn)生結(jié)點的過程如下圖所示:結(jié)點旁的編號是結(jié)點產(chǎn)生的先后順序。從產(chǎn)生的順序可以看出，深度越 大的結(jié)點越先進行擴展，即先產(chǎn)生它的子結(jié)點。例如，有了結(jié)點(3) 和(31)后，并不是繼續(xù)產(chǎn)生(3)的子結(jié)點，而是先產(chǎn)生(31)的子 結(jié)點(312)o這是由于(31)的深度是2, (3)的深度是1, (31)的深度大，所以先擴展。同前邊圖的深度優(yōu)先遍歷聯(lián)系起來這種在搜索過程中，深度大的節(jié)點先進行擴展的算法，稱之為深度 優(yōu)先搜索法。簡稱 dfs 法。(depth_first_search)。深度

40、優(yōu)先搜索算法教程(刀深度優(yōu)先搜索的特點:(1) 對已產(chǎn)生的節(jié)點按深度排序，深度人的先得到擴展，即先產(chǎn)生它的子 節(jié)點。深度大的節(jié)點是后產(chǎn)生的，但先得到擴展，即“后產(chǎn)生，先擴展”， 因此，采用堆棧作為該算法的數(shù)據(jù)結(jié)構(gòu)。深度優(yōu)先搜索的基本思想:1、把初始狀態(tài)賦到slate中，即初狀態(tài)入棧，并初始化指針1>object,1>top o(注釋：state(x)表示節(jié)點x的狀態(tài)，state表示初始狀態(tài)，object表示 作擴展的節(jié)點。top表示由節(jié)點object擴展的子節(jié)點。)2、分別用waymax種途徑擴展object的子節(jié)點。從途徑1開始擴展新節(jié)點1一> way num o(注釋：w

41、aymax表示所有可能擴展子節(jié)點的途徑的總數(shù)目，waynum 表示所選途徑編號)(2) 判斷waynum途徑可行嗎？(即可否擴展新節(jié)點)若不行，轉(zhuǎn)2(5) o(3) 對新節(jié)點設(shè)父指針，新狀態(tài)入棧。top+1 >top,object一>father(top), state(object)經(jīng)途徑 waynum 改變后的新狀態(tài) 一>state(top)中 o(注釋：father(x)節(jié)點x的父節(jié)點的標號。)(4) top是目標節(jié)點嗎？是，則調(diào)用打印結(jié)果子程序print打印結(jié)果路 徑。若只要求一個方案則結(jié)束，否則，讓節(jié)點top出棧再繼續(xù)執(zhí)行下一o(5) 選擇下一條路徑，即waynum

42、+1一>waynum,若 waynum<=waymax,貝轉(zhuǎn) 2一(2)。3、選擇用來擴展的新節(jié)點。(1) 若 objecktop,(即 object 有子節(jié)點)則轉(zhuǎn) 3(3)。(2) top出棧，top-1一top,若top=0 (?？談t結(jié)束)，若top已擴展, 再轉(zhuǎn)3(2)o(3) top一object,若object已規(guī)定深度，則轉(zhuǎn)3(2)。否則轉(zhuǎn)2。 深度優(yōu)先搜索pascal語言程序：program dfs(input,output);const n=擴展節(jié)點估計數(shù)；waymax=擴展節(jié)點途徑數(shù); var state, father： arrayl.n of integer

43、;top, object, waynum： integer;procedure print(v： integer);beginwhile v>0 dobegin write(statev, *<=');v： =fathervend;end;beginstatel：二初狀態(tài);object： =1 ； top:=l; fatherl:=0;while top>0 dobegin（第二步）for waynum:=l to waymax dobeginif way(maxnum) 可彳丁 thenbegintop:=top+l; fathertop :=object;stat

44、etop:=新狀態(tài)；if top是冃標節(jié)點thenbeginprint(top); top:=top-l;end;end;end;if top>object then object:=top(第三步)else repeat top:=top-l; object:=top until topofathertop+1 ; end;end.深度優(yōu)先搜索算法教程（3）深度優(yōu)先搜索的基本算法如下:一、遞歸算法 遞歸過程為：procedure dfs_try (i);for r:=l to maxr doif子結(jié)點mr符號條件then產(chǎn)生的子結(jié)點mr壓入棧；輸出if子結(jié)點mi是日標結(jié)點thenels

45、e dfstry (1+1)；棧頂元素出棧(刪去mr);endif；enddo；主程序為:program dfs；初始狀態(tài)入棧；dfstry (1)；二、非遞歸算法:program dfs (dep)；dep： =0；repeatdep：二dep+1；j： =0； p：二false；repeatj： =j+1；if mr符合條件then產(chǎn)生子結(jié)點mr并將英記錄;if子結(jié)點是目標then輸出并出棧elsep：二true；elseif j>=maxj then 回溯 else p： =false；endif；until p=true；until dep=o；其中回溯過程如下：procedur

46、e backtracking；dep： =dep-1 ；if dep>0 then取回棧頂元素else p： =true；不同問題的深度優(yōu)先搜索基本算法是一樣的，但在具體處理方法上，編 程的技巧上，不盡相同，甚至?xí)泻艽蟛顒e。比如例1的解法還可以這樣來設(shè)計：從表中看出，趙同學(xué)只喜愛d 本書，無其他選擇余地。因此可以在搜索前就確定下來。為了編程方便, 把趙錢二人位置互換，這樣程序只需對張王劉錢四人進行搜索。另外，發(fā)現(xiàn)表示“喜愛書表”的數(shù)組有多個0,為減少不必要的試探， 我們改用鏈表來表示。例如第3位同學(xué)的鏈表是：like (3, 0) =2, 表示他喜愛的第一本書編號是3,最后like (

47、3, 3) =0,表示3是最后一本喜愛的書。深度優(yōu)先搜索算法教程（切深度優(yōu)先搜索算法小結(jié)1. 可以用深度優(yōu)先搜索法處理的問題是各種各樣的。有的搜索深度是 已知和固定的，有的是未知的，有的搜索深度是有限制的，但達到目標 的深度不定，但我們也看到，無論問題的內(nèi)容、性質(zhì)、求解要求如何不 同，但它們的程序結(jié)構(gòu)都是相同的，即都是第四節(jié)中描述的算法結(jié)構(gòu)，不相同的僅僅是存儲結(jié)點的數(shù)據(jù)庫結(jié)構(gòu)、產(chǎn)生規(guī)則和輸出要求。2. 深度優(yōu)先搜索法有遞歸和非遞歸兩種設(shè)汁方法.一般地，當搜索深 度較小、問題遞歸形式較明顯時，用遞歸方法設(shè)計較好，它可以使程序 結(jié)構(gòu)更簡捷易懂。但當搜索深度較大，由于系統(tǒng)堆棧容量的限制，遞歸 易產(chǎn)生

48、溢出，用非遞歸設(shè)計方法較合適。3. 探度優(yōu)先搜索法有廣義和狹義兩種理解。廣義的理解是只要最新產(chǎn) 個的結(jié)點（即深度最大的結(jié)點）先進行擴展的搜索法，就稱為深度優(yōu)先搜 索。在這種理解情況下，深度優(yōu)先搜索算法有全部保留和不全部保留產(chǎn) 生的結(jié)點兩種情況，而狹義的理解是，僅僅指保留全部產(chǎn)生的結(jié)點的算 法。本書取前一種廣義的理解。不保留全部結(jié)點的算法，屬于一般的冋 溯算法范疇。保留全部結(jié)點的算法，實際上是在數(shù)據(jù)庫中產(chǎn)生一結(jié)點之 間的搜索樹，因此也屬于圖搜索算法的范疇。4. 不全部保留結(jié)點的深度優(yōu)先搜索法，由于把擴展完的結(jié)點從數(shù)據(jù)庫 中彈出刪去，這樣，一般在數(shù)據(jù)庫中存儲的結(jié)點數(shù)就是深度值，因此它 占用的空間較少。所以，當搜索樹的結(jié)點較多，用其他方法易產(chǎn)生內(nèi)存 溢出時