計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第16章

PAGE16第16章 窮舉搜索用回溯法設(shè)計(jì)一個(gè)給圖G(V,E)著色的算法。我們假定圖是用鄰接矩陣表示，而可用顏色的集合是C={1,2,…,m}，m可視為常數(shù)。我們要求把所有合法的著色全部輸出。解： 假設(shè)圖的頂點(diǎn)集合是V={v1,v2,…,vn}，鄰接矩陣是A[1..n,1..n]，其中A[i,j]=1表示頂點(diǎn)vi和vj之間有邊(1≤i,j≤n)。我們用一個(gè)n元組(x[1],x[2],…,x[n])表示對(duì)這n個(gè)頂點(diǎn)的著色，其中x[i]C是對(duì)頂點(diǎn)vi的著色(1≤i≤n)，這是著色問(wèn)題的一個(gè)顯示約束。圖G的一個(gè)合法的著色還必須滿足隱式約束，即如果A[i,j]=1,那么必須有x[i]x[j]。搜索樹(shù)中第k層的一個(gè)點(diǎn)x用一個(gè)k元組x[1..k]=(x[1],x[2],…,x[k])表示，它表示前k個(gè)頂點(diǎn)已著色為x[1],x[2],…,x[k]，它的兒子有m個(gè)，每個(gè)對(duì)應(yīng)一個(gè)(k+1)元組，x[1..k+1]=(x[1],x[2],…,x[k],x[k+1])，其中x[k+1]分別是1,2,…,和m。我們先設(shè)計(jì)一個(gè)判定函數(shù)Valid(k,c,x[1..k-1])，用來(lái)檢查樹(shù)中(k-1)層的一個(gè)活點(diǎn)(x[1],x[2],…,x[k-1])的一個(gè)兒子y=(x[1],x[2],…,x[1..k-1],x[k])，如果x[k]=c，也就是把頂點(diǎn)vk著色為c，是否是活點(diǎn)。這里，一個(gè)k層的活點(diǎn)要滿足顯示約束x[i]C，還要滿足前k個(gè)頂點(diǎn)的隱式約束。下面是Valid(k,c,x[1..k-1])算法的偽碼。Valid(k,c,x[1..k-1]) //圖G(V,E)的鄰接矩陣A為默認(rèn)輸入//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為默認(rèn)輸入//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個(gè)點(diǎn)著色為c，這個(gè)兒子是活點(diǎn) ifk=n //這個(gè)點(diǎn)是答案點(diǎn) then countcount+1 //全局變量，統(tǒng)計(jì)答案點(diǎn)個(gè)數(shù) outputx[1..n] //輸出這個(gè)合法著色 else m-color(k+1,x[1..k]) //否則從這點(diǎn)遞歸下去 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)的一個(gè)最大團(tuán)是一個(gè)NPC問(wèn)題。請(qǐng)?jiān)O(shè)計(jì)一個(gè)回溯算法來(lái)搜索圖G的一個(gè)最大團(tuán)。假定圖G是用鄰接矩陣表示的。解： 假設(shè)圖G的頂點(diǎn)集合是V={v1,v2,…,vn}，鄰接矩陣是A[1..n,1..n]，其中A[i,j]=1表示頂點(diǎn)vi和vj之間有邊。我們用一個(gè)k元組x=(x[1],x[2],…,x[k])表示搜索樹(shù)中k層的一個(gè)點(diǎn)，它代表前面k個(gè)頂點(diǎn)的一個(gè)子集C(k≤n)，其中x[i]=1表示vi屬于集合C，而x[i]=0表示vi不屬于集合C(1≤i≤k)。子集C也許是一個(gè)團(tuán)，也許不是。因此，x[i]{0,1}是這個(gè)搜索空間的顯示約束(1≤i≤n)。一個(gè)k層的點(diǎn)x有兩個(gè)k+1層的兒子，它們是在點(diǎn)x所代表的子集C的基礎(chǔ)上，對(duì)應(yīng)x[k+1]的兩個(gè)取值，一個(gè)是x[k+1]=0，另一個(gè)是x[k+1]=1。如果k層的一個(gè)點(diǎn)x所代表的子集不構(gòu)成一個(gè)團(tuán)，那么這個(gè)點(diǎn)是個(gè)死點(diǎn)。顯然，死點(diǎn)以下的搜索樹(shù)可被刪除。因?yàn)槲覀冎恍枰乙粋€(gè)最大團(tuán)，所以用一個(gè)專門(mén)的n元組y[1..n]=(y[1],y[2],…,y[n])記錄當(dāng)前找到的最大團(tuán)，而它含有的頂點(diǎn)個(gè)數(shù)用變量largest來(lái)記錄。這是一個(gè)全局變量，一旦發(fā)現(xiàn)更大的團(tuán)，則更新這個(gè)全局變量。給定搜索樹(shù)中k-1層的一個(gè)活點(diǎn)x=(x[1],x[2],…,x[k-1])，我們用size(x,k-1)表示它對(duì)應(yīng)的團(tuán)C的頂點(diǎn)個(gè)數(shù)|C|，顯然有size(x,k-1)k-1。我們需要設(shè)計(jì)一個(gè)判定函數(shù)，當(dāng)擴(kuò)展點(diǎn)是活點(diǎn)x時(shí)，判斷它的兩個(gè)兒子是否是值得發(fā)展的活點(diǎn)。它需要做下面幾件事：檢測(cè)點(diǎn)x的每個(gè)兒子(x[1],x[2],…,x[k-1],x[k])(x[k]=0或1)代表的子集是否是一個(gè)團(tuán)。如果不是，該兒子成死點(diǎn)。當(dāng)一個(gè)兒子代表的子集C是一個(gè)團(tuán)時(shí)，還要檢查這個(gè)團(tuán)能否有希望發(fā)展為比目前找到的最大的團(tuán)還要大的團(tuán)。辦法是把余下的(n-k)個(gè)頂點(diǎn)全部加到這個(gè)團(tuán)中，如果加上后的頂點(diǎn)個(gè)數(shù)，即size(x,k)+(n-k)，比largest要小或相等，那么這個(gè)點(diǎn)也是個(gè)死點(diǎn)，否則是個(gè)活點(diǎn)。當(dāng)一個(gè)兒子被判定是個(gè)活點(diǎn)時(shí)，如果它對(duì)應(yīng)的團(tuán)比當(dāng)前找到的最大團(tuán)大，則更新變量largest和n元組y[1..n]。這里，我們要指出的是，如果x[k]=1的兒子是一個(gè)團(tuán)時(shí)，必有size(x,k)=size(x,k-1)+1。而且，不論是否會(huì)更新largest，都有size(x,k)+(n-k)>largest，除非n=k。這是因?yàn)椋绻桓?，我們有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，這個(gè)兒子是底層一個(gè)點(diǎn)，更新largest后，它成為死點(diǎn)。當(dāng)然，它對(duì)應(yīng)的團(tuán)的規(guī)模對(duì)應(yīng)于更新后的largest被記下。所以，如果x[k]=1的兒子是一個(gè)團(tuán)，并且k<n，它必定是個(gè)活點(diǎn)?；厮莘ǖ膫未a如下，其中，子程序Clique(k,x[1..k-1])實(shí)現(xiàn)上述判定函數(shù)功能的第(1)部分，即用來(lái)檢查活點(diǎn)x[1..k-1]的一個(gè)x[k]=1的兒子是否對(duì)應(yīng)一個(gè)團(tuán)。判定函數(shù)的另兩部分的功能在子程序Backtrack-Clique(k,x[1..k-1])中完成。子程序Backtrack-Clique(k,x[1..k-1])是回溯算法的主要部分，它以遞歸形式搜索以一個(gè)k-1層活點(diǎn)為根的子樹(shù)中有沒(méi)有一個(gè)活點(diǎn)使得它代表的團(tuán)比目前找到的最大團(tuán)更大。如果有，則更新全局變量y[1..n]。當(dāng)我們的主程序以k=1調(diào)用這個(gè)子程序時(shí)，即可得到結(jié)果。Clique(k,x[1..k-1]) //檢查vk是否與x[1..k-1]代表的團(tuán)中所有頂點(diǎn)相鄰，矩陣A是默認(rèn)輸入//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]代表的團(tuán)含vi而沒(méi)有邊(vk,vi) thenreturnfalseendifendforreturntrueEndBacktrack-Clique(k,x[1..k-1],size(x,k-1)) //矩陣A為默認(rèn)輸入//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這個(gè)兒子代表的子集是一個(gè)團(tuán)then x[k]?1size(x,k)?size(x,k-1)+1ifsize(x,k)>largest //如果比全局最大的團(tuán)還大，更新 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ù)遞歸搜索 //因?yàn)閗<n，由前面解釋，size(x,k)+(n-k)>largestendifendifif(size(x,k-1)+n-k)>largestand(k+1)￡n //x[k]=0的兒子是活點(diǎn)的條件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給出非遞歸形式的回溯法的通用算法。解: 假設(shè)搜索空間是n維的一棵搜索樹(shù)T。我們用一個(gè)向量x[1..k]表示一個(gè)k層的活點(diǎn)x(kn)，它的前k維的取值是x[i]并滿足顯式約束x[i]Si(1ik)。因?yàn)槭腔厮莘?，?dāng)前的活點(diǎn)都存于堆棧S。如果點(diǎn)x在棧頂，那么，從棧底到棧頂?shù)捻旤c(diǎn)序列實(shí)際上是搜索樹(shù)T中，從樹(shù)根到點(diǎn)x的路徑。所以，我們可以從棧底到棧頂順序存放x[1]，x[2]，…，x[k]，來(lái)表示這些活點(diǎn)。這樣一來(lái)，從棧底開(kāi)始的i個(gè)元素，x[1]，x[2]，…，x[i]，恰好等于第i層的活點(diǎn)x[1..i]的各維的取值(1ik)。我們用集合T(k)表示活點(diǎn)x[1..k]的兒子集合。當(dāng)回溯法剛開(kāi)始訪問(wèn)點(diǎn)x[1..k]時(shí)，計(jì)算出T(k)。我們可以簡(jiǎn)單地置T(k)=Sk+1，但根據(jù)x[1..k]的取值計(jì)算，往往可大大減小這個(gè)集合T(k)。這個(gè)集合是動(dòng)態(tài)變化的，被訪問(wèn)過(guò)的兒子會(huì)從集合中刪去。因?yàn)閿?shù)組x[1..n]實(shí)際上起到了堆棧的作用，所以不需另外再設(shè)堆棧。下面是偽碼，其中，B(x[1..k])是判斷點(diǎn)x[1..k]是否是活點(diǎn)的判定函數(shù)，T(x[1..k])是計(jì)算點(diǎn)x[1..k]的兒子集合T(k)的函數(shù)，Answer(x[1..k])是判斷點(diǎn)x[1..k]是否是答案點(diǎn)的函數(shù)。因?yàn)樗阉骺臻g是n維，我們規(guī)定T(n)=。Backtrack(n) //解是n元組，S[i]=Si(1in)是默認(rèn)輸入T(0)S[1] //根的兒子集合，S[1]=S1，level0 //根的層號(hào)whilelevel0 klevel ifT(k)= then levellevel-1 else extractuT(k) //檢查T(mén)(k)中下一個(gè)兒子u kk+1 //兒子u在第k+1層 x[k]u ifB(x[1..k])=true //如果該兒子是活點(diǎn) then levelk T(k) //先前如有T(k)，則清空 T(k)T(x[1..k]) //由x[1..k]重新計(jì)算T(k) ifAnswer(x[1..k])=yes thenoutputx[1..k] //輸出答案點(diǎn) endif endif //否則，死點(diǎn)，level未變 endifendwhileEnd請(qǐng)?jiān)O(shè)計(jì)一個(gè)回溯算法來(lái)搜索一個(gè)圖G(V,E)的所有最大獨(dú)立集。假定圖G是用鄰接矩陣表示的。解： 與尋找最大團(tuán)一樣，假設(shè)圖的頂點(diǎn)集合是V={v1,v2,…,vn}，鄰接矩陣是A[1..n,1..n]，其中，A[i,j]=1表示頂點(diǎn)vi和vj之間有邊。我們用一個(gè)k元組x[1..k]=(x[1],x[2],…,x[k])表示搜索樹(shù)中k層的一個(gè)點(diǎn)x，它代表前k個(gè)頂點(diǎn)的一個(gè)子集C，其中x[i]=1表示vi屬于集合C而x[i]=0表示vi不屬于集合C(1≤i≤k)。這個(gè)子集C也許是一個(gè)獨(dú)立集，也許不是。如果子集C是一個(gè)獨(dú)立集，點(diǎn)x就是個(gè)活點(diǎn)，否則是死點(diǎn)。一個(gè)k層的活點(diǎn)x有兩個(gè)k+1層的兒子，它們是在點(diǎn)x所代表的子集基礎(chǔ)上，對(duì)應(yīng)x[k+1]的兩個(gè)取值，一個(gè)是x[k+1]=0，另一個(gè)是x[k+1]=1。因此，x[k]{0,1}是這個(gè)搜索空間的顯示約束。因?yàn)槲覀円页鏊械淖畲螵?dú)立集，所以只用一個(gè)n元組y[1..n]=(y[1],y[2],…,y[n])來(lái)表示當(dāng)前找到的最大獨(dú)立集已不夠用。因?yàn)樗阉鳂?shù)中每一個(gè)活點(diǎn)x對(duì)應(yīng)一個(gè)獨(dú)立集，我們用size(x,k)記錄k層一個(gè)活點(diǎn)x[1..k]對(duì)應(yīng)的獨(dú)立集C的規(guī)模，size(x,k)=|C|，并用變量largest來(lái)記錄當(dāng)前找到的最大獨(dú)立集的規(guī)模。當(dāng)我們找到一個(gè)大于等于當(dāng)前找到的最大獨(dú)立集時(shí)，便把它壓入一個(gè)堆棧S。當(dāng)全部搜索完成時(shí)，所有最大獨(dú)立集就存放在棧頂部分。注意，S是獨(dú)立于回溯法本身所用的堆棧。我們需要設(shè)計(jì)一個(gè)判定函數(shù)，在搜索到k-1層的一個(gè)活點(diǎn)x=(x[1],x[2],…,x[k-1])時(shí)，判定函數(shù)需要判斷它的兩個(gè)兒子是否是值得發(fā)展的活點(diǎn)。它需要做下面幾件事：檢測(cè)點(diǎn)x的每個(gè)兒子(x[1],x[2],…,x[k-1],x[k])(x[k]=0或1)對(duì)應(yīng)的子集是否是一個(gè)獨(dú)立集。如果不是，該兒子成死點(diǎn)。當(dāng)一個(gè)兒子對(duì)應(yīng)的子集是一個(gè)獨(dú)立集時(shí)，還要檢查這個(gè)獨(dú)立集能否有希望發(fā)展為與目前找到的最大的獨(dú)立集有同等規(guī)?；蚋蟮莫?dú)立集。辦法是把余下的(n-k)個(gè)點(diǎn)全部加到這個(gè)獨(dú)立集中，如果頂點(diǎn)個(gè)數(shù)比largest小，那么這個(gè)點(diǎn)也是個(gè)死點(diǎn)，否則是個(gè)活點(diǎn)。當(dāng)一個(gè)兒子是個(gè)活點(diǎn)，并且它對(duì)應(yīng)的獨(dú)立集大于等于當(dāng)前找到的最大獨(dú)立集時(shí)，則更新變量largest并把這個(gè)點(diǎn)壓入堆棧S?；厮莘ǖ膫未a如下，其中，Disconnect(k,x[1..k-1])是用來(lái)實(shí)現(xiàn)上述判定函數(shù)功能的第(1)件事，即檢查活點(diǎn)x[1..k-1]的x[k]=1的兒子所對(duì)應(yīng)的子集是否是一個(gè)獨(dú)立集，而其余兩件事是在子程序Backtrack-Independent-Set(k,x[1..k-1],size(x,k-1))中完成。該子程序以遞歸形式找出以一個(gè)k-1層活點(diǎn)x[1..k-1]為根的子樹(shù)中所有大于等于目前找到的最大獨(dú)立集的活點(diǎn)并將它們壓入堆棧S。當(dāng)我們的主程序以k=1調(diào)用這個(gè)子程序時(shí)，即可從算法結(jié)束時(shí)堆棧S中得到所有最大獨(dú)立集。Disconnect(k,x[1..k]) //檢查vk與x[1..k-1]的獨(dú)立集的點(diǎn)不相鄰。矩陣A為默認(rèn)輸入//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]的頂點(diǎn)集合含vi而且有邊(vk,vi) thenreturnfalseendifendforreturntrueEndBacktrack-Independent-Set(k,x[1..k-1],size(x,k-1)) //矩陣A為默認(rèn)輸入//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這個(gè)兒子所含集合是一個(gè)獨(dú)立集 then x[k]?1 size(x,k)?size(x,k-1)+1 ifsize(x,k)≥largest //大于等于當(dāng)前最大的獨(dú)立集，入棧 then forjk+1ton //使得每個(gè)解都含有n個(gè)值x[1..n] x[j]0 endfor Push(S,(x[1..n],size(x,k)) //獨(dú)立集及其規(guī)模入棧 largest?size(x,k) //也許相等 endif if(k+1)￡n //肯定是活點(diǎ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的兒子是活點(diǎn)的條件 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≠ //輸出所有最大獨(dú)立集 (x[1..n],size)?Pop(S) ifsize=largest thenoutputx[1..n] endifendwhileEnd請(qǐng)?jiān)O(shè)計(jì)一個(gè)回溯算法來(lái)搜索一個(gè)有向圖G(V,E)的一條哈密爾頓回路。假定圖G是用鄰接表表示的。解： 假設(shè)圖的頂點(diǎn)集合是V={v1,v2,…,vn}。(vi,vj)E表示頂點(diǎn)vi和vj之間有邊。搜索樹(shù)中k層的一個(gè)點(diǎn)x是一個(gè)k元組x=(x[1],x[2],…,x[k])，其中x[i]V(1≤i≤n)，這也是搜索空間的顯示約束。這個(gè)k元組的頂點(diǎn)序列，x[1],x[2],…,x[k]，也許是一個(gè)有k個(gè)頂點(diǎn)的簡(jiǎn)單路徑，也許不是。這個(gè)頂點(diǎn)序列成為一條簡(jiǎn)單路徑的充要條件是頂點(diǎn)各異并且每相鄰兩點(diǎn)有邊。如果它是一條簡(jiǎn)單路徑，它就是一個(gè)活點(diǎn)，否則是死點(diǎn)。給定搜索樹(shù)中k-1層的一個(gè)活點(diǎn)x[1..k-1]=(x[1],x[2],…,x[k-1])，判定函數(shù)需要檢測(cè)該點(diǎn)的每一個(gè)兒子是否是一個(gè)活點(diǎn)。它有n個(gè)k層兒子，即x[k]=vi(1≤i≤n)。當(dāng)x[k]=vi時(shí)，x[1..k]=(x[1],x[2],…,x[k-1],vi)是活點(diǎn)的充要條件是vi{x[1],x[2],…,x[k-1]}并且vi與x[k-1]相鄰，即(x[k-1],vi)E。當(dāng)一個(gè)兒子是活點(diǎn)時(shí)，搜索便以這個(gè)兒子為擴(kuò)展點(diǎn)遞歸搜索，否則檢查下一個(gè)兒子。當(dāng)每個(gè)活點(diǎn)兒子都已搜索完畢，這個(gè)點(diǎn)本身成為死點(diǎn)而回溯到它父親的結(jié)點(diǎn)。當(dāng)擴(kuò)展點(diǎn)對(duì)應(yīng)的路徑長(zhǎng)為n時(shí)，檢查是否對(duì)應(yīng)一條哈密爾頓回路。如果是，則輸出后算法結(jié)束。下面?zhèn)未a中，Simple-Path是個(gè)判定函數(shù)，它檢查擴(kuò)展點(diǎn)的一個(gè)兒子是否對(duì)應(yīng)一條簡(jiǎn)單路徑。Simple-Path(x[1..k-1],v[i]) //檢查vix[1..k-1]，并且與x[k-1]相鄰。鄰接表為默認(rèn)輸入。//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]) //鄰接表為默認(rèn)輸入//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] //算法結(jié)束 endif if(k+1)￡n //這時(shí)必有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用后進(jìn)先出的D搜索法找出n皇后問(wèn)題的一個(gè)解。解： 搜索樹(shù)與回溯法中的一樣，但搜索順序不同。假設(shè)x[1..k-1]是一個(gè)(k-1)層中一個(gè)擴(kuò)展點(diǎn)x，要想點(diǎn)x的一個(gè)兒子y成為活點(diǎn)，y的第k個(gè)皇后必須不與前面k-1個(gè)皇后相攻擊。假設(shè)兩皇后的(行,列)位置分別是(i,j)和(k,l)，它們會(huì)相互攻擊當(dāng)且僅當(dāng)(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這個(gè)問(wèn)題的Answer函數(shù)很簡(jiǎn)單，只要k=n且第k個(gè)皇后的位置(k,l)滿足判定函數(shù)，這個(gè)點(diǎn)就是答案點(diǎn)。我們用一個(gè)記錄v來(lái)代表搜索樹(shù)中一個(gè)點(diǎn)。點(diǎn)v有(n+1)個(gè)域(fields)，其中v.level表示該點(diǎn)在搜索樹(shù)中的層號(hào)，而v.x[1..n]則表示第1行到第n行中皇后的位置。下面是用后進(jìn)先出的分枝限界法解n皇后問(wèn)題的偽碼。LIFO-Branch-and-Bound-N-Queen(n)foundfalse //答案點(diǎn)尚未找到root.level0 //root表示搜索樹(shù)的根，層號(hào)為0x[0]0root.x[1..n][0..0] //表示還沒(méi)有皇后S //堆棧清空Push(S,root) //根結(jié)點(diǎn)入棧whileSandfound=false //搜索開(kāi)始并一直到堆棧為空或者答案找到 vPop(S) //彈出棧頂?shù)臄U(kuò)展點(diǎn) kv.level+1 //它兒子的層號(hào)為k x[1..k-1]v.x[1..k-1] //兒子的頭k-1個(gè)皇后與父親的相同(如k=1，則不操作) forl1ton //開(kāi)始檢查每個(gè)兒子 ifB(k,l,x[1..k-1])=true then u.levelk //建一個(gè)第k層活點(diǎn)u u.x[1..k-1]x[1..k-1] //如k=1，則不操作 u.x[k]l Push(S,u) //一個(gè)活兒子進(jìn)棧 ifk=n //答案點(diǎn)找到 then x[1..n]u.x[1..n] foundtrue returnx[1..n] //算法結(jié)束 endif endif endforendwhilereturn(nosolution)End用最大價(jià)值先出的分枝限界法找一個(gè)圖G(V,E)的最大團(tuán)。假定圖G是用鄰接矩陣表示的。解： 假設(shè)圖的頂點(diǎn)集合是V={v1,v2,…,vn}，鄰接矩陣是A[1..n,1..n]，其中A[i,j]=1表示頂點(diǎn)vi和vj之間有邊。我們用一個(gè)k元組x[1..k]=(x[1],x[2],…,x[k])表示搜索樹(shù)中k層的一個(gè)點(diǎn)，對(duì)應(yīng)于前k個(gè)頂點(diǎn)的一個(gè)子集C，其中x[i]=1表示vi屬于集合C而x[i]=0表示vi不屬于這個(gè)集合(1≤i≤k≤n)。這個(gè)子集C也許是一個(gè)團(tuán)，也許不是。如果k層的一個(gè)點(diǎn)x[1..k]所對(duì)應(yīng)的子集C不構(gòu)成一個(gè)團(tuán)，那么這個(gè)點(diǎn)是個(gè)死點(diǎn)，否則是個(gè)活點(diǎn)。顯然，死點(diǎn)以下的搜索樹(shù)可被刪除。一個(gè)k-1層的活點(diǎn)x[1..k-1]有兩個(gè)k層的兒子，它們是在點(diǎn)x[1..k-1]所代表的子集基礎(chǔ)上，對(duì)應(yīng)x[k]的兩個(gè)取值，一個(gè)是x[k]=0，另一個(gè)是x[k]=1。因此，x[i]{0,1}是這個(gè)搜索空間的顯示約束(1≤i≤n)。我們用一個(gè)最大堆H來(lái)保存當(dāng)前的所有活點(diǎn)。因?yàn)槲覀円乙粋€(gè)最大團(tuán)，所以用一個(gè)n元組y[1..n]=(y[1],y[2],…,y[n])記錄當(dāng)前找到的最大團(tuán)C，而它含有的頂點(diǎn)個(gè)數(shù)用變量largest來(lái)記錄。其中y[i]=1表示vi屬于C，而y[i]=0表示vi不屬于這個(gè)團(tuán)(1≤i≤n)。這是一個(gè)全局變量，一旦發(fā)現(xiàn)更大的團(tuán)，則更新這個(gè)全局變量。我們需要設(shè)計(jì)一個(gè)判定函數(shù)，它為擴(kuò)展點(diǎn)x[1..k-1]=(x[1],x[2],…,x[k-1])判斷它的兩個(gè)兒子是否是值得發(fā)展的活點(diǎn)。它需要做下面幾件事：檢測(cè)點(diǎn)x[1..k-1]的x[k]=1的兒子代表的子集是否是一個(gè)團(tuán)。如果不是，該兒子成死點(diǎn)。它的x[k]=0的兒子不需檢查，因?yàn)檫@個(gè)兒子和它父親x[1..k-1]有相同的團(tuán)。當(dāng)一個(gè)k層兒子y代表的子集是一個(gè)團(tuán)C時(shí)，還要檢查這個(gè)團(tuán)能否有希望發(fā)展為比目前找到的最大的團(tuán)還大的團(tuán)。辦法是把余下的(n-k)個(gè)還未作取舍的頂點(diǎn)全部加到這個(gè)團(tuán)中，這個(gè)集合的頂點(diǎn)個(gè)數(shù)稱為該點(diǎn)y的潛在價(jià)值，也就是這個(gè)團(tuán)C能發(fā)展的上界。如果這個(gè)上界比largest還要小或相等，那么這個(gè)點(diǎn)也是個(gè)死點(diǎn)，否則是個(gè)活點(diǎn)。如果是個(gè)活點(diǎn)，將它插入最大堆H?；铧c(diǎn)的關(guān)鍵字就是它的潛在價(jià)值。當(dāng)一個(gè)k層兒子y是個(gè)活點(diǎn)，并且它對(duì)應(yīng)的團(tuán)比當(dāng)前找到的最大團(tuán)大，則更新變量largest和n元組y[1..n]。我們用一個(gè)記錄來(lái)存放與活點(diǎn)v有關(guān)的參數(shù)，它含有以下幾個(gè)域:v.level =活點(diǎn)v所在的層號(hào),根算第0層v.upper =活點(diǎn)v的潛在價(jià)值v.lower =活點(diǎn)v的價(jià)值下界，即v對(duì)應(yīng)的團(tuán)所含頂點(diǎn)個(gè)數(shù)v.x[1..n] =活點(diǎn)v對(duì)頂點(diǎn)1，2，…，n的取舍決定。當(dāng)展開(kāi)點(diǎn)，即最大堆的根，是搜索樹(shù)中k-1層的一個(gè)活點(diǎn)v時(shí)，如上所述，判定函數(shù)檢測(cè)該點(diǎn)的兩個(gè)k層兒子。如果是活點(diǎn)，則把該兒子插入堆中。處理完兩個(gè)兒子后，刪除這個(gè)展開(kāi)點(diǎn)，并修復(fù)這個(gè)堆。在下面?zhèn)未a中，Clique(k,x[1..k-1])是用來(lái)檢查活點(diǎn)x[1..k-1]的x[k]=1的兒子所對(duì)應(yīng)的集合是否是一個(gè)團(tuán)。它完成判定函數(shù)要做的3件事中的第1件。其它兩件事在主程序中完成。Clique(k,x[1..k-1]) //查vk與x[1..k-1]的團(tuán)的頂點(diǎn)都有邊。A[1..n,1..n]是默認(rè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 //如果沒(méi)有邊(vk,vi) thenreturnfalse endifendforreturntrueEnd在下面?zhèn)未a中，最大堆用一個(gè)數(shù)組H[1..heapsize]實(shí)現(xiàn)，初始時(shí)，heapsize=1。Max-Clique(A[1..n,1..n],y[1..n],largest) //屬出最大團(tuán)y[1..n]，它的頂點(diǎn)個(gè)數(shù)是largestt.level0 //根的層號(hào)=0t.uppern //根的潛在價(jià)值t.lower0 //根代表的團(tuán)的頂點(diǎn)個(gè)數(shù)t.x[1..n][0..0] //根代表的團(tuán)是空集H[1]t //把根記錄插入堆里heapsize1largest0 //下界初值為0y[1..n][0..0] //答案點(diǎn)初始為空whileheapsize>0 vHeap-Extract-Max(H[1..heapsize],max) //摘取H[1] kv.level //層號(hào) ifk=n thenreturny[1..n],largest //y是答案點(diǎn)，v也是?？赡躹=y endif kk+1 ifk=1 thenx[0]0 //表示根結(jié)點(diǎn) endif x[1..k-1]v.x[1..k-1] //x[0..k-1]是臨時(shí)工作變量 ifClique(k,x[1..k-1])=true //v[k]=1的兒子是活點(diǎn)，建點(diǎn)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 //更新最大團(tuán) 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，潛在價(jià)值比父親小1 right.lowerv.lower //右兒子下界與父親的同 right.levelk //比父親大1 right.x[1..k-1]x[1..k-1] //與父親同 right.x[k]0 ifright.upper>largest //否則是死點(diǎn)刪除 thenMax-Heap-Insert(H[1..heapsize],right) //right是活點(diǎn)入堆 endifendwhilereturny[1..n],largestEnd用最大價(jià)值先出的分枝限界法找出有向圖G(V,E)中以點(diǎn)sV為起點(diǎn)的最長(zhǎng)的一條簡(jiǎn)單路徑。假定圖G是用鄰接矩陣表示的，路徑的長(zhǎng)度為邊的個(gè)數(shù)。解： 假設(shè)圖的頂點(diǎn)集合是V={v[1],v[2],…,v[n]}，鄰接矩陣是A[1..n,1..n]，其中A[i,j]=1表示頂點(diǎn)v[i]和v[j]之間有邊。搜索樹(shù)的根含頂點(diǎn)s。搜索樹(shù)中k層的一個(gè)點(diǎn)x，對(duì)應(yīng)一個(gè)k+1元組x[1..k+1]=(x[1],x[2],…,x[k+1])，其中，x[1]=s，x[i]V(2≤i≤k+1)是顯式約束。如果頂點(diǎn)序列，x[1],x[2],…,x[k+1]，是一條從s開(kāi)始的長(zhǎng)為k的簡(jiǎn)單路徑，那么點(diǎn)x就是一個(gè)活點(diǎn)，否則是死點(diǎn)。以死點(diǎn)為根的子樹(shù)可刪除。根算第0層，它對(duì)應(yīng)的頂點(diǎn)序列，x[1]，只含一個(gè)點(diǎn)s。搜索樹(shù)中每一個(gè)活點(diǎn)v以一個(gè)記錄形式保存在一個(gè)最大堆中，它有以下的域：v.level =活點(diǎn)v的層號(hào)，也是v對(duì)應(yīng)的路徑的長(zhǎng)度。v.x[1..level+1] =活點(diǎn)v所對(duì)應(yīng)的路徑上的頂點(diǎn)序列，其中v.x[1]=s。另外，算法設(shè)置全局變量y[1..longest+1]和longest來(lái)記錄目前找到的最長(zhǎng)路徑的頂點(diǎn)序列以及它的長(zhǎng)度。我們把搜索樹(shù)中一個(gè)活點(diǎn)v對(duì)應(yīng)的路徑的長(zhǎng)度，v.level，作為v的關(guān)鍵字，放在一個(gè)最大堆H中。如果當(dāng)前展開(kāi)點(diǎn)，也就是堆H的根，是搜索樹(shù)中k層的一個(gè)活點(diǎn)v，v.level=k，v.x[1..k+1]=(x[1],x[2],…,x[k+1])，那么分枝限界法做下面幾件事：把點(diǎn)v從堆中摘除并修復(fù)堆。如果k=n-1，那么這個(gè)展開(kāi)點(diǎn)是個(gè)答案點(diǎn)，路徑長(zhǎng)是n-1，算法中止。否則，等堆里沒(méi)有點(diǎn)為止，即所有可能的情況都已搜索完，這時(shí)y[1..longest+1]和longest就是解。用判定函數(shù)檢測(cè)點(diǎn)v在搜索樹(shù)中的每一個(gè)兒子是否是活點(diǎn)。它有n個(gè)k+1層兒子，即x[k+2]=v[j](1≤j≤n)。當(dāng)x[k+2]=v[j]時(shí)，這個(gè)兒子是活點(diǎn)的充要條件是v[j]{x[1],x[2],…,x[k+1]}并且(x[k+1]，v[j])E。當(dāng)一個(gè)兒子x[1..k+2]=(x[1],x[2],…,x[k+1],v[j])是活點(diǎn)時(shí)，它對(duì)應(yīng)的簡(jiǎn)單路徑顯然比父親的路徑長(zhǎng)一條邊。因此，將這個(gè)兒子插入堆中，并更新變量longest和y[1..longest+1]。在下面?zhèn)未a中，Simple-Path是判定函數(shù)，用以檢查擴(kuò)展點(diǎn)的兒子x[k+2]=v[j]是否對(duì)應(yīng)一條簡(jiǎn)單路徑。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中，最大堆用一個(gè)數(shù)組H[1..heapsize]實(shí)現(xiàn)，初始時(shí)，heapsize=1，而H[1]中存的是搜索樹(shù)的根的信息。Longest-Path(A[1..n,1..