2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 深度優(yōu)先搜索和廣度優(yōu)先搜索.doc

《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 深度優(yōu)先搜索和廣度優(yōu)先搜索.doc》由會員分享，可在線閱讀，更多相關(guān)《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 深度優(yōu)先搜索和廣度優(yōu)先搜索.doc（16頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 深度優(yōu)先搜索和廣度優(yōu)先搜索 從一個簡單題目開始。 例1．輸出n個元素的無重復(fù)的全排列。（1<=n<=9） 在這里我們可以對每一個元素編號，形成1,2,…,8,9個數(shù)字的全排列。我們用一個一維數(shù)組來處理，相當(dāng)于有9個位置，每個位置可以放1到9，再進(jìn)行重復(fù)性判斷，即在每個位置放一個數(shù)字時判斷它前面是否已經(jīng)使用該數(shù)字。通過數(shù)組中元素值的變化，產(chǎn)生全排列。 下面給出非遞歸例程，其中，變量k是表示位置指針，數(shù)組x用來裝每個位置的值。 const n=5; var x:array[1..10] of integer; k:integer; {位置指針} function try:boolean; {判重函數(shù)} var i:integer; begin for i:=1 to k-1 do if x[i]=x[k] then begin try:=false;exit;end; try:=true; end; procedure out; {輸出過程} var i:integer; begin for i:=1 to n do write(x[i]); writeln; end; begin k:=1; x[1]:=0; while k>0 do begin inc(x[k]); {當(dāng)前第k個位置中增加1} if x[k]>n then {判斷當(dāng)前第k個位置中是否超界，超界指針后移一位} dec(k) else if try then {判重} begin inc(k);x[k]:=0; {前進(jìn)1位} if k>n then{判斷指針是否超界，決定一個排列是否完成,完成指針后移一位} begin out;dec(k);end; end; end; end. 下面是遞歸例程： const n=5; var x:array[1..10] of integer; function try(v1,k:integer):boolean; {判重函數(shù),v1表示位置，k表示所放的值} var i:integer; begin for i:=1 to v1-1 do if x[i]=k then begin try:=false;exit;end; try:=true; end; procedure out; {輸出過程} var i:integer; begin for i:=1 to n do write(x[i]); writeln; end; procedure search(v:integer); {v表示第v個位置} var i:integer; begin if v>n then begin out;exit;end; {若v超界，一個排列完成} for i:=1 to n do {在第v個位置上分別放1到n} if try(v,i) then {如果不重復(fù)，處理第v+1個位置} begin x[v]:=i;search(v+1);end; end; begin search(1); end. 說明：使用非遞歸的好處是節(jié)約內(nèi)存，當(dāng)一些題目對內(nèi)存消耗較大時，建議使用非遞歸方式；但使用遞歸方式在程序運(yùn)行時間上要好一些，因?yàn)樵诿總€節(jié)點(diǎn)擴(kuò)展時，遞歸方式少一個范圍超界判斷。 例題一 簡單的背包問題。 設(shè)有一個背包，可以放入的重量為s?，F(xiàn)有n件物品，重量分別為 均為正整數(shù)，從n件物品中挑選若干件，使得放入背包的重量之和正好為s。 分析：可以設(shè)定n個位置，每個位置只能放0和1，這樣形成一個0和1可重復(fù)的排列，或者是產(chǎn)生一個n位的2進(jìn)制數(shù)。 例程： var w:array[1..20] of integer; x:array[1..20] of integer; n:integer; s:longint; procedure init; var i:integer; begin readln(n,s); for i:=1 to n do read(w[i]); end; function try(v1,k:integer):boolean; {判斷目標(biāo)函數(shù),v1表示位置，k表示所放的值} var i:integer; s1:longint; begin s1:=w[k]; for i:=1 to v1-1 do s1:=s1+x[i]*w[i]; if s1=s then begin for i:=1 to v1-1 do if x[i]=0 then write(w[i], ); writeln(w[k]); end; if s1>=s then begin try:=false;exit;end; else try:=true; end; procedure search(v:integer); {v表示第v個位置} var i:integer; begin if v>n then exit;{若v超界，一個排列完成,本次選擇物品方案不成功，退出} for i:=0 to 1 do{在第v個位置上分別放0到1} if try(v,i) then{判斷所選物品之和是否大于等于s,否則處理第v+1個位置} begin x[v]:=i;search(v+1);end; end; begin init;search(1); end. 說明：本文用全排列進(jìn)行引入DFS搜索,目的是表明DFS有一定的模式，如下： procedure search(v:integer；相關(guān)形參); {v表示當(dāng)前擴(kuò)展節(jié)點(diǎn)層數(shù)（或者叫深度）} {過程定義的變量表} begin if <超界條件> then begin out;exit;end; {若v超界，out來作超界處理} 形成某種節(jié)點(diǎn)擴(kuò)展程序段（例如：for i:=1 to n do） if 〈判斷所到節(jié)點(diǎn)的算法函數(shù)或條件〉 then {例如判重} begin 當(dāng)前節(jié)點(diǎn)處理； search(v+1); {處理下一個層數(shù)} end; end; 例題二 給出一個自然數(shù)n( ),把n分解為若干個大于1的自然數(shù)之乘積。請編寫程序找出所有的分解方案。 分析：此題目的關(guān)鍵是怎樣產(chǎn)生需要擴(kuò)展的各個節(jié)點(diǎn)。不難看出乘積為n的若干自然數(shù)，剛好都是n的約數(shù)。因此其分解方案變成了求這些約數(shù)的不同組合（元素可重復(fù)），問題得到解決。 例程： var y:array[1..50] of longint; {用來存放n的所有約數(shù)} x:array[0..50] of integer; {用來存放組合數(shù)的對應(yīng)n的約數(shù)所在位置值} n:longint; xlen:integer; procedure init; var i,j,t:longint; k:integer; begin fillchar(x,sizeof(x),0); x[0]:=1; xlen:=0; for i:=2 to trunc(sqrt(n)) do {找出n的所有約數(shù)} if n mod i=0 then begin inc(xlen);y[xlen]:=i;inc(xlen);y[xlen]:=n div i; if i=n div i then {對完全平方數(shù)的處理} dec(xlen); end; for i:=1 to xlen-1 do {為保證輸出方案由小到大的順序，進(jìn)行排序處理} begin k:=i; for j:=i+1 to xlen do if y[k]>y[j] then k:=j; t:=y[i];y[i]:=y[k];y[k]:=t; end; end; function try(v1,k:integer):boolean; {判定所選約數(shù)之乘積與n的關(guān)系} var i:integer; t:longint; begin t:=y[k]; for i:=1 to v1-1 do t:=t*y[x[i]]; if t=n then {與n剛好相等，輸出一種方案} begin for i:=1 to v1-1 do write(y[x[i]], ); writeln(y[k]); end; if tm then begin for i:=1 to m do write(x[i]); writeln;exit; end; for i:=x[v-1]+1 to n do begin x[v]:=i;search(v+1);end; end; begin readln(n,m); fillchar(x,sizeof(x),0); search(1); end. 另外，如果該題目改成： 給出一個自然數(shù)n( ),把n分解為若干個大于1的自然數(shù)之乘積。請編寫程序求出所有的分解方案總數(shù)。 可用如下方法，供大家參考： var n,t:longint; function search(a,min:longint):longint; var i,s:longint; begin s:=0; for i:=min to trunc(sqrt(a)) do if a mod i=0 then s:=s+search(a div i,i); search:=s+1; end; begin readln(n); t:=search(n,2)-1; writeln(t); end. 例題三 圖論中的遍歷問題，例如圖論中單源點(diǎn)之間的最短通路問題。 問題：設(shè)有n個城市分布在若干地理位置，某兩個城市存在一條通道，給出這兩個相通城市之間的距離，求一個城市到另一個城市的最短距離。如下圖： 兩個城市之間的如果不相通其距離我們設(shè)定為零，否則它們的距離。數(shù)據(jù)提供方式我們用鄰接矩陣。 6 0 4 8 0 0 0 4 0 3 4 6 0 8 3 0 2 2 0 0 4 2 0 4 9 0 6 2 4 0 4 0 0 0 9 4 0 分析：本題目我們就定義求c1到c6之間的最短距離，可以對每一個點(diǎn)進(jìn)行編號，然后用一個二維數(shù)組來存放鄰接矩陣，用本文所述的DFS的固定模式就可以得出本題目的算法。例程如下。 const infile=xx.txt; {數(shù)據(jù)文件} var y:array[1..10,1..10] of integer; {存放鄰接矩陣} x:array[1..10] of integer; {存放各點(diǎn)的編號} xbak:array[1..10] of integer; {存放當(dāng)前最短路徑的順序各點(diǎn)} n:integer; {點(diǎn)數(shù)目} slen:longint; {最短路徑值} i:integer; procedure init; var i,j:integer; begin assign(input,infile); reset(input); readln(n); for i:=1 to n do for j:=1 to n do read(y[i,j]); close(input); end; procedure out(vv:integer); var i:integer; s:longint; begin s:=0; for i:=1 to vv-1 do inc(s,y[x[i],x[i+1]]); if sn then exit; for i:=2 to n do if try(v,i) then begin x[v]:=i;search(v+1);end; end; begin init; {讀取數(shù)據(jù)} slen:=maxlongint; {設(shè)最短路徑值為最大} x[1]:=1; {固定從編號為1的位置} search(2); {從第2個位置開始搜索} writeln(slen); {輸出結(jié)果} i:=1; while xbak[i]>0 do begin write(xbak[i], );inc(i);end; writeln; end. 大家可以把這個題目改成從一個點(diǎn)，到某幾個點(diǎn)的最短路徑。 這類問題也可以用E.W.Dijkstra方法來做，并且其時間效率要高一些。 深度搜索有一定固定模式，但其變種還很多，就其實(shí)質(zhì)來說是“怎樣構(gòu)造一棵用來搜索的樹(tree),然后對這棵樹(tree)進(jìn)行高效率的剪支”，更重要的是對題目描述的問題建立科學(xué)合理的數(shù)學(xué)模型。 二、廣度搜索（BFS） 入門例題： 給出一個由1，2，3，4，5，6組成的6位數(shù)，相鄰的兩個數(shù)字可以交換位置，問最少經(jīng)過多少次交換，可以到達(dá)另一個目標(biāo)6位數(shù)。例如： 對于123456，最少經(jīng)過兩次交換，可以變成231456。 分析：這個題目與前面講過的深度搜索相比有一個明顯不同，會出現(xiàn)“又回去了”的情況（產(chǎn)生樹的分支有連通的情況），例如：由123456可以變成213456，而213456又可以變成123456，這樣形成了循環(huán)。所以需要我們用廣度搜索來完成，需要的預(yù)備知識是《數(shù)據(jù)結(jié)構(gòu)》中的隊(duì)列。關(guān)鍵點(diǎn)在“最少次數(shù)及解決樹的分支連通問題”。 例程： const n=6; var p1:integer; {隊(duì)列出列指針,指向openx表} p2:integer; {隊(duì)列入列指針, 指向openx表} openx:array[1..1000] of string[n]; {存放已經(jīng)出現(xiàn)過的6位數(shù)} openy:array[1..1000] of integer; {存放樹(tree)的前綴層數(shù),即當(dāng)前移動次數(shù)} st1:string; {初始狀態(tài)，一個6位數(shù)} st2:string; {目標(biāo)狀態(tài)，一個6位數(shù)} st:string; i:integer; tc:char; function find(stx:string):boolean; {對生成新的狀態(tài)進(jìn)行判重} var i:integer; begin for i:=1 to p2 do if stx=openx[i] then begin find:=false;exit;end; find:=true; end; procedure out; {結(jié)果輸出} begin writeln(openy[p1+1]); halt; end; begin readln(st1); readln(st2); p1:=1;p2:=1;openx[1]:=st1; {初始設(shè)置} fillchar(openy,sizeof(openy),0); while p1<=p2 do begin for i:=1 to n-1 do {對當(dāng)前x[p1]狀態(tài)，生成所有有效分支} begin st:=openx[p1]; tc:=st[i];st[i]:=st[i+1];st[i+1]:=tc; {交換位置I和i+1中的數(shù)字} if st=st2 then {達(dá)到目標(biāo)狀態(tài)，轉(zhuǎn)向結(jié)果輸出} out; if find(st) then {判重} begin inc(p2);openx[p2]:=st; {隊(duì)列入列操作} openy[p2]:=openy[p1]+1; {取得當(dāng)前樹的擴(kuò)展層數(shù),即：移動次數(shù)} end; end; inc(p1); {隊(duì)列出列操作} end; end. 有一些資料的描述是，把隊(duì)列放在一個獨(dú)立的線性表中，上面的程序是直接把隊(duì)列放在數(shù)組openx中，這樣節(jié)約一些空間。顯然DFS的時間效率體現(xiàn)在“判重”的算法上，提高時間效率方法很多，其中hash表是重要的一種算法，請參看相關(guān)資料。 例題二 有10升油在10升的容器中，另有兩個7升和3升的空容器，要求用這三個容器倒油，使得最后在10升和7升的容器中各有5升油，問最少的倒油次數(shù)是多少？ var a:array[1..3] of integer; {每個容器的容量} x:array[1..1000,1..3] of shortint; {存放已經(jīng)出現(xiàn)過的狀態(tài)} y:array[1..1000] of integer; {存放樹(tree)的前綴層數(shù),即當(dāng)前倒油次數(shù)} b:array[1..3] of integer; {目標(biāo)狀態(tài)} c:array[1..3] of integer; p1:integer; p2:integer; i,j,t:integer; pt:boolean; procedure init; begin assign(input,xx1.txt); reset(input); readln(a[1],a[2],a[3]); readln(x[1,1],x[1,2],x[1,3]); {讀取初始狀態(tài)} readln(b[1],b[2],b[3]); {讀取目標(biāo)狀態(tài)} close(input); end; procedure out; begin writeln(y[p1]+1); halt; end; function find:boolean; var i:integer; begin for i:=1 to p2 do if (c[1]=x[i,1]) and (c[2]=x[i,2]) and (c[3]=x[i,3]) then begin find:=false;exit;end; find:=true; end; begin init; fillchar(y,sizeof(y),0); p1:=1;p2:=1; while p1<=p2 do begin for i:=1 to 3 do {對當(dāng)前x[p1…]狀態(tài)，生成所有有效分支} for j:=1 to 3 do if i<>j then begin for t:=1 to 3 do c[t]:=x[p1,t]; pt:=false; if c[i]+c[j]<=a[j] then {從i到j(luò)全部倒完} begin c[j]:=c[j]+c[i];c[i]:=0;pt:=true;end; if (c[j]=0) and (pt=false) then {只能倒一部分} begin c[i]:=c[i]-(a[j]-c[j]);c[j]:=a[j];pt:=true; end; if pt then begin if (c[1]=b[1]) and (c[2]=b[2]) and (c[3]=b[3]) then out; {到達(dá)目標(biāo)輸出} if find then {判重} begin inc(p2); {隊(duì)列入列操作} for t:=1 to 3 do x[p2,t]:=c[t]; {取得當(dāng)前樹的擴(kuò)展層數(shù),即：倒油次數(shù)} y[p2]:=y[p1]+1; end; end; end; inc(p1); {隊(duì)列出列操作} end; end.