搜索基本算法20128

1、搜索基本算法搜索是人工智能中的一種基本方法，利用計(jì)算機(jī)的高性能來(lái)有目的、有方法的窮舉一個(gè)問(wèn)題的部分或所有的可能情況，從而求出問(wèn)題的解的一種方法。在建立搜索算法時(shí)，首先需要關(guān)注的問(wèn)題是，以什么作為狀態(tài)？這些狀態(tài)之間又有什么樣的關(guān)系？其實(shí)，在這樣的思考過(guò)程中，我們已經(jīng)不知不覺(jué)地將一個(gè)具體的問(wèn)題抽象成了一個(gè)圖論的模型樹（如圖所示）。即搜索算法的使用第一步在于搜索樹的建立。根結(jié)點(diǎn)一個(gè)成功的解目標(biāo)結(jié)點(diǎn)第0層第1層第2層第3層由上圖可以知道，這樣形成的一棵樹叫搜索樹（圖）。初始狀態(tài)對(duì)應(yīng)著根結(jié)點(diǎn)，目標(biāo)狀態(tài)對(duì)應(yīng)著目標(biāo)結(jié)點(diǎn)。排在前的結(jié)點(diǎn)叫父結(jié)點(diǎn)，其后的結(jié)點(diǎn)叫子結(jié)點(diǎn)，同一層中的結(jié)點(diǎn)是兄弟結(jié)點(diǎn)，由父結(jié)點(diǎn)產(chǎn)生子結(jié)點(diǎn)叫

2、擴(kuò)展。完成搜索的過(guò)程就是找到一條從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑，找出一個(gè)最優(yōu)的解。這種搜索算法的實(shí)現(xiàn)類似于圖或樹的遍歷，通?？梢杂袃煞N不同的實(shí)現(xiàn)方法：深度優(yōu)先搜索（epth First search）和寬度優(yōu)先搜索（First Search），下文對(duì)這兩種方法分別進(jìn)行討論。 深度優(yōu)先搜索一深度搜索如算法名稱那樣，深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索樹。它的基本思想是：為了求得問(wèn)題的解，先選擇某一種可能情況向前（子結(jié)點(diǎn)）探索，在探索過(guò)程中，一旦發(fā)現(xiàn)原來(lái)的選擇不符合要求，就回溯至父親結(jié)點(diǎn)重新選擇另一結(jié)點(diǎn)，繼續(xù)向前探索，如此反復(fù)進(jìn)行，直至求得最優(yōu)解。如迷宮問(wèn)題（可以理解為遍歷圖的問(wèn)題）：進(jìn)入迷

3、宮后，先隨意選擇一個(gè)前進(jìn)方向，一步步向前試探前進(jìn)，如果碰到死胡同，說(shuō)明前進(jìn)方向已無(wú)路可走，這時(shí)，回到上一步，改變前進(jìn)方向是否有路可走，如果有路可走，則沿該方向再向前試探；如果已無(wú)路可走，則再返回一步，再看其它方向是否還有路可走；如果有路可走，則沿該方向再向前試探。按此原則不斷搜索回溯再搜索，直到找到新的出路或從原路返回入口處無(wú)解為止。深度優(yōu)先搜索在樹（圖）的遍歷中也稱作樹（圖）的先序遍歷。對(duì)于樹而言，深度優(yōu)先搜索的思路可以描述為：（） 將根結(jié)點(diǎn)置為出發(fā)結(jié)點(diǎn)。（） 訪問(wèn)該出發(fā)結(jié)點(diǎn)。（） 依次將出發(fā)結(jié)點(diǎn)的子結(jié)點(diǎn)置為新的出發(fā)結(jié)點(diǎn)，進(jìn)行深度優(yōu)先遍歷回溯（執(zhí)行（）。（） 回溯上一層的出發(fā)結(jié)點(diǎn)。深度優(yōu)先搜

4、索的具體編程可用遞歸過(guò)程或模擬梯歸來(lái)實(shí)現(xiàn)。他們各有各有優(yōu)缺點(diǎn)。通常情況下采用遞歸方式實(shí)現(xiàn)搜索算法，因?yàn)檫f歸形式的程序符合思維習(xí)慣，編寫起來(lái)較容易。下面是深度優(yōu)先搜索的用遞歸方式實(shí)現(xiàn)的程序框架：Procedure dfs（i:integer）;Var k:integer;Begin If 所有階段都已求解 then Begin 比較最優(yōu)解并保存； endelse beginfor k:=1 to i（同一深度可能決策的范圍）do begin 窮舉當(dāng)前階段所有可能的決策（方案、結(jié)點(diǎn)）k if k方案可行 then begin 記錄狀態(tài)變化；DFS(i+1); / 將子結(jié)點(diǎn)作為新的出發(fā)結(jié)點(diǎn)狀態(tài)恢復(fù)（

5、現(xiàn)場(chǎng)恢復(fù)）； endend; end;End.二例 題1. 選擇最短路徑【問(wèn)題描述】有如下所示的交通路線圖，邊上數(shù)值表示該道路的長(zhǎng)度，現(xiàn)要求出從1號(hào)地點(diǎn)到達(dá)7號(hào)地點(diǎn)的最短的路徑長(zhǎng)度是多少，并輸出該長(zhǎng)度。 1 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 75317912 6 7 5 4 3 2 1 1 6 7 5 4 3 2 1 6 7 5 4 3 2 1 6 7 5 4 3 2 1 6 7 5 4 3 2 1第1層第2層第3層第4層第5層522233154812119 1 2 3 4 5 7 2 1 3

6、 5 7 6 410圖1 圖2【問(wèn)題分析】首先需要把圖1轉(zhuǎn)化成搜索樹模式。在建立搜索樹之前，各節(jié)點(diǎn)之間的狀態(tài)，結(jié)點(diǎn)與結(jié)點(diǎn)之間的關(guān)系。結(jié)點(diǎn)狀態(tài)：現(xiàn)有結(jié)點(diǎn)號(hào)，每個(gè)結(jié)點(diǎn)存在兩種狀態(tài)，即已進(jìn)入搜素路徑或者未進(jìn)入搜素路徑，初始狀態(tài)都是未進(jìn)入搜索路徑，兩種狀態(tài)可以用“1”和“0”表示。結(jié)點(diǎn)之間關(guān)系：存在路勁或者不存在路徑。存在路徑有具體的數(shù)值表示，不存在路徑可以用“-1”來(lái)代替。在明確以上兩點(diǎn)的基礎(chǔ)上建立如圖2所示的搜索樹。求最短路徑就是遍歷該搜索樹的過(guò)程。首先從號(hào)結(jié)點(diǎn)開始，在遍歷過(guò)程中，搜索到與結(jié)點(diǎn)時(shí)存在路徑，首先把結(jié)點(diǎn)納入路徑，然后累加路徑的長(zhǎng)度同時(shí)判斷該結(jié)點(diǎn)是否為結(jié)點(diǎn)。繼續(xù)調(diào)用以為起點(diǎn)的搜索，開始繼

7、續(xù)遍歷中的結(jié)點(diǎn)，發(fā)現(xiàn)結(jié)點(diǎn)、已在路徑中，結(jié)點(diǎn)不存在連接，判斷與結(jié)點(diǎn)的連接，存在連接，同樣把結(jié)點(diǎn)納入路徑，累加路徑的長(zhǎng)度，同時(shí)判斷該結(jié)點(diǎn)是否為結(jié)點(diǎn)，依次類推，形成一顆搜索樹，一條完整的搜索路徑：-。完成第一條路徑的搜索以后，即完成了第5層面的搜素，但是前面的4個(gè)層面還沒(méi)有完成，這時(shí)回溯至第4層完成結(jié)點(diǎn)和結(jié)點(diǎn)的搜索，不存在連接，繼續(xù)回溯至第3層，遍歷至結(jié)點(diǎn)，遍歷結(jié)點(diǎn)，發(fā)現(xiàn)結(jié)點(diǎn)、結(jié)點(diǎn)已經(jīng)存在路徑中，與結(jié)點(diǎn)存在連接，同樣把結(jié)點(diǎn)納入路徑，累加路徑的長(zhǎng)度，同時(shí)判斷該結(jié)點(diǎn)是否為結(jié)點(diǎn)，然后以結(jié)點(diǎn)為起點(diǎn)，遍歷搜索結(jié)點(diǎn)，發(fā)現(xiàn)無(wú)連接，這樣宣布這條路徑失敗，回溯至第4層，繼續(xù)遍歷結(jié)點(diǎn)-，結(jié)點(diǎn)已在連接中，結(jié)點(diǎn)本身，結(jié)點(diǎn)不

8、存在連接，繼續(xù)遍歷結(jié)點(diǎn)，發(fā)現(xiàn)與該結(jié)點(diǎn)存在連接，同樣把結(jié)點(diǎn)納入路徑，累加路徑的長(zhǎng)度，同時(shí)發(fā)現(xiàn)該結(jié)點(diǎn)為終結(jié)點(diǎn)。完成又一路經(jīng)的的深度搜索：-。所得路徑長(zhǎng)度與前一次比較，保留小的數(shù)值。依次類推完成所有的路徑搜索，求出最短路徑?，F(xiàn)設(shè)定鄰接矩陣表示圖的連接和權(quán)值：ai,j=x,或者ai,j=-1（表示兩者之間不存在距離）。bi=1表示結(jié)點(diǎn)i是否已經(jīng)遍歷過(guò)。用變量min來(lái)保存最優(yōu)解，而用total變量保存求解過(guò)程中臨時(shí)解（當(dāng)前路徑總長(zhǎng)度）。該過(guò)程深度搜索子程序框架結(jié)構(gòu)如下：procedure dfs(I:integer);var k:integer;begin if 到達(dá)了終點(diǎn)n then begin 保存

9、較優(yōu)解；endn else beginn for 窮舉決策范圍內(nèi)I的值 don if I到k點(diǎn)有直接聯(lián)邊并且k點(diǎn)沒(méi)有遍歷過(guò) then beginn 把a(bǔ)I,K累加入路徑長(zhǎng)度total；k標(biāo)記為已遍歷；dfs(k)；n 現(xiàn)場(chǎng)恢復(fù)（還原加入的結(jié)點(diǎn)的狀態(tài)和和減去加入的路徑長(zhǎng)度）；n end;n end; End;【程序代碼】Var i,n,total,min:longint; a:array1.100,1.100 of integer; b:array1.100 0f boolean;procedure dfs(i:integer);var k：integer;beginif i=n then be

10、gin if total<min then min:=total;end else begin for k:=1 to n do if (bk=false) and (i<>k) and (ai,k>0) then begin bk:=true; total:=total+ai,k;if total>min then begin bk:=false; total:=total-ai,k;continue； /剪 枝 end;dfs(k); /搜索遍歷 bk:=false; total:=total-ai,k; /現(xiàn)場(chǎng)恢復(fù)end; end;end;begin /主程

11、序read(n);Fillchar(b,sizeof(b),false); /置初值,作為是否加入路徑標(biāo)志total:=0;b1:=true;min:=maxlongint; /置初值for i:=1 to 7 do /讀入所有點(diǎn)與點(diǎn)之間的距離（不存在路徑用-1代替） for j:= 1 to 7 do read(ai,j)；dfs(1); writeln('total=',min);end.三算法優(yōu)化在例題中有一個(gè)值得思考的問(wèn)題，每次尋找到一條完成的路徑后，需要與前一次的所求的的最短路徑值相比較，以獲取最短路徑。這樣的比較是否可以考慮把他放置在把結(jié)點(diǎn)納入路徑的過(guò)程中，一旦發(fā)現(xiàn)

12、現(xiàn)有的路徑值大于現(xiàn)保留的最短路徑值，就立即終止當(dāng)前路徑搜索，回溯，搜索另一條路徑，這樣可以大大減少了搜索的次數(shù)，這就是搜索優(yōu)化方式之一剪枝。所謂剪枝就是通過(guò)某種判斷，避免一些不必要的遍歷過(guò)程，形象地說(shuō)，就是剪彩去了搜索樹中的某些不符合要求的“枝條”，減少搜索時(shí)間和空間。剪枝算法按照其判斷思路可大致分成三類：可行性剪枝、最優(yōu)化剪枝和判重剪枝。顯而易見，應(yīng)用剪枝優(yōu)化的核心問(wèn)題是設(shè)計(jì)剪枝判斷方法，即確定哪些枝條應(yīng)當(dāng)舍棄，哪能些枝條應(yīng)當(dāng)保留的方法。在設(shè)計(jì)一個(gè)優(yōu)秀的設(shè)計(jì)剪枝判斷方法的過(guò)程中，一般需要考慮以下三個(gè)方面的問(wèn)題。1 正確性 剪枝方法之所以能夠優(yōu)化程序的執(zhí)行效率，正如前文所述是因?yàn)樗軌颉凹糁Α?/p>

13、過(guò)程中剪掉沒(méi)有價(jià)值的枝葉，這些枝葉的“值”不存在對(duì)最優(yōu)解的準(zhǔn)確性產(chǎn)生影響，為此必須在考慮剪枝方法的正確性。當(dāng)然，由必要條件的定義，我們知道，沒(méi)有被剪的枝不意味著其中一定有正解，否則就不必搜索了。2 力 度剪枝的力度是指搜索中剪去的枝與所有枝的比值。搜索的效率很大程序上取決于剪枝的力度，因?yàn)榱Χ葘?duì)搜索效率的貢獻(xiàn)并不僅僅是成正比的，而是呈幾何級(jí)數(shù)上升的，強(qiáng)有力的剪枝可以省去一大半的時(shí)間或空間。剪枝方法只有在具有了較強(qiáng)的力度的時(shí)候，才能真正收到優(yōu)化的效果，因此，剪枝的力度可以說(shuō)是剪枝優(yōu)化的生命。3 代 價(jià)剪枝的代價(jià)是指剪枝本身所花費(fèi)的時(shí)間與空間。一般說(shuō)來(lái)，設(shè)計(jì)好剪枝判斷方法之后，需對(duì)搜索樹的每個(gè)枝條

14、都要執(zhí)行一次判斷操作。但是判斷操作無(wú)疑帶來(lái)的是時(shí)間代價(jià)開銷的遞增，如果剪枝判斷的時(shí)間消耗過(guò)多，就就可能減小、甚至完全抵消提高判斷力度所能帶來(lái)的優(yōu)化效果，這就變成得不償失。很多情況下，能否較好的處理這個(gè)矛盾，往往成為搜索算法優(yōu)化的關(guān)健。剪枝條件的獲取，并不是盲目的，恰恰相反，剪枝有一些邏輯性與規(guī)律性的方法。剪枝條件的獲取主要要有兩個(gè)方法：直覺(jué)法和推理法。在引題“選擇最短路徑”中，剪枝的條件獲取比較直覺(jué)。在每次納入結(jié)點(diǎn)的過(guò)程中，加入路徑的長(zhǎng)度，隨之與當(dāng)前最短路徑值比較，大于當(dāng)前最優(yōu)路徑的值即剪枝。四經(jīng)典例題1數(shù)字排列(number.pas)【問(wèn)題描述】列出所有從數(shù)字1到數(shù)字n的連續(xù)自然數(shù)的排列，要

15、求所產(chǎn)生的任一數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字?！据斎敫袷健?單獨(dú)一行N（1<=N<=9）【輸出格式】 由1n組成的所有不重復(fù)的數(shù)字序列，每行一個(gè)序列?！緲永斎搿?3【樣例輸出】1 2 3 1 3 2 2 1 3 2 3 13 1 2 3 2 1 【問(wèn)題分析】采用方法：可以采用全排的手段，也可以采用回溯+去重剪枝。本題實(shí)質(zhì)就是對(duì)n個(gè)數(shù)進(jìn)行排列組合，并打印出所有的組合?，F(xiàn)以n=3為例建立一棵如下圖所示的搜索樹，每一條路徑代表一個(gè)組合。但是根據(jù)題意在對(duì)n個(gè)數(shù)值進(jìn)行組合的過(guò)程中，不允許出現(xiàn)相同的數(shù)字，為此在對(duì)搜索樹搜索的過(guò)程中可以進(jìn)行適當(dāng)?shù)募糁Γ@樣可以大大提高搜索效率。圖中用“”實(shí)現(xiàn)對(duì)

16、n=3數(shù)值的剪枝。 在程序?qū)崿F(xiàn)的過(guò)程中定義一個(gè)函數(shù)確定該數(shù)是否被使用，沒(méi)有則遞歸處理下一位數(shù)，否則剪枝回溯，直到k>n。 13 13 12 11 11 13 12 11 12 13 12 11 13 10 13 13 12 11 11 13 12 11 12 13 12 11 12 13 13 12 11 11 13 12 11 12 13 12 11 11【程序代碼】program number;var a:array 1.100 of integer; i,n:integer;function pd(k,i:integer):boolean; /判斷需排列的數(shù)字是否重復(fù)；var m:

17、integer;begin m:=1; while (m<k)and(i<>am) do m:=m+1;/與排列的數(shù)字比較判重； if m=k then pd:=true else pd:=false;end;procedure try(k:integer); /回溯搜索全排組合；var i:integer;begin if k>n then begin /完成一次數(shù)字排列后打印 for i:=1 to n do write(ai:5); writeln end else for i:=1 to n do /從1-n完成按次序?qū)崿F(xiàn)全排 if pd(k,i) then b

18、egin /判重，逐個(gè)按序選出需排列的數(shù)字 ak:=i /選出的數(shù)字放入數(shù)組a中； try(k+1); /回溯調(diào)用排列下一位數(shù)字; end;end;begin assign(input,'number.in');reset(input); assign(output,'number.out');rewrite(output); readln(n); try(1);end. 2特殊的質(zhì)數(shù)（USACO練習(xí)題 spnumber.pas）【問(wèn)題描述】農(nóng)民約翰的母?？偸巧a(chǎn)出最好的肋骨。你能通過(guò)農(nóng)民約翰和美國(guó)農(nóng)業(yè)部標(biāo)記在每根肋骨上的數(shù)字認(rèn)出它們。農(nóng)民約翰確定他賣給買方的是

19、真正的質(zhì)數(shù)肋骨，是因?yàn)閺挠疫呴_始切下肋骨,每次還剩下的肋骨上的數(shù)字都組成一個(gè)質(zhì)數(shù)，舉例來(lái)說(shuō)：7 3 3 1全部肋骨上的數(shù)字7331是質(zhì)數(shù)，三根肋骨733是質(zhì)數(shù)，二根肋骨 73 是質(zhì)數(shù)，當(dāng)然，最后一根肋骨7也是質(zhì)數(shù)。7331 被叫做長(zhǎng)度 4 的特殊質(zhì)數(shù)。 寫一個(gè)程序?qū)o定的肋骨的數(shù)目 N (1<=N<=8)，求出所有的特殊質(zhì)數(shù)。數(shù)字1不被看作一個(gè)質(zhì)數(shù)?！据斎敫袷健繂为?dú)的一行包含N。 【輸出格式】按順序輸出長(zhǎng)度為 N 的特殊質(zhì)數(shù)，每行一個(gè)。 【樣例輸入】4【樣例輸出】233323392393239929393119313737333739379337975939719373317333

20、7393【問(wèn)題分析】采用方法：深度優(yōu)先搜索+條件剪枝。問(wèn)題的本質(zhì)就是尋找一個(gè)n位的質(zhì)數(shù)，然后逐位去掉末尾，要求該形成的新數(shù)也是質(zhì)數(shù)。根據(jù)樣例數(shù)據(jù)分析可以采用末尾補(bǔ)奇數(shù)的方式，然后判斷該數(shù)是否為質(zhì)數(shù)。即逐步深搜添加的數(shù)值為1、3、5、7、9，同時(shí)對(duì)該數(shù)進(jìn)行判斷是不是質(zhì)數(shù)（素?cái)?shù)），是則遞歸處理下一位數(shù)，不是則剪枝回溯，直到depth>n。 或者直接深搜19，然后條件判斷是不是質(zhì)數(shù)（素?cái)?shù)），是則遞歸處理下一位數(shù)，不是則剪枝回溯，直到depth>n。當(dāng)然在處理完該4位數(shù)是質(zhì)數(shù)后需要記錄該數(shù)。【程序代碼】program spnumber;var s:longint; n,b:longint;

21、function pd(x:longint):boolean; /判斷所獲得的數(shù)值是否為素?cái)?shù)var flag:boolean; i:longint;begin flag:=true; if x=1 then flag:=flase; else begin for i:=2 to trunc(sqrt(x) do if x mod i=0 then begin flag:=false; break; end; end;end;procedure dfs(s:longint);var k:longint;begin if s>n then begin writeln(b) exit end;

22、 /完成符合位數(shù)要求素?cái)?shù)搜索后，輸出該素?cái)?shù) for k:=1 to 9 do begin if (k=2)or(k mod 2 =1) then begin /要求末尾加入k值為2或者為奇數(shù) b:=b*10+k; /累加位數(shù)，并把k值加入末尾，形成新的b值if pd(b)then dfs(s+1); /判斷新形成的數(shù)值是否是素?cái)?shù)，是深度搜索下1位數(shù)值； s:=s-1;b:=b div 10; /恢復(fù)現(xiàn)場(chǎng)，為繼續(xù)加入下一個(gè)數(shù)值初始化； end; end; end;begin assign(input,'spnumber.in');reset(input); assign(outp

23、ut,'spnumber.out');rewrite(output); readln(n); /讀入數(shù)值的位數(shù) s:=1; /統(tǒng)計(jì)位數(shù) dfs(1); /搜索數(shù)值 close(input);close(output);end.3.砝碼稱重（NOIP 1996 提高組weight.pas）【問(wèn)題描述】設(shè)有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重<=1000），求：用這些砝碼能稱出的不同重量的個(gè)數(shù)，但不包括一個(gè)砝碼也不用的情況?！据斎敫袷健枯斎胛募兄挥幸恍幸钥崭穹指舻?個(gè)數(shù)字，a1 a2 a3 a4 a5 a6。表示1g砝碼有a1個(gè)，2g砝碼有a2個(gè)，3

24、g砝碼有a3個(gè)，5g砝碼有a4個(gè)，10g砝碼有a5個(gè)20g砝碼有a6個(gè)?！据敵龈袷健?輸出文件中只有一行數(shù)據(jù)：Total=N。表示用這些砝碼能稱出的不同重量的個(gè)數(shù)，但不包括一個(gè)砝碼也不用的情況?！据斎霕永?1 1 0 0 0 0【輸出樣例】Total=3【問(wèn)題分析】采用方法：深度優(yōu)先搜索。問(wèn)題的實(shí)質(zhì)就是完成對(duì)不同的數(shù)值的組合，求能夠形成多少種不同的組合。首先建一棵搜索樹，如下圖所示，然后對(duì)該搜索樹做一次深度遍歷。 b 0 d 0 d 0 0 d d h 0 0 b 0 a 0 第1個(gè)砝碼第2個(gè)砝碼第3個(gè)砝碼第6個(gè)砝碼由上圖可以知道每1種砝碼都存在多種情況，可以取0n個(gè)，同樣當(dāng)?shù)?種砝碼取0個(gè)

25、的時(shí)候，同樣第二種砝碼存在多種取法，依次類推，即建立了如上圖所示的搜索樹。直接深搜16，直到depth>6，然后直接用一維數(shù)組，記錄能夠稱重的砝碼，統(tǒng)計(jì)該數(shù)組的值，得出能夠稱重的種類?！境绦虼a】program weight;var f:array0.1000of longint; /用于記錄能夠稱重的不同重量 a,w:array1.6of longint; 數(shù)組a存放砝碼的個(gè)數(shù)，數(shù)組w存放砝碼的重量 s,i:longint;procedure dfs(i:longint);var j:longint;begin if i>6 then begin /完成1次6個(gè)砝碼的組合，并記錄

26、能夠稱重的重量 fs:=1;exit; end; for j:=0 to ai do begin /按不同種類的砝碼數(shù)量搜索能夠稱重的重量 s:=s+j*wi; dfs(i+1); / 進(jìn)入下一類別砝碼重量的搜索 s:=s-j*wi; /恢復(fù)現(xiàn)場(chǎng)，為搜索下一個(gè)重量做準(zhǔn)備 end;end;begin/ assign(input,'weight.in');reset(input);/ assign(output,'weight.out');rewrite(output); for i:=1 to 6 do read(ai); /分別讀入砝碼的個(gè)數(shù) w1:=1;w2:

27、=2;w3:=3; w4:=5;w5:=10;w6:=20;/定義砝碼的重量 fillchar(f,sizeof(f),0); /初始化數(shù)組f； s:=0; /初始化初值s， dfs(1); /深度搜索調(diào)用過(guò)程 s:=0; for i:=1 to 1000 do s:=s+fi; writeln('Total=',s); / close(output);close(input);end.4.導(dǎo)游（2007年寧波市中小學(xué)程序設(shè)計(jì)比賽決賽題 guide.pas）【問(wèn)題描述】寧波市的中小學(xué)生們?cè)阪?zhèn)海中學(xué)參加程序設(shè)計(jì)比賽之余，熱情的主辦方邀請(qǐng)同學(xué)們參觀鎮(zhèn)海中學(xué)內(nèi)的各處景點(diǎn)，已知鎮(zhèn)海中學(xué)

28、內(nèi)共有n處景點(diǎn)?，F(xiàn)在有n位該校的學(xué)生志愿承擔(dān)導(dǎo)游和講解任務(wù)。每個(gè)學(xué)生志愿者對(duì)各個(gè)景點(diǎn)的熟悉程度是不同的，如何將n位導(dǎo)游分配至n處景點(diǎn)，使得總的熟悉程度最大呢？要求每個(gè)景點(diǎn)處都有一個(gè)學(xué)生導(dǎo)游?！据?入】輸入文件中有若干行：第一行只有一個(gè)正整數(shù)n，表示有n個(gè)景點(diǎn)和n個(gè)學(xué)生導(dǎo)游。第二行至第n+1行共n行，每行有n個(gè)以空格分隔的正整數(shù)。第i+1行的第j個(gè)數(shù)k(1k1000)，表示第i個(gè)學(xué)生導(dǎo)游對(duì)景點(diǎn)j的熟悉程度為k?！据?出】輸出文件只有一行，該行只有一個(gè)正整數(shù)，表示求得的熟悉程度之和的最大值?！緲永斎搿俊緲永敵觥? 2410 6 89 2 31 7 2【樣例說(shuō)明】第1個(gè)學(xué)生負(fù)責(zé)第3個(gè)景點(diǎn)，第2個(gè)

29、學(xué)生負(fù)責(zé)第1個(gè)景點(diǎn)，第3個(gè)學(xué)生負(fù)責(zé)第2個(gè)景點(diǎn)時(shí)，熟悉程度總和為24，達(dá)到最大值?！緮?shù)據(jù)限制】50%的數(shù)據(jù)，1n9；100%的數(shù)據(jù)，1n17?！締?wèn)題分析】 8 6 10 3 2 9 2 7 1采用方法：深度搜索+調(diào)整剪枝。問(wèn)題的實(shí)質(zhì)就是在搜索二維數(shù)組中的值，要求每行每列中只能取一個(gè)值，然后求該數(shù)值的和，找出其中最大的和。根據(jù)樣例，首先建立一棵搜索樹，如下圖所示。根據(jù)以樣例建立的搜索樹可以看出，可以采用深搜遍歷搜索樹的方法求的該問(wèn)題的解，但是根據(jù)數(shù)據(jù)限制“100%的數(shù)據(jù)，1n17”，采用遍歷全部的方式肯定存在超時(shí)。變通思維方式，題意中最大景點(diǎn)的值是1000，轉(zhuǎn)換二維數(shù)組的值，用1000減去該值，變

30、求二維數(shù)組中最大的值為求最小值，然后在深度遍歷的過(guò)程中，比較所獲取的和值，比當(dāng)前已獲取的最小值比較，小則遞歸處理下一個(gè)數(shù)值，大或者等于則剪枝回溯，直到depth>n?！境绦虼a】program guide;const maxn=50;var a:array1.maxn,1.maxnof longint; f:array1.maxnof boolean; /用于標(biāo)識(shí)景點(diǎn)、導(dǎo)游是否被分配過(guò)； n,i,j,ans:longint;procedure dfs(i,s:longint); var j:longint;begin if i>n then begin / 當(dāng)完成一次導(dǎo)游搜索組合，

31、得出當(dāng)前最佳的得的熟悉程度值 if ans>s then ans:=s;exit; end; if s>=ans then exit; /當(dāng)前得到的熟悉程度值大于先前最佳熟悉程度值時(shí)則剪枝 for j:=1 to n do /按導(dǎo)游對(duì)各景點(diǎn)的熟悉程度搜索 if fj then begin /假如該景點(diǎn)未被分配過(guò)導(dǎo)游 fj:=false; /標(biāo)識(shí)景點(diǎn)使用標(biāo)識(shí) dfs(i+1,s+ai,j); /累加景點(diǎn)熟悉程度值，并進(jìn)入下一層景點(diǎn)熟悉程度的搜索 fj:=true; / 完成以該近點(diǎn)為前提的搜索，恢復(fù)現(xiàn)場(chǎng)，為同層下一景點(diǎn)搜索做準(zhǔn)備 end;end;begin assign(input,

32、'guide.in');reset(input); assign(output,'guide.out');rewrite(output); read(n); for i:=1 to n do for j:=1 to n do beginread(ai,j); /讀入各導(dǎo)游對(duì)各景點(diǎn)的熟悉程度ai,j:=1000-ai,j; /變求最大值為最小值 end;fillchar(f,sizeof(f),true); /初始化布爾數(shù)組為“true” ans:=maxlongint; dfs(1,0); /深度搜索調(diào)用 writeln(n*1000-ans); /求的最大熟悉

33、程度的值 close(output);close(input);end.5.外星生命（live.pas）【問(wèn)題描述】在外太空航行的飛船拍到了某種外星生命的圖像?？茖W(xué)家在研究該圖像時(shí)，把該圖像分為n行m列,共n*m個(gè)格子，每格給出了一個(gè)以整數(shù)表示的相似度的值?，F(xiàn)在請(qǐng)你幫助統(tǒng)計(jì)該圖像可以分成幾部分？給定一個(gè)正整數(shù)的靈敏度值x, 如果某格與某相鄰格子的相似度值的差值小于或等于x時(shí)，該格與該相鄰格子屬于同一個(gè)部件（所謂相鄰，是指上、下、左、右之一）。如下圖所示，當(dāng)靈敏度值分別為10和5時(shí)，可以分為3個(gè)部件和5個(gè)部件。1015132522502352825102502452401001051112918

34、999104102100908810151325225023528251025024524010010511129189991041021009088【輸 入】輸入文件live.in中有若干行：第一行有三個(gè)整數(shù)n、m和x,表示圖像有n行m列,設(shè)定的靈敏度為x。第二行起至第n+1行，每行有m個(gè)整數(shù)，互相間以一個(gè)空格分隔。第k+1行的第j個(gè)整數(shù)，表示圖像中第k行第j列的相似度值。【輸 出】 輸出文件live.out中只有一行，該行只有一個(gè)整數(shù)，表示可以劃分出的部件數(shù)?！緲永斎?】 【樣例輸入2】4 6 10 4 6 5 10 15 13 252 250 235 10 15 13 252 250

35、23528 25 10 250 245 240 28 25 10 250 245 240 100 105 11 12 91 89 100 105 11 12 91 8999 104 102 100 90 88 99 104 102 100 90 88【樣例輸出1】 【樣例輸出2】3 5【數(shù)據(jù)限制】1n,m1000【問(wèn)題分析】采用方法：深度搜索。本問(wèn)題的實(shí)質(zhì)就是對(duì)一個(gè)二維數(shù)組的搜索，要求在搜索的過(guò)程中求出相鄰的兩個(gè)數(shù)的差值小于等于x的連續(xù)最大區(qū)域單元格的個(gè)數(shù)以樣例1為例，以中心點(diǎn)10為例，可以向4個(gè)不同方向查詢。在同一行向左搜索不得小于1，向右搜索不得小于n，在同一列的搜索過(guò)程中，向上不得小于1

36、，向下搜索不得大于m，同時(shí)在搜索的必須保證連續(xù)相鄰兩數(shù)的絕對(duì)值差值不得大于靈敏度值x,完成對(duì)二維數(shù)組的搜索，計(jì)算出符合靈敏度的區(qū)塊數(shù)量。在深度遍歷的過(guò)程中，分別按照四個(gè)方向深度遍歷，在搜索遍歷過(guò)程中同時(shí)滿足三個(gè)條件：在規(guī)定的二維數(shù)組行列中搜索、該結(jié)點(diǎn)數(shù)據(jù)內(nèi)有被納入其他區(qū)域中和相鄰連續(xù)區(qū)域的絕對(duì)差值小于等于比當(dāng)前已獲取的最小值靈敏度值x，符合要求則遞歸處理下一個(gè)數(shù)值，不符合回溯，遍歷完所有二維數(shù)組結(jié)點(diǎn)?！境绦虼a】program live;var f:array1.1000,1.1000of integer; /用于存放二維數(shù)組的值； visited:array1.1000,1.1000of b

37、oolean;/標(biāo)識(shí)二維數(shù)組是否被訪問(wèn)過(guò)； n,m,x,i,j,re:longint;procedure dfs(i,j:longint);/開展以某點(diǎn)為中心，敏感度為x的上下左右搜索； begin visitedi,j:=false; if (i>1) and visitedi-1,j and (abs(fi-1,j-fi,j)<=x) then dfs(i-1,j); if (i<n) and visitedi+1,j and (abs(fi+1,j-fi,j)<=x) then dfs(i+1,j); if (j>1) and visitedi,j-1 an

38、d (abs(fi,j-1-fi,j)<=x) then dfs(i,j-1); if (j<m) and visitedi,j+1 and (abs(fi,j+1-fi,j)<=x) then dfs(i,j+1); end;begin assign(input,'live.in');reset(input); assign(output,'live.out');rewrite(output); read(n,m,x); /讀入n、m和敏感程度x的值； for i:=1 to n do for j:=1 to m do read(fi,j);

39、/讀入二維數(shù)組值 re:=0;fillchar(visited,sizeof(visited),true);/初始化標(biāo)識(shí)數(shù)組 for i:=1 to n do for j:=1 to m do /按列、行逐個(gè)搜索 if visitedi,j then begin inc(re);dfs(i,j);end;/假如該值沒(méi)有被訪問(wèn)過(guò)，則作為一個(gè)區(qū)域，并開展敏感度 x的搜索； writeln(re); close(input);close(output);end.6數(shù)的拆分（snumber.pas）【問(wèn)題描述】對(duì)于正整數(shù) n ，輸出其和等于 n 且滿足以下限制條件的所有正整數(shù)的和式，以及和式的總數(shù)。組

40、成和式的數(shù)字自左至右構(gòu)成一個(gè)非遞增的序列。如n=4，程序輸出為：4=44=3+14=2+24=2+1+14=1+1+1+15【輸入文件】輸入文件snumber.in僅一行，該行只有一個(gè)正整數(shù)n(1n50)?！据敵鑫募枯敵鑫募number.out包含若干行，最后一行輸出和式的數(shù)目，除此之外，前面每一行輸出一個(gè)和式，組成和式的數(shù)字自左至右構(gòu)成一個(gè)非遞增的序列，不同行的和式先按照等號(hào)右邊的第一個(gè)數(shù)字降序排列，若第一個(gè)數(shù)字相同，則按第二個(gè)數(shù)字降序排列，依此類推，直到輸出所有和式為止?！据斎霕永?【輸出樣例】5=55=4+15=3+25=3+1+15=2+2+15=2+1+1+15=1+1+1+1

41、+17【問(wèn)題分析】解決方法：深度搜索+調(diào)整剪枝。問(wèn)題的實(shí)質(zhì)就是對(duì)輸入的n進(jìn)行拆分。根據(jù)樣例建立的一顆如圖所示的搜索樹。 5 50 41 32 22 10 20 10 10 10 11 21 11 11 10 11 11 11 11第一層第二層第三層由樣例圖可知，每一組數(shù)據(jù)存在兩個(gè)數(shù)字，前一個(gè)數(shù)字為依次需要拆分的數(shù)字，另一個(gè)為下一拆分起點(diǎn)最大數(shù)值（該數(shù)值在取值過(guò)程中需要進(jìn)行適當(dāng)?shù)恼{(diào)整，與先前所拆分的數(shù)值進(jìn)行比較，取兩者較小數(shù)值為再次拆分對(duì)象，即為下一層搜索對(duì)象的起始值，目的避免重復(fù)拆分?jǐn)?shù)值，進(jìn)行適度調(diào)整剪枝），然后對(duì)該數(shù)值進(jìn)行遞歸處理，判斷剩余的數(shù)值是否為0，是則打印，并回溯至上一層，繼續(xù)該層中

42、其他數(shù)值的拆分。不是則按序窮舉當(dāng)前層的所有取值，并遞歸深搜下一層剩余數(shù)值的拆分。以上圖拆分5=2+2+1和5=2+1+1+1為例。首先在完成前一組數(shù)值拆分恢復(fù)現(xiàn)場(chǎng)，回溯窮舉至2（第一層），得第一個(gè)拆分?jǐn)?shù)值2，余下的數(shù)值5-2，即為3，剩下數(shù)值3與已拆分前一個(gè)所得數(shù)值比較取較小值2（避免5再次拆分成2和3），獲得拆分?jǐn)?shù)值窮舉范圍即2-1，進(jìn)入第二層搜索，首先是窮舉2，獲得第二個(gè)拆分?jǐn)?shù)值2，計(jì)算剩余數(shù)值得1，然后遞歸調(diào)拆分余下的數(shù)值1，首先判斷剩下的數(shù)值是否為0（完成拆分），不是，該數(shù)值與前一個(gè)拆分所得的數(shù)值2比較取小數(shù)值得1，獲得該數(shù)的數(shù)值拆分范圍為1-1，進(jìn)入第三層搜索，取第三個(gè)拆分?jǐn)?shù)值1，同

43、時(shí)剩下的數(shù)值減去該數(shù)值得0，遞歸調(diào)用，拆分余下的數(shù)值0，在遞歸調(diào)用過(guò)程中，發(fā)現(xiàn)剩余數(shù)值為0，遞歸調(diào)用結(jié)束，即打印該拆分?jǐn)?shù)即4=2+2+1，恢復(fù)現(xiàn)場(chǎng)至上一層，得剩余數(shù)值為1，再次恢復(fù)現(xiàn)場(chǎng)至上一層（第二層），得剩余數(shù)值為3，窮舉下一個(gè)拆分?jǐn)?shù)值1，據(jù)悉完成5=1+1+1+1+1的拆分?！境绦虼a】program snumber;const maxn=50;var a:array0.maxnof integer; /用于存放拆分的數(shù)值； left,n:integer;變量left用于存放n拆分以后所剩下的值 total:longint;procedure dfs(k:integer);var i,mi

44、n:integer;begin if left=0 then begin 當(dāng)剩下的的值為“0”時(shí)，完成一組拆分，累加 write(n,'=',a1);total:=total+1; for i:=2 to k-1 do write('+',ai);writeln; end else begin if left<ak-1 then min:=left else min:=ak-1; for i:=min downto 1 do begin ak:=i;left:=left-i; dfs(k+1); left:=left+i; end; end;end;beg

45、in assign(input,'snumber.in');reset(input); assign(output,'snumber.out');rewrite(output); readln(n);a0:=n;left:=n;total:=0; dfs(1);writeln(total); close(input);close(output);end.7.棋 盤（USACO練習(xí)題checker.pas）【問(wèn)題描述】檢查一個(gè)如下的6×6的跳棋棋盤，有六個(gè)棋子被放置在棋盤上，使得每行、每列只有一個(gè)，每條對(duì)角線(包括兩條主對(duì)角線的所有平行線)上至多有一個(gè)棋

46、子，如下圖所示。上面的布局可以用序列2 4 6 1 3 5來(lái)描述，第i個(gè)數(shù)字表示在第i行的相應(yīng)位置有一個(gè)棋子，如下： 行號(hào) 1 2 3 4 5 6 列號(hào) 2 4 6 1 3 5 這只是跳棋放置的一個(gè)解。請(qǐng)編一個(gè)程序找出所有跳棋放置的解。并以上面的序列方法輸出解（按字典順序排列）。請(qǐng)輸出前3個(gè)解，最后一行是解的總個(gè)數(shù)。 【輸入格式】 一個(gè)數(shù)字N (6 <= N <= 13) 表示棋盤是N × N大小的。 【輸出格式】 前三行為前三個(gè)解，每個(gè)解的兩個(gè)數(shù)字之間用一個(gè)空格隔開，第四行只有一個(gè)數(shù)字，表示解的總數(shù)。 【輸入樣例】6 【輸出樣例】2 4 6 1 3 5 3 6 2 5

47、1 4 4 1 5 2 6 3 4【問(wèn)題分析】解決方法：深搜+優(yōu)化。問(wèn)題的實(shí)質(zhì)就是類似八皇后問(wèn)題。首先建立一顆搜索樹，如下圖所示以6×6的跳棋棋盤建立的一顆搜索樹，在深度搜索解的過(guò)程中最為主要的是檢查判斷，即檢查同一列、對(duì)角線是否有其他棋子存在，為此可以通過(guò)建立標(biāo)志數(shù)組bi、ci-k和dk+i。數(shù)組bi控制同一列只能有一個(gè)棋子存在；ci-k控制“”對(duì)角線是否有棋子存在，在同一“”對(duì)角線上其行列坐標(biāo)之差是相等的；dk+i控制“/”對(duì)角線是否有棋子存在，在同一“”對(duì)角線上其行列坐標(biāo)之和是相等的。這樣在放置下一個(gè)棋子的時(shí)候，判斷需要放置棋子位置的所在的列、對(duì)角線上是否有棋子，即該棋子的列、

48、對(duì)角線標(biāo)志值是否為初始值（“0”），是則可以放置該棋子，然后遞歸調(diào)用，直到depth>n,回溯；反之枚舉同一行中的其他列放置位置。繼續(xù)判斷，一旦發(fā)現(xiàn)該行不存在合適的棋子放置位置時(shí)，同樣，回溯，修改上一行中棋子放置位置，直到遍歷棋盤中的所有的位置。問(wèn)題優(yōu)化：但是這樣的搜索對(duì)于該題最后一個(gè)數(shù)據(jù)測(cè)試數(shù)據(jù)無(wú)法通過(guò)。為此可以優(yōu)化該算法?？梢酝ㄟ^(guò)考慮對(duì)稱方法。如果n是偶數(shù)，第一行枚舉前一半的數(shù)，這樣每搜索出一種方案后，沿中線對(duì)稱過(guò)來(lái)又是一種方案，并且因?yàn)榈谝恍械臄?shù)小于一半，對(duì)稱過(guò)來(lái)的方案總大于原方案，即在搜索樹中后被搜索到，不會(huì)出現(xiàn)重復(fù)的情況。 如果n是奇數(shù)，先在中間行和中間列放之，并且位置都不超過(guò)

49、半數(shù)(<n div 2)，且中間行大于中間列，這樣每搜索出一種方案，把它對(duì)稱旋轉(zhuǎn)后一共有8種方案，因?yàn)橹虚g行和中間列的的不出現(xiàn)重復(fù)，所以8種方案不重復(fù)。這樣只需枚舉原來(lái)的1/8即可。 1 2 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 1 2 1 1 1 2 1 1 1 1 1 1 1 2 11 2 3 4 5 6123456 1 1【程序代碼】var a:array-50.50 of longint; b,c,d：array-50.50 of boolean；n,t:longint;procedure dfs(k:longint);var j,i:longint;beginif k>n then begin if t<3 then begin write(a1); for j:=2 to n do write(' ',aj);writeln;end;t:=t+1;exit;end;for i:=1 to n doif (bi=0) and (ci-k=0) and (dk+i=0) then begin ak:=i;bi:=1;ci-k:=1;di+k:=1;dfs(k+1);bi:=0;ci-k:=0;di+k:=0;end;end;beginassign(input,'