【正文】 結點符合條件then begin open增1，并把新結點存入數(shù)據(jù)庫隊尾；if新結點與原有結點有重復 then 刪于該結點(open減1)else if 新結點即目標 then 輸出并退出 。 end{if}。 end{for}。until closed=open。{隊列為空}使用廣度優(yōu)先搜索時，離根結點最近的結點先擴展，所以廣度優(yōu)先搜索法比較適合求步數(shù)最少的解，由于深度優(yōu)先使用了標志法，使得存儲空間大大減少，而廣度優(yōu)先要保留所有搜索過的節(jié)點，隨著搜索程度的加深，所需的存儲空間成指數(shù)增加。因此在必要時我們采用雙向搜索來減少搜索空間和存儲空間，如下面的例子。廣度優(yōu)先算法應用例 字串變換（NOIP2002tg）[問題描述]:已知有兩個字串 A$, B$ 及一組字串變換的規(guī)則（至多6個規(guī)則）:A1$ B1$　A2$ B2$ 規(guī)則的含義為：在 A$中的子串 A1$ 可以變換為 B1$、A2$ 可以變換為 B2$ …。例如：A$＝39。abcd39?！$＝39。xyz39。 變換規(guī)則為：‘a(chǎn)bc’‘xu’　‘ud’‘y’　‘y’‘yz’　則此時，A$ 可以經(jīng)過一系列的變換變?yōu)?B$，其變換的過程為：‘a(chǎn)bcd’‘xud’‘xy’‘xyz’ 共進行了三次變換，使得 A$ 變換為B$。[輸入]:鍵盤輸人文件名。文件格式如下：　　A$ B$　　A1$ B1$ \　　A2$ B2$ | 變換規(guī)則　　... ... /　　所有字符串長度的上限為 20。[輸出]:輸出至屏幕。格式如下：　　若在 10 步（包含 10步）以內(nèi)能將 A$ 變換為 B$ ，則輸出最少的變換步數(shù)；否則輸出NO ANSWER![輸入輸出樣例]:abcd xyzabc xuud yy yz屏幕顯示：3算法分析：此題是求變換的最少步數(shù)，很顯然可以使用廣度優(yōu)先搜索法，如果直接從初狀態(tài)搜到目標狀態(tài)，最壞情況下存儲的結點數(shù)超過6的10次方冪，搜索空間過大，因此我們考慮使雙向搜索，同時從初始狀態(tài)和目標狀態(tài)向中間狀態(tài)搜索，當相遇時搜索結束。采用雙向搜索，存儲的結點數(shù)還有可能超限，我們在前向搜索隊列中存儲5步內(nèi)變換的結點，在后向搜索隊列中，由于第5步產(chǎn)生的結點只是用來與前向隊列中的結點比較，所以可以不存儲在隊列中，后向搜索隊列只需存儲4步內(nèi)的結點，這樣就解決了存儲空間問題。為了使用方便，在程序設計中用一個數(shù)組a[1..max]存儲兩個隊列，前向搜索隊列為a[1..mid]，后向搜索隊列為a[mid..max]，用st存儲搜索方向，st=0表示前向搜索，st=1表示后向搜索，用op[st]和cl[st]分別表示隊列尾指針和首指針，用be表示隊列起始位置，循環(huán)產(chǎn)生每一個結點，若在10內(nèi)無解退出循環(huán)，若在10內(nèi)找到解則輸出解并退出程序。源程序：const mid=12000。max=16000。type node=record s:string。x:byte。end。var i,mark:integer。 a:array [1..max]of ^node。 x:array[0..6,0..1]of string[20]。 d,fil:string。 op,cl:array [0..1] of integer。procedure Init。{讀取數(shù)據(jù)，初始化}var f:text。t:string。begin readln(fil)。 assign(f,fil)。reset(f)。i:=0。 while not eof(f) do begin readln(f,t)。 x[i,0]:=copy(t,1,pos(39。 39。,t)1)。 x[i,1]:=copy(t,pos(39。 39。,t)+1,length(t))。 inc(i)。 end。{while} mark:=i1。close(f)。end。{判斷是否到達目標狀態(tài)}procedure bool(be,st:integer)。begin for i:=midbe+1 to cl[1st] do if a[cl[st]]^.s=a[i]^.s then begin writeln(a[cl[st]]^.x+a[i]^.x)。 halt。 end。{if}end。{判斷節(jié)點是否與前面的結點重復}procedure check(be,st:integer)。begin for i:=be+1 to cl[st]1 doif a[i]^.s=a[cl[st]]^.s thenbegin dec(cl[st])。exit。 end。 bool(be,st)。end。 {擴展產(chǎn)生新節(jié)點}procedure expand(be,st:integer)。var i,j,k,lx,ld:integer。begin inc(op[st])。d:=a[op[st]]^.s。 k:=a[op[st]]^.x。ld:=length(d)。 for i:=1 to mark do begin lx:=length(x[i,st])。 for j:=1 to ld do begin if (copy(d,j,lx)=x[i,st]) then begin if (st1)or(k4)then begin inc(cl[st])。 new(a[cl[st]])。 end。{if} a[cl[st]]^.s:= copy(d,1,j1)+ x[i,1st]+ copy(d,j+lx,ld)。 a[cl[st]]^.x:=k+1。 check(be,st)。{檢查是否重復} end。{if} end。{for} end。{for}end。procedure bfs。var be,k,st:integer。Begin for st:=0 to 1 do begin if st=0 then be:=0 else be:=mid。 op[st]:=be+0。cl[st]:=be+1。 new(a[cl[st]])。 a[cl[st]]^.s:=x[0,st]。 a[cl[st]]^.x:=0。 end。{for} repeat if (op[0]cl[0])and(a[cl[0]]^.x=5)then expand(0,0)。 if (op[1]cl[1])and(a[cl[1]]^.x=5)then expand(mid,1)。 until(op[0]=cl[0])or(a[cl[0]]^.x5)or(op[1]=cl[1])or (a[cl[1]]^.x5)。End。BEGIN init。bfs。writeln(39。NO ANSWER!39。)END.兩種搜索算法的比較：搜索方式擴展方式數(shù)據(jù)結構適合求解的問題深度優(yōu)先后產(chǎn)生先擴展?？尚薪饣蛩薪鈴V度優(yōu)先先產(chǎn)生先擴展隊列最優(yōu)解在選擇搜索方式時，并不是完全遵循以上原則，具體還是要根據(jù)題目的要求而定。在求最優(yōu)解時，如果搜索的深度不大，我們也可以考慮使用深度優(yōu)先搜索；在求解可行解時，如果搜索的深度沒有限制，或者搜索的代價與搜索的深度成正比,我們也應該使用廣度優(yōu)先搜索。算法在信息學奧賽中的應用（動態(tài)規(guī)劃法）在學習動態(tài)規(guī)劃法之前，我們先來了解動態(tài)規(guī)劃的幾個概念 階段：把問題分成幾個相互聯(lián)系的有順序的幾個環(huán)節(jié)，這些環(huán)節(jié)即稱為階段。 狀態(tài)：某一階段的出發(fā)位置稱為狀態(tài)。 決策：從某階段的一個狀態(tài)演變到下一個階段某狀態(tài)的選擇。 狀態(tài)轉(zhuǎn)移方程：前一階段的終點就是后一階段的起點，前一階段的決策選擇導出了后一階段的狀態(tài)，這種關系描述了由k階段到k+1階段狀態(tài)的演變規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。動態(tài)規(guī)劃法的定義：在求解問題中，對于每一步?jīng)Q策，列出各種可能的局部解，再依據(jù)某種判定條件，舍棄那些肯定不能得到最優(yōu)解的局部解，在每一步都經(jīng)過篩選，以每一步都是最優(yōu)解來保證全局是最優(yōu)解，這種求解方法稱為動態(tài)規(guī)劃法。一般來說，適合于用動態(tài)規(guī)劃法求解的問題具有以下特點： 可以劃分成若干個階段，問題的求解過程就是對若干個階段的一系列決策過程。 每個階段有若干個可能狀態(tài) 一個決策將你從一個階段的一種狀態(tài)帶到下一個階段的某種狀態(tài)。 在任一個階段，最佳的決策序列和該階段以前的決策無關。 各階段狀態(tài)之間的轉(zhuǎn)換有明確定義的費用，而且在選擇最佳決策時有遞推關系（即動態(tài)轉(zhuǎn)移方程）。動態(tài)規(guī)劃法所處理的問題是一個多階段最優(yōu)化決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達到結束狀態(tài)。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線。如下圖：動態(tài)規(guī)劃設計都有著一定的模式，一般要經(jīng)歷以下幾個步驟： 劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。確定狀態(tài)：將問題發(fā)展到各個階段時所處的各種客觀情況用不同的狀態(tài)表示出來。確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因為決策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導出本階段的狀態(tài)，所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可以寫出。 尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。 程序設計實現(xiàn)：動態(tài)規(guī)劃的主要難點在于理論上的設計，一旦設計完成，實現(xiàn)部分就會非常簡單。根據(jù)以上的步驟設計，可以得到動態(tài)規(guī)劃設計的一般模式：for k:=階段最小值to 階段最大值do {順推每一個階段} for I:=狀態(tài)最小值to 狀態(tài)最大值do {枚舉階段k的每一個狀態(tài)} for j:=決策最小值to 決策最大值do {枚舉階段k中狀態(tài)i可選擇的每一種決策}f[ik]:=min（max）{f[ik1]+a[ik1，jk1]|ik1通過決策jk1可達ik} 有了以上的設計模式，對于簡單的動態(tài)規(guī)劃問題，就可以按部就班地進行動態(tài)規(guī)劃設計。動態(tài)規(guī)劃算法應用例1：合唱隊形（noip2004tg）【問題描述】N位同學站成一排，音樂老師要請其中的(NK)位同學出列，使得剩下的K位同學排成合唱隊形。合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1, 2, …, K，他們的身高分別為T1, T2, …, TK，則他們的身高滿足T1 T2 … Ti , Ti Ti+1 … TK (1 = i = K)。你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形?！据斎胛募浚? = N = 100），表示同學的總數(shù)。第一行有n個整數(shù)，用空格分隔，第i個整數(shù)Ti（130 = Ti = 230）是第i位同學的身高（厘米）?！据敵鑫募浚@一行只包含一個整數(shù)，就是最少需要幾位同學出列?！緲永斎搿?186 186 150 200 160 130 197 220【樣例輸出】 4算法分析：此題采用動態(tài)規(guī)劃法求解。先分別從左到右求最大上升子序列，從右到左求最大下降子序列，再枚舉中間最高的一個人。算法實現(xiàn)起來也很簡單，時間復雜度O(N^2)。我們先考慮如何求最大上升子序列的長度，設f1(i)為前i個同學的最大上升子序列長度。若要求f1(i)，必須先求得f1(1),f1(2),…,f1(i1)，再選擇一個最大的f1(j)（ji），在前j個數(shù)中的最大上升序后添加Ti，就可得到前i個數(shù)的最大上升子序列f1(i)。這樣就得到狀態(tài)轉(zhuǎn)移方程：f1(i)=max{f1(j)+1} (ji,TjTi)邊界條件：f1(1)=1。設f2(i)為后面Ni+1位排列的最大下降子序列長度，用同樣的方法可以得到狀態(tài)轉(zhuǎn)移方程：f2(i)=max{f2(j)+1} (ij,TjTi)；邊界值為f2(N)=1。有了狀態(tài)轉(zhuǎn)移方程，程序?qū)崿F(xiàn)就非常容易了。源程序：var t,f1,f2:array[1..100]of byte。 i,j,n,max:integer。begin assign(input,39。39。)。 reset(input)。 readln(n)。 for i:=1 to n do begin read(t[i])。f1[i]:=1。f2[i]:=1。end。{for} close(input)。 max:=0。 for i:=2 to n do for j:=1 to i1 do begin if (t[i]t[j])and(f1[j]=f1[i]) then f1[i]:=f1[j]+1。 {從左到右求最大上升子序列} if (t[ni+1]t[nj+1])and(f2[nj+1]=f2[ni+1]) then f2[ni+1]:=f2[nj+1]+1。 {從右到左求最大下降子序列} end。{for} for i:=1 to n do if maxf1[i]+f2[i] then max:=f1[i]+f2[i]。 {枚舉中間最高的} assign(output,39。39。)。rewrite(output)。 writeln(nmax+1)。 close(output)。end.運用動態(tài)規(guī)劃法求解問題的關鍵是找出狀態(tài)轉(zhuǎn)移方程，只要找出了狀態(tài)轉(zhuǎn)移方程，問題就解決了一半，剩下的事情就是解決如何把狀態(tài)轉(zhuǎn)移方程用程序?qū)崿F(xiàn)。