day3搜索-曹利國-noip培訓(xùn)

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