day3搜索-曹利國-noip培訓

,搜索算法,搜索算法的基本思想,搜索是計算機解題中常用的方法，它實質上是枚舉法的應用。由于它相當于枚舉法，所以其效率是相當?shù)氐?。因此，為了提高搜索的效率，人們想出了很多剪枝的方法，如分枝定界，啟發(fā)式搜索等等。在競賽中，我們不僅要熟練掌握這些方法，而且要因地制宜地運用一些技巧，以提高搜索的效率。定義：FunctionExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation;表示對給出的節(jié)點狀態(tài)Sitution采用第ExpendWayNo種擴展規(guī)則進行擴展，并且返回擴展后的狀態(tài)。,基本搜索算法一【回溯算法】,回溯算法是采用了一種“走不通就掉頭”思想作為其控制結構，用先根遍歷的方法來構造解答樹，可用于找所有解以及最優(yōu)解?；厮菟惴▽臻g的消耗較少，當其與分枝定界法一起使用時，對于所求解在解答樹中層次較深的問題有較好的效果。但應避免在后繼節(jié)點可能與前繼節(jié)點相同的問題中使用，以免產(chǎn)生循環(huán)。,基本搜索算法一【回溯算法】,Node(節(jié)點類型)RecordSitutation:TSituation（當前節(jié)點狀態(tài)）;Way-NO:Integer（已使用過的擴展規(guī)則的數(shù)目）;End,基本搜索算法一【回溯算法】,遞歸算法ProcedureBackTrack(Situation:TSituation;deepth:Integer);Vari:Integer;BeginIfdeepthMaxthen(空間達到極限,跳出本過程);IfSituation=Targetthen(找到目標);ForI:=1toTotalExpendMethoddoBeginBackTrack(ExpendNode(Situation,I),deepth+1);End-For;End;,構造字串生成長度為n的字串，其字符從26個英文字母的前p(p26)個字母中選取，使得沒有相鄰的子序列相等。例如p=3，n=5時abcba滿足條件abcbc不滿足條件輸入：n，p輸出：所有滿足條件的字串,分析,狀態(tài)：待擴展的字母序號at。實際上字串s亦參與了遞歸運算，但是由于該變量的存儲量太大，因此我們將s設為全局變量；邊界條件和目標狀態(tài)：產(chǎn)生了一個滿足條件的字串，即at=n+1；搜索范圍：第at位置可填的字母集a.chr(ord(a)+p-1)；約束條件：當前字串沒有相鄰子串相等的情況varn，p：integer；字串長度和可選字母的個數(shù)tl：longint；滿足條件的字串數(shù)ed：char；可選字母集中的最大字母s：string；滿足條件的字串,proceduresolve(at：integer)；遞歸擴展第at個字母varch：char；i：integer；beginifat=n+1若產(chǎn)生了一個滿足條件的字串，則輸出，滿足條件的字串數(shù)+1thenbeginwriteln(f，s)；inc(tl)；exit回溯end；thenforchatoeddo搜索每一個可填字母beginss+ch；i1；檢查當前字串是否符合條件while(icopy(s，length(s)-2*i+1，i)doinc(i)；,ifiatdiv2thensolve(at+1)；若當前字串符合條件，則遞歸擴展下一個字母delete(s，length(s)，1)恢復填前的字串endforend；solvebeginreadln(n，p)；輸入字串長度和前綴長短edchr(ord(a)+p-1)；計算可選字母集中的最大字母s；tl0；滿足條件的字串初始化為空，字串數(shù)為0solve(1)；從第1個字母開始遞歸計算所有滿足條件的字串writeln(Total：，tl)；輸出滿足條件的字串數(shù)end.main,基本搜索算法,深度搜索與廣度搜索深度搜索與廣度搜索的區(qū)別：深度搜索下一次擴展的是本次擴展出來的子節(jié)點中的一個，而廣度搜索擴展的則是本次擴展的節(jié)點的兄弟節(jié)點。在具體實現(xiàn)上為了提高效率,所以采用了不同的數(shù)據(jù)結構。廣度搜索是求解最優(yōu)解的一種較好的方法，而深度搜索多用于只要求解，并且解答樹中的重復節(jié)點較多并且重復較難判斷時使用，但往往可以用A*或回溯算法代替。,搜索策略,綜合數(shù)據(jù)庫與問題相關的所有數(shù)據(jù)元素構成的集合，用來表述問題狀態(tài)或有關事實。產(chǎn)生式規(guī)則構建了綜合數(shù)據(jù)庫以后，還需要研究問題的移動規(guī)則，稱為產(chǎn)生式規(guī)則。搜索策略搜索策略的實質是確定如何選取規(guī)則的方式。有兩種基本方式：一種是不考慮給定問題所具有的特定知識，系統(tǒng)根據(jù)事先確定好某種固定順序，依次調用規(guī)則或隨機調用規(guī)則，這實際上是盲目搜索的方法。另一種是考慮問題領域可應用的知識，動態(tài)地確定規(guī)則的排列次序，優(yōu)先調用較合適的規(guī)則使用，這就是通常所說的啟發(fā)式搜索策略。,一些基本概念,節(jié)點：記錄擴展的狀態(tài)?；?邊：記錄擴展的路徑。搜索樹：描述搜索擴展的整個過程。節(jié)點的耗散值令C(i,j)為從節(jié)點ni到nj的這段路徑（或者?。┑暮纳⒅?一條路徑的耗散值就等于連接這條路徑各節(jié)點間所有弧的耗散值總和?？梢杂眠f歸公式描述如下：C(ni,t)=C(ni,nj)+C(nj,t),八數(shù)碼問題,在3*3組成的九宮格棋盤上，擺有八個將牌，每一個將牌都刻有18中的某一個數(shù)碼。棋盤中留有一個空格，允許其周圍的某一個將牌向空格中移動，如右圖所示。這樣通過移動將牌就可以不斷改變的布局結構，給出一個初始布局（稱初始狀態(tài)）和一個目標布局（稱目標狀態(tài)），問如何移動將牌，才能實現(xiàn)從初始狀態(tài)到目標狀態(tài)的轉換。,綜合數(shù)據(jù)庫,Pxy，其中1=1thenbeginPm,n:=Pm-1,n;Pm-1,n:=0end;ifn+1=3thenbeginPm,n:=Pm,n+1;Pm,n+1:=0end;ifm+1=3thenbeginPm,n:=Pm+1,n;Pm+1,n:=0end;ConstDir:array1.4,1.2ofinteger對應四種產(chǎn)生式規(guī)則=(1,0),(-1,0),(0,1),(0,-1);,控制策略,PROCEDUREProduction-System；DATA初始化數(shù)據(jù)庫Repeat在規(guī)則集中選擇某一條可作用于DATA的規(guī)則RDATAR作用于DATA后得到的結果UntilDATA滿足結束條件,寬度優(yōu)先搜索,PROCEDUREBFS-SEARCH;(算法1)1.G:=G0;2.open:=(Source);3.closed:=nil;4.Repeat5.IFOPEn=nilthenExit(Fail);6.n:=FIRST(OPEn);Remove(n,open);7.Add(n,closed);8.ifn=GoalthenExit(Success);9.mi:=Expand(n);10.對mi，舍去在G中已經(jīng)出現(xiàn)的節(jié)點；11.將圖中未出現(xiàn)的mi加入到open表的表尾12.Add(mi,G);13.Untilfalse;,八數(shù)碼問題擴展過程,八數(shù)碼搜索的主框架,List1=source;closed:=0;open:=1;初始化open,closed,ListRepeatclosed:=closed+1;n:=Listclosed;取出closed對應的節(jié)點Forx:=1to4donew:=Move(n,4);按第x條規(guī)則擴展，得到newifnot_Appear(new,List)then判重open:=open+1;Listopen:=new;加入新節(jié)點到openListopen.Father:=closed;修改指針ifListopen=GoalthenGetOut;Untilclosed=bestthenexit;最優(yōu)化剪枝if(Liststep=Goal)and(stepbest)thenbest=step;記錄當前最少步驟forx:=1to4do對使用第x條規(guī)則擴展new:=expand(Liststep,4);ifnot_Appear(new,List)then判重Liststep:=new;插入當前節(jié)點對new進行標號;Recursive(step);遞歸搜索下一層清除new的標號;PROCEDUREDFSList1:=Source;Best:=maxint;Recursive(1);輸出,遞歸與非遞歸方式的比較,兩種方式本質上是等價，但兩者也時有區(qū)別的。遞歸方式實現(xiàn)簡單，非遞歸方式較之比較復雜；遞歸方式需要利用?？臻g，如果搜索量過大的話，可能造成棧溢出，所以在?？臻g無法滿足的情況下，選用非遞歸實現(xiàn)方式較好。,啟發(fā)式搜索,啟發(fā)式搜索是利用問題擁有的啟發(fā)信息來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。這種利用啟發(fā)信息的搜索過程稱為啟發(fā)式搜索方法。評價函數(shù)為了提高搜索效率，引入啟發(fā)信息來進行搜索，在啟發(fā)式搜索過程中，要對open表進行排序，這就需要有一種方法來計算待擴展節(jié)點有希望通向目標節(jié)點的程度，我們總希望能找到最有希望通向目標節(jié)點的待擴展節(jié)點優(yōu)先擴展。一種常用的方法就是定義評價函數(shù)f(evaluationfuntion)對各個節(jié)點進行計算，其目的就是估算出“有希望”的節(jié)點來。,“不在位獎牌個數(shù)”作為啟發(fā)信息的搜索過程,雙向寬度優(yōu)先搜索,雙向寬度優(yōu)先搜索注意的方面,規(guī)則必須可逆隨時判重交叉擴展,搜索算法的優(yōu)化,一、雙向廣度搜索二、分支定界三、A*算法,搜索算法的優(yōu)化,一、雙向廣度搜索從正反兩個方向進行廣度搜索，理想情況下可以減少二分之一的搜索量，從而提高搜索速度。從初始狀態(tài)和目標狀態(tài)兩個方向同時進行擴展，如果兩棵解答樹在某個節(jié)點第一次發(fā)生重合，則該節(jié)點所連接的兩條路徑所拼成的路徑就是最優(yōu)解。,搜索算法的優(yōu)化,添加一張節(jié)點表，作為反向擴展表。在正向擴展出一個節(jié)點后，需在反向表中查找是否有重合節(jié)點。反向擴展時與之相同。,搜索算法的優(yōu)化,對雙向廣度搜索算法的改進：略微修改一下控制結構，每次while循環(huán)時只擴展正反兩個方向中節(jié)點數(shù)目較少的一個，可以使兩邊的發(fā)展速度保持一定的平衡，從而減少總擴展節(jié)點的個數(shù)，加快搜索速度。,搜索算法的優(yōu)化,例題1：(最短編號序列)表A和表B各含k(k=20)個元素，元素編號從1到k。兩個表中的每個元素都是由0和1組成的字符串。（不是空串）字符串的長度，則一條完成全部任務的路徑是。,【分析】如果考慮從城市i出發(fā)，搜索所有相鄰的城市，再根據(jù)當前所處的城市，確定任務的完成情況，從中找到最優(yōu)解。這種搜索的效率極低。我們只需到達上貨和下貨的城市，其它的城市僅作為中間過程。因此，首先必須確定可能和不可能完成的任務，然后求出任意兩城市間的最短路徑。在搜索時，就只需考慮有貨要上的城市，或者是要運到該城市的貨全在車上兩種情況。同時，還可以設定兩個簡單的檻值。如果當前費用+還需達的城市=當前最優(yōu)解，或當前費用+返回城市1的費用=當前最優(yōu)解，則不需繼續(xù)往下搜索。,搜索剪枝應用舉例,例題3：（多處理機調度問題）有n相同的處理機P1,P2Pn,和m個獨立的作業(yè)J1,J2jm,處理機以互不相關的方式處理作業(yè)，現(xiàn)約定任何作業(yè)可以在任何一臺處理機上運行，但未完工之前不允許中斷作業(yè)，作業(yè)也不能拆分成更小的作業(yè)，已知作業(yè)Ji需要處理機處理的時間為Ti（i=1,2m）。編程完成以下兩個任務：任務一：己知n、m和Ti（i=1,2m），求解一個調度方案，使得完成這m個作業(yè)的總工時最少并輸出最少工時。任務二：給定作業(yè)時間表和限定完工時間，求在時間內完成這批作業(yè)所需最少處理機臺數(shù)和調度方案。,搜索剪枝應用舉例,【分析】此題有兩種搜索方法：方法一：按順序搜索每個作業(yè)。當搜索一個作業(yè)時，將其放在每臺處理機搜索一次。方法二：按順序搜索每臺處理機。當搜索一臺處理機時，將每個作業(yè)放在上面搜索一次。對比上述兩種方法，可以發(fā)現(xiàn)：方法二較方法一更容易剪枝。,搜索剪枝應用舉例,兩種方法剪枝的對照：對于方法一：只能根據(jù)目前已確定的需時最長的處理機的耗時與目前最佳解比較。對于方法二：可約定Time1Time2Timen（Timei表示第i臺處理機的處理時間）,從而可以設定檻值：如當前處理機的處理時間=目前最佳解，或剩下的處理機臺數(shù)上一臺處理機的處理時間剩余的作業(yè)需要的處理時間，則回溯。第二種方法顯然是比第一種要好的。,搜索剪枝應用舉例,第二種方法的深層探討：對于任務一，首先可以用貪心求出Time1的上界。然后，還可以求出Time1的下界:UP（作業(yè)總時間/處理機臺數(shù)）（UP表示大于等于該小數(shù)的最小整數(shù)）。搜索便從上界開始，找到一個解后，若等于下界即可停止搜索。對于任務二，可采用深度+可變下界。下界為：UP（作業(yè)總時間/限定時間），即至少需要的處理機臺數(shù)。并設定Time1的上界為T。,搜索剪枝應用舉例,例題4:有一個棋子，其1、6面2、4面3、5面相對?，F(xiàn)給出一個M*N的棋盤，棋子起初處于(1,1)點，擺放狀態(tài)給定，現(xiàn)在要求用最少的步數(shù)從(1,1)點翻滾到(M,N)點，并且1面向上。,搜索與其他算法的結合,【分析】這道題目用簡單的搜索很容易發(fā)生超時，所以可以考慮使用動態(tài)規(guī)劃來解題。對于一個棋子，其總共只有24種狀態(tài)。在(1,1)點時，其向