计算机算法基础 第2版 习题及答案 第16章

PAGE16第16章 穷举搜索用回溯法设计一个给图G(V,E)着色的算法。我们假定图是用邻接矩阵表示，而可用颜色的集合是C={1,2,…,m}，m可视为常数。我们要求把所有合法的着色全部输出。解： 假设图的顶点集合是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。我们先设计一个判定函数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]) //这是回溯法的递归形式供后面主程序调用，矩阵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 //全局变量，统计答案点个数 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])记录当前找到的最大团，而它含有的顶点个数用变量largest来记录。这是一个全局变量，一旦发现更大的团，则更新这个全局变量。给定搜索树中k-1层的一个活点x=(x[1],x[2],…,x[k-1])，我们用size(x,k-1)表示它对应的团C的顶点个数|C|，显然有size(x,k-1)k-1。我们需要设计一个判定函数，当扩展点是活点x时，判断它的两个儿子是否是值得发展的活点。它需要做下面几件事：检测点x的每个儿子(x[1],x[2],…,x[k-1],x[k])(x[k]=0或1)代表的子集是否是一个团。如果不是，该儿子成死点。当一个儿子代表的子集C是一个团时，还要检查这个团能否有希望发展为比目前找到的最大的团还要大的团。办法是把余下的(n-k)个顶点全部加到这个团中，如果加上后的顶点个数，即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后，它成为死点。当然，它对应的团的规模对应于更新后的largest被记下。所以，如果x[k]=1的儿子是一个团，并且k<n，它必定是个活点。回溯法的伪码如下，其中，子程序Clique(k,x[1..k-1])实现上述判定函数功能的第(1)部分，即用来检查活点x[1..k-1]的一个x[k]=1的儿子是否对应一个团。判定函数的另两部分的功能在子程序Backtrack-Clique(k,x[1..k-1])中完成。子程序Backtrack-Clique(k,x[1..k-1])是回溯算法的主要部分，它以递归形式搜索以一个k-1层活点为根的子树中有没有一个活点使得它代表的团比目前找到的最大团更大。如果有，则更新全局变量y[1..n]。当我们的主程序以k=1调用这个子程序时，即可得到结果。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)) //继续递归搜索 //因为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在栈顶，那么，从栈底到栈顶的顶点序列实际上是搜索树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，但根据x[1..k]的取值计算，往往可大大减小这个集合T(k)。这个集合是动态变化的，被访问过的儿子会从集合中删去。因为数组x[1..n]实际上起到了堆栈的作用，所以不需另外再设堆栈。下面是伪码，其中，B(x[1..k])是判断点x[1..k]是否是活点的判定函数，T(x[1..k])是计算点x[1..k]的儿子集合T(k)的函数，Answer(x[1..k])是判断点x[1..k]是否是答案点的函数。因为搜索空间是n维，我们规定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的规模，size(x,k)=|C|，并用变量largest来记录当前找到的最大独立集的规模。当我们找到一个大于等于当前找到的最大独立集时，便把它压入一个堆栈S。当全部搜索完成时，所有最大独立集就存放在栈顶部分。注意，S是独立于回溯法本身所用的堆栈。我们需要设计一个判定函数，在搜索到k-1层的一个活点x=(x[1],x[2],…,x[k-1])时，判定函数需要判断它的两个儿子是否是值得发展的活点。它需要做下面几件事：检测点x的每个儿子(x[1],x[2],…,x[k-1],x[k])(x[k]=0或1)对应的子集是否是一个独立集。如果不是，该儿子成死点。当一个儿子对应的子集是一个独立集时，还要检查这个独立集能否有希望发展为与目前找到的最大的独立集有同等规模或更大的独立集。办法是把余下的(n-k)个点全部加到这个独立集中，如果顶点个数比largest小，那么这个点也是个死点，否则是个活点。当一个儿子是个活点，并且它对应的独立集大于等于当前找到的最大独立集时，则更新变量largest并把这个点压入堆栈S。回溯法的伪码如下，其中，Disconnect(k,x[1..k-1])是用来实现上述判定函数功能的第(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调用这个子程序时，即可从算法结束时堆栈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)) //独立集及其规模入栈 largest¬size(x,k) //也许相等 endif if(k+1)£n //肯定是活点 thenBacktrack-Independent-Set(k+1,x[1..k],size(x,k)) //继续递归搜索 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)) //继续递归搜索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“largest”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])，判定函数需要检测该点的每一个儿子是否是一个活点。它有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时，检查是否对应一条哈密尔顿回路。如果是，则输出后算法结束。下面伪码中，Simple-Path是个判定函数，它检查扩展点的一个儿子是否对应一条简单路径。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]) //继续递归搜索 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|)。所以，判定函数与回溯法中的相同，可以由下面的子程序实现。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函数很简单，只要k=n且第k个皇后的位置(k,l)满足判定函数，这个点就是答案点。我们用一个记录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) //弹出栈顶的扩展点 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，而它含有的顶点个数用变量largest来记录。其中y[i]=1表示vi属于C，而y[i]=0表示vi不属于这个团(1≤i≤n)。这是一个全局变量，一旦发现更大的团，则更新这个全局变量。我们需要设计一个判定函数，它为扩展点x[1..k-1]=(x[1],x[2],…,x[k-1])判断它的两个儿子是否是值得发展的活点。它需要做下面几件事：检测点x[1..k-1]的x[k]=1的儿子代表的子集是否是一个团。如果不是，该儿子成死点。它的x[k]=0的儿子不需检查，因为这个儿子和它父亲x[1..k-1]有相同的团。当一个k层儿子y代表的子集是一个团C时，还要检查这个团能否有希望发展为比目前找到的最大的团还大的团。办法是把余下的(n-k)个还未作取舍的顶点全部加到这个团中，这个集合的顶点个数称为该点y的潜在价值，也就是这个团C能发展的上界。如果这个上界比largest还要小或相等，那么这个点也是个死点，否则是个活点。如果是个活点，将它插入最大堆H。活点的关键字就是它的潜在价值。当一个k层儿子y是个活点，并且它对应的团比当前找到的最大团大，则更新变量largest和n元组y[1..n]。我们用一个记录来存放与活点v有关的参数，它含有以下几个域:v.level =活点v所在的层号,根算第0层v.upper =活点v的潜在价值v.lower =活点v的价值下界，即v对应的团所含顶点个数v.x[1..n] =活点v对顶点1，2，…，n的取舍决定。当展开点，即最大堆的根，是搜索树中k-1层的一个活点v时，如上所述，判定函数检测该点的两个k层儿子。如果是活点，则把该儿子插入堆中。处理完两个儿子后，删除这个展开点，并修复这个堆。在下面伪码中，Clique(k,x[1..k-1])是用来检查活点x[1..k-1]的x[k]=1的儿子所对应的集合是否是一个团。它完成判定函数要做的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在下面伪码中，最大堆用一个数组H[1..heapsize]实现，初始时，heapsize=1。Max-Clique(A[1..n,1..n],y[1..n],largest) //属出最大团y[1..n]，它的顶点个数是largestt.level0 //根的层号=0t.uppern //根的潜在价值t.lower0 //根代表的团的顶点个数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是用邻接矩阵表示的，路径的长度为边的个数。解： 假设图的顶点集合是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就是解。用判定函数检测点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]。在下面伪码中，Simple-Path是判定函数，用以检查扩展点的儿子x[k+2]=v[j]是否对应一条简单路径。Simple-Path(x[1..k+1]，v[j]) //检查：v[j]不出现在序列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在下面伪码中，最大堆用一个数组H[1..heapsize]实现，初始时，heapsize=1，而H[1]中存的是搜索树的根的信息。Longest-Path(A[1..n,1..