搜索算法-比較

搜索算法搜索算法的基本思想

搜索是計算機解題中常用的方法，它實質(zhì)上是枚舉法的應(yīng)用。由于它相當(dāng)于枚舉法，所以其效率是相當(dāng)?shù)氐?。因此，為了提高搜索的效率，人們想出了很多剪枝的方法，如分枝定界，啟發(fā)式搜索等等。在競賽中，我們不僅要熟練掌握這些方法，而且要因地制宜地運用一些技巧，以提高搜索的效率。定義：Function

ExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation;表示對給出的節(jié)點狀態(tài)Sitution采用第ExpendWayNo種擴展規(guī)則進(jìn)行擴展，并且返回擴展后的狀態(tài)?；舅阉魉惴ㄒ弧净厮菟惴ā炕厮菟惴ㄊ遣捎昧艘环N“走不通就掉頭”思想作為其控制結(jié)構(gòu)，用先根遍歷的方法來構(gòu)造解答樹，可用于找所有解以及最優(yōu)解?；厮菟惴▽臻g的消耗較少，當(dāng)其與分枝定界法一起使用時，對于所求解在解答樹中層次較深的問題有較好的效果。但應(yīng)避免在后繼節(jié)點可能與前繼節(jié)點相同的問題中使用，以免產(chǎn)生循環(huán)?；舅阉魉惴ㄒ弧净厮菟惴ā?lt;Type>

Node(節(jié)點類型)＝Record

Situtation:TSituation（當(dāng)前節(jié)點狀態(tài)）;Way-NO:Integer（已使用過的擴展規(guī)則的數(shù)目）;End基本搜索算法一【回溯算法】[遞歸算法]Procedure

BackTrack(Situation:TSituation;deepth:Integer);Var

i:Integer;Begin

If

deepth>Maxthen(空間達(dá)到極限,跳出本過程);IfSituation=Targetthen(找到目標(biāo));

ForI:=1to

TotalExpendMethod

do

Begin

BackTrack(ExpendNode(Situation,I),deepth+1);End-For;End;構(gòu)造字串

生成長度為n的字串，其字符從26個英文字母的前p(p≤26)個字母中選取，使得沒有相鄰的子序列相等。例如p=3，n=5時

‘a(chǎn)bcba’滿足條件

‘a(chǎn)bcbc’不滿足條件輸入：n，p輸出：所有滿足條件的字串

分析狀態(tài)：待擴展的字母序號at。實際上字串s亦參與了遞歸運算，但是由于該變量的存儲量太大，因此我們將s設(shè)為全局變量；

邊界條件和目標(biāo)狀態(tài)：產(chǎn)生了一個滿足條件的字串，即at=n+1；搜索范圍：第at位置可填的字母集{‘a(chǎn)’..chr(ord(‘a(chǎn)’)+p-1)}；約束條件：當(dāng)前字串沒有相鄰子串相等的情況varn，p：integer；{字串長度和可選字母的個數(shù)}

tl：longint；{滿足條件的字串?dāng)?shù)}ed：char；{可選字母集中的最大字母}s：string；{滿足條件的字串}proceduresolve(at：integer)；{遞歸擴展第at個字母}

var

ch：char；

i：integer；

beginifat=n+1{若產(chǎn)生了一個滿足條件的字串，則輸出，滿足條件的字串?dāng)?shù)+1}thenbegin

writeln(f，s)；inc(tl)；exit{回溯}end；{then}forch←'a'toeddo{搜索每一個可填字母}begins←s+ch；i←1；{檢查當(dāng)前字串是否符合條件}

while(i<=atdiv2)and(copy(s，length(s)-i+1，i)<>copy(s，length(s)-2*i+1，i))doinc(i)；ifi>atdiv2thensolve(at+1)；{若當(dāng)前字串符合條件，則遞歸擴展下一個字母}

delete(s，length(s)，1){恢復(fù)填前的字串}

end{for}end；{solve}begin

readln(n，p)；{輸入字串長度和前綴長短}ed←chr(ord('a')+p-1)；{計算可選字母集中的最大字母}s←''；tl←0；{滿足條件的字串初始化為空，字串?dāng)?shù)為0}solve(1)；{從第1個字母開始遞歸計算所有滿足條件的字串}

writeln('Total：'，tl)；{輸出滿足條件的字串?dāng)?shù)}

end.{main}基本搜索算法[深度搜索與廣度搜索]深度搜索與廣度搜索的區(qū)別：深度搜索下一次擴展的是本次擴展出來的子節(jié)點中的一個，而廣度搜索擴展的則是本次擴展的節(jié)點的兄弟節(jié)點。在具體實現(xiàn)上為了提高效率,所以采用了不同的數(shù)據(jù)結(jié)構(gòu)。廣度搜索是求解最優(yōu)解的一種較好的方法，而深度搜索多用于只要求解，并且解答樹中的重復(fù)節(jié)點較多并且重復(fù)較難判斷時使用，但往往可以用A*或回溯算法代替。搜索策略綜合數(shù)據(jù)庫

與問題相關(guān)的所有數(shù)據(jù)元素構(gòu)成的集合，用來表述問題狀態(tài)或有關(guān)事實。產(chǎn)生式規(guī)則 構(gòu)建了綜合數(shù)據(jù)庫以后，還需要研究問題的移動規(guī)則，稱為產(chǎn)生式規(guī)則。搜索策略 搜索策略的實質(zhì)是確定如何選取規(guī)則的方式。有兩種基本方式：一種是不考慮給定問題所具有的特定知識，系統(tǒng)根據(jù)事先確定好某種固定順序，依次調(diào)用規(guī)則或隨機調(diào)用規(guī)則，這實際上是盲目搜索的方法。另一種是考慮問題領(lǐng)域可應(yīng)用的知識，動態(tài)地確定規(guī)則的排列次序，優(yōu)先調(diào)用較合適的規(guī)則使用，這就是通常所說的啟發(fā)式搜索策略。一些基本概念節(jié)點：記錄擴展的狀態(tài)?；?邊：記錄擴展的路徑。搜索樹：描述搜索擴展的整個過程。節(jié)點的耗散值 令C(i,j)為從節(jié)點ni到nj的這段路徑（或者弧）的耗散值,一條路徑的耗散值就等于連接這條路徑各節(jié)點間所有弧的耗散值總和。可以用遞歸公式描述如下：

C(ni,t)=C(ni,nj)+C(nj,t)4搜索樹根節(jié)點葉子節(jié)點4,5,6,7,88123567八數(shù)碼問題

在3*3組成的九宮格棋盤上，擺有八個將牌，每一個將牌都刻有1—8中的某一個數(shù)碼。棋盤中留有一個空格，允許其周圍的某一個將牌向空格中移動，如右圖所示。這樣通過移動將牌就可以不斷改變的布局結(jié)構(gòu)，給出一個初始布局（稱初始狀態(tài)）和一個目標(biāo)布局（稱目標(biāo)狀態(tài)），問如何移動將牌，才能實現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)換。綜合數(shù)據(jù)庫{Pxy}，其中1<=x,y<=3，Pxy∈{0,1,2,3,4,5,6,7,8}，且Pxy互不相等

用Pascal語言描述如下：typeT8no=array[1..3,1..3]ofinteger;{棋盤狀態(tài)}

TList=record{描述一個節(jié)點}Father:integer;

{父指針}

dep:byte;

{深度}x,y:byte; {空格的位置}state:T8no;

end;constMax=10000;vars,t:T8no;{s為初始狀態(tài)，t為目標(biāo)狀態(tài)}List:array[0..max]ofTList;{綜合數(shù)據(jù)庫}產(chǎn)生式規(guī)則if條件then規(guī)則；設(shè)Pxy表示將牌第x行第y列的數(shù)碼，m,n表示數(shù)碼空格所在的行列值，記Pm,n=0,則可以得到如下四條規(guī)則：

①ifn-1>=1thenbeginPm,n:=Pm,n-1-

;Pm,n-1-

-:=0end;②ifm-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:array[1..4,1..2]ofinteger{對應(yīng)四種產(chǎn)生式規(guī)則}=((1,0),(-1,0),(0,1),(0,-1));控制策略

PROCEDUREProduction-System；DATA初始化數(shù)據(jù)庫Repeat

在規(guī)則集中選擇某一條可作用于DATA的規(guī)則R

DATAR作用于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é)點；11.

將圖中未出現(xiàn)的mi加入到open表的表尾12.

Add(mi,G);13.

Untilfalse;

八數(shù)碼問題擴展過程

八數(shù)碼搜索的主框架

List[1]=source;closed:=0;open:=1;{初始化open,closed,List}

Repeat

closed:=closed+1;n:=List[closed];{取出closed對應(yīng)的節(jié)點}

Forx:=1to4do[

new:=Move(n,4);{按第x條規(guī)則擴展，得到new}

ifnot_Appear(new,List)then{判重}

[open:=open+1;List[open]:=new;{加入新節(jié)點到open}

List[open].Father:=closed;{修改指針}

ifList[open]=GoalthenGetOut;

];

]

Untilclosed<open;八數(shù)碼問題寬度優(yōu)先算法框架List[1]=source;closed:=0;open:=1;{加入初始節(jié)點,List為擴展節(jié)點的表}Repeatclosed:=closed+1;n:=List[closed];{取出closed對應(yīng)的節(jié)點}Forx:=1to4do[new:=Move(n,4);{對n節(jié)點使用第x條規(guī)則，得到new}ifnot_Appear(new,List)then[{如果new沒有在List中出現(xiàn)}open:=open+1;List[open]:=new;{加入新節(jié)點到open}

List[open].Father:=closed;{修改指針}ifList[open]=GoalthenGetOut;];]Untilclosed<open;八數(shù)碼參考程序（寬度優(yōu)先）program8no_bfs;{八數(shù)碼的寬度優(yōu)先搜索算法}ConstDir:array[1..4,1..2]ofinteger

{四種移動方向，對應(yīng)產(chǎn)生式規(guī)則}=((1,0),(-1,0),(0,1),(0,-1));n=10000;TypeT8no=array[1..3,1..3]ofinteger;

TList=recordFather:integer;

{父指針}

dep:byte;

{深度}X0,Y0:byte; {0的位置}State:T8no;

{棋盤狀態(tài)}end;Var

Source,Target:T8no;List:array[0..10000]ofTList;{綜合數(shù)據(jù)庫}

Closed,open,Best:integer{Best表示最優(yōu)移動次數(shù)}Answer:integer;{記錄解}Found:Boolean;{解標(biāo)志}procedureGetInfo;{讀入初始和目標(biāo)節(jié)點}

var

i,j:integer;beginfori:=1to3doforj:=1to3doread(Source[i,j]);fori:=1to3doforj:=1to3doread(Target[i,j]);end;procedureInitialize;{初始化}

var

x,y:integer;beginFound:=false;Closed:=0;open:=1;withList[1]dobeginState:=Source;dep:=0;Father:=0;Forx:=1to3doFory:=1to3doifState[x,y]=0thenBeginx0:=x;y0:=y;End;end;end;FunctionSame(A,B:T8no):Boolean;{判斷A,B狀態(tài)是否相等}

Var

i,j:integer;BeginSame:=false;Fori:=1to3doforj:=1to3doifA[i,j]<>B[i,j]thenexit;Same:=true;End;functionnot_Appear(new:tList):boolean;{判斷new是否在List中出現(xiàn)}

vari:integer;begin

not_Appear:=false;fori:=1toopendoifSame(new.State,List[i].State)thenexit;

not_Appear:=true;end;procedureMove(n:tList;d:integer;varok:boolean;varnew:tList);{將第d條規(guī)則作用于n得到new,OK是new是否可行的標(biāo)志}

var

x,y:integer;beginX:=n.x0+Dir[d,1];Y:=n.y0+Dir[d,2];{判斷new的可行性}ifnot((X>0)and(X<4)and(Y>0)and(Y<4))thenbeginok:=false;exitend;OK:=true;new.State:=n.State;{new=Expand(n,d)}

new.State[X,Y]:=0;new.State[n.x0,n.y0]:=n.State[X,Y];new.X0:=X;new.Y0:=Y;end;procedureAdd(new:tList);{插入節(jié)點new}beginifnot_Appear(new)thenBegin{如果new沒有在List出現(xiàn)}

Inc(open);{new加入open表}

List[open]:=new;end;end;procedureExpand(Index:integer;varn:tList);{擴展n的子節(jié)點}

vari:integer;new:tList;OK:boolean;BeginifSame(n.State,Target)thenbegin{如果找到解}Found:=true;Best:=n.Dep;Answer:=Index;Exit;end;Fori:=1to4dobegin{依次使用４條規(guī)則}

Move(n,i,OK,new);ifnotokthencontinue;new.Father:=Index;

new.Dep:=n.dep+1;

Add(new);end;end;

procedureGetOutInfo;{輸出}procedureOutlook(Index:integer);{遞歸輸出每一個解}

var

i,j:integer;beginifIndex=0thenexit;

Outlook(List[Index].Father);withList[Index]dofori:=1to3dobeginforj:=1to3dowrite(State[i,j],'');

writeln;end;

writeln;end;begin

Writeln('Total=',Best);

Outlook(Answer);end;procedureMain;{搜索主過程}beginRepeat

Inc(Closed);

Expand(Closed,List[Closed]);{擴展Closed}Until(Closed>=open)orFound;ifFoundthenGetOutInfo{存在解}elseWriteln('noanswer');{無解}end;Begin

Assign(Input,'input.txt');ReSet(Input);

Assign(Output,'Output.txt');ReWrite(Output);

GetInfo;Initialize;Main;

Close(Input);Close(Output);End.深度優(yōu)先搜索框架PROCEDUREDFS-SEARCH;(算法2)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.

將圖中未出現(xiàn)的mi加入到open表的表頭(壓棧)11.

Add(mi,G);12.

Untilfalse;

深度優(yōu)先搜索遞歸形式procedureDFS_recursive(i);(算法3)

ifn=targetthen更新當(dāng)前最優(yōu)值并保存路徑;

forr:=1to規(guī)則數(shù)

do[

new:=Expand(n,r)

if值節(jié)點new符合條件

then[

產(chǎn)生的子節(jié)點new壓入棧;

DFS_recursive(i+1);

棧頂元素出棧;

]

]

programDFS;

初始化;

DFS_recursive(1);八數(shù)碼問題的遞規(guī)搜索PROCEDURERecursive(step);ifstep>=bestthenexit;{最優(yōu)化剪枝}if(List[step]=Goal)and(step<best)thenbest=step; {記錄當(dāng)前最少步驟}forx:=1to4do[ {對使用第x條規(guī)則擴展} new:=expand(List[step],4);ifnot_Appear(new,List)then{判重}

List[step]:=new;{插入當(dāng)前節(jié)點}

對new進(jìn)行標(biāo)號;

Recursive(step); {遞歸搜索下一層}

清除new的標(biāo)號;]PROCEDUREDFSList[1]:=Source;Best:=maxint;Recursive(1);

輸出遞歸與非遞歸方式的比較兩種方式本質(zhì)上是等價，但兩者也時有區(qū)別的。遞歸方式實現(xiàn)簡單，非遞歸方式較之比較復(fù)雜；遞歸方式需要利用?？臻g，如果搜索量過大的話，可能造成棧溢出，所以在?？臻g無法滿足的情況下，選用非遞歸實現(xiàn)方式較好。啟發(fā)式搜索啟發(fā)式搜索是利用問題擁有的啟發(fā)信息來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的。這種利用啟發(fā)信息的搜索過程稱為啟發(fā)式搜索方法。評價函數(shù) 為了提高搜索效率，引入啟發(fā)信息來進(jìn)行搜索，在啟發(fā)式搜索過程中，要對open表進(jìn)行排序，這就需要有一種方法來計算待擴展節(jié)點有希望通向目標(biāo)節(jié)點的程度，我們總希望能找到最有希望通向目標(biāo)節(jié)點的待擴展節(jié)點優(yōu)先擴展。一種常用的方法就是定義評價函數(shù)f(evaluationfuntion)對各個節(jié)點進(jìn)行計算，其目的就是估算出“有希望”的節(jié)點來。“不在位獎牌個數(shù)”作為啟發(fā)信息的搜索過程雙向?qū)挾葍?yōu)先搜索雙向?qū)挾葍?yōu)先搜索注意的方面規(guī)則必須可逆隨時判重交叉擴展搜索算法的優(yōu)化一、雙向廣度搜索二、分支定界三、A*算法搜索算法的優(yōu)化一、雙向廣度搜索從正反兩個方向進(jìn)行廣度搜索，理想情況下可以減少二分之一的搜索量，從而提高搜索速度。從初始狀態(tài)和目標(biāo)狀態(tài)兩個方向同時進(jìn)行擴展，如果兩棵解答樹在某個節(jié)點第一次發(fā)生重合，則該節(jié)點所連接的兩條路徑所拼成的路徑就是最優(yōu)解。搜索算法的優(yōu)化添加一張節(jié)點表，作為反向擴展表。在正向擴展出一個節(jié)點后，需在反向表中查找是否有重合節(jié)點。反向擴展時與之相同。搜索算法的優(yōu)化對雙向廣度搜索算法的改進(jìn)：略微修改一下控制結(jié)構(gòu)，每次while循環(huán)時只擴展正反兩個方向中節(jié)點數(shù)目較少的一個，可以使兩邊的發(fā)展速度保持一定的平衡，從而減少總擴展節(jié)點的個數(shù)，加快搜索速度。搜索算法的優(yōu)化例題1：(最短編號序列)

表A和表B各含k(k<=20)個元素，元素編號從1到k。兩個表中的每個元素都是由0和1組成的字符串。（不是空串）字符串的長度<=20。例如下表的A和B兩個表，每個表都含3個元素（k=3）。

元素編號

字符串11210111310

元素編號

字符串111121030表B表A搜索算法的優(yōu)化

對于表A和表B，存在一個元素編號的序列2113，分別用表A中的字符串和表B中的字符串去置換相應(yīng)的元素編號，可得相同的字符串序列101111110，見下表。具有上述性質(zhì)的元素編號序列稱之為S(AB)。對于上例S(AB)=2113。編寫程序：從文件中讀入表A和表B的各個元素，尋找一個長度最短的元素編號序列S(AB)。（若找不到長度<=100的編號序列，則輸出“NoAnswer”。

元素編號序列2113

用表A的字符串替換101111110

用表B的字符串替換101111110【分析】由于表Ａ和表Ｂ不確定，所以不可能找到一種數(shù)學(xué)的方法。因為是求最優(yōu)解，不適合用深度優(yōu)先搜索，所以必須采用廣度優(yōu)先搜索的方法。但是當(dāng)表Ａ和表Ｂ中的元素過多時，直接搜索會超時。必須對搜索的算法加以改進(jìn)。此題的規(guī)則既可以正向使用，又可以逆向使用，因此可以采用雙向搜索。搜索算法的優(yōu)化在大方法確定后，算法的框架就已經(jīng)基本形成，再對算法進(jìn)行適當(dāng)?shù)馗倪M(jìn)：

1、存儲當(dāng)前的Ａ串和Ｂ串是很費空間的，但因為Ａ串和Ｂ串的大部分相同，故只需記錄不同部分，并作個標(biāo)記。

2、為了保證兩個方向擴展結(jié)點的速度相對平衡，可以采取每次擴展結(jié)點數(shù)較少的方向，而不是兩方向輪流擴展。搜索算法的優(yōu)化二、分支定界分支定界實際上是A*算法的一種雛形，其對于每個擴展出來的節(jié)點給出一個預(yù)期值，如果這個預(yù)期值不如當(dāng)前已經(jīng)搜索出來的結(jié)果好的話，則將這個節(jié)點(包括其子節(jié)點)從解答樹中刪去，從而達(dá)到加快搜索速度的目的。

搜索算法的優(yōu)化二、分支定界解題過程：１、添加一個全局變量BestAnswer，記錄當(dāng)前最優(yōu)解。２、在每次生成一個節(jié)點時，計算其預(yù)期值，并與BestAnswer比較。如果不好，則調(diào)用回溯過程。搜索算法的優(yōu)化三、A*算法A*算法中更一般的引入了一個估價函數(shù)f,其定義為f=g+h。其中g(shù)為到達(dá)當(dāng)前節(jié)點的耗費，而h表示對從當(dāng)前節(jié)點到達(dá)目標(biāo)節(jié)點的耗費的估計。其必須滿足兩個條件：１、h必須小于等于實際的從當(dāng)前節(jié)點到達(dá)目標(biāo)節(jié)點的最小耗費h*。２、f必須保持單調(diào)遞增。搜索算法的優(yōu)化三、A*算法

A*算法的控制結(jié)構(gòu)與廣度搜索的十分類似，只是每次擴展的都是當(dāng)前待擴展節(jié)點中f值最小的一個，如果擴展出來的節(jié)點與已擴展的節(jié)點重復(fù)，則刪去這個節(jié)點。如果與待擴展節(jié)點重復(fù)，如果這個節(jié)點的估價函數(shù)值較小，則用其代替原待擴展節(jié)點。當(dāng)A*算法出現(xiàn)數(shù)據(jù)溢出時，從待擴展節(jié)點中取出若干個估價函數(shù)值較小的節(jié)點，然后放棄其余的待擴展節(jié)點，從而可以使搜索進(jìn)一步的進(jìn)行下去。搜索算法的優(yōu)化搜索剪枝應(yīng)用舉例

例題2：（任務(wù)安排）

Ｎ個城市，若干城市間有道路相連，一輛汽車在城市間運送貨物，總是從城市１出發(fā)，又回到城市１。該車每次需完成若干個任務(wù)，每個任務(wù)都是要求該車將貨物從一個城市運送至另一個。例如若要完成任務(wù)２－>6，則該車一次旅程中必含有一條子路徑。先到２，再到６。編程由文件讀入道路分布的領(lǐng)接矩陣，然后對要求完成的若干任務(wù)，尋找一條旅行路線，使得在完成任務(wù)最多的前提下，經(jīng)過的城市總次數(shù)最少。如上例中經(jīng)過城市總次數(shù)為８，城市１和２各經(jīng)過２次均以２次計（起點不計），Ｎ<60。 搜索剪枝應(yīng)用舉例

如下圖所示，如果要求的任務(wù)是２－>３，２－>４，３－>１，２－>５，６－>４，則一條完成全部任務(wù)的路徑是１－>２－>３－>１－>２－>５－>６－>４－>１。

【分析】如果考慮從城市i出發(fā)，搜索所有相鄰的城市，再根據(jù)當(dāng)前所處的城市，確定任務(wù)的完成情況，從中找到最優(yōu)解。這種搜索的效率極低。我們只需到達(dá)上貨和下貨的城市，其它的城市僅作為中間過程。因此，首先必須確定可能和不可能完成的任務(wù)，然后求出任意兩城市間的最短路徑。在搜索時，就只需考慮有貨要上的城市，或者