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

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

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

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

4、egin(用第way條規(guī)則擴(kuò)展當(dāng)前節(jié)點(diǎn))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 (空間達(dá)到極限，跳出本過(guò)程);if situat

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

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

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

8、for i:=1 to totalexpendmethod do （擴(kuò)展一層子節(jié)點(diǎn)）beginnew-s:=expendnode （listclosesituation,i）;if not （new-s in list） then（擴(kuò)展出的節(jié)點(diǎn)從未出現(xiàn)過(guò)）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;（待擴(kuò)

9、展節(jié)點(diǎn)表）close:array1. . max of node;（已擴(kuò)展節(jié)點(diǎn)表） openl, closel: integer;（表的長(zhǎng)度）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 (擴(kuò)展一層子節(jié)點(diǎn))beginnews:=expendnode(closeclosel. situation, i);if not (new-s in list) then(擴(kuò)展出的節(jié)點(diǎn)從未出現(xiàn)過(guò))beginopenl:=openl+l;openopenl si tuat ion:=news:openopenl level:二closeclosel level+1;openopenl last:=closel;end-

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

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

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

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

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

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

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

18、istclose situation, i）if not （new-s in list1.close） then（擴(kuò)展出的節(jié)點(diǎn)未與已擴(kuò)展的節(jié)點(diǎn)重復(fù)）beginif not （new-s in listclose+1open） then（擴(kuò)展出的節(jié)點(diǎn)未與待擴(kuò)展的節(jié)點(diǎn)重復(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(擴(kuò)展出來(lái)的節(jié)點(diǎn)的估價(jià)函數(shù)值小于與其相同的節(jié)點(diǎn))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;對(duì)a*算法的改進(jìn)一分階段a*：當(dāng)a*算

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

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

22、 a"n=a"xl*a"x2。在保證a"xl和a"x2的最優(yōu)性之后，a"n的最優(yōu)性應(yīng)該得到保證。但是仔細(xì)分析后可以發(fā)現(xiàn)，all與*x2的乘法過(guò)程屮可 能有一部分的重復(fù)，所以在計(jì)算*n時(shí)耍減去其重復(fù)部分。由丁重復(fù)部分的 計(jì)算較繁瑣，所以可以將其化為一組展開計(jì)算。描述如下：i：=n;（拆分 a"n）split n :=xl;（分解方案）usedn:二true;（在乘法過(guò)程中出現(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 （計(jì)算總的乘法次數(shù)）if usedi then count:二count+1;result:=count;（返回乘法次數(shù)）思路二：通過(guò)對(duì)思路一的輸出結(jié)果的分析可以發(fā)現(xiàn)個(gè)規(guī)律： a/19 二 *1*18a/18二a"2*a"16a" 16 二 *8*8*8 二 *4*a"4a4=a2*a23 2二8*d對(duì)于一個(gè)n,先構(gòu)造一個(gè)最接近的2"k,然后利用在構(gòu)造過(guò)程 中產(chǎn)生的2"1,對(duì)n-2k進(jìn)行二進(jìn)制分解，可以得出解。對(duì)次數(shù)的計(jì) 算

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ù)都沒(méi)有采用思路二種的分解方法，而都優(yōu)于思路二中所給出的解。但是經(jīng)過(guò)實(shí)測(cè)，思路一二的所有的解的情況相同，而卻得不出以上數(shù)據(jù)中的解。經(jīng)過(guò)對(duì)a"2 a"15的數(shù)據(jù)的完全分析，發(fā)現(xiàn)對(duì)于一個(gè)ab,存在多個(gè)分解方法都可以得出最優(yōu)解，而在思路一中只保留了一組分解方式。例如對(duì)于*6只保留了 a"2*a"4,從而使*3*3這條路中斷，以至采用思路一 的算法時(shí)無(wú)法得出正確的耗費(fèi)值，從而丟失了最優(yōu)解。所以在計(jì)算 a"n=a"xl*a"x2的重復(fù)吋，要

26、引入一個(gè)搜索過(guò)程。例 如: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)紀(jì)錄所有的可能解）node=recordsplit:integer;next :link;end;<var>solution:array1. . 1000 of link;（對(duì)于 a n 的所有可能 解）cost :array1. 1000 of integer;（解的代價(jià)）

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）;（搜索計(jì)算最優(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 (動(dòng)態(tài)規(guī)劃計(jì)算所有解) 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é)，每人只能選一本。事先讓每個(gè)人將自己喜愛的書填寫在下表中。希 望你設(shè)計(jì)一個(gè)程序，打印分書的所有可能方案，當(dāng)然是讓每個(gè)人都滿意。分析這個(gè)問(wèn)題屮喜愛的書是隨機(jī)的，沒(méi)有什么規(guī)律，所以用窮舉法比 較合適。為編程方便，用1、2、3、4、5分別表示這五本書。這五本書的一種全

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

33、 所以可以用遞歸算法。算法如下：procedure try（i）;beginfor j:=l to 5 dobeginif第i個(gè)同學(xué)分給第j本書符合條件thenbegin記錄第i個(gè)數(shù)；if i=5 then 打印一個(gè)解 else try（i+l）;刪去第i個(gè)數(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é)點(diǎn)mr符合條件then 產(chǎn)生新節(jié)點(diǎn)并存于dep指向的棧頂；if子節(jié)點(diǎn)是日標(biāo)then輸出并退出（或退棧）else p:=true;else if r>=maxr then 回溯

36、 else p:=flase;endif;until p:=true;until dep=0;其中回溯過(guò)程如下：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.上述程序運(yùn)行產(chǎn)生結(jié)點(diǎn)的過(guò)程如下圖所示:結(jié)點(diǎn)旁的編號(hào)是結(jié)點(diǎn)產(chǎn)生的先后順序。從產(chǎn)生的順序可以看出，深度越 大的結(jié)點(diǎn)越先進(jìn)行擴(kuò)展，即先產(chǎn)生它的子結(jié)點(diǎn)。例如，有了結(jié)點(diǎn)(3) 和(31)后，并不是繼續(xù)產(chǎn)生(3)的子結(jié)點(diǎn)，而是先產(chǎn)生(31)的子 結(jié)點(diǎn)(312)o這是由于(31)的深度是2, (3)的深度是1, (31)的深度大，所以先擴(kuò)展。同前邊圖的深度優(yōu)先遍歷聯(lián)系起來(lái)這種在搜索過(guò)程中，深度大的節(jié)點(diǎn)先進(jìn)行擴(kuò)展的算法，稱之為深度 優(yōu)先搜索法。簡(jiǎn)稱 dfs 法。(depth_first_search)。深度

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

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

42、+1一>waynum,若 waynum<=waymax,貝轉(zhuǎn) 2一(2)。3、選擇用來(lái)擴(kuò)展的新節(jié)點(diǎn)。(1) 若 objecktop,(即 object 有子節(jié)點(diǎn))則轉(zhuǎn) 3(3)。(2) top出棧，top-1一top,若top=0 (?？談t結(jié)束)，若top已擴(kuò)展, 再轉(zhuǎn)3(2)o(3) top一object,若object已規(guī)定深度，則轉(zhuǎn)3(2)。否則轉(zhuǎn)2。 深度優(yōu)先搜索pascal語(yǔ)言程序：program dfs(input,output);const n=擴(kuò)展節(jié)點(diǎn)估計(jì)數(shù)；waymax=擴(kuò)展節(jié)點(diǎn)途徑數(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是冃標(biāo)節(jié)點(diǎn)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)先搜索的基本算法如下:一、遞歸算法 遞歸過(guò)程為：procedure dfs_try (i);for r:=l to maxr doif子結(jié)點(diǎn)mr符號(hào)條件then產(chǎn)生的子結(jié)點(diǎn)mr壓入棧；輸出if子結(jié)點(diǎn)mi是日標(biāo)結(jié)點(diǎn)thenels

45、e dfstry (1+1)；棧頂元素出棧(刪去mr);endif；enddo；主程序?yàn)?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é)點(diǎn)mr并將英記錄;if子結(jié)點(diǎn)是目標(biāo)then輸出并出棧elsep：二true；elseif j>=maxj then 回溯 else p： =false；endif；until p=true；until dep=o；其中回溯過(guò)程如下：procedur

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

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

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