幾近萬能的算法

1、幾近萬能的算法1知識(shí)準(zhǔn)備1、分階段決策2、狀態(tài)3、方案4、決策2了解深度優(yōu)先搜索法1、degree first serch2、在每個(gè)階段的決策時(shí)，采取能深則深的原則試探所有可行的方案，一旦深入一層則保存當(dāng)前操作引起的狀態(tài)3、一旦試探失敗，為了擺脫當(dāng)前失敗狀態(tài)，采取回到上一階段嘗試下一方案的策略（回溯策略）；或者在求解所有解時(shí)，求得一個(gè)解后，回溯到上一階段嘗試下一方案，以求解下一個(gè)解4、在各個(gè)階段嘗試方案時(shí)，采取的是窮舉的思想3引題1 【例1】采摘果子。有如下圖所示的一棵果樹，圖中的結(jié)點(diǎn)表示樹上的果子，結(jié)點(diǎn)左邊的數(shù)字表示結(jié)點(diǎn)的編號(hào)，里面的權(quán)值就是果子的重量，現(xiàn)在果農(nóng)想把某條樹枝的果子全部采摘下來

2、，并保證被采摘果子的總重量是所有樹枝中最大的。問，這條樹枝上所有果子的總重量是多少？45 輸入文件fruit.in共包含了n2行，其中n表示圖中果子的個(gè)數(shù)，第一行的一個(gè)整數(shù)表示果樹中果子的數(shù)量，第2n行表示各果子之間的連接關(guān)系（用鄰接表表示），最后一行依次表示了各個(gè)果子自身的重量，用n個(gè)用空格隔開的整數(shù)。輸出文件fruit.out只包含一個(gè)整數(shù)，表示某條樹枝上所有果子的重量（是所有樹枝中果子總重量最大的那根樹枝）。6fruit.in181 2 3 4 02 5 6 03 7 8 04 9 10 05 11 12 06 13 07 14 15 08 09 010 16 011 17 012 01

3、3 014 015 016 017 18 018 02 5 30 6 3 22 29 28 10 11 4 9 24 33 8 21 7 1fruit.out9471、分析樣例數(shù)據(jù)2、樣例數(shù)據(jù)如何來求解3、窮舉什么？4、窮舉實(shí)現(xiàn)的方式81、A1,3=3表示1號(hào)結(jié)點(diǎn)的第2個(gè)兒子是3號(hào)結(jié)點(diǎn)，AI,1表示結(jié)點(diǎn)本身。用一維數(shù)組W表示每個(gè)結(jié)點(diǎn)的重量信息。 2、狀態(tài)保存及繼續(xù)深入。tot:=tot+waI,j，繼續(xù)往下搜索，用語句fruit(aI,j)來實(shí)現(xiàn)3、回溯處理。tot:=tot-wai,j；為下一次搜索作準(zhǔn)備，就是inc(j)。 9數(shù)據(jù)輸入for i:=1 to n do begin j:=0;

4、 repeat inc(j);read(fin,ai,j); until ai,j=0; readln(fin); end; for i:=1 to n do read(fin,wi);close(fin);10tot:=tot+w1;fruit(1);Procedure fruit(i:byte); j:=2; if ai,j=0 then begin if maxtottot then maxtot:=tot;exit;end else begin while ai,j0 do begin tot:=tot+wai,j;fruit(ai,j);tot:=tot-wai,j; j:=j+1;

5、 end; end;11Dfs算法小結(jié)1、dfs的算法思想2、狀態(tài)改變及現(xiàn)場保存3、回溯處理及現(xiàn)場恢復(fù)4、什么時(shí)候須進(jìn)行回溯處理？5、各個(gè)階段當(dāng)前須嘗試的方案選擇（第一個(gè)方案開始？還是接著原來方案的下一個(gè)方案？）6、遞歸程序結(jié)構(gòu)12遞歸結(jié)構(gòu)框架Procedure try(i:integer);Var k:integer;Begin If 所有階段都已求解 then Begin 比較最優(yōu)解并保存；回溯；endelse begin 窮舉當(dāng)前階段所有可能的決策（方案、結(jié)點(diǎn)）k if k方案可行 then begin 記錄狀態(tài)變化；try(i+1);狀態(tài)恢復(fù)（回溯）； end end;End;13承上

6、啟下1【例2】【題目描述】 列出所有從數(shù)字1到數(shù)字n的連續(xù)自然數(shù)的排列，要求所產(chǎn)生的任一數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字?！据斎敫袷健恐挥幸粋€(gè)整數(shù)n(1n9)【輸出格式】由1n組成的所有不重復(fù)的數(shù)字序列，每行一個(gè)序列，數(shù)字之間用空格隔開?！据斎霕永?【輸出樣例】1 2 31 3 22 1 32 3 13 1 23 2 114算法分析1、不能再用原來的窮舉法2、本題算法思考（1）每個(gè)階段指什么？各個(gè)階段須完成什么任務(wù)？（2）各個(gè)階段試探的方案是什么？15主程序結(jié)構(gòu)var n:integer; a:array1.9 of integer; f:array1.9 of boolean; 用于記錄是否

7、重復(fù)begin fillchar(f,sizeof(f),false); readln(n); try(1);end.16輸出子過程procedure print; var i:integer; begin for i:=1 to n do if in then write(ai, ) else writeln(an); end;17深度搜索子過程procedure try(i:integer); var j:integer; begin if in then print else for j:=1 to n do if not fj 如果j沒有被使用,則繼續(xù) then begin ai:=j

8、; 放入一個(gè)數(shù)j fj:=true; 標(biāo)記該數(shù)已經(jīng)使用 try(i+1); 繼續(xù)放下一個(gè)數(shù) fj:=false; 回溯時(shí)重置使用標(biāo)記 end; end;18引題2 【例4】選擇最短路徑。有如下所示的交通路線圖，邊上數(shù)值表示該道路的長度，編程求從1號(hào)地點(diǎn)到達(dá)7號(hào)地點(diǎn)的最短的路徑長度是多少，并輸出這個(gè)長度。19與“引題1”不同的地方？201、是一個(gè)顯式圖2、權(quán)值是邊權(quán)3、需要判重處理21數(shù)據(jù)結(jié)構(gòu)1、鄰接矩陣表示圖的連接和權(quán)值。AI,j=x,或者aI,j=maxint。Bi表示結(jié)點(diǎn)i是否已經(jīng)遍歷過2、用變量min來保存最優(yōu)解，而用tot變量保存求解過程中臨時(shí)解（當(dāng)前路徑總長度）。3、狀態(tài)。Tot的值

9、和結(jié)點(diǎn)的遍歷標(biāo)志值22程序結(jié)構(gòu)1、遞歸結(jié)構(gòu)2、主程序中用try(1)調(diào)用遞歸子程序 3、子程序結(jié)構(gòu)23procedure try(I:integer);var k:integer;begin if 到達(dá)了終點(diǎn) then begin 保存較優(yōu)解；返回上一點(diǎn)繼續(xù)求解（回溯）；end else begin 窮舉從I出發(fā)當(dāng)前可以直接到達(dá)的點(diǎn)k； if I到k點(diǎn)有直接聯(lián)邊 并且 k點(diǎn)沒有遍歷過 then then begin 把AI,K累加入路徑長度tot;k標(biāo)記為已遍歷；try(k); 現(xiàn)場恢復(fù)； end; end;24關(guān)鍵環(huán)節(jié)的分析1、遞歸結(jié)束的判斷2、保存較優(yōu)解的處理3、各個(gè)階段可試探方案的窮舉和

10、可行性判斷25主程序數(shù)據(jù)輸入 readln(fi,n); for i:=1 to n do begin for j:=1 to n do read(fi,ai,j); readln(fi); end; close(fi);26主程序預(yù)處理和調(diào)用子程序tot:=0;min:=maxint;b1:=1;try(1);writeln(tot=,min);27procedure try(i:integer);var k:integer;begin if i=n then begin if totmin then min:=tot;exit;end else begin for k:=1 to n do

11、 if (bk=0) and (ik) and (ai,k32700) then begin bk:=1;tot:=tot+ai,k;try(k);bk:=0; tot:=tot-ai,k; end; end;end;28遞歸子程序結(jié)構(gòu)if i=n+1 then begin 輸出解；返回；endelsefor c:=A to chr(64+m) dobegin if c 可以放置 then begin 把c放置到位置1上;try(i+1)；狀態(tài)恢復(fù)；end end;29承上啟下2 【例4】郵票問題2。郵局發(fā)行一套有n種不同面值的郵票，如果限制每封信所貼的郵票張數(shù)不能超過m枚。存在整數(shù)R，使得用

12、不超過m枚的郵票可以貼出一下連續(xù)序列：1，2，3，4，5，.,R。 編程求出可以得到盡可能大的R值以及對應(yīng)的n種郵票面值。 30求同思維想想原來郵票問題1是如何求解的？311、窮舉所有郵票可能的面值組合2、進(jìn)一步窮舉每種郵票可能貼的數(shù)量3、根據(jù)1、2的窮舉計(jì)算當(dāng)前方案可能的最大連續(xù)r值4、每產(chǎn)生一個(gè)r值后和原來rmax比較，保存較優(yōu)解32主程序s1:=1;rmax:=0;f:=0;writeln;write(n,m=);readln(n,m);try(1); 首次調(diào)用過程，開始窮舉郵票面值for o:=1 to n do write(go:4); 輸出每種郵票的面值writeln;writel

13、n(rmax=,rmax);33procedure try(i:integer);varj,temp,l:integer;beginfor j:=si-1+1 to m*si-1+1 do beginsi:=j; if i=n then begin f:=0;stamp:=;work_out_r(1,m);temp:=1; while temp in stamp do temp:=temp+1;if rmaxtemp-1 thenfor l:=1 to n do begin gl:=sl;rmax:=temp-1;end;endelse try(i+1); end;end;34procedur

14、e work_out_r(i1,ej:integer);vark:integer;beginfor k:=0 to ej do beginf:=f+k*si1; if i1=n then stamp:=stamp+f else work_out_r(i1+1,ej-k);f:=f-k*si1; end;end;35Dfs的應(yīng)用和優(yōu)化1、何時(shí)考慮用dfs？2、適用的題型3、出解的方式4、優(yōu)化策略36network 多臺(tái)計(jì)算機(jī)相互連接，構(gòu)成計(jì)算機(jī)網(wǎng)絡(luò)。在這個(gè)問題中，我們只考慮“線性”的網(wǎng)絡(luò)：計(jì)算機(jī)首尾相連，構(gòu)成一條計(jì)算機(jī)的鏈，除了首尾2臺(tái)計(jì)算機(jī)外，每臺(tái)計(jì)算機(jī)恰與2臺(tái)計(jì)算機(jī)相連。計(jì)算機(jī)的物理位置可以

15、用直角坐標(biāo)表示。在施工時(shí)，電纜將被埋在地下，因此連接網(wǎng)絡(luò)中2臺(tái)計(jì)算機(jī)所需的電纜長度等于他們之間的距離再加上額外的16米，以便從地下連接到計(jì)算機(jī)，并為施工留些余量。 出于經(jīng)濟(jì)、技術(shù)等方面的考慮，要求所使用的電纜總長度盡可能地短。寫一個(gè)程序，幫助尋找最優(yōu)的網(wǎng)絡(luò)連接方案。 輸入和輸出 輸入文件的第一行是一個(gè)整數(shù)，表示計(jì)算機(jī)的總數(shù)。網(wǎng)絡(luò)中包括至少2臺(tái)，至多10臺(tái)的計(jì)算機(jī)。接下來的每一行將給出1臺(tái)計(jì)算機(jī)的橫坐標(biāo)和縱坐標(biāo)，中間用空格隔開。坐標(biāo)值是0到150的整數(shù)。在一個(gè)坐標(biāo)點(diǎn)上不會(huì)有2臺(tái)計(jì)算機(jī)。 輸出只有一行，給出你的程序所找到的最優(yōu)連接方案所需電纜的總長度。結(jié)果四舍五入保留2位小數(shù)。37輸入文件：65

16、1955 2838 10128 62111 8443 116輸出文件：3054538主程序 readln(fin,n);min:=32650; for i:=1 to n do readln(fin,xi,yi); close(fin); for i:=1 to n do bi:=0; s:=0;j:=1; for i:=1 to 6 do begin bi:=1; try(i,j); bi:=0; s:=0; end;39子程序procedure try(i,j:byte);var k:integer;begin if j=n then begin if smin then continue

17、; s:=s+f(i,k); bk:=1; try(k,j+1); s:=s-f(i,k);bk:=0; end;end;40是否還存在優(yōu)化的素材？41隱式圖的dfs求解 在N*N的棋盤上(1=N=10)填入1,2,.N*N共N*N個(gè)數(shù),使得任意兩個(gè)相鄰的數(shù)之和為素?cái)?shù). 例如,當(dāng)N=2時(shí),有 1 2 4 3 Input 輸入第一行為一整數(shù)T,表示有T組測試數(shù)據(jù). 每組測試數(shù)據(jù)一行,為一整數(shù)N(1=N=10) Output 輸出滿足條件的最小序列的方案。 最小序列即將每一行連接起來組成一行，然后使前面的盡可能小，當(dāng)?shù)谝粋€(gè)數(shù)字相同時(shí)則比較下面一個(gè)，依次類推。 比如當(dāng)時(shí)，序列為1 2 4 3，當(dāng)無滿

18、足條件的方案時(shí)輸出NO。 42Sample Input1 2 Sample Output1 2 4 3 43算法整理1、總的算法考慮2、素?cái)?shù)如何判斷3、階段表示4、各個(gè)階段方案的枚舉5、各個(gè)階段當(dāng)前方案可行的判斷44篩法判斷素?cái)?shù)fillchar(d,sizeof(d),1);d1:=false;for i:=2 to 200 doif di then begin j:=i; while j200-i do begin j:=j+i; dj:=false; end;end;45主程序readln(t); for h:=1 to t do begin fillchar(f,sizeof(f),0); flag:=false; f1:=1; readln(n);m1,1:=1; solve(1,2); if flag then 判斷是否有解 print 打印 else writeln(NO); end;46Dfs子程序procedure