搜索基本算法20128

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

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

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

4、索的具體編程可用遞歸過程或模擬梯歸來實現(xiàn)。他們各有各有優(yōu)缺點。通常情況下采用遞歸方式實現(xiàn)搜索算法，因為遞歸形式的程序符合思維習(xí)慣，編寫起來較容易。下面是深度優(yōu)先搜索的用遞歸方式實現(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é)點）k if k方案可行 then begin 記錄狀態(tài)變化；DFS(i+1); / 將子結(jié)點作為新的出發(fā)結(jié)點狀態(tài)恢復(fù)（

5、現(xiàn)場恢復(fù)）； endend; end;End.二例 題1. 選擇最短路徑【問題描述】有如下所示的交通路線圖，邊上數(shù)值表示該道路的長度，現(xiàn)要求出從1號地點到達7號地點的最短的路徑長度是多少，并輸出該長度。 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【問題分析】首先需要把圖1轉(zhuǎn)化成搜索樹模式。在建立搜索樹之前，各節(jié)點之間的狀態(tài)，結(jié)點與結(jié)點之間的關(guān)系。結(jié)點狀態(tài)：現(xiàn)有結(jié)點號，每個結(jié)點存在兩種狀態(tài)，即已進入搜素路徑或者未進入搜素路徑，初始狀態(tài)都是未進入搜索路徑，兩種狀態(tài)可以用“1”和“0”表示。結(jié)點之間關(guān)系：存在路勁或者不存在路徑。存在路徑有具體的數(shù)值表示，不存在路徑可以用“-1”來代替。在明確以上兩點的基礎(chǔ)上建立如圖2所示的搜索樹。求最短路徑就是遍歷該搜索樹的過程。首先從號結(jié)點開始，在遍歷過程中，搜索到與結(jié)點時存在路徑，首先把結(jié)點納入路徑，然后累加路徑的長度同時判斷該結(jié)點是否為結(jié)點。繼續(xù)調(diào)用以為起點的搜索，開始繼

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

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

9、較優(yōu)解；endn else beginn for 窮舉決策范圍內(nèi)I的值 don if I到k點有直接聯(lián)邊并且k點沒有遍歷過 then beginn 把aI,K累加入路徑長度total；k標(biāo)記為已遍歷；dfs(k)；n 現(xiàn)場恢復(fù)（還原加入的結(jié)點的狀態(tài)和和減去加入的路徑長度）；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 totalmin then min:=total;end else begin for k:=1 to n do if (bk=false) and (ik) and (ai,k0) then begin bk:=true; total:=total+ai,k;if totalmin then begin bk:=false; total:=total-ai,k;continue； /剪 枝 end;dfs(k); /搜索遍歷 bk:=false; total:=total-ai,k; /現(xiàn)場恢復(fù)end; end;end;begin /主程序read(n);Fillchar(b,

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

12、回溯，搜索另一條路徑，這樣可以大大減少了搜索的次數(shù)，這就是搜索優(yōu)化方式之一剪枝。所謂剪枝就是通過某種判斷，避免一些不必要的遍歷過程，形象地說，就是剪彩去了搜索樹中的某些不符合要求的“枝條”，減少搜索時間和空間。剪枝算法按照其判斷思路可大致分成三類：可行性剪枝、最優(yōu)化剪枝和判重剪枝。顯而易見，應(yīng)用剪枝優(yōu)化的核心問題是設(shè)計剪枝判斷方法，即確定哪些枝條應(yīng)當(dāng)舍棄，哪能些枝條應(yīng)當(dāng)保留的方法。在設(shè)計一個優(yōu)秀的設(shè)計剪枝判斷方法的過程中，一般需要考慮以下三個方面的問題。1 正確性 剪枝方法之所以能夠優(yōu)化程序的執(zhí)行效率，正如前文所述是因為它能夠“剪枝”過程中剪掉沒有價值的枝葉，這些枝葉的“值”不存在對最優(yōu)解的準(zhǔn)

13、確性產(chǎn)生影響，為此必須在考慮剪枝方法的正確性。當(dāng)然，由必要條件的定義，我們知道，沒有被剪的枝不意味著其中一定有正解，否則就不必搜索了。2 力 度剪枝的力度是指搜索中剪去的枝與所有枝的比值。搜索的效率很大程序上取決于剪枝的力度，因為力度對搜索效率的貢獻并不僅僅是成正比的，而是呈幾何級數(shù)上升的，強有力的剪枝可以省去一大半的時間或空間。剪枝方法只有在具有了較強的力度的時候，才能真正收到優(yōu)化的效果，因此，剪枝的力度可以說是剪枝優(yōu)化的生命。3 代 價剪枝的代價是指剪枝本身所花費的時間與空間。一般說來，設(shè)計好剪枝判斷方法之后，需對搜索樹的每個枝條都要執(zhí)行一次判斷操作。但是判斷操作無疑帶來的是時間代價開銷的

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

15、單獨一行N（1=Nn。 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:integer;begin m:=1; while (mk)and(iam) do m:=m+1;/與排

16、列的數(shù)字比較判重； if m=k then pd:=true else pd:=false;end;procedure try(k:integer); /回溯搜索全排組合；var i:integer;begin if kn 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 begin /判重，逐個按序選出需排列的數(shù)字 ak:=i /選出的數(shù)字放入數(shù)組a中； try(k+1); /回溯調(diào)用排列下一位數(shù)字; en

17、d;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）【問題描述】農(nóng)民約翰的母?？偸巧a(chǎn)出最好的肋骨。你能通過農(nóng)民約翰和美國農(nóng)業(yè)部標(biāo)記在每根肋骨上的數(shù)字認(rèn)出它們。農(nóng)民約翰確定他賣給買方的是真正的質(zhì)數(shù)肋骨，是因為從右邊開始切下肋骨,每次還剩下的肋骨上的數(shù)字都組成一個質(zhì)數(shù)，舉例來說：7 3 3 1全部肋骨上的數(shù)字7331是質(zhì)數(shù)，三根肋骨733是質(zhì)數(shù)，二根肋骨 73

18、是質(zhì)數(shù)，當(dāng)然，最后一根肋骨7也是質(zhì)數(shù)。7331 被叫做長度 4 的特殊質(zhì)數(shù)。 寫一個程序?qū)o定的肋骨的數(shù)目 N (1=Nn。 或者直接深搜19，然后條件判斷是不是質(zhì)數(shù)（素數(shù)），是則遞歸處理下一位數(shù)，不是則剪枝回溯，直到depthn。當(dāng)然在處理完該4位數(shù)是質(zhì)數(shù)后需要記錄該數(shù)?！境绦虼a】program spnumber;var s:longint; n,b:longint;function pd(x:longint):boolean; /判斷所獲得的數(shù)值是否為素數(shù)var flag:boolean; i:longint;begin flag:=true; if x=1 then flag:=fla

19、se; 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 sn then begin writeln(b) exit end; /完成符合位數(shù)要求素數(shù)搜索后，輸出該素數(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值

20、加入末尾，形成新的b值if pd(b)then dfs(s+1); /判斷新形成的數(shù)值是否是素數(shù)，是深度搜索下1位數(shù)值； s:=s-1;b:=b div 10; /恢復(fù)現(xiàn)場，為繼續(xù)加入下一個數(shù)值初始化； end; end; end;begin assign(input,spnumber.in);reset(input); assign(output,spnumber.out);rewrite(output); readln(n); /讀入數(shù)值的位數(shù) s:=1; /統(tǒng)計位數(shù) dfs(1); /搜索數(shù)值 close(input);close(output);end.3.砝碼稱重（NOIP 1996

21、 提高組weight.pas）【問題描述】設(shè)有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重6，然后直接用一維數(shù)組，記錄能夠稱重的砝碼，統(tǒng)計該數(shù)組的值，得出能夠稱重的種類。【程序代碼】program weight;var f:array0.1000of longint; /用于記錄能夠稱重的不同重量 a,w:array1.6of longint; 數(shù)組a存放砝碼的個數(shù)，數(shù)組w存放砝碼的重量 s,i:longint;procedure dfs(i:longint);var j:longint;begin if i6 then begin /完成1次6個砝碼的組合，并記錄能夠稱重的重

22、量 fs:=1;exit; end; for j:=0 to ai do begin /按不同種類的砝碼數(shù)量搜索能夠稱重的重量 s:=s+j*wi; dfs(i+1); / 進入下一類別砝碼重量的搜索 s:=s-j*wi; /恢復(fù)現(xiàn)場，為搜索下一個重量做準(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); /分別讀入砝碼的個數(shù) w1:=1;w2:=2;w3:=3; w4:=5;w5:=10;w6:

23、=20;/定義砝碼的重量 fillchar(f,sizeof(f),0); /初始化數(shù)組f； s:=0; /初始化初值s， dfs(1); /深度搜索調(diào)用過程 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è)計比賽決賽題 guide.pas）【問題描述】寧波市的中小學(xué)生們在鎮(zhèn)海中學(xué)參加程序設(shè)計比賽之余，熱情的主辦方邀請同學(xué)們參觀鎮(zhèn)海中學(xué)內(nèi)的各處景點，已知鎮(zhèn)海中學(xué)內(nèi)共有n處景點?，F(xiàn)在有n位該校的學(xué)生志愿承擔(dān)導(dǎo)游和講解任務(wù)。每個學(xué)生志愿

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

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

26、，比當(dāng)前已獲取的最小值比較，小則遞歸處理下一個數(shù)值，大或者等于則剪枝回溯，直到depthn?！境绦虼a】program guide;const maxn=50;var a:array1.maxn,1.maxnof longint; f:array1.maxnof boolean; /用于標(biāo)識景點、導(dǎo)游是否被分配過； n,i,j,ans:longint;procedure dfs(i,s:longint); var j:longint;begin if in then begin / 當(dāng)完成一次導(dǎo)游搜索組合，得出當(dāng)前最佳的得的熟悉程度值 if anss then ans:=s;exit; end

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

28、rite(output); read(n); for i:=1 to n do for j:=1 to n do beginread(ai,j); /讀入各導(dǎo)游對各景點的熟悉程度ai,j:=1000-ai,j; /變求最大值為最小值 end;fillchar(f,sizeof(f),true); /初始化布爾數(shù)組為“true” ans:=maxlongint; dfs(1,0); /深度搜索調(diào)用 writeln(n*1000-ans); /求的最大熟悉程度的值 close(output);close(input);end.5.外星生命（live.pas）【問題描述】在外太空航行的飛船拍到了某種

29、外星生命的圖像?？茖W(xué)家在研究該圖像時，把該圖像分為n行m列,共n*m個格子，每格給出了一個以整數(shù)表示的相似度的值?，F(xiàn)在請你幫助統(tǒng)計該圖像可以分成幾部分？給定一個正整數(shù)的靈敏度值x, 如果某格與某相鄰格子的相似度值的差值小于或等于x時，該格與該相鄰格子屬于同一個部件（所謂相鄰，是指上、下、左、右之一）。如下圖所示，當(dāng)靈敏度值分別為10和5時，可以分為3個部件和5個部件。1015132522502352825102502452401001051112918999104102100908810151325225023528251025024524010010511129189991041021009

30、088【輸 入】輸入文件live.in中有若干行：第一行有三個整數(shù)n、m和x,表示圖像有n行m列,設(shè)定的靈敏度為x。第二行起至第n+1行，每行有m個整數(shù)，互相間以一個空格分隔。第k+1行的第j個整數(shù)，表示圖像中第k行第j列的相似度值。【輸 出】 輸出文件live.out中只有一行，該行只有一個整數(shù)，表示可以劃分出的部件數(shù)。【樣例輸入1】 【樣例輸入2】4 6 10 4 6 5 10 15 13 252 250 235 10 15 13 252 250 23528 25 10 250 245 240 28 25 10 250 245 240 100 105 11 12 91 89 100 105

31、 11 12 91 8999 104 102 100 90 88 99 104 102 100 90 88【樣例輸出1】 【樣例輸出2】3 5【數(shù)據(jù)限制】1n,m1000【問題分析】采用方法：深度搜索。本問題的實質(zhì)就是對一個二維數(shù)組的搜索，要求在搜索的過程中求出相鄰的兩個數(shù)的差值小于等于x的連續(xù)最大區(qū)域單元格的個數(shù)以樣例1為例，以中心點10為例，可以向4個不同方向查詢。在同一行向左搜索不得小于1，向右搜索不得小于n，在同一列的搜索過程中，向上不得小于1，向下搜索不得大于m，同時在搜索的必須保證連續(xù)相鄰兩數(shù)的絕對值差值不得大于靈敏度值x,完成對二維數(shù)組的搜索，計算出符合靈敏度的區(qū)塊數(shù)量。在深度遍

32、歷的過程中，分別按照四個方向深度遍歷，在搜索遍歷過程中同時滿足三個條件：在規(guī)定的二維數(shù)組行列中搜索、該結(jié)點數(shù)據(jù)內(nèi)有被納入其他區(qū)域中和相鄰連續(xù)區(qū)域的絕對差值小于等于比當(dāng)前已獲取的最小值靈敏度值x，符合要求則遞歸處理下一個數(shù)值，不符合回溯，遍歷完所有二維數(shù)組結(jié)點?！境绦虼a】program live;var f:array1.1000,1.1000of integer; /用于存放二維數(shù)組的值； visited:array1.1000,1.1000of boolean;/標(biāo)識二維數(shù)組是否被訪問過； n,m,x,i,j,re:longint;procedure dfs(i,j:longint);/開

33、展以某點為中心，敏感度為x的上下左右搜索； begin visitedi,j:=false; if (i1) and visitedi-1,j and (abs(fi-1,j-fi,j)=x) then dfs(i-1,j); if (in) and visitedi+1,j and (abs(fi+1,j-fi,j)1) and visitedi,j-1 and (abs(fi,j-1-fi,j)=x) then dfs(i,j-1); if (jm) and visitedi,j+1 and (abs(fi,j+1-fi,j)=x) then dfs(i,j+1); end;begin a

34、ssign(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);/讀入二維數(shù)組值 re:=0;fillchar(visited,sizeof(visited),true);/初始化標(biāo)識數(shù)組 for i:=1 to n do for j:=1 to m do /按列、行逐個搜索 if visitedi,j then begin inc(re);dfs(i,j);e

35、nd;/假如該值沒有被訪問過，則作為一個區(qū)域，并開展敏感度 x的搜索； writeln(re); close(input);close(output);end.6數(shù)的拆分（snumber.pas）【問題描述】對于正整數(shù) n ，輸出其和等于 n 且滿足以下限制條件的所有正整數(shù)的和式，以及和式的總數(shù)。組成和式的數(shù)字自左至右構(gòu)成一個非遞增的序列。如n=4，程序輸出為：4=44=3+14=2+24=2+1+14=1+1+1+15【輸入文件】輸入文件snumber.in僅一行，該行只有一個正整數(shù)n(1n50)。【輸出文件】輸出文件snumber.out包含若干行，最后一行輸出和式的數(shù)目，除此之外，前面每

36、一行輸出一個和式，組成和式的數(shù)字自左至右構(gòu)成一個非遞增的序列，不同行的和式先按照等號右邊的第一個數(shù)字降序排列，若第一個數(shù)字相同，則按第二個數(shù)字降序排列，依此類推，直到輸出所有和式為止?！据斎霕永?【輸出樣例】5=55=4+15=3+25=3+1+15=2+2+15=2+1+1+15=1+1+1+1+17【問題分析】解決方法：深度搜索+調(diào)整剪枝。問題的實質(zhì)就是對輸入的n進行拆分。根據(jù)樣例建立的一顆如圖所示的搜索樹。 5 50 41 32 22 10 20 10 10 10 11 21 11 11 10 11 11 11 11第一層第二層第三層由樣例圖可知，每一組數(shù)據(jù)存在兩個數(shù)字，前一個數(shù)字為依

37、次需要拆分的數(shù)字，另一個為下一拆分起點最大數(shù)值（該數(shù)值在取值過程中需要進行適當(dāng)?shù)恼{(diào)整，與先前所拆分的數(shù)值進行比較，取兩者較小數(shù)值為再次拆分對象，即為下一層搜索對象的起始值，目的避免重復(fù)拆分?jǐn)?shù)值，進行適度調(diào)整剪枝），然后對該數(shù)值進行遞歸處理，判斷剩余的數(shù)值是否為0，是則打印，并回溯至上一層，繼續(xù)該層中其他數(shù)值的拆分。不是則按序窮舉當(dāng)前層的所有取值，并遞歸深搜下一層剩余數(shù)值的拆分。以上圖拆分5=2+2+1和5=2+1+1+1為例。首先在完成前一組數(shù)值拆分恢復(fù)現(xiàn)場，回溯窮舉至2（第一層），得第一個拆分?jǐn)?shù)值2，余下的數(shù)值5-2，即為3，剩下數(shù)值3與已拆分前一個所得數(shù)值比較取較小值2（避免5再次拆分成2

38、和3），獲得拆分?jǐn)?shù)值窮舉范圍即2-1，進入第二層搜索，首先是窮舉2，獲得第二個拆分?jǐn)?shù)值2，計算剩余數(shù)值得1，然后遞歸調(diào)拆分余下的數(shù)值1，首先判斷剩下的數(shù)值是否為0（完成拆分），不是，該數(shù)值與前一個拆分所得的數(shù)值2比較取小數(shù)值得1，獲得該數(shù)的數(shù)值拆分范圍為1-1，進入第三層搜索，取第三個拆分?jǐn)?shù)值1，同時剩下的數(shù)值減去該數(shù)值得0，遞歸調(diào)用，拆分余下的數(shù)值0，在遞歸調(diào)用過程中，發(fā)現(xiàn)剩余數(shù)值為0，遞歸調(diào)用結(jié)束，即打印該拆分?jǐn)?shù)即4=2+2+1，恢復(fù)現(xiàn)場至上一層，得剩余數(shù)值為1，再次恢復(fù)現(xiàn)場至上一層（第二層），得剩余數(shù)值為3，窮舉下一個拆分?jǐn)?shù)值1，據(jù)悉完成5=1+1+1+1+1的拆分。【程序代碼】prog

39、ram snumber;const maxn=50;var a:array0.maxnof integer; /用于存放拆分的數(shù)值； left,n:integer;變量left用于存放n拆分以后所剩下的值 total:longint;procedure dfs(k:integer);var i,min:integer;begin if left=0 then begin 當(dāng)剩下的的值為“0”時，完成一組拆分，累加 write(n,=,a1);total:=total+1; for i:=2 to k-1 do write(+,ai);writeln; end else begin if lef

40、tak-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;begin 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.

41、7.棋 盤（USACO練習(xí)題checker.pas）【問題描述】檢查一個如下的66的跳棋棋盤，有六個棋子被放置在棋盤上，使得每行、每列只有一個，每條對角線(包括兩條主對角線的所有平行線)上至多有一個棋子，如下圖所示。上面的布局可以用序列2 4 6 1 3 5來描述，第i個數(shù)字表示在第i行的相應(yīng)位置有一個棋子，如下： 行號 1 2 3 4 5 6 列號 2 4 6 1 3 5 這只是跳棋放置的一個解。請編一個程序找出所有跳棋放置的解。并以上面的序列方法輸出解（按字典順序排列）。請輸出前3個解，最后一行是解的總個數(shù)。 【輸入格式】 一個數(shù)字N (6 = N n,回溯；反之枚舉同一行中的其他列放置位

42、置。繼續(xù)判斷，一旦發(fā)現(xiàn)該行不存在合適的棋子放置位置時，同樣，回溯，修改上一行中棋子放置位置，直到遍歷棋盤中的所有的位置。問題優(yōu)化：但是這樣的搜索對于該題最后一個數(shù)據(jù)測試數(shù)據(jù)無法通過。為此可以優(yōu)化該算法?？梢酝ㄟ^考慮對稱方法。如果n是偶數(shù)，第一行枚舉前一半的數(shù)，這樣每搜索出一種方案后，沿中線對稱過來又是一種方案，并且因為第一行的數(shù)小于一半，對稱過來的方案總大于原方案，即在搜索樹中后被搜索到，不會出現(xiàn)重復(fù)的情況。 如果n是奇數(shù)，先在中間行和中間列放之，并且位置都不超過半數(shù)(n then begin if t3 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,checker.in);reset(input);assign(output,checker.out);rewrite(output);readln(n);fillchar(b,sizeof(b),