搜索算法精講搜索算法-----顯式圖與隱式圖頂點表示問題的一個狀態(tài)邊

表示狀態(tài)之間的轉化規(guī)則隱式圖和產生式系統(tǒng)只有初始狀態(tài)和變化規(guī)則，在搜索的過程中產生出新狀態(tài)。搜索就是按某次序遍歷所有可能有“解”的頂點

產生式系統(tǒng)綜合數(shù)據(jù)庫

與問題相關的所有數(shù)據(jù)元素構成的集合，用來表述問題狀態(tài)或有關事實。產生式規(guī)則 構建了綜合數(shù)據(jù)庫以后，還需要研究問題的移動規(guī)則，稱為產生式規(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)4搜索樹根節(jié)點葉子節(jié)點4,5,6,7,88123567八數(shù)碼問題

在3*3組成的九宮格棋盤上，擺有八個將牌，每一個將牌都刻有1—8中的某一個數(shù)碼。棋盤中留有一個空格，允許其周圍的某一個將牌向空格中移動，如右圖所示。這樣通過移動將牌就可以不斷改變的布局結構，給出一個初始布局（稱初始狀態(tài)）和一個目標布局（稱目標狀態(tài)），問如何移動將牌，才能實現(xiàn)從初始狀態(tài)到目標狀態(tài)的轉換。綜合數(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為目標狀態(tài)}List:array[0..max]ofTList;{綜合數(shù)據(jù)庫}產生式規(guī)則if條件then規(guī)則；設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{對應四種產生式規(guī)則}=((1,0),(-1,0),(0,1),(0,-1));控制策略

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

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

DATAR作用于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中已經出現(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對應的節(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對應的節(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

{四種移動方向，對應產生式規(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;VarSource,Target:T8no;List:array[0..10000]ofTList;{綜合數(shù)據(jù)庫}Closed,open,Best:integer{Best表示最優(yōu)移動次數(shù)}Answer:integer;{記錄解}Found:Boolean;{解標志}procedureGetInfo;{讀入初始和目標節(jié)點}vari,j:integer;beginfori:=1to3doforj:=1to3doread(Source[i,j]);fori:=1to3doforj:=1to3doread(Target[i,j]);end;procedureInitialize;{初始化}varx,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)是否相等}Vari,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;beginnot_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是否可行的標志}varx,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);{遞歸輸出每一個解}vari,j:integer;beginifIndex=0thenexit;Outlook(List[Index].Father);withList[Index]dofori:=1to3dobeginforj:=1to3dowrite(State[i,j],'');writeln;end;writeln;end;beginWriteln('Total=',Best);Outlook(Answer);end;procedureMain;{搜索主過程}beginRepeatInc(Closed);Expand(Closed,List[Closed]);{擴展Closed}Until(Closed>=open)orFound;ifFoundthenGetOutInfo{存在解}elseWriteln('noanswer');{無解}end;BeginAssign(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更新當前最優(yōu)值并保存路徑;

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

do[

new:=Expand(n,r)

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

then[

產生的子節(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; {記錄當前最少步驟}forx:=1to4do[ {對使用第x條規(guī)則擴展} new:=expand(List[step],4);ifnot_Appear(new,List)then{判重}List[step]:=new;{插入當前節(jié)點}

對new進行標號;Recursive(step); {遞歸搜索下一層}

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

輸出遞歸與非遞歸方式的比較兩種方式本質上是等價，但兩者也時有區(qū)別的。遞歸方式實現(xiàn)簡單，非遞歸方式較之比較復雜；遞歸方式需要利用?？臻g，如果搜索量過大的話，可能造成棧溢出，所以在棧空間無法滿足的情況下，選用非遞歸實現(xiàn)方式較好。啟發(fā)式搜索啟發(fā)式搜索是利用問題擁有的啟發(fā)信息來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。這種利用啟發(fā)信息的搜索過程稱為啟發(fā)式搜索方法。評價函數(shù) 為了提高搜索效率，引入啟發(fā)信息來進行搜索，在啟發(fā)式搜索過程中，要對open表進行排序，這就需要有一種方法來計算待擴展節(jié)點有希望通向目標節(jié)點的程度，我們總希望能找到最有希望通向目標節(jié)點的待擴展節(jié)點優(yōu)先擴展。一種常用的方法就是定義評價函數(shù)f(evaluationfuntion)對各個節(jié)點進行計算，其目的就是估算出“有希望”的節(jié)點來。評價函數(shù)的選取通常，我們可以將評價函數(shù)f拆分成兩個部分；即對節(jié)點n，有f(n)=g(n)+h(n)。其中函數(shù)g是節(jié)點n對歷史（初始節(jié)點s）的評價值，函數(shù)h是節(jié)點n對未來（目標節(jié)點t）的評價值。f(n)規(guī)定為對從初始節(jié)點s，通過約束節(jié)點n，到達目標節(jié)點t上，最小耗散路徑(最佳路徑)的耗散值f*(n)的估計值。其中，g(n)規(guī)定為對從s到n最小耗散路徑(最佳路徑)的耗散值g*(n)的估計值。h(n)規(guī)定為對從n到t最小耗散路徑(最佳路徑)的耗散值h*(n)的估計值。因此，f*(n)=g*(n)+h*(n)就表示從初試節(jié)點出發(fā)到達目標節(jié)點的最小耗散路徑(最佳路徑)的耗散值。 顯然，g(n)的值很容易從到目前為止的搜索樹上計算出來。也就是根據(jù)搜索歷史對g*(n)做出估計，顯然，g(n)≥g*(n)。h(n)則依賴啟發(fā)信息，通常稱為啟發(fā)函數(shù)。啟發(fā)式圖搜索算法框架PROCEDUREA*-SEARCH;G:=G0;{其中G表示搜索圖，G0是初始圖}open:=(Source);{把source(初始節(jié)點)加入open表}closed:=nil;{置closed表為空}Repeat IFopen=nilthenExit(Fail);{如果open為空，輸出無解并退出} n:=FIRST(OPEn);Remove(n,open);{取出open表首節(jié)點,從open刪除n} Add(n,closed);{把n加入到closed表} ifn=GoalthenExit(Success);{如果n為目標，就退出并輸出解} mi:=Expand(n);{mi=mj∪mk∪ml,mj為未出現(xiàn)過的節(jié)點,mk為在open中的節(jié)點,ml為在closed中的節(jié)點}

計算mi的估價函數(shù)值f(n,mi); Add(mj,G);標記和修改mj的指針;{把mj加入圖G,并標記修改指針} iff(n,mk)<f(mk)thenf(mk):=f(n,mk),標記mk到n的指針; iff(n,ml)<f(ml)thenf(ml):=f(n,ml),標記ml到n的指針,Add(ml,open)

對open中的節(jié)點按估價函數(shù)值的大小重新排序；Untilfalse;“不在位獎牌個數(shù)”作為啟發(fā)信息的搜索過程A*搜索的性質性質1：若有兩個A*算法A1和A2,R若A2比A1有較多的啟發(fā)信息（即對所有非目標接點均有h2(n)>h1(n)）,則在具有一條從s到t的隱含圖上，搜索結束時，由A2所擴展的每一個節(jié)點，也必定由A1所擴展，即A1擴展的節(jié)點數(shù)至少和A2一樣多。根據(jù)這個性質可知，使用啟發(fā)函數(shù)h(n)的A*算法，比不使用h(n)（h(n)=0）的算法，求得最佳路徑時擴展的節(jié)點要少，使用h(n)啟發(fā)信息強的A*算法比使用h(n)啟發(fā)信息弱的A*算法擴展的節(jié)點數(shù)要少。因此，我們在考慮問題時，在滿足h(n)≤h*(n)的條件下，要盡量擴大h函數(shù)的值。性質2：若存在初始節(jié)點s到目標節(jié)點t的路徑，則A*必能找到最佳路徑。如果A*選作擴展的任一節(jié)點n，有f(n)≤f*(s)。性質3：若h(n)滿足單調限制條件，也就是說啟發(fā)函數(shù)h滿足單調性，則A*擴展了節(jié)點n之后就已經找到了到達節(jié)點n的最佳路徑。即若A*選n來擴展，在單調限制條件下有g(n)=g*(n)，其由A*所擴展的節(jié)點序列，其f值也是非遞減的，即f(ni)≤f(nj)?！辈辉谖粚⑴频穆窂綑嘀岛汀白鳛閱l(fā)函數(shù)的搜索過程雙向寬度優(yōu)先搜索雙向寬度優(yōu)先搜索注意的方面規(guī)則必須可逆隨時判重交叉擴展各種搜索算法的比較算法寬度優(yōu)先深度優(yōu)先W作為啟發(fā)函數(shù)A*P作為啟發(fā)函數(shù)A*雙向搜索擴展的節(jié)點數(shù)35至少35141121穩(wěn)定性穩(wěn)定不穩(wěn)定穩(wěn)定穩(wěn)定基本穩(wěn)定常用的搜索搜索策略⑴求任一解路的搜索 回溯法(Backtracking)

爬山法(HillClimbing)

寬度優(yōu)先法(Breadth-first)

深度優(yōu)先法(Depth-first)

限定范圍的搜索(BeamSearch)

好的優(yōu)先法(Best-first)⑵求最佳解路的搜索 大英博物館法(BritishMuseum)

分支界限法(BranchandBound)

動態(tài)規(guī)劃法(DynamicProgramming)

最佳圖的搜索(A*)⑶與或圖的搜索 一般與或圖搜索(AO*)

極大極小法(Minimax) αβ剪枝法(Alpha-betaPrunning)

啟發(fā)式剪枝法(HeuristicPrunning)問題1:神經網(wǎng)絡

在蘭蘭的模型中，神經網(wǎng)絡就是一張有向圖，圖中的節(jié)點稱為神經元，而且兩個神經元之間至多有一條邊相連，下圖是一個神經元的例子：圖中，X1—X3是信息輸入渠道，Y1－Y2是信息輸出渠道，C1表示神經元目前的狀態(tài)，Ui是閾值，可視為神經元的一個內在參數(shù)。神經元按一定的順序排列，構成整個神經網(wǎng)絡。在蘭蘭的模型之中，神經網(wǎng)絡中的神經無分為幾層；稱為輸入層、輸出層，和若干個中間層。每層神經元只向下一層的神經元輸出信息，只從上一層神經元接受信息。蘭蘭規(guī)定，Ci服從公式(1)（其中n是網(wǎng)絡中所有神經元的數(shù)目）公式中的Wji（可能為負值）表示連接j號神經元和i號神經元的邊的權值。當Ci大于0時，該神經元處于興奮狀態(tài)，否則就處于平靜狀態(tài)。當神經元處于興奮狀態(tài)時，下一秒它會向其他神經元傳送信號，信號的強度為Ci。如此．在輸入層神經元被激發(fā)之后，整個網(wǎng)絡系統(tǒng)就在信息傳輸?shù)耐苿酉逻M行運作。現(xiàn)在，給定一個神經網(wǎng)絡，及當前輸入層神經元的狀態(tài)Ci，要求你的程序運算出最后網(wǎng)絡輸出層的狀態(tài)。

【輸入格式】

第一行是兩個整數(shù)n（1≤n≤20）和p。接下來n行，每行兩個整數(shù)，第i＋1行是神經元i最初狀態(tài)和其閾值（Ui），非輸入層的神經元開始時狀態(tài)必然為0。再下面P行，每行由兩個整數(shù)i，j及一個整數(shù)Wij，表示連接神經元i、j的邊權值為Wij【輸出格式】

輸出包含若干行，每行有兩個整數(shù)，分別對應一個神經元的編號，及其最后的狀態(tài)，兩個整數(shù)間以空格分隔。僅輸出最后狀態(tài)非零的輸出層神經元狀態(tài)，并且按照編號由小到大順序輸出！若輸出層的神經元最后狀態(tài)均為0，則輸出NULL。分析

理解問題的第一步就是認真“讀題”。那么我們先來看一看這個題目涉及的問題。研究一下題目中所給的圖的一些性質，可以發(fā)現(xiàn)如下特點：1．圖中所有的節(jié)點都有一個確定的等級，我們記作Level(i)2．圖中所有的邊都是有向的，并且從Level值為i-1的節(jié)點指向Level值為i的節(jié)點我們不妨將其抽象為“階段圖”。更一般地，我們可以發(fā)現(xiàn)所有的階段圖都是有向無環(huán)的，這樣我們可以通過拓撲排序來得到期望的處理節(jié)點的順序?？尚兴惴?/p>

由于階段圖的性質使得該圖的所有邊所連接節(jié)點的等級都是相鄰的，因此就可以設計出一個基于寬度優(yōu)先搜索（即BFS）的算法：1．初始時將所有輸入層的節(jié)點放入隊列；2．取出隊列中的一個元素，不重復地擴展并處理該節(jié)點所發(fā)出的邊的目標節(jié)點；3．如果隊列非空，則轉向2；4．輸出輸出層中所有滿足條件的節(jié)點。但是由于本題在問題描述中并沒有明確的給出判斷一個節(jié)點是否是輸入節(jié)點，因此需要在算法進行的過程當中額外地考慮一些邊界情況的數(shù)據(jù)（這個過程即便是真實數(shù)據(jù)沒有這樣出也是要有的），下面給出的更一般的算法可能會更好的跳過這些邊界情況。1．對原圖中所有的節(jié)點進行一次拓撲排序；2．按照拓撲順序處理每一個節(jié)點；3．輸出輸出層中所有滿足條件的節(jié)點。問題2:聰明的打字員阿蘭是某機密部門的打字員，她現(xiàn)在接到一個任務：需要在一天之內輸入幾百個長度固定為6的密碼。當然，她希望輸入的過程中敲擊鍵盤的總次數(shù)越少越好。不幸的是，出于保密的需要，該部門用于輸入密碼的鍵盤是特殊設計的，鍵盤上沒有數(shù)字鍵，而只有以下六個鍵：Swap0,Swap1,Up,Down,Left,Right，為了說明這6個鍵的作用，我們先定義錄入?yún)^(qū)的6個位置的編號，從左至右依次為1，2，3，4，5，6。下面列出每個鍵的作用：Swap0：按Swap0，光標位置不變，將光標所在位置的數(shù)字與錄入?yún)^(qū)的1號位置的數(shù)字（左起第一個數(shù)字）交換。如果光標已經處在錄入?yún)^(qū)的1號位置，則按Swap0鍵之后，錄入?yún)^(qū)的數(shù)字不變；Swap1：按Swap1，光標位置不變，將光標所在位置的數(shù)字與錄入?yún)^(qū)的6號位置的數(shù)字（左起第六個數(shù)字）交換。如果光標已經處在錄入?yún)^(qū)的6號位置，則按Swap1鍵之后，錄入?yún)^(qū)的數(shù)字不變；Up：按Up，光標位置不變，將光標所在位置的數(shù)字加1（除非該數(shù)字是9）。例如，如果光標所在位置的數(shù)字為2，按Up之后，該處的數(shù)字變?yōu)?；如果該處數(shù)字為9，則按Up之后，數(shù)字不變，光標位置也不變；Down：按Down，光標位置不變，將光標所在位置的數(shù)字減1（除非該數(shù)字是0），如果該處數(shù)字為0，則按Down之后，數(shù)字不變，光標位置也不變；Left：按Left，光標左移一個位置，如果光標已經在錄入?yún)^(qū)的1號位置（左起第一個位置）上，則光標不動；Right：按Right，光標右移一個位置，如果光標已經在錄入?yún)^(qū)的6號位置（左起第六個位置）上，則光標不動。當然，為了使這樣的鍵盤發(fā)揮作用，每次錄入密碼之前，錄入?yún)^(qū)總會隨機出現(xiàn)一個長度為6的初始密碼，而且光標固定出現(xiàn)在1號位置上。當巧妙地使用上述六個特殊鍵之后，可以得到目標密碼，這時光標允許停在任何一個位置?，F(xiàn)在，阿蘭需要你的幫助，編寫一個程序，求出錄入一個密碼需要的最少的擊鍵次數(shù)。擴展規(guī)則設當前狀態(tài)為(S,index)，下一個狀態(tài)為(S’,index’)①Swap0：ifindex<>1then[S’:=S;S’[1]:=S[index];S’[index]:=S[1];Index’:=index;]②Swap1：ifindex<>6then[S’:=S;S’[6]:=S[index];S’[index]:=S[6];Index’:=index;]③Up：ifS[index]<>9then[S’:=S;S’[index]:=S’[index]+1;Index’:=index;]④Down：ifS[index]<>0then[S’:=S;S’[index]:=S’[index]-1;Index’:=index;]⑤Left：ifindex<>0then[S’:=S;Index’:=index-1;]⑥Right：ifindex<>6then[S’:=S;Index’:=index+1;]數(shù)據(jù)結構的處理

如果我們用（S,index）表示問題中的一個狀態(tài)，S為密碼，index表示光標位置。那么，（Source，1）為問題的初始狀態(tài)，（Target，pos）為問題的目標狀態(tài)。其中pos任意。那么綜合數(shù)據(jù)庫中可能存在的節(jié)點數(shù)為：6*106。

constmaxl=6000000;typestatetype=array[1..6]ofshortint;Nodetype=recordstate:statetype;{密碼}point,step:shortint;{光標位置，按鍵次數(shù)}end;varq:array[0..maxl]ofNodetype;

{隊列}app:array[1..6,0..9,0..9,0..9,0..9,0..9,0..9]ofboolean;{判重數(shù)組}final:statetype;{目標狀態(tài)}算法選擇closed:=0;open:=1;q[1].point:=1;fillchar(app,sizeof(app),false);whiletruedobeginclosed:=closedmodmaxl+1;withq[closed]dobeginifcomparebyte(state,final,6)=0then打印輸出；{如果是目標的話}

調用6條規(guī)則擴展出state新節(jié)點；

ifnotapp[point,state[1],state[2],state[3],state[4],state[5],state[6]]{判重}thenbeginopen:=openmodmaxl+1;q[open].state:=state;q[open].step:=step+1;q[open].point:=point;app[point,state[1],state[2],state[3],state[4],state[5],state[6]]:=true;end;問題3:：AmazingRobots已知條件：

迷宮

i（i=1,2）（每個不會大于20*20）守衛(wèi)

Gi（0<=Gi<=10）（守衛(wèi)循環(huán)移動進行執(zhí)勤）（守衛(wèi)巡邏的方格數(shù)（2..4））求：兩個機器人都離開迷宮所用的最少指令數(shù)目和離開制指令序列（10000步以內）。每一步可以發(fā)出的命令可以是N,E,S,W中的一種，有4種選擇。對每一步具體發(fā)出哪個命令，直接搜索。假設最后結果是T。（也就是最少出宮時間）時間復雜度是O(4T)這種方法時間復雜度太高，絕對不可行!!5*4和4*4的迷宮第一個機器人的位置是(2,2)第二個機器人的位置是(3,2)當前時間是0。狀態(tài)((2,2),(3,2),0)狀態(tài)表示：（第一個機器人位置，第二個機器認位置，時間）E((2,2),(3,2),0)((2,3),(3,3),1)時間已知，則所有Guard的位置可知。Guard、Robot的位置均已知，所以狀態(tài)可以轉移0時刻1時刻2時刻3時刻0時刻和2時刻是一樣的1時刻和3時刻是一樣的。稍加分析：此Guard循環(huán)以2為周期循環(huán)。狀態(tài)轉移，需要的信息是：Robot位置，Guard位置。PositionofRobot1,2是的作用就是記錄Robot位置。Time的作用就是為了計算Guard的位置狀態(tài)：(positionofRobot1,positionofRobot2,Time)Time<=10000，這是狀態(tài)數(shù)過多的罪魁禍首！題目說：Guard巡邏經過的格子數(shù)只可能是2,3,4。也就是說機器人巡邏周期只能是2,4,6。[2,4,6]=12，所以第0時刻、12時刻、24時刻……Guard的狀態(tài)完全相同。12可以看作Guard的周期。Time只要記錄當前是第幾個周期。因為周期確定了，Guard的位置也完全確定了！0<=Time<=11狀態(tài)數(shù)(n*n)*(n*n)*12=12n4。用BFS算法，標志數(shù)組判重。時間復雜度O(12n4)。n<=20完全可以承受^-^聰明的打字員(nOI2001第一試第三題)阿蘭是某機密部門的打字員，她現(xiàn)在接到一個任務：需要在一天之內輸入幾百個長度固定為6的密碼。當然，她希望輸入的過程中敲擊鍵盤的總次數(shù)越少越好。不幸的是，出于保密的需要，該部門用于輸入密碼的鍵盤是特殊設計的，鍵盤上沒有數(shù)字鍵，而只有以下六個鍵：Swap0,Swap1,Up,Down,Left,Right，為了說明這6個鍵的作用，我們先定義錄入?yún)^(qū)的6個位置的編號，從左至右依次為1，2，3，4，5，6。下面列出每個鍵的作用：Swap0：按Swap0，光標位置不變，將光標所在位置的數(shù)字與錄入?yún)^(qū)的1號位置的數(shù)字（左起第一個數(shù)字）交換。如果光標已經處在錄入?yún)^(qū)的1號位置，則按Swap0鍵之后，錄入?yún)^(qū)的數(shù)字不變；Swap1：按Swap1，光標位置不變，將光標所在位置的數(shù)字與錄入?yún)^(qū)的6號位置的數(shù)字（左起第六個數(shù)字）交換。如果光標已經處在錄入?yún)^(qū)的6號位置，則按Swap1鍵之后，錄入?yún)^(qū)的數(shù)字不變；Up：按Up，光標位置不變，將光標所在位置的數(shù)字加1（除非該數(shù)字是9）。例如，如果光標所在位置的數(shù)字為2，按Up之后，該處的數(shù)字變?yōu)?；如果該處數(shù)字為9，則按Up之后，數(shù)字不變，光標位置也不變；Down：按Down，光標位置不變，將光標所在位置的數(shù)字減1（除非該數(shù)字是0），如果該處數(shù)字為0，則按Down之后，數(shù)字不變，光標位置也不變；Left：按Left，光標左移一個位置，如果光標已經在錄入?yún)^(qū)的1號位置（左起第一個位置）上，則光標不動；Right：按Right，光標右移一個位置，如果光標已經在錄入?yún)^(qū)的6號位置（左起第六個位置）上，則光標不動。當然，為了使這樣的鍵盤發(fā)揮作用，每次錄入密碼之前，錄入?yún)^(qū)總會隨機出現(xiàn)一個長度為6的初始密碼，而且光標固定出現(xiàn)在1號位置上。當巧妙地使用上述六個特殊鍵之后，可以得到目標密碼，這時光標允許停在任何一個位置?，F(xiàn)在，阿蘭需要你的幫助，編寫一個程序，求出錄入一個密碼需要的最少的擊鍵次數(shù)。產生式規(guī)則設當前狀態(tài)為(S,index)，下一個狀態(tài)為(S’,index’)①Swap0：ifindex<>1then[S’:=S;S’[1]:=S[index];S’[index]:=S[1];Index’:=index;]②Swap1：ifindex<>6then[S’:=S;S’[6]:=S[index];S’[index]:=S[6];Index’:=index;]③Up：ifS[index]<>9then[S’:=S;S’[index]:=S’[index]+1;Index’:=index;]④Down：ifS[index]<>0then[S’:=S;S’[index]:=S’[index]-1;Index’:=index;]⑤Left：ifindex<>0then[S’:=S;Index’:=index-1;]⑥Right：ifindex<>6then[S’:=S;Index’:=index+1;]數(shù)據(jù)結構的處理

如果我們用（S,index）表示問題中的一個狀態(tài)，S為密碼，index表示光標位置。那么，（Source，1）為問題的初始狀態(tài)，（Target，pos）為問題的目標狀態(tài)。其中pos任意。那么綜合數(shù)據(jù)庫中可能存在的節(jié)點數(shù)為：6*106。

constmaxl=6000000;typestatetype=array[1..6]ofshortint;Nodetype=recordstate:statetype;{密碼}point,step:shortint;{光標位置，按鍵次數(shù)}end;varq:array[0..maxl]ofNodetype;

{隊列}app:array[1..6,0..9,0..9,0..9,0..9,0..9,0..9]ofboolean;{判重數(shù)組}final:statetype;{目標狀態(tài)}算法選擇closed:=0;open:=1;q[1].point:=1;fillchar(app,sizeof(app),false);whiletruedobeginclosed:=closedmodmaxl+1;withq[closed]dobeginifcomparebyte(state,final,6)=0then打印輸出；{如果是目標的話}

調用6條規(guī)則擴展出state新節(jié)點；

ifnotapp[point,state[1],state[2],state[3],state[4],state[5],state[6]]{判重}thenbeginopen:=openmodmaxl+1;q[open].state:=state;q[open].step:=step+1;q[open].point:=point;app[point,state[1],state[2],state[3],state[4],state[5],state[6]]:=true;end;條件1：V=nπH=m層形狀：每層都是一個圓柱體。條件2：設從下往上數(shù)第i(1<=i<=m)層蛋糕是半徑為Ri,

高度為Hi的圓柱。當i<m時，要求Ri>Ri+1且Hi>Hi+1。條件3：表面積Q最小，令Q=Sπ問題：給出的n和m，找出蛋糕的制作方案（適當?shù)腞i和Hi的值），使S最小。

(除Q外，以上所有數(shù)據(jù)皆為正整數(shù))輸入

n(n<=10000)，

m(m<=20)輸出

S（若無解則S=0）。圓柱公式

V=πR2HS側=2πRHS底=πR2問題4:生日蛋糕解析法？

轉變思路，搜索？數(shù)據(jù)庫 用(i,Ri,Hi,Vi,Si)表示第i層蛋糕的一個狀態(tài)。其中Ri,Hi分別為第i層蛋糕的半徑和高，Vi,Si分別表示做完第i層蛋糕后剩下的蛋糕體積和當前蛋糕的表面積?？梢?，初始狀態(tài)：(1,R1,H1,n-R1*R1*H1,R1*R1+2*R1*H1)

目標狀態(tài)：(m,Rm,Hm,0,Sm)

于是，我們的目標是找到一條從初始狀態(tài)到任意目標狀態(tài)的路徑，并且Sm最小.擴展的規(guī)則

(i,Ri,Hi,Vi,Si)(i+1,Ri+1,Hi+1,Vi+1,Si+1)

滿足:

（1）Ri>Ri+1

（2）Hi>Hi+1

（3）Vi+1=Vi-Ri+1*Ri+1*Hi+1

（4）Si+1=Si+2*Ri+1*Hi+1確定第一層蛋糕的大小根據(jù)上一層蛋糕的大小確定下一層蛋糕該怎么做看是否符合條件

1）是否做到了m層

2）是否最終體積為03）是否當前面積最小若上述條件成立，則保留當前最優(yōu)值，否則繼續(xù)做下一層蛋糕，若重做蛋糕基本算法Search(i,Ri,Hi,Si,Vi){對第i層蛋糕進行搜索}if(i=m)and(Vi=0)then更新最優(yōu)值else forRi+1Ri-1downtom-i+1 forHi+1Hi-1downtom-i+1[ Si+1Si+2*Ri+1*Hi+1 Vi+1Vi-Ri+1*Ri+1*Hi+1 Search(i+1,Ri+1,Hi+1,Si+1,Vi+1)]Problem-Cake {枚舉所有的初始狀態(tài)-----第一層蛋糕的大小}forR1mtosqrt(n/m)do/*假設H1=1，只做一層蛋糕*/ forH1ndiv(R1*R1)downtomdo[ S1=2*R1*H1+R1*R1 V1=n-R1*R1*H1 Search(1,R1,H1,S1,V1) ]優(yōu)化？？（1）因為知道余下的蛋糕體積,因此可以估算一下余下側面積,

這樣我們可以就加入如下剪枝條件:if當前的表面積+余下的側面積>當前最優(yōu)值thenexit

設已經做了i層蛋糕,則還需做m-i層,Si’：為第i層蛋糕的側面積,FSi：余下的側面積,怎么求FSi

?

因為:

2Vi=2Ri+1*Ri+1*Hi+1+...+2Rm*Rm*Hm

=Ri+1*

Si+1’+...+Rm*

Sm’

≤Ri+1*(Si+1’+...+Sm’)=Ri+1*

FSi

所以:

FSi≥

2Vi/Ri+1

因此剪枝條件為：

ifSi-1+2*Vi-1/Ri>當前最優(yōu)值thenexit優(yōu)化？？(2)如果剩下的蛋糕材料太少，不能保證做到m層,那么沒有必要繼續(xù)往下做了，設， 最m層半徑和高都為1，Rm=Hm=1

第m-1層半徑和高都為2，Rm-1=Hm-1=2…………

第i+1層半徑和高都為i,Ri=Hi=m–i

這樣，余下的m-i層的最小體積為

因此,剪枝條件為,ifVi<MINithenexit(3)如果剩下的蛋糕材料太多，以最大的方式做完m層,仍有材料剩余,那么沒有必要繼續(xù)往下做了，設， 第i+1層半徑和高分別為，Ri+1=Ri–

1

，Hi+1=Hi–1

第i+2層半徑和高分別為，Ri+2=Ri–2

，Hi+2=Hi–2

…………

第i+j層半徑和高分別為，Ri+j=Ri–j

，Hi+j=Hi–j

這樣，余下的m-i層的最大體積為優(yōu)化？？因此,剪枝條件為,ifVi＞MAXi,R,Hthenexit計算MINifori1tondo[SS+i*i*i;

MINm-iS

]計算MAXi,R,HforR1tosqrt(n)doforH1tondiv(R*R)do[

S0;forimdownto1do[

SS+(R-i)*(R-i)*(H-i);

MAXi,R,HS ] ]初始化Search(i,Ri,Hi,Si,Vi){對每層蛋糕進行搜索}

ifSi+2*Vi/Ri>當前最優(yōu)值thenexit;{剪枝1}ifVi<MINithenexit;{剪枝2}ifVi

＞MAXithenexit;{剪枝3}ifi<mthen forRi+1min(sqrt(vi

divm),Ri–1)downtom-i+1forHi+1min(Vidiv(Ri+1*Ri+1),Hi-1)downtom-i+1[ Si+1Si+2*Ri+1*Hi+1 Vi+1Vi-Ri+1*Ri+1*Hi+1 Search(i+1,Ri+1,Hi+1,Si+1,Vi+1)]elseifVi=0then更新最優(yōu)值程序主框架Problem-Cake1.計算MINi和MAXiR,H;2.forR1mtosqrt(n)do/*假設H1=1，只做一層蛋糕*/3.forH1ndiv(R1*R1)downtomdo[4.S1=2*R1*H1+R1*R15. V1=n-R1*R1*H16.Search(1,R1,H1,S1,V1)7.]問題5：埃及分數(shù)在古埃及，人們使用單位分數(shù)的和(形如1/a的,a是自然數(shù))表示一切有理數(shù)。如：2/3=1/2+1/6,但不允許2/3=1/3+1/3,因為加數(shù)中有相同的。對于一個分數(shù)a/b,表示方法有很多種，但是哪種最好呢？首先，加數(shù)少的比加數(shù)多的好，其次，加數(shù)個數(shù)相同的，最小的分數(shù)越大越好。如：19/45=1/3+1/12+1/18019/45=1/3+1/15+1/4519/45=1/3+1/18+1/30,19/45=1/4+1/6+1/18019/45=1/5+1/6+1/18.最好的是最后一種，因為1/18比1/180,1/45,1/30,1/180都大。給出a,b(0<a<b<1000),編程計算最好的表達方式。輸入：ab輸出：若干個數(shù)，自小到大排列，依次是單位分數(shù)的分母。例如：輸入：1945輸出：5618分析1.節(jié)點類型是一個K元組（a1,a2,...ak）,代表當前解中的分母a1,a2..ak.2.節(jié)點擴展方法按照a1<a2<a3..<ak的順序擴展,擴展第k層節(jié)點的時候，最簡單的辦法就是從a[k-1]+1開始枚舉a[k],一直到預先確定的最大值。但是這個最大值怎么確定呢？直觀的講，a[k]總不能太大，因為如果a[k]太大，1/a[k]就很小，1/a[k+1]..1/a[k+2]..就更小，那么，盡管加了很多項，還可能不夠a/b.例如：例如已經擴展到

19/45=1/5+????

如果第二項是1/100,那么由于19/45-1/5=2/9=0.22222...那么接下來至少要0.2222/(1/100)=22項加起來才足夠2/9,所以繼續(xù)擴展下去至少還要擴展22項,加起來才差不多夠a/b。

PROCEDURESearch(k,a,b);{決定第k個分母d[k]}1.

Ifk=depth+1thenexit{depth需要進行枚舉}2.

elseif(a=1)and(b>d[k-1])then[

｛a整除b的情況｝3.

d[k]:=b;4.

ifnotfoundor(d[k]<answer[k])then更新解;5.

]6.

else[7.

s:=max{bdiva,d[k-1]+1};{確定d[k]的上下界s,t;}t:=(depth-k+1)*bdiva

8.

fori:=stotdo[9.

d[k]:=i;10.m:=gcd(a,b);｛a,b的最大公約數(shù)為m｝11.

search(k+1,(i*a-b)divm,(b*i)divm);12.

]13.

]例6：序關系計數(shù)用關系’<’和’=’將3個數(shù)a、b和c依次排列有13種不同的關系： a<b<c，a<b=c，a<c<b，a=b<c，a=b=c，a=c<b， b<a<c，b<a=c，b<c<a，b=c<a， c<a<b，c<a=b，c<b<a。輸入n輸出n個數(shù)依序排列時有多少種關系。1、枚舉所有序關系表達式由于類似于‘a=b’和‘b=a’的序關系表達式是等價的，為此，規(guī)定等號前面的大寫字母在ASCII表中的序號，必須比等號后面的字母序號小。狀態(tài)（Step，F(xiàn)irst，Can）：其中Step表示當前確定第Step個關系符號；First表示當前大寫字母中最小字母的序號；Can是一個集合，集合中的元素是還可以使用的大寫字母序號邊界條件（step=n）：即確定了最后關系符號搜索范圍（First≤i≤n）：枚舉當前大寫字母的序號約束條件（iinCan）：序號為i的大寫字母可以使用procedureCount(Step，F(xiàn)irst，Can)；{從當前狀態(tài)出發(fā)，遞歸計算序關系表達式數(shù)}beginifStep=nthenbegin{若確定了最后一個關系符號，則輸出統(tǒng)計結果}fori←FirsttondoifiinCanthenInc(Total)；

Exit{回溯}end；{then}fori←Firsttondo{枚舉當前的大寫字母}ifiinCanthenbegin{序號為i的大寫字母可以使用}Count(Step+1，i+1，Can-{i})；{添等于號}Count(Step+1，1，Can-{i}) {添小于號}End{then}end；{Count}該算法的時間復雜度是W(n!)2、粗略利用信息（記憶化搜索）

若已經確定了前k個數(shù)，并且下一個關系符號是小于號，這時所能產生的序關系數(shù)就是剩下的n-k個數(shù)所能產生的序關系數(shù)。設i個數(shù)共有F{i}種不同的序關系，那么，由上面的討論可知，在算法1中，調用一次Count(Step+1，1，Can-{i})之后，Total的增量應該是F{n-Step}。這個值可以在第一次調用Count(Step+1，1，Can-{i})時求出。而一旦知道了F{n-Step}的值，就可以用Total←Total+F{n-Step}代替調用Count(Step+1，1，Can-{i})

procedureCount(Step，F(xiàn)irst，Can)；{Step，F(xiàn)irst，Can的含義同算法1}beginifStep=nthenbegin{若確定了最后一個關系符號，則輸出統(tǒng)計結果}fori←FirsttondoifiinCanthenInc(Total)；Exit{回溯}end；{then}fori←Firsttondo{枚舉當前的大寫字母}ifiinCan{序號為i的大寫字母可以使用}thenbeginCount(Step+1，i+1，Can-{i})；{添等于號}

ifF{n-Step}=-1thenbegin第一次調用}F{n-Step}←Total；Count(Step+1，1，Can-{i})；{添小于號}F{n-Step}←Total-F{n-Step}{F{n-Step}=Total的增量}end{then}elseTotal←Total+