搜索相關算法學案

1、搜索相關算法 無論什么類型的題目，只要能歸納出數(shù)學模型，我們就盡量用解析方法來求解。因為一個好的數(shù)學模型建立了客觀事物間準確的運算關系，運用這個數(shù)學模型求接求解是再合適不過的了。當然，這僅是一種可能性，因為并非所有編程者都能在有限的時間內(nèi)把問題分析得如此透徹，并非所有給定的問題都能建立數(shù)學模型，即使有了數(shù)學模型，也不一定能立即運用現(xiàn)成算法。因此在某些情況下，還需要通過搜索（列舉所有可能情況）來尋求問題的解。一、枚舉法枚舉（也稱窮舉），是程序設計中常見的一種算法，它利用計算機運算速度快、精度高的特點，對問題的所有可能情況，一個不漏地（最好也不重復）依次進行檢查，從中找出符合要求的合理解。枚舉法常

2、用于解決“是否存在”或“有多少種可能”等類型的問題。枚舉法算法比較簡單，但當需要枚舉的可能情況較多時，執(zhí)行枚舉算法的工作量將會很大。因此，在用枚舉法設計算法時，應重點注意使方案優(yōu)化，盡量減少運算工作量。通常，只要對實際問題作詳細的分析，將與問題有關的知識條理化、完備化、系統(tǒng)化，從中找出規(guī)律，或對所有可能的情況進行分類，引出一些有用的信息，枚舉量是可以減少的。例1 今天是星期幾A、B、C、D、E、F、G七個人爭論今天是星期幾A：后天是星期三 B：不對，今天是星期三 C：你們都錯了，明天是星期三 D：今天既不是期二也不是星期三，更不是星期五 E：我確信昨天是星期五 F：明天是星期六 G：不管怎樣，

3、昨天不是星期六他們之中只有一個人講的對，是哪一個？今天到底是星期幾？算法分析讓計算機進行推理工作，是人工智能研究的重要課題。機器推理的一般方法是：先窮舉所有可能解，再來逐一檢驗可能有解是不是真正的解。我們先假定今天是星期一，然后逐一判斷七人誰說對誰說錯，若今天不是星期一，再假定是星期二，重復以上操作，直到找出正確解。程序清單 今天是星期幾program exam1;const weekday:array0.6 of string=(Sunday,Monday,Tuesday,Wednesday,Thursday,Friday,Saturday);var todayno, num, i:byte

4、; ok:Boolean;today, tomorrow, aftertomorrow, yesterday:string; man:array0.6 of byte;begin for todayno:=0 to 6 do begin /窮舉今天 fillchar(man, sizeof(man), 0); today:=weekdaytodayno; yesterday:=weekday(todayno+6) mod 7; /計算昨天1 / 7 tomorrow:=weekday(todayno+1) mod 7; aftertomorrow:=weekday(today+2) mod 7

5、; if aftertomorrow=Wednesday then man0:=1; /A說的話：后天是星期三 if today=Wednesday then man1:=1; if tomorrow=Wednesday then man2:=1; if (today<>Tuesday) and (today<>Wednesday) and (today<>Friday) then man3:=1; if yesterday=Friday then man4:=1; if tomorrow=saturday then man5:=1; if yesterda

6、y<>Saturday then man6:=1; num:=0; for i:=0 to 6 do num:=num+mani; if num=1 then begin writeln(today is , weekdaytodayno, .); ok:=true; end;end; if not ok then writeln(No solution.);end.例236塊磚36個人搬，男搬4女搬3，2個小兒抬1磚，要求1次全搬完，問需男、女、小兒各多少？算法分析男、女、小兒的人數(shù)可以分別記作M、W、C，它們的取值范圍分別是0，36，0，36，0，36且C必須是偶數(shù)。合理解需要

7、滿足的條件：36人：M+W+C=36 36磚：M*4+W*3+C/2=36（程序略）開 始 （M，W，C）第一重循環(huán)M （0,*,*） (1,*,*) (,*,*) (36,*,*)第二重循環(huán)W (0,0,*) (0,*) (0,36,*) (36,0,*) (36,*) (36,36,*)第三重循環(huán)C (0,0,0) (0,0,2) (0,0, ) (0,0,36) (0,1,0) (0,1,2) (0,1,) (0,1,36) () (36,36,36)解空間(規(guī)模：37*37*19=26011解生成樹由上圖得知逐一將M、W、C從0枚舉到36顯然不是最佳方法（枚舉量大）優(yōu)化策略一 剪枝由M

8、*4+W*3+C/2=36 容易看出：M0，9 W0，12，由此得出更強的結論：M0，9 W0，12 C0，2，4，6，8，36優(yōu)化后解的空間大小是10*13*19=2470個可能解，不到基本算法的10%，這就是一種很強的估化策略（去掉了原來解中90%的分支和葉子，而這些被剪掉的枝葉中沒有可能解，全是不可能解）。這種通過精簡循環(huán)變量的取值范圍從而減少搜索算法的策略，通常稱為剪枝。優(yōu)化策略二 降維本題有3個未知量，但只有2個方程，這種未知量的個數(shù)多于方程的個數(shù)，我們把這樣的方程（組）長為不定方程（組）。如果我們把未知量的個數(shù)減去方程的個數(shù)所得的差，稱為不定方程的維數(shù)，那么本例就是一維不定方程，純

9、粹的不定方程，有無窮多個解，但對于具體問題，往往存在一些隱含限制（如本例中的人數(shù)必須是非負整數(shù)，小兒的人數(shù)還必須是偶數(shù)），使解的個數(shù)成為有限個。本題可以抽象為如下的數(shù)字模型M+W+C=36 M*4+W*3+C/2=36 M、W、C為非負整數(shù)兩個方程聯(lián)立，可以消去一個未知量（如C），得7*M+5*W=36 從而可以得出結論M0，5 W=（36-7*M）/5（前提36-7*M是5的倍數(shù)） C=36-M-W這樣本題只需要一維循環(huán)來枚舉M，減少了循環(huán)層次，這種策略通常稱為降維。小結使用窮舉法的基本前提是可能解的個數(shù)必須是有限的，同時還要考慮計算機運行時所占存儲空間和所耗時間必須是可接受的。用窮舉算法解

10、決問題，要分析：（1）解的結構（解的分量（變元）個數(shù)）和可能有解的規(guī)模（界定各分量的取值范圍）（2）可能解的生成（用什么方法生成或遍歷所有可能解，既無遺漏，又不重復）？（3）算法優(yōu)化枚舉算法的時間復雜度可以用狀態(tài)總數(shù)*考察單個狀態(tài)的耗時來表示，因此優(yōu)化主要是：a降少狀態(tài)總數(shù)（即減少枚舉變量和枚舉變量的值域）；b（降低單個狀態(tài)的考察代價）優(yōu)化過程從以下幾個方面考慮a提取有效信息；b減少重復計算；c將原問題化為更小的問題；d根據(jù)問題的性質(zhì)進行截枝；e引進其他算法。練習：1設有下列的算式_ 2 0 8 ) 1程序要求：求出中的數(shù)字，并打印出完整的算式來。2酒廠選址某島的居民們酷愛一種無酒精啤酒。以前

11、這種啤酒都是從波蘭進口，但今年居民們想建一個自己的啤酒廠。島上所有的城市都座落在海邊，并且由一條沿海岸線的環(huán)島高速路連接，酒廠的投資者收集了關于啤酒需求量的信息，即每天各城市消費的啤酒桶數(shù)。另外還知道相鄰城市間的距離。每桶啤酒每千米的運費是1元。日運費是將所需要的啤酒從酒廠運到所有城市所需的運費之和。日運費的多少和酒廠的選址有關。投資者想找到一個合適的城市來修建酒廠，以使得日運費最小。任務：設計一個程序，讀入城市的數(shù)目、相鄰兩城市間的距離及每個城市消費的啤酒桶數(shù)，計算和輸出最小的日運費。輸入：第1行是一個整數(shù)n（5<=n<=10000），表示城市的數(shù)目。城市沿高速路編號，使得相鄰城

12、市的編號也相鄰（城市1和n也被認為是相鄰的）。以下的n行，每行有兩個非負整數(shù)，第i+1行的數(shù)zi和di分別是城市i每日的啤酒消費量（桶）和從城市i沿高速路到下一個城市的距離（千米）。高速路的總長不會超過1000000千米。每座城市的日消費量不會超過1000桶。輸出：唯一一行應該是一個整數(shù)，表示所需的最小日運費（元）。 枚舉方法簡析枚舉過程一般較簡單，變化較少。如：需枚舉的變量較少，循環(huán)的層數(shù)固定，每一個變量的枚舉范圍相對固定，可循的數(shù)學規(guī)律較少、較簡單，且不能加撤，即不能回溯，更嚴格的說，單純的枚舉只以算一種思想，而不是能單獨解決問題的一種算法。搜索從本質(zhì)上來說是枚舉，但搜索更靈活，更能體現(xiàn)智

13、能邏輯的魅力，其于枚舉思想的搜索較其“母體”有許多不可替代的優(yōu)勢，如：循環(huán)的層數(shù)是可變化的，動態(tài)的，可以把抽象的、復雜的數(shù)學邏輯規(guī)律統(tǒng)一起來，簡便地對枚舉遍歷過程進行管理，同時也可以利用這些規(guī)律方便地減少枚舉量。搜索可以分為深度優(yōu)先搜索和廣度優(yōu)先搜索。二回溯搜索回溯算法是一種盡早剪枝的深度優(yōu)先搜索算法。回溯算法是所有搜索算法中最為基本的一種算法，是按照深度優(yōu)先的順序來擴展結點，其采用了一種“走不通就掉頭”的思想。有些問題在往下一步搜索時，每一步都出現(xiàn)很多個分支，為了求得問題的解，我們必須對每一個分支都要試探，看看是否符合題設的約束條件（有時也稱為約束函數(shù)），若發(fā)現(xiàn)某一步試探過程中確認其不合條件

14、，則從此處往下的試探不必再繼續(xù)進行下去，而是立即返回到上一步去試探其他分支（我們稱為回溯），直到找到問題的解。如果回溯到問題的初始狀態(tài)后還要返回，則表示問題無解。 回溯法的算法框架（偽代碼）：procedure run(當前狀態(tài));var i:integer; if 當前狀態(tài)為邊界 then if 當前狀態(tài)為最佳目標狀態(tài) then 記下最優(yōu)結果； exit; /回溯/ for i算符最小值 to 算符最大值 do 算符i作用于當前狀態(tài)，擴展出一個子狀態(tài)； if （子狀態(tài)滿足約束條件） and （子狀態(tài)滿足最優(yōu)要求）then run(子狀態(tài))； 例N皇后問題在一個N*N的國際象棋棋盤上，放置N個

15、皇后，為使它們和平共處，規(guī)定：所有皇后不能處于同一行、同一列、同一對角線，求出能放置N個皇后的所有可行的布局。輸入一個整數(shù)N（2<=N<=20）。輸出一個整數(shù)，表示N皇后問題的可行布局的總數(shù)算法分析（1）判定條件 計算機如何判定兩個棋子是否在同一行、同一列或同一對角線上？用坐標表示每個格子的位置。顯然，對于兩個格子(i1,j1)(i2,j2)，若i1=i2，它們在同一行，若j1=j2，它們在同一列，|i2-i1|=|j2-j1|，則它們在同一條對角線上，我們創(chuàng)建一個函數(shù)try(i，j)，測試位置(i, j)上是否可以放置皇后。（2）數(shù)據(jù)結構 如何表達布局？用一個二維數(shù)組來記錄每個布

16、局，如Ai,j=0表示位置（i,j）上未放皇后，Ai,j=1表示位置（i,j）上放置了皇后，同時，由于每列只能放一個皇后，因此用一個一維數(shù)組X記錄布局，其中Xj記錄第j列的皇后的行號，如X1=6表示第1列的皇后在第6行。（3）算法討論 設1到（j-1）個皇后已經(jīng)放妥，下面將第j個皇后放入到第j列，用過程place(j)來完成：若j>N，則已找到一個可行的方案，輸出；否則，用循環(huán)語句依次從第1行至第N行試放，若不與前j-1個皇后沖突，則把第j個皇后放在該行，再遞歸調(diào)用place(j+1)來放置第j+1個皇后。程序清單 N皇后問題program pro1;const maxn=20;var

17、n:byte; count:longint; x:array1.maxn,1.maxn of integer;procedure print; var j:byte;begin inc(count); for j:=1 to n do write(xj:4); writeln(solution:, count);end;function try(i,j:byte):Boolean;var k:byte;begin for k:=1 to j-1 do if (xk=i) or (abs(xk-i)=abx(k-j) then exit(false); exit(true);end;proced

18、ure place(j:byte);var i:byte;begin if j>n then print else for i:=1 to n do if try(i,j) then begin xj:=i; place(j+1); end;end;begin readln(n); place(1); writeln(count);end.上面的算法是典型的遞歸算法，在放置第j個皇后時都要從已經(jīng)放置的第1j-1上皇后進行循環(huán)，檢驗該位置（i,j）是否存在沖突。實際本算法還可以改進。回溯法我們定義幾個數(shù)組，來存儲在某位置放入皇后后對棋盤各格子的影響開始時，假定所有格子都是未被限制的（可以放

19、置皇后），用F表示，當某位置上放了皇后，則與其在同一行、同一列、同一斜線上的格子被限制了，變?yōu)門。所以我們定義三個一維數(shù)組A1.n、B2.2*n、C1-n.1-n，用Ai表示第i行所有格子的狀態(tài)，用B和C表示位置（i,j）上的皇后所在的兩條對角線上所有格子的狀態(tài)。這樣，某個格子(i,j)能放入皇后的前提就是Ai Bi+j Ci-j的值都是F；若在格子(i,j)上放入皇后后，則使Ai、Bi+j、Ci-j值都為T。（程序略）練習：1跳馬問題問題描述 在5*5的棋盤上，從左上角的方格0出發(fā)，按日字跳馬，要求不重復地跳經(jīng)所有方格，求出符合要求的所有跳馬方案，輸出方案總數(shù)，并輸出前5個方案，按5*5的棋盤格式對應輸出，如：0 5 14 9 2013 8 19 4 1518 1 6 21 107 12 23 16 324 17 2 11 222傳染病控制問題背景 近來，一種新的傳染病肆虐全球。蓬萊國也發(fā)現(xiàn)了零星感染者，為防止該病在該國大范圍流行，該國政府決定不惜一切代價控制傳染病的蔓延。不幸的是，由于人們尚未完全認識