1、枚舉與搜索講稿1有關搜索的NOIP試題 神經(jīng)網(wǎng)絡(2003)-寬搜偵探推理(2003)-枚舉與優(yōu)化傳染病控制(2003)-深搜與優(yōu)化蟲食算(2004)-深搜與優(yōu)化火柴棒等式(2008)-簡單枚舉雙棧排序 (2008)-二分圖的搜索 靶形數(shù)獨(2009)-深搜與優(yōu)化 2簡單枚舉法所謂枚舉，即對可能的解集合一一列舉。解題思路為：首先確定可能的解集合抽象出解包含的參數(shù)，確定每個參數(shù)的數(shù)據(jù)范圍對解的每個參數(shù)的數(shù)據(jù)范圍采用循環(huán)語句一一枚舉 對每次枚舉，根據(jù)題意給定的條件判定是否解，是否是最優(yōu)解。 3火柴棒等式 給你n根火柴棍，你可以拼出多少個形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整

2、數(shù)（若該數(shù)非零，則最高位不能是0）。用火柴棍拼數(shù)字0-9的拼法如圖所示：注意：1. 加號與等號各自需要兩根火柴棍2. 如果AB，則A+B=C與B+A=C視為不同的等式（A、B、C=0）3. n根火柴棍必須全部用上4分析09的數(shù)字所用的火柴數(shù)：6,2,5,5,4,5,6,3,7,6 對于N=24，去掉+，=，實際上數(shù)字只有20根火柴。首先考慮解集合，因為最多為20根火柴組成數(shù)字：不可能為10個1；不可能8個1，1個4；不可能為7個1，2個7或1個0；.C不會超過10005枚舉答案設F(I)表示數(shù)為I時的火柴棍數(shù)FOR A=0 TO 1000 DO IF F(A)best then bestsum

3、；這個算法枚舉狀態(tài)為O（n9） 13從減少重復計算入手記錄先前考察的結(jié)果。在統(tǒng)計長方體2時，只要將長方體1的統(tǒng)計結(jié)果加上長方體3就可以了，而不必按上述算法那樣重新進行計算?？疾爝^程改為 ： for xx1 to x2 do 計算長方體的體積 for yy1 to y2 do sumsum+mapx，y，z2； if sumbest then bestsum； 調(diào)整最優(yōu)解由于利用了計算出的結(jié)果，整個算法的時間復雜度降為O（n8）。143、提取恰當?shù)男畔⑸鲜隹疾鞂嶋H上求出z軸坐標為z2的平面中矩形（x1，y1，x2，y2）的數(shù)和。我們將這個數(shù)和記為value(a) value(A)=value(A

4、BCD)+value(B)-value(BC)-value(BD)這就啟發(fā)我們用另一種方法表示立方體的信息：設recx，y，z表示z軸坐標為z的水平面中矩形（1，1，x，y）的數(shù)和。z軸坐標為z的水平面中左上角為（x1，y1）、右下角為（x2，y2）的矩陣的數(shù)和為recx2，y2，z+ recx1，y1，z-recx2，y1，z-recx1，y2，z15Rec數(shù)組可以在輸入數(shù)據(jù)的同時計算fillchar(rec，size(rec)，0)；rec數(shù)組初始化for z1 to n do 逐層輸入信息 for x1 to n do 逐行輸入z平面的信息for y1 to n do 逐列輸入z平面上x

5、行的信息begin read(mapx，y，z)； 輸入z平面上（x,y）中的數(shù) if (x=1)and(y=1) 計算z平面上以（1，1）為左上角、（x,y）為右下角的矩形的數(shù)和 then rec1，1，zmap1，1，z else if y=1 then recx，y，zrecx-1，n，z+mapx，y，z else recx，y，zrecx，y-1，z+mapx，y，z； end；for 這樣，考察過程就可以改為 sumsum+recx2，y2，z2+recx1，y1，z2-recx2，y1，z2-recx1，y2，z2； if sumbest then bestsum；時間復雜度降為

6、O（n6）。16如果長方體a的數(shù)和是負數(shù)，則長方體a的計算結(jié)果廢棄，考察長方體b-a。因為長方體b的數(shù)和=長方體b-a的數(shù)和+長方體a的數(shù)和，由于長方體a的數(shù)和為負，長方體b-a的數(shù)和一定大于等于長方體b的數(shù)和。由此可見，在累計長方體數(shù)和的時候，只要由上而下地枚舉長方體下底面的z軸坐標即可。設total(z)以z軸坐標為z的平面為下底面的長方體的最大數(shù)和17算法框架for x11 to n do 枚舉所有可能的子平面for x21 to n dofor y11 to n dofor y21 to n do begin total0；以（x1,y1）為左上角、（x2,y2）為右下上角） for

7、z1 to n do 枚舉長方體b下底面的z軸坐標 begin totalmax total，0 + recx2，y2，z + recx1-1，y1-1，z - recx2，y1-1，z - recx-1-1，y2，z； 計算以z為下底面的長方體b的最大數(shù)和 if total best then besttotal； 調(diào)整最優(yōu)解 end； end；這一改進使得考察的狀態(tài)整數(shù)降為n518深度優(yōu)先搜索深度優(yōu)先搜索算法是搜索中的一種控制策略，但與枚舉法不同的是，它是從初始狀態(tài)出發(fā)，運用題目給出的條件、規(guī)則，按照深度優(yōu)先的順序擴展所有可能情況，當所有可能情況都探索過且都無法到達目標的時候，再回退到上一

8、個出發(fā)點，繼續(xù)探索另一個可能情況，這種不斷回頭尋找目標的方法也稱為“回溯法”。深度搜索是求解特殊型計數(shù)題或較復雜的枚舉題中使用頻率最高的一種算法。 19深度搜索算法的幾個重要因素(1) 狀態(tài): 作為遞歸的值參。(2) 邊界條件: 作為遞歸的結(jié)束條件，通常以深度結(jié)束。(3) 遞歸范圍: 作為for循環(huán)的初值和終值。(4) 約束條件: 滿足解的條件。(5) 最優(yōu)性要求：滿足最優(yōu)解的條件。20深度搜索的基本框架procedure dfs(當前狀態(tài))；begin if 當前狀態(tài)為邊界 then begin if 當前狀態(tài)為最佳目標狀態(tài) then 記下最優(yōu)結(jié)果；exit；回溯 end； for i算符最

9、小值 to 算符最大值 do begin 算符i作用于當前狀態(tài)，擴展出一個子狀態(tài)； 標記子狀態(tài)路徑； if (子狀態(tài)滿足約束條件) and (子狀態(tài)滿足最優(yōu)性要求)then dfs(子狀態(tài))； 恢復子狀態(tài)路徑； 回溯 end；end；21N皇后問題 在N*N的棋盤上放置N個皇后而彼此不受攻擊（即在棋盤的任一行，任一列和任一對角線上不能放置兩個皇后），編程求解所有的擺放方法。22基本思想由于皇后的擺放位置不能通過某種公式來確定，因此對于每個皇后的擺放位置可以進行試探；按行放置皇后，每一行放一皇后；對每一行所放置的皇后按列進行試探；若某個位置能放，則放，否則試放下一個位置若某一行沒有任何一個位置可

10、放，則表示前面的皇后沒放好，需要回溯。若n個皇后都放好了，則得到了一個解。23算法基本框架Procedure Try(i:integer)；搜索第i行皇后的位置var j:integer;begin if i=n+1 then 輸出方案； for j:=1 to n do if 皇后能放在第i行第j列的位置 then begin 放置第i個皇后； 對放置皇后的位置進行標記； Try（i+1） 對放置皇后的位置釋放標記； end;end;24邊界條件設置怎樣判斷某列放置了皇后 a: array 1.MaxN of Boolean; 豎線被控制標記怎樣判斷某對角線上放置了皇后 b: array 2

11、.MaxN * 2 of Boolean; 左上到右下斜線被控制標記 c: array 1-MaxN . MaxN-1 of Boolean; 左下到右上斜線被控制標記25程序Procedure Try( i: integer)；var j:integer;begin if i=n+1 then print； for j:=1 to n do if aj and bi+j and ci-j then begin ai:=j; aj:=false; bi+j:=false; ci-j:=false; Try (i+1) aj:=true; bi+j:= true; ci-j:= true; en

12、d;end;26給出一個矩陣及一些國都名：o k d u b l i n dublina l p g o c e v tokyor a s m u s m b londono s l o n d o n romey i b l g l r c bonnk r z u r i c h pariso a i b x m u z oslot p q g l a m v lima要求從這個矩陣中找出這些國都名，并輸出它們的起始位置及方向。尋找國都名 搜索的方向27算法思想將字符矩陣讀入到二維數(shù)組，然后對每一個國都名進行搜索，首先需要在矩陣中找到國都名的第一個字符，然后沿八個方向進行搜索。直到找到國都名

13、為止。若在矩陣中沒有找到，則輸出相應的信息。在搜索過程時，類似八皇后問題，建立一個標志數(shù)組，標識已經(jīng)搜索過的方向，在對八個方向搜索時，可以建立一個方向數(shù)組，使得程序更加簡潔明了 Const Fx : Array1.8,1.2 Of Shortint 定義八個方向 =(0,1),(0,-1),(1,0),(-1,0),(1,-1),(-1,1),(1,1),(-1,-1); 28Procedure Work(T,X,Y:Integer);搜索路徑，T為國都名的字符位置，X，Y為當前搜索的坐標Var I : Integer;Begin If T=Length(S)+1 Then begin 搜索完

14、，打印輸出 Out; exit end; For I:=1 To 8 Do 八個方向進行搜索 Begin X:=X+FxI,1; Y:=Y+FxI,2; 坐標變化 If (AX,Y=ST)And(BX,Y) Then Begin W:=W+Chr(I+48); 記錄路徑 BX,Y:=False; 設置已經(jīng)搜索 Work(T+1,X,Y); 繼續(xù)搜索下一個 Delete(W,Length(W),1);恢復原路徑 BX,Y:=True; 恢復標志 End; X:=X-FxI,1; Y:=Y-FxI,2; 返回后，坐標恢復 End;End;29構(gòu)造字串生成長度為n的字串，其字符從26個英文字母的前p

15、(p26)個字母中選取，使得沒有相鄰的子序列相等。例如p=3，n=5時 a b c b a滿足條件 a b c b c不滿足條件輸入：n，p輸出：所有滿足條件的字串30分析狀態(tài)：待擴展的字母序號i。由于該變量的存儲量太大，因此我們將s設為全局變量；邊界條件：產(chǎn)生了一個滿足條件的字串，即 i=n+1；搜索范圍：從a開始的后p個字符； 約束條件：當前字串沒有相鄰子串相等的情況31procedure solve (i: integer)； var j, k: integer； t : longint ; begin if i=n+1 then 若產(chǎn)生了一個滿足條件的字串，則輸出 begin writ

16、eln (s)； inc( t )；exit 回溯 end； for k1 to p do 搜索每一個可填字母 begin ss+chr(64 + k )；j1；檢查當前字串是否符合條件 while (j=i div 2) and (copy(s,length(s)-j+1,j)copy(s,length(s)-2*j+1,j) do inc (j)； if ji div 2 then solve(i+1)； 若當前字串符合條件，則遞歸擴展下一個字母 delete( s, length (s), 1 ) 恢復填前的字串 end;end;32記憶化搜索1. 遞歸前對尚待搜索的信息進行預處理 如果

17、搜索對象是通過某種運算直接得出其結(jié)果的，那么搜索前一般需進行預處理通過相應運算將所有搜索對象的計算結(jié)果置入常量表，搜索過程中只要將當前搜索對象的結(jié)果值從常量表取出即可。2.記憶化搜索如果解答樹中存在一些性質(zhì)相同的子樹，那么，只要我們知道了其中一棵子樹的性質(zhì)，就可以根據(jù)這個信息，導出其它子樹的性質(zhì)。這就是自頂向下記憶化搜索的基本思想。33序關系計數(shù)用關系和=將3個數(shù)a、b和c依次排列有13種不同的關系：abc， ab=c， acb， a=bc， a=b=c， a=cb， bac， ba=c， bca， b=ca， cab， ca=b， cba。輸入n輸出n個數(shù)依序排列時有多少種關系。341 、枚

18、舉所有序關系表達式由于類似于a=b和b=a的序關系表達式是等價的，為此，規(guī)定等號前面的大寫字母在ASCII表中的序號，必須比等號后面的字母序號小。狀態(tài)（Step，F(xiàn)irst，Can）：其中Step表示當前確定第Step個關系符號；First表示當前大寫字母中最小字母的序號；Can是一個集合，集合中的元素是還可以使用的大寫字母序號邊界條件（step=n）：即確定了最后關系符號搜索范圍（Firstin）：枚舉當前大寫字母的序號約束條件（i in Can）：序號為i的大寫字母可以使用35procedure Count(Step，F(xiàn)irst，Can)； 從當前狀態(tài)出發(fā)，遞歸計算序關系表達式數(shù) begi

19、n if Step=n then begin 若確定了最后一個關系符號，則輸出統(tǒng)計結(jié)果 for iFirst to n do if i in Can then Inc(Total)； Exit 回溯 end；then for iFirst to n do 枚舉當前的大寫字母 if i in Can then begin 序號為i的大寫字母可以使用 Count(Step+1，i+1，Can-i)； 添等于號 Count(Step+1，1，Can-i) 添小于號 Endthen end； Count該算法的時間復雜度是W(n!)362、粗略利用信息 若已經(jīng)確定了前k個數(shù)，并且下一個關系符號是小于號

20、，這時所能產(chǎn)生的序關系數(shù)就是剩下的n-k個數(shù)所能產(chǎn)生的序關系數(shù)。設i個數(shù)共有Fi種不同的序關系，那么，由上面的討論可知，在算法1中，調(diào)用一次Count(Step+1，1，Can-i)之后，Total的增量應該是Fn-Step。這個值可以在第一次調(diào)用Count(Step+1，1，Can-i)時求出。而一旦知道了Fn-Step的值，就可以用TotalTotal+Fn-Step 代替調(diào)用Count(Step+1，1，Can-i) 37procedure Count(Step，F(xiàn)irst，Can)； Step，F(xiàn)irst，Can的含義同算法1 begin if Step=n then begin 若確

21、定了最后一個關系符號，則輸出統(tǒng)計結(jié)果 for iFirst to n do if i in Can then Inc(Total)；Exit 回溯 end；then for iFirst to n do 枚舉當前的大寫字母if i in Can 序號為i的大寫字母可以使用then begin Count(Step+1，i+1，Can-i)；添等于號 if Fn-Step=-1 then begin 第一次調(diào)用 Fn-Step Total；Count(Step+1，1，Can-i)； 添小于號 Fn-Step Total-Fn-Step Fn-Step=Total的增量end thenelse

22、TotalTotal+Fn-Step Fn-Step已經(jīng)求出 endthen end；count該算法實質(zhì)上就是自頂向下記憶化方式的搜索，它的時間復雜度為W(2n)。 383、充分利用信息在搜索的過程中，如果確定在第k個大寫字母之后添加第一個小于號，則可得到下面兩條信息：第一條信息：前k個大寫字母都是用等號連接的。前半部分將產(chǎn)生的序關系數(shù)，就是n個物體中取k個的組合數(shù)第二條信息：在此基礎上繼續(xù)搜索，將產(chǎn)生Fn-k個序關系表達式。這樣，我們可以得到Fn 的遞推關系式：采用上述公式計算Fn的算法記為算法3，它的時間復雜度是W(n2)。39var Total ：Comp；答案 F ：array0.m

23、axn of Comp；Fi為i個數(shù)的序關系表達式個數(shù) i，j ：Integer； x ：Comp； begin FillChar(F，Sizeof(F)，0)；F初始化 F0 1； for i1 to n do begin遞推F數(shù)組 Fi 0；x1； for j1 to i do begin 計算Fi xx*(i-j+1)/j；Fi Fi+x*Fi-j Endfor end；for writeln(Fn)； 輸出結(jié)果 end；main40傳染病控制傳染病的傳播具有如下性質(zhì)：第一:它的傳播途徑是樹型的，一個人X只可能被某個特定的人Y感染，只要Y不得病，或者是XY之間的傳播途徑被切斷，則X就不會

24、得病。第二:這種疾病的傳播有周期性，在一個疾病傳播周期之內(nèi)，傳染病將只會感染一代患者，而不會再傳播給下一代。第三:在一個疾病傳播周期內(nèi)，只能設法切斷一條傳播途徑，而沒有被控制的傳播途徑就會引起更多的易感人群被感染（也就是與當前已經(jīng)被感染的人有傳播途徑相連，且連接途徑?jīng)]有被切斷的人群）。當不可能有健康人被感染時，疾病就中止傳播。所以，蓬萊國疾控中心要制定出一個切斷傳播途徑的順序，以使盡量少的人被感染。你的程序要針對給定的樹，找出合適的切斷順序 。41貪心我們首先來通過對樣例數(shù)據(jù)和其它的一些比較簡單的數(shù)據(jù)進行一些觀察，很容易得到一種貪心的算法，對這種算法可做如下的描述：1我們用Sum(i)表示以i

25、為根節(jié)點的子樹上的節(jié)點總數(shù)。那么我們每次砍掉當前層中還未砍掉的節(jié)點里面使得Sum(i)取到最大值的那個節(jié)點；2重復第1步直到當前層中的節(jié)點為空。 一個反例42隨機化搜索1我們通過隨機函數(shù)來選擇即將被砍掉的節(jié)點，可以通過設置權(quán)值來使得算法更大可能地去選擇“看起來最優(yōu)”的決策；2重復第1步直到當前層中的節(jié)點為空；3對前兩步執(zhí)行多次并選取所得到的最優(yōu)結(jié)果。這個算法被設計出來以后，就很難在構(gòu)造出能使這個算法失敗的數(shù)據(jù)了，因此在考場上能夠設計出來這個算法就已經(jīng)很令人滿意了，而事實也恰恰如此（這個算法可以通過所有的測試數(shù)據(jù)）。43蟲食算所謂蟲食算，就是原先的算式中有一部分被蟲子啃掉了，需要我們根據(jù)剩下的數(shù)

26、字來判定被啃掉的字母。 BADC + CBDA DCCC 給出一個N進制的蟲食算式，相同的字母代表相同的數(shù)字，不同的字母代表不同的數(shù)字。要求求出滿足這個算式的唯一一組解，也就是字母和數(shù)字的一一對應關系. 44解決方案1要求一一對應的關系，就可以枚舉這些一一對應的關系，找出符合的一項。這樣，關系總數(shù)有O(N!)個，最壞情況下必須枚舉所有的關系，并且加以判斷，復雜度高達O(N*N!)！45優(yōu)化大體上，從算式最后一位開始模擬運算情況，當可遞推時遞推，不可遞推則枚舉。對于一豎列，先處理兩個加數(shù)，當遇到的字母的值不確定時，則枚舉當前位（注意與前面的情況判重）；否則不作為處理和，當遇到的字母的值不確定時,

27、可從加數(shù)部分確定的值來確定（注意與前面的情況判重和進位）；否則看加數(shù)部分確定的值是否能得到和部分（注意進位）。引出矛盾就回溯。例如它最后一位的情況是(D+E) mod N=A, 對于最后一位只要枚舉D,E的情況；A 則可以由D,E的值遞推而來。對于倒數(shù)2位, (E+C+最后一位進位) mod N=A ；E的值可以用前面的結(jié)果；枚舉C；判斷A是否為(D+C+最后一位進位) mod N雖然復雜度還是O(N!)，但這種方法限制很多（相當于剪枝）。 46解決方案3兩個M位數(shù)相加，可以按位相加，設第i位的進位xi=1,表示有進位，為xi表示沒有進位。 BADC+ CBDA DCCC 枚舉每位是否進位，復

28、雜度是O(2n), (因為首位不可能進位，無須枚舉)。然后，用高斯消元法來解方程，復雜度是O(n3) 。總復雜度是O(2n*n3) 。47優(yōu)化在解決方案3的基礎上，我們可以對進位的枚舉剪枝。觀察這個豎列：A+B=C，若無進位則有A=C且BC且B=C.若能推導出A=A （A,B為任何不相等字母），則當前的枚舉不可行?？捎眠f歸枚舉，從后向前枚舉，處理一個豎列時則用上述2個不等式，看是否矛盾。數(shù)據(jù)結(jié)構(gòu)用鄰接矩陣。（規(guī)定A=B，在有向圖中有邊）。若加進不等式A=B ，要加入所有x(x=A) =y(B=y)，枚舉x,y，用O(n2)的時間。再判斷是否有x=y.48靶形數(shù)獨輸入9*9的數(shù)，其中一些是空格，

29、要求完成 靶形數(shù)獨，使得得到分數(shù)最大。49搜索剪枝首先是搜索順序的控制. 我們總是選擇當前選擇余地最小的格子進行搜索. 如果有兩個格子的選擇范圍一樣大, 那么優(yōu)先搜索盡量靠里的格子. 這樣可以使得搜索樹的上端枝條盡量少, 顯著地減少了搜索樹的節(jié)點數(shù). 優(yōu)先搜索靠里的格子是為了盡快得到一個得分較高的解, 提高最優(yōu)性剪枝的效率最優(yōu)性剪枝: 設當前還沒有填入的數(shù)字總和為sum, 當前的得分為cur, 最優(yōu)得分為best, 如果sum*10+cur=best, 那么已經(jīng)沒有繼續(xù)搜索的必要了, 剪枝.使用位運算來進行集合操作: 計算選擇范圍大小, 判斷數(shù)字k能否放入(i, j). 可以顯著減小算法的常數(shù)

30、.50寬度優(yōu)先搜索寬度優(yōu)先搜索算法也是搜索中的一種控制策略，它不像深度優(yōu)先搜索那樣一直往前搜索，直到找到答案位置。寬度優(yōu)先搜索是對每一步都擴展出所有可能的狀態(tài)，逐層往下搜索。對于一般圖而言，它從某個未被訪問的頂點v出發(fā),依次訪問v的各個未曾訪問過的鄰接點,直到所有已被訪問的鄰接點都被訪問到.要實現(xiàn)寬度優(yōu)先，必須借助對列存放擴展的節(jié)點。 51寬度優(yōu)先搜索算法框架procedure bfs(v);Init_queue(q); Visite(v); vistedv:=true; Insert_queue(q,w)；While not empty(q) do 取出隊首元素 vFor 對所有v擴展出來的

31、元素wif not visitedw then visite(w);visitedw:=true; Insert_queue(q,w) delete_queue(q,v);52街道賽跑下圖給出了一個沿街道賽跑的路線。圖中有許多點，給以標號0，1，N(此圖中N=9)，點之間可以用含箭頭的線相連。標號為0的點是起點；標號為N的點為終點。含箭頭的線表示單向通行的街道。運動員沿箭頭所指方向從一個點跑向另一個點；在每一個點上，運動員可以選擇任何一個箭頭(向外的)繼續(xù)向前跑。53一個完整路線具有如下特點： 1路線中每一點都可從出發(fā)點到達； 2路線中每一點都可到達終點； 3終點處沒有向外的箭頭。 運動員要到

32、達終點，但不要求路線(圖)中的每一點都經(jīng)過。但是路線(圖)中的某些點是必經(jīng)之點。上圖的例子中，必經(jīng)之點是：0，3，6，9。 任務A: 題目給出一個完整路線（圖），請編程找出所有必經(jīng)之點。請注意，輸出必經(jīng)之點時，應不包括起點和終點。任務B: 假定賽跑必須在相鄰的2天來舉行。因此，要把原來給定的完整路線（圖）分成兩個子路線（圖）。第1天從點0出發(fā)，結(jié)束于“分裂點”。第2天從“分裂點”出發(fā)，結(jié)束于點N。 題目給出一個完整路線（圖）C，請編程輸出所有可能的“分裂點”（任務B）?！胺至腰c”S一定不是起點或終點。C可被S分成兩個完整的子路線：這兩個子路線沒有公共的箭頭線，并且S是這兩個子路線的唯一公共點。

33、在上的例子中，僅點3是“分裂點”。54輸入數(shù)據(jù)：輸入數(shù)據(jù)描述一個完整路線（最多50個點，最多100個箭頭），共n1行。前面n行描述箭頭的終點，其中第i行中的每一個數(shù)字表示從點i（1in）出發(fā)的每一個箭頭的終點，以2作為該行的結(jié)束。最后一行（第n+1行）中有一個數(shù)字1，表示輸入結(jié)束。輸出數(shù)據(jù)：輸出兩行數(shù)據(jù)，第1行表示必經(jīng)點（子任務A）首先是必經(jīng)點的總數(shù)，其后是必經(jīng)點的標號，標號的順序無關緊要。第2行表示“分裂點”：首先是分裂點的總數(shù)，其后是分裂點的標號，標號出現(xiàn)的先后順序無關緊要（子任務B）。55分析必經(jīng)點:是指運動員從起點0出發(fā)，沿箭頭方向跑，無論走哪條路線，都經(jīng)由該點到達終點N。所有這些點組

34、成必經(jīng)點的集合。反之，在完整路線中去除必經(jīng)點集合中的任一個點，無論運動員選擇哪條路線跑，都不可能從起點0跑至終點N。分裂點: 某點是必經(jīng)點； 在完整路線中去除這個必經(jīng)點后，由起點出發(fā)的運動員無論如何也不會跑到由這個必經(jīng)點出發(fā)的任一箭頭的終點； 完整路線中去除這個必經(jīng)點后的所有點，分成兩個互為獨立的集合: 可從出發(fā)點0到達。這些點組成子路徑1； 無法從出發(fā)點0到達。這些點組成子路徑2； 兩個集合中的點之間，無任何箭頭相連；56思路從點0開始，按逐層搜索的方法對刪除當前判別點后的路線重復進行訪問，直至找不到可訪問的點為止。廣度搜索的結(jié)果，將路線上的所有點(除當前判別點外)分為兩個集合： 寬度優(yōu)先搜

35、索中訪問到的點，即從出發(fā)點0可達的點集合，設這些點到達標志； 寬度優(yōu)先搜索中未訪問過的點，即不可從出發(fā)點0到達的點集合。這些點設未到達標志；若終點N在第二個集合中，則當前判別點是必經(jīng)點，然后再判別兩個集合是否互為獨立。若與必經(jīng)點相連的所有點都在第二個集合中，且兩個集合中的點之間無任何箭頭相連，則這個必經(jīng)點亦是分裂點。 57輸入完整路線的相鄰矩陣data1;For i1 to n-1 do /順序設點1、點2，點N1為當前判別點 begin datadata1; /刪除頂點i，構(gòu)建新圖的相鄰矩陣data； for j1 to n do begin datai,j0; dataj,i0 end; BFS(0)； /寬