計算機算法基礎 第2版 習題及答案 第16章

PAGE16第16章 窮舉搜索用回溯法設計一個給圖G(V,E)著色的算法。我們假定圖是用鄰接矩陣表示，而可用顏色的集合是C={1,2,…,m}，m可視為常數(shù)。我們要求把所有合法的著色全部輸出。解： 假設圖的頂點集合是V={v1,v2,…,vn}，鄰接矩陣是A[1..n,1..n]，其中A[i,j]=1表示頂點vi和vj之間有邊(1≤i,j≤n)。我們用一個n元組(x[1],x[2],…,x[n])表示對這n個頂點的著色，其中x[i]C是對頂點vi的著色(1≤i≤n)，這是著色問題的一個顯示約束。圖G的一個合法的著色還必須滿足隱式約束，即如果A[i,j]=1,那么必須有x[i]x[j]。搜索樹中第k層的一個點x用一個k元組x[1..k]=(x[1],x[2],…,x[k])表示，它表示前k個頂點已著色為x[1],x[2],…,x[k]，它的兒子有m個，每個對應一個(k+1)元組，x[1..k+1]=(x[1],x[2],…,x[k],x[k+1])，其中x[k+1]分別是1,2,…,和m。我們先設計一個判定函數(shù)Valid(k,c,x[1..k-1])，用來檢查樹中(k-1)層的一個活點(x[1],x[2],…,x[k-1])的一個兒子y=(x[1],x[2],…,x[1..k-1],x[k])，如果x[k]=c，也就是把頂點vk著色為c，是否是活點。這里，一個k層的活點要滿足顯示約束x[i]C，還要滿足前k個頂點的隱式約束。下面是Valid(k,c,x[1..k-1])算法的偽碼。Valid(k,c,x[1..k-1]) //圖G(V,E)的鄰接矩陣A為默認輸入//input:A[1..n,1..n],x[1..k-1],k,c (如果k=1，則x[1..k-1]為空，用x[0]=0表示)fori1tok-1ifA[k,i]=1andx[i]=c thenreturnfalseendifendforreturntrueEnd下面是給圖G(V,E)著色的回溯法的偽碼m-Color(k,x[1..k-1]) //這是回溯法的遞歸形式供后面主程序調(diào)用，矩陣A為默認輸入//input:x[1..k-1],A[1..n,1..n],k(如果k=1，則x[1..k-1]為空，用x[0]=0表示)forc1tomifvalid(k,c,x[1..k-1]))=true then x[k]c //第k個點著色為c，這個兒子是活點 ifk=n //這個點是答案點 then countcount+1 //全局變量，統(tǒng)計答案點個數(shù) outputx[1..n] //輸出這個合法著色 else m-color(k+1,x[1..k]) //否則從這點遞歸下去 endifendifendforEnd下面是主程序Color-Main(A[1..n,1..n],C) //C={1,2,…,m}//input:A[1..n,1..n],Ccount0x[0]0m-color(1,x[0])ifcount=0 thenreturn(notm-colorable) elsereturn(Thereare’count‘differentvalidcolorings)endifEnd我們知道，找出圖G(V,E)的一個最大團是一個NPC問題。請設計一個回溯算法來搜索圖G的一個最大團。假定圖G是用鄰接矩陣表示的。解： 假設圖G的頂點集合是V={v1,v2,…,vn}，鄰接矩陣是A[1..n,1..n]，其中A[i,j]=1表示頂點vi和vj之間有邊。我們用一個k元組x=(x[1],x[2],…,x[k])表示搜索樹中k層的一個點，它代表前面k個頂點的一個子集C(k≤n)，其中x[i]=1表示vi屬于集合C，而x[i]=0表示vi不屬于集合C(1≤i≤k)。子集C也許是一個團，也許不是。因此，x[i]{0,1}是這個搜索空間的顯示約束(1≤i≤n)。一個k層的點x有兩個k+1層的兒子，它們是在點x所代表的子集C的基礎上，對應x[k+1]的兩個取值，一個是x[k+1]=0，另一個是x[k+1]=1。如果k層的一個點x所代表的子集不構成一個團，那么這個點是個死點。顯然，死點以下的搜索樹可被刪除。因為我們只需要找一個最大團，所以用一個專門的n元組y[1..n]=(y[1],y[2],…,y[n])記錄當前找到的最大團，而它含有的頂點個數(shù)用變量largest來記錄。這是一個全局變量，一旦發(fā)現(xiàn)更大的團，則更新這個全局變量。給定搜索樹中k-1層的一個活點x=(x[1],x[2],…,x[k-1])，我們用size(x,k-1)表示它對應的團C的頂點個數(shù)|C|，顯然有size(x,k-1)k-1。我們需要設計一個判定函數(shù)，當擴展點是活點x時，判斷它的兩個兒子是否是值得發(fā)展的活點。它需要做下面幾件事：檢測點x的每個兒子(x[1],x[2],…,x[k-1],x[k])(x[k]=0或1)代表的子集是否是一個團。如果不是，該兒子成死點。當一個兒子代表的子集C是一個團時，還要檢查這個團能否有希望發(fā)展為比目前找到的最大的團還要大的團。辦法是把余下的(n-k)個頂點全部加到這個團中，如果加上后的頂點個數(shù)，即size(x,k)+(n-k)，比largest要小或相等，那么這個點也是個死點，否則是個活點。當一個兒子被判定是個活點時，如果它對應的團比當前找到的最大團大，則更新變量largest和n元組y[1..n]。這里，我們要指出的是，如果x[k]=1的兒子是一個團時，必有size(x,k)=size(x,k-1)+1。而且，不論是否會更新largest，都有size(x,k)+(n-k)>largest，除非n=k。這是因為，如果不更新，我們有size(x,k)+(n-k)=size(x,k-1)+1+(n-k)=size(x,k-1)+(n-(k-1))>largest。如果更新，那么，(更新后的largest)=size(x,k)。我們有size(x,k)+(n-k)=(更新后的largest)+(n-k)>(更新后的largest)，除非n=k。然而，如果n=k，這個兒子是底層一個點，更新largest后，它成為死點。當然，它對應的團的規(guī)模對應于更新后的largest被記下。所以，如果x[k]=1的兒子是一個團，并且k<n，它必定是個活點?；厮莘ǖ膫未a如下，其中，子程序Clique(k,x[1..k-1])實現(xiàn)上述判定函數(shù)功能的第(1)部分，即用來檢查活點x[1..k-1]的一個x[k]=1的兒子是否對應一個團。判定函數(shù)的另兩部分的功能在子程序Backtrack-Clique(k,x[1..k-1])中完成。子程序Backtrack-Clique(k,x[1..k-1])是回溯算法的主要部分，它以遞歸形式搜索以一個k-1層活點為根的子樹中有沒有一個活點使得它代表的團比目前找到的最大團更大。如果有，則更新全局變量y[1..n]。當我們的主程序以k=1調(diào)用這個子程序時，即可得到結果。Clique(k,x[1..k-1]) //檢查vk是否與x[1..k-1]代表的團中所有頂點相鄰，矩陣A是默認輸入//input:k,x[1..k-1],A[1..n,1..n](如果k=1，則x[1..k-1]為空，用x[0]=0表示)fori?1tok-1ifx[i]=1andA[k,i]=0 //如果x[1..k-1]代表的團含vi而沒有邊(vk,vi) thenreturnfalseendifendforreturntrueEndBacktrack-Clique(k,x[1..k-1],size(x,k-1)) //矩陣A為默認輸入//input:k,x[1..k-1],size(x,k-1),A[1..n,1..n] (如果k=1，那么x[1..k-1]為空，size(x,k-1)=0)ifClique(k,x[1..k-1])=true //x[k]=1這個兒子代表的子集是一個團then x[k]?1size(x,k)?size(x,k-1)+1ifsize(x,k)>largest //如果比全局最大的團還大，更新 then y[1..k]?x[1..k] largest?size(x,k)endifif(k+1)￡n thenBacktrack-Clique(k+1,x[1..k],size(x,k)) //繼續(xù)遞歸搜索 //因為k<n，由前面解釋，size(x,k)+(n-k)>largestendifendifif(size(x,k-1)+n-k)>largestand(k+1)￡n //x[k]=0的兒子是活點的條件then x[k]?0size(x,k)?size(x,k-1)Backtrack-Clique(k+1,x[1..k],size(x,k))endifEnd主程序偽碼如下。Maximum-Clique(G(V,E))//input:A[1..n,1..n]largest?0y[1..n]?[0..0]size(x,0)?0x[0]0 Backtrack-Clique(1,x[0],size(x,0)) returnlargest,y[1..n]End給出非遞歸形式的回溯法的通用算法。解: 假設搜索空間是n維的一棵搜索樹T。我們用一個向量x[1..k]表示一個k層的活點x(kn)，它的前k維的取值是x[i]并滿足顯式約束x[i]Si(1ik)。因為是回溯法，當前的活點都存于堆棧S。如果點x在棧頂，那么，從棧底到棧頂?shù)捻旤c序列實際上是搜索樹T中，從樹根到點x的路徑。所以，我們可以從棧底到棧頂順序存放x[1]，x[2]，…，x[k]，來表示這些活點。這樣一來，從棧底開始的i個元素，x[1]，x[2]，…，x[i]，恰好等于第i層的活點x[1..i]的各維的取值(1ik)。我們用集合T(k)表示活點x[1..k]的兒子集合。當回溯法剛開始訪問點x[1..k]時，計算出T(k)。我們可以簡單地置T(k)=Sk+1，但根據(jù)x[1..k]的取值計算，往往可大大減小這個集合T(k)。這個集合是動態(tài)變化的，被訪問過的兒子會從集合中刪去。因為數(shù)組x[1..n]實際上起到了堆棧的作用，所以不需另外再設堆棧。下面是偽碼，其中，B(x[1..k])是判斷點x[1..k]是否是活點的判定函數(shù)，T(x[1..k])是計算點x[1..k]的兒子集合T(k)的函數(shù)，Answer(x[1..k])是判斷點x[1..k]是否是答案點的函數(shù)。因為搜索空間是n維，我們規(guī)定T(n)=。Backtrack(n) //解是n元組，S[i]=Si(1in)是默認輸入T(0)S[1] //根的兒子集合，S[1]=S1，level0 //根的層號whilelevel0 klevel ifT(k)= then levellevel-1 else extractuT(k) //檢查T(k)中下一個兒子u kk+1 //兒子u在第k+1層 x[k]u ifB(x[1..k])=true //如果該兒子是活點 then levelk T(k) //先前如有T(k)，則清空 T(k)T(x[1..k]) //由x[1..k]重新計算T(k) ifAnswer(x[1..k])=yes thenoutputx[1..k] //輸出答案點 endif endif //否則，死點，level未變 endifendwhileEnd請設計一個回溯算法來搜索一個圖G(V,E)的所有最大獨立集。假定圖G是用鄰接矩陣表示的。解： 與尋找最大團一樣，假設圖的頂點集合是V={v1,v2,…,vn}，鄰接矩陣是A[1..n,1..n]，其中，A[i,j]=1表示頂點vi和vj之間有邊。我們用一個k元組x[1..k]=(x[1],x[2],…,x[k])表示搜索樹中k層的一個點x，它代表前k個頂點的一個子集C，其中x[i]=1表示vi屬于集合C而x[i]=0表示vi不屬于集合C(1≤i≤k)。這個子集C也許是一個獨立集，也許不是。如果子集C是一個獨立集，點x就是個活點，否則是死點。一個k層的活點x有兩個k+1層的兒子，它們是在點x所代表的子集基礎上，對應x[k+1]的兩個取值，一個是x[k+1]=0，另一個是x[k+1]=1。因此，x[k]{0,1}是這個搜索空間的顯示約束。因為我們要找出所有的最大獨立集，所以只用一個n元組y[1..n]=(y[1],y[2],…,y[n])來表示當前找到的最大獨立集已不夠用。因為搜索樹中每一個活點x對應一個獨立集，我們用size(x,k)記錄k層一個活點x[1..k]對應的獨立集C的規(guī)模，size(x,k)=|C|，并用變量largest來記錄當前找到的最大獨立集的規(guī)模。當我們找到一個大于等于當前找到的最大獨立集時，便把它壓入一個堆棧S。當全部搜索完成時，所有最大獨立集就存放在棧頂部分。注意，S是獨立于回溯法本身所用的堆棧。我們需要設計一個判定函數(shù)，在搜索到k-1層的一個活點x=(x[1],x[2],…,x[k-1])時，判定函數(shù)需要判斷它的兩個兒子是否是值得發(fā)展的活點。它需要做下面幾件事：檢測點x的每個兒子(x[1],x[2],…,x[k-1],x[k])(x[k]=0或1)對應的子集是否是一個獨立集。如果不是，該兒子成死點。當一個兒子對應的子集是一個獨立集時，還要檢查這個獨立集能否有希望發(fā)展為與目前找到的最大的獨立集有同等規(guī)?；蚋蟮莫毩⒓?。辦法是把余下的(n-k)個點全部加到這個獨立集中，如果頂點個數(shù)比largest小，那么這個點也是個死點，否則是個活點。當一個兒子是個活點，并且它對應的獨立集大于等于當前找到的最大獨立集時，則更新變量largest并把這個點壓入堆棧S?；厮莘ǖ膫未a如下，其中，Disconnect(k,x[1..k-1])是用來實現(xiàn)上述判定函數(shù)功能的第(1)件事，即檢查活點x[1..k-1]的x[k]=1的兒子所對應的子集是否是一個獨立集，而其余兩件事是在子程序Backtrack-Independent-Set(k,x[1..k-1],size(x,k-1))中完成。該子程序以遞歸形式找出以一個k-1層活點x[1..k-1]為根的子樹中所有大于等于目前找到的最大獨立集的活點并將它們壓入堆棧S。當我們的主程序以k=1調(diào)用這個子程序時，即可從算法結束時堆棧S中得到所有最大獨立集。Disconnect(k,x[1..k]) //檢查vk與x[1..k-1]的獨立集的點不相鄰。矩陣A為默認輸入//input:k,x[1..k-1],A[1..n,1..n](如果k=1，則x[1..k-1]為空，用x[0]=nil表示)fori?1tok-1 ifx[i]=1andA[k,i]=1 //如果x[1..k-1]的頂點集合含vi而且有邊(vk,vi) thenreturnfalseendifendforreturntrueEndBacktrack-Independent-Set(k,x[1..k-1],size(x,k-1)) //矩陣A為默認輸入//input:k,x[1..k-1],size(x,k-1),A[1..n,1..n](如果k=1，則x[1..k-1]為空，size(x,k-1)=0)ifDisconnect(k,x[1..k])=true //x[k]=1這個兒子所含集合是一個獨立集 then x[k]?1 size(x,k)?size(x,k-1)+1 ifsize(x,k)≥largest //大于等于當前最大的獨立集，入棧 then forjk+1ton //使得每個解都含有n個值x[1..n] x[j]0 endfor Push(S,(x[1..n],size(x,k)) //獨立集及其規(guī)模入棧 largest?size(x,k) //也許相等 endif if(k+1)￡n //肯定是活點 thenBacktrack-Independent-Set(k+1,x[1..k],size(x,k)) //繼續(xù)遞歸搜索 endifendifif(size(x,k-1)+n-k)≥largestand(k+1)￡n //x[k]=0的兒子是活點的條件 then x[k]?0 size(x,k)?size(x,k-1) Backtrack-Independent-Set(k+1,x[1..k],size(x,k)) //繼續(xù)遞歸搜索endifEnd主程序偽碼如下。Maximum-Independent-Set(G(V,E))//input:A[1..n,1..n]largest?0size(x,0)0x[0]0Backtrack-Independent-Set(1,x[0],size(x,0)) output(Largestindependentsethas“l(fā)argest”vertices)whileS≠ //輸出所有最大獨立集 (x[1..n],size)?Pop(S) ifsize=largest thenoutputx[1..n] endifendwhileEnd請設計一個回溯算法來搜索一個有向圖G(V,E)的一條哈密爾頓回路。假定圖G是用鄰接表表示的。解： 假設圖的頂點集合是V={v1,v2,…,vn}。(vi,vj)E表示頂點vi和vj之間有邊。搜索樹中k層的一個點x是一個k元組x=(x[1],x[2],…,x[k])，其中x[i]V(1≤i≤n)，這也是搜索空間的顯示約束。這個k元組的頂點序列，x[1],x[2],…,x[k]，也許是一個有k個頂點的簡單路徑，也許不是。這個頂點序列成為一條簡單路徑的充要條件是頂點各異并且每相鄰兩點有邊。如果它是一條簡單路徑，它就是一個活點，否則是死點。給定搜索樹中k-1層的一個活點x[1..k-1]=(x[1],x[2],…,x[k-1])，判定函數(shù)需要檢測該點的每一個兒子是否是一個活點。它有n個k層兒子，即x[k]=vi(1≤i≤n)。當x[k]=vi時，x[1..k]=(x[1],x[2],…,x[k-1],vi)是活點的充要條件是vi{x[1],x[2],…,x[k-1]}并且vi與x[k-1]相鄰，即(x[k-1],vi)E。當一個兒子是活點時，搜索便以這個兒子為擴展點遞歸搜索，否則檢查下一個兒子。當每個活點兒子都已搜索完畢，這個點本身成為死點而回溯到它父親的結點。當擴展點對應的路徑長為n時，檢查是否對應一條哈密爾頓回路。如果是，則輸出后算法結束。下面?zhèn)未a中，Simple-Path是個判定函數(shù)，它檢查擴展點的一個兒子是否對應一條簡單路徑。Simple-Path(x[1..k-1],v[i]) //檢查vix[1..k-1]，并且與x[k-1]相鄰。鄰接表為默認輸入。//input:x[1..k-1],v[1..n],E(如果k=1，則x[1..k-1]為空，用x[0]=0表示。)forj?1tok-1 ifx[j]=v[i] //v[i]=vi thenreturnfalse endifendforif(x[k-1],v[i])E thenreturntrue elsereturnfalseendifEndBacktrack-Hamiliton-Cycle(k,x[1..k-1]) //鄰接表為默認輸入//input:k,x[1..k-1],v[1..n],E(如果k=1，則x[1..k-1]為空，用x[0]=0表示)fori?1ton ifSimple-Path(x[1..k-1],v[i])=true then x[k]v[i] ifk=nand(x[k],x[1])E then foundtrue returnx[1..n] //算法結束 endif if(k+1)￡n //這時必有found=false thenBacktrack-Hamiliton-Cycle(k+1,x[1..k]) //繼續(xù)遞歸搜索 endif endifendforEnd主程序偽碼如下。Hamilton((G(V,E)) //鄰接表為輸入//input:GraphG (圖的鄰接表)foundfalsex[0]0Backtrack-Hamiliton-Cycle(1,x[0]) End用后進先出的D搜索法找出n皇后問題的一個解。解： 搜索樹與回溯法中的一樣，但搜索順序不同。假設x[1..k-1]是一個(k-1)層中一個擴展點x，要想點x的一個兒子y成為活點，y的第k個皇后必須不與前面k-1個皇后相攻擊。假設兩皇后的(行,列)位置分別是(i,j)和(k,l)，它們會相互攻擊當且僅當(j=l或|i-k|=|j-l|)。所以，判定函數(shù)與回溯法中的相同，可以由下面的子程序?qū)崿F(xiàn)。B(k,l,x[1..k-1])//input:k,l,x[1..k-1](如果k=1,則x[1..k-1]為空,用x[0]=0表示)fori1tok-1jx[i]if(j=l)or(|i-k|=|j-l|) thenreturnfalseendifendforreturntrueEnd這個問題的Answer函數(shù)很簡單，只要k=n且第k個皇后的位置(k,l)滿足判定函數(shù)，這個點就是答案點。我們用一個記錄v來代表搜索樹中一個點。點v有(n+1)個域(fields)，其中v.level表示該點在搜索樹中的層號，而v.x[1..n]則表示第1行到第n行中皇后的位置。下面是用后進先出的分枝限界法解n皇后問題的偽碼。LIFO-Branch-and-Bound-N-Queen(n)foundfalse //答案點尚未找到root.level0 //root表示搜索樹的根，層號為0x[0]0root.x[1..n][0..0] //表示還沒有皇后S //堆棧清空Push(S,root) //根結點入棧whileSandfound=false //搜索開始并一直到堆棧為空或者答案找到 vPop(S) //彈出棧頂?shù)臄U展點 kv.level+1 //它兒子的層號為k x[1..k-1]v.x[1..k-1] //兒子的頭k-1個皇后與父親的相同(如k=1，則不操作) forl1ton //開始檢查每個兒子 ifB(k,l,x[1..k-1])=true then u.levelk //建一個第k層活點u u.x[1..k-1]x[1..k-1] //如k=1，則不操作 u.x[k]l Push(S,u) //一個活兒子進棧 ifk=n //答案點找到 then x[1..n]u.x[1..n] foundtrue returnx[1..n] //算法結束 endif endif endforendwhilereturn(nosolution)End用最大價值先出的分枝限界法找一個圖G(V,E)的最大團。假定圖G是用鄰接矩陣表示的。解： 假設圖的頂點集合是V={v1,v2,…,vn}，鄰接矩陣是A[1..n,1..n]，其中A[i,j]=1表示頂點vi和vj之間有邊。我們用一個k元組x[1..k]=(x[1],x[2],…,x[k])表示搜索樹中k層的一個點，對應于前k個頂點的一個子集C，其中x[i]=1表示vi屬于集合C而x[i]=0表示vi不屬于這個集合(1≤i≤k≤n)。這個子集C也許是一個團，也許不是。如果k層的一個點x[1..k]所對應的子集C不構成一個團，那么這個點是個死點，否則是個活點。顯然，死點以下的搜索樹可被刪除。一個k-1層的活點x[1..k-1]有兩個k層的兒子，它們是在點x[1..k-1]所代表的子集基礎上，對應x[k]的兩個取值，一個是x[k]=0，另一個是x[k]=1。因此，x[i]{0,1}是這個搜索空間的顯示約束(1≤i≤n)。我們用一個最大堆H來保存當前的所有活點。因為我們要找一個最大團，所以用一個n元組y[1..n]=(y[1],y[2],…,y[n])記錄當前找到的最大團C，而它含有的頂點個數(shù)用變量largest來記錄。其中y[i]=1表示vi屬于C，而y[i]=0表示vi不屬于這個團(1≤i≤n)。這是一個全局變量，一旦發(fā)現(xiàn)更大的團，則更新這個全局變量。我們需要設計一個判定函數(shù)，它為擴展點x[1..k-1]=(x[1],x[2],…,x[k-1])判斷它的兩個兒子是否是值得發(fā)展的活點。它需要做下面幾件事：檢測點x[1..k-1]的x[k]=1的兒子代表的子集是否是一個團。如果不是，該兒子成死點。它的x[k]=0的兒子不需檢查，因為這個兒子和它父親x[1..k-1]有相同的團。當一個k層兒子y代表的子集是一個團C時，還要檢查這個團能否有希望發(fā)展為比目前找到的最大的團還大的團。辦法是把余下的(n-k)個還未作取舍的頂點全部加到這個團中，這個集合的頂點個數(shù)稱為該點y的潛在價值，也就是這個團C能發(fā)展的上界。如果這個上界比largest還要小或相等，那么這個點也是個死點，否則是個活點。如果是個活點，將它插入最大堆H。活點的關鍵字就是它的潛在價值。當一個k層兒子y是個活點，并且它對應的團比當前找到的最大團大，則更新變量largest和n元組y[1..n]。我們用一個記錄來存放與活點v有關的參數(shù)，它含有以下幾個域:v.level =活點v所在的層號,根算第0層v.upper =活點v的潛在價值v.lower =活點v的價值下界，即v對應的團所含頂點個數(shù)v.x[1..n] =活點v對頂點1，2，…，n的取舍決定。當展開點，即最大堆的根，是搜索樹中k-1層的一個活點v時，如上所述，判定函數(shù)檢測該點的兩個k層兒子。如果是活點，則把該兒子插入堆中。處理完兩個兒子后，刪除這個展開點，并修復這個堆。在下面?zhèn)未a中，Clique(k,x[1..k-1])是用來檢查活點x[1..k-1]的x[k]=1的兒子所對應的集合是否是一個團。它完成判定函數(shù)要做的3件事中的第1件。其它兩件事在主程序中完成。Clique(k,x[1..k-1]) //查vk與x[1..k-1]的團的頂點都有邊。A[1..n,1..n]是默認輸入//input:k,x[1..k-1],A[1..n,1..n](如果k=1,則x[1..k-1]為空，用x[0]=0表示)fori?1tok-1 ifx[i]=1andA[k,i]=0 //如果沒有邊(vk,vi) thenreturnfalse endifendforreturntrueEnd在下面?zhèn)未a中，最大堆用一個數(shù)組H[1..heapsize]實現(xiàn)，初始時，heapsize=1。Max-Clique(A[1..n,1..n],y[1..n],largest) //屬出最大團y[1..n]，它的頂點個數(shù)是largestt.level0 //根的層號=0t.uppern //根的潛在價值t.lower0 //根代表的團的頂點個數(shù)t.x[1..n][0..0] //根代表的團是空集H[1]t //把根記錄插入堆里heapsize1largest0 //下界初值為0y[1..n][0..0] //答案點初始為空whileheapsize>0 vHeap-Extract-Max(H[1..heapsize],max) //摘取H[1] kv.level //層號 ifk=n thenreturny[1..n],largest //y是答案點，v也是。可能v=y endif kk+1 ifk=1 thenx[0]0 //表示根結點 endif x[1..k-1]v.x[1..k-1] //x[0..k-1]是臨時工作變量 ifClique(k,x[1..k-1])=true //v[k]=1的兒子是活點，建點left then left.upperv.upper //左兒子上界與父親同，必定>largest left.levelk left.x[1..k-1]x[1..k-1] left.lowerv.lower+1 left.x[k]1 ifleft.lower>largest //更新最大團 then largestleft.lower y[1..k]left.x[1..k] forjk+1ton y[j]0 //用0填充 endfor endif Max-Heap-Insert(H[1..heapsize],left) endif right.upperv.upper-1 //考慮右兒子v[k]=0，潛在價值比父親小1 right.lowerv.lower //右兒子下界與父親的同 right.levelk //比父親大1 right.x[1..k-1]x[1..k-1] //與父親同 right.x[k]0 ifright.upper>largest //否則是死點刪除 thenMax-Heap-Insert(H[1..heapsize],right) //right是活點入堆 endifendwhilereturny[1..n],largestEnd用最大價值先出的分枝限界法找出有向圖G(V,E)中以點sV為起點的最長的一條簡單路徑。假定圖G是用鄰接矩陣表示的，路徑的長度為邊的個數(shù)。解： 假設圖的頂點集合是V={v[1],v[2],…,v[n]}，鄰接矩陣是A[1..n,1..n]，其中A[i,j]=1表示頂點v[i]和v[j]之間有邊。搜索樹的根含頂點s。搜索樹中k層的一個點x，對應一個k+1元組x[1..k+1]=(x[1],x[2],…,x[k+1])，其中，x[1]=s，x[i]V(2≤i≤k+1)是顯式約束。如果頂點序列，x[1],x[2],…,x[k+1]，是一條從s開始的長為k的簡單路徑，那么點x就是一個活點，否則是死點。以死點為根的子樹可刪除。根算第0層，它對應的頂點序列，x[1]，只含一個點s。搜索樹中每一個活點v以一個記錄形式保存在一個最大堆中，它有以下的域：v.level =活點v的層號，也是v對應的路徑的長度。v.x[1..level+1] =活點v所對應的路徑上的頂點序列，其中v.x[1]=s。另外，算法設置全局變量y[1..longest+1]和longest來記錄目前找到的最長路徑的頂點序列以及它的長度。我們把搜索樹中一個活點v對應的路徑的長度，v.level，作為v的關鍵字，放在一個最大堆H中。如果當前展開點，也就是堆H的根，是搜索樹中k層的一個活點v，v.level=k，v.x[1..k+1]=(x[1],x[2],…,x[k+1])，那么分枝限界法做下面幾件事：把點v從堆中摘除并修復堆。如果k=n-1，那么這個展開點是個答案點，路徑長是n-1，算法中止。否則，等堆里沒有點為止，即所有可能的情況都已搜索完，這時y[1..longest+1]和longest就是解。用判定函數(shù)檢測點v在搜索樹中的每一個兒子是否是活點。它有n個k+1層兒子，即x[k+2]=v[j](1≤j≤n)。當x[k+2]=v[j]時，這個兒子是活點的充要條件是v[j]{x[1],x[2],…,x[k+1]}并且(x[k+1]，v[j])E。當一個兒子x[1..k+2]=(x[1],x[2],…,x[k+1],v[j])是活點時，它對應的簡單路徑顯然比父親的路徑長一條邊。因此，將這個兒子插入堆中，并更新變量longest和y[1..longest+1]。在下面?zhèn)未a中，Simple-Path是判定函數(shù)，用以檢查擴展點的兒子x[k+2]=v[j]是否對應一條簡單路徑。Simple-Path(x[1..k+1]，v[j]) //檢查：v[j]不出現(xiàn)在序列x[1..k+1]中并與x[k+1]相鄰//input:x[1..k+1],v[j]V(1jn)fori1tok+1 ifx[i]=v[j] thenreturnfalse endifendforletx[k+1]=v[i]ifA(i,j)=0 thenreturnfalse elsereturntrueendifEnd在下面?zhèn)未a中，最大堆用一個數(shù)組H[1..heapsize]實現(xiàn)，初始時，heapsize=1，而H[1]中存的是搜索樹的根的信息。Longest-Path(A[1..n,1..