计算机算法设计与分析第八章 回溯法

第八章回溯法8.1一般方法8.28-皇后问题8.3子集和数问题18.1一般方法什么是回溯回溯回溯入口出口回溯迷宫游戏什么是回溯法回溯法是一个既带有系统性又带有跳跃性的的搜索算法回溯法是以深度优先的方式系统地搜索问题的解,它适用于解一些组合数较大的问题。回溯2问题的解可以用一个n元组(x1,…,xn)来表示，其中的xi取自于某个有穷集Si

,并且这些解必须使得某一限界函数P(x1,…,xn)取极值。不断地用修改过的限界函数Pi(x1,…,xn)去测试正在构造的n元组的部分向量,看是否可能导致最优解,如果不能,就将可能要测试的mi+1…mn个向量略去。回溯法的解需要满足一组综合的约束条件,通常分为:显式约束和隐式约束显式约束条件:

限定每个x只从一个给定的集合上取值,满足显式约束的所有元组确定一个可能的解空间例:xi>=0,si={所有非负实数}隐式约束条件:

描述了xi必须彼此相关的情况回溯法的基本概念3例:4-皇后问题在一个4*4棋盘上放4个皇后,使每两个皇后之间都不能互相“攻击”,即使得每两个皇后都不能在同一行、同一列及同一条斜角线上。4皇后问题可以表示为4-元组(x1,…,x4)

，其中xi是放置皇后i所在的列号。显式约束条件:

si={1,2,3,4},1≤i≤4隐式约束条件:

没有两个xi可以相同,且没有两个皇后可以在同一条斜角线上Q1Q2Q3Q44问题描述:已知n+1个正数:wi(1≤i≤n)和M,要求找出wi的和数是M的所有子集。

例:n=4,(w1,

w2,

w3,w4)=(11,13,24,7),M=31

满足要求的子集是(11,13,7)和(24,7)用wi的下标来表示解向量更为方便,因此这两个解向量可以表示为:(1,2,4)和(3,4)显式约束条件:xi∈{j|j是wi的下标值,1≤j≤n}隐式约束条件:要求没有两个xi是相同的,且相应的wi的和数等于M为避免产生同一个子集的重复情况(如(1,2,4)和(1,4,2)),附加一个隐式约束条件:xi≤xi+1,1≤j≤n例:子集和数问题5一个问题的解可以有多种表示形式,而这些表示形式都使得所有的解是满足某些约束条件的多元组子集和数问题的另一种列式表示:每一个解的子集由一个大小固定的n-元组(x1,…,xn)所表示,它使得xi∈{0,1},1≤i≤n;

如果选择wi,则xi=1;否则xi=0解向量(1,2,4)和(3,4)可表示为(1,1,0,1)和(0,0,1,1)例:子集和数问题6145674334101112942421415161732322021222343432526272841143031323331133813341924291342183450342………4-皇后问题的解空间树x1=1x2=2712345678910111213141516x2=2x2=3x2=4x2=3x2=4x2=4x1=1x1=2x1=3x1=4x3=3x3=4x3=4x3=4x4=4子集和数问题的解空间树1

解空间树中的路径对应一个向量根结点到自身的空路径对应一个空向量()

树中红色的路径分别对应向量:(4)(1,2,4)(2,3,4)817123456789101112131415161820232425192122262728293031x1=1x1=0x2=1x3=1101010x2=0x3=0x3=1x3=0x2=1x2=0x3=1x3=0x3=1x3=01010101010子集和数问题的解空间树2注:结点按D-检索方式编号从根结点到叶结点的一条路径确定解空间中的一个元组树中红色路径表示元组(1,1,0,1)9解空间树(状态空间树)的术语问题状态(problemstate):树中的每一个结点确定所求解问题的一个问题状态状态空间(statespace):由根结点到其他结点的所有路径确定了这个问题的状态空间解状态(solutionstates):是这样一些问题状态S,对于这些问题状态,由根到S的那条路径确定了这个解空间中的一个元组答案状态(answerstates):是这样的一些解状态S,对于这些解状态而言,由根到S的这条路径确定了这问题的一个解10静态树(statictrees):树结构与所要解决问题的实例无关动态树(dynamictrees):树结构是与实例相关的,且树结构是动态确定的活结点:自己已经生成而其所有的儿子结点还没有全部生成的结点E-结点(正在扩展的结点):当前正在生成其儿子结点的活结点死结点:不再进一步扩展或者其儿子结点已全部生成的生成结点解空间树(状态空间树)的术语11问题状态的生成第一种状态生成方法:当前的E-结点R一旦生成一个新的儿子结点C,这个C结点就变成一个新的E-结点,当检测完了子树C后,R结点就再次成为E-结点,生成下一个儿子结点。(该方法也称为深度优先结点生成法)第二种状态生成方法:一个E-结点一直保持到变成死结点为止。它又分为两种方法:宽度优先生成方法(队列方法)和D-检索方法(栈方法)第一种状态生成方法对应回溯法第二种状态生成方法对应分枝-限界法12结点2变成E-结点,它再生成结点3,路径变为(1,2),即皇后1在第1列上,皇后2在第2列上,所以结点3被杀死,此时应回溯13x2=22x1=1开始把根结点作为唯一的活结点,根结点就成为E-结点而且路径为();接着生成儿子结点,假定按自然数递增的次序来生成儿子,那么结点2被生成,这条路径为(1),即把皇后1放在第1列上kill112例:4-皇后问题138x2=3回溯到结点2生成结点8,路径变为(1,3),则结点8成为E-结点,它生成结点9和结点11都会被杀死(即它的儿子表示不可能导致答案的棋盘格局),所以结点8也被杀死,应回溯13x2=22x1=1kill11x3=49x3=2112123killkill例:4-皇后问题1231413x2=415x4=3回溯到结点2生成结点13,路径变为(1,4),结点13成为E-结点,由于它的儿子表示的是一些不可能导致答案结点的棋盘格局,因此结点13也被杀死,应回溯8x2=313x2=22x1=1kill11x3=49x3=2killkill14x3=2kill112123412316x3=3kill例:4-皇后问题1518x1=213x2=415x4=313x2=22x1=1kill11x3=49x3=2killkill8x2=314x3=2kill16x3=3kill结点2的所有儿子表示的都是不可能导致答案的棋盘格局,因此结点2也被杀死;再回溯到结点1生成结点18,路径变为(2)19x2=124x2=3killkill结点18的儿子结点19、结点24被杀死,应回溯例:4-皇后问题1121216131x4=3结点18生成结点29,结点29成为E-结点,路径变为(2,4);18x1=213x2=415x4=313x2=22x1=1kill11x3=49x3=2killkill8x2=314x3=2kill16x3=3kill19x2=124x2=3killkill121231234结点29生成结点30,路径变为(2,4,1)结点30生成结点31,路径变为(2,4,1,3),找到一个4-皇后问题的可行解29x2=430x3=1可行解17从根结点出发,以深度优先方式搜索整个解空间。首先根结点成为一个活结点,同时也成为当前的扩展结点。在当前扩展结点处,搜索向纵深方向移至一个新结点,该新结点成为一个新的活结点,并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。此时应回溯至最近的一个活结点处,并使该活结点成为当前的扩展结点。回溯法以这种方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。回溯法搜索过程18回溯算法的形式化描述假设回溯法要找出所有的答案结点设(x1,x2,…,xi-1)是状态空间树中由根到一个结点的路径，而T(x1,…xi-1)是下述所有结点xi的集合，它使得对于每一个xi，(x1,x2,…,xi)是一条由根到结点xi的路径；假定存在一些限界函数Bi,如果路径(x1,x2,…,xi)不可能延伸到一个答案结点,则Bi(x1,x2,…,xi)取假值,否则取真值。解向量X(1:n)中的第i个分量,就是那些选自集合T(x1,x2,…,xi-1)且使Bi为真的xi19回溯算法的形式化描述procedureBACKTRACK(n)intk,n;localX(1:n);k=1;while(k>0)do{if(还剩有没检验的X(k)使得X(k)∈T(X(1)…X(k-1))andB(X(1)…X(k))==TRUE)then

{if(X(1)…X(k))是一条抵达答案结点的路径)thenprint(X(1)…X(k));k=k+1;}elsek=k-1;}endBACKTRACK//回溯//打印数组X//考虑下一个集合在X(1)…X(k-1)已经被选定的情况下,T(X(1)…X(k-1))给出X(k)的所有可能的取值,限界函数B(X(1)…X(k))判断哪些X(k)满足隐式约束条件20procedureRBACKTRACK(k)globalX(1:n);intk,n;for(满足下式的每个X(k),X(k)∈T(X(1)…X(k-1))andB(X(1),…B(k))==true)do{if(X(1),…,X(k))是一条抵达答案结点的路径

thenprint(X(1)…X(k));

callRBACKTRACK(k+1);

}endRBACKTRACK回溯算法的递归描述进入算法时,解向量X中的前k-1个分量X(1)…X(k-1)已经被赋值对于所有可以由根结点到达,并可能使限界函数B为真的结点X(k),判断(X(1)…X(k))是否是一条能抵达答案结点的路径21回溯法的效率估计回溯法的效率主要取决于四种因素:生成下一个X(k)的时间满足显式约束条件的X(k)的数目限界函数Bi的计算时间对于所有的i，满足Bi的X(k)的数目一旦选定了一种状态空间树结构,前三种因素对于所要解决的实例没有多大的关系,只有第四种因素,对于问题的不同实例,生成的结点数是不相同的22回溯法的效率估计重新排列动态状态空间树信息熵法蒙特卡罗方法 估计状态空间树展开的节点数238.28-皇后问题问题描述:在一个8*8棋盘上放置8个皇后,使得每两个皇后之间都不能互相“攻击”,即每两个皇后都不能在同一行、同一列及同一条斜角线上Q1Q2Q3Q4Q5Q6Q7Q88皇后问题可以表示为8-元组(x1,…,x8),其中xi是放置皇后i所在的列号图中的可行解表示为一个8-元组即(4,6,8,2,7,1,3,5)24a11a12a13a14a15a16a17a18a21a22a23a24a25a26a27a28a31a32a33a34a35a36a37a38a41a42a43a44a45a46a47a48a51a52a53a54a55a56a57a58a61A62a63a64a65a66a67a68a71a72a73a74a75a76a77a78a81a82a83a84a85a86a87a88用二维数组A(1:8,1:8)的下标来标记每个皇后的位置，那么可以看到:对于在由左到右的同一条斜角线上的每个元素具有相同的“行-列”值;对于在由右到左的同一条斜角线上的每个元素则具有相同的“行+列”值设有两个皇后被放置在(i,j)和(k,l)位置上,那么当且仅当

i–j=k-l或

i+j=k+l

时,它们才在同一条斜角线上。将这两个等式分别变换成:j-l=i-k或

j-l=k-i因此当且仅当|j-l|=|i-k|

时(即两个皇后所在位置的行差距等于列差距时),两个皇后在同一条斜角线上25procedurePLACE(k)inti,k;i=1;while(i<k)do{if(X[i]==X[k]orABS(X[i]-X[k])==ABS(i-k))thenreturn(false);i=i+1;}return(true);endPLACE若一个皇后能放在第k行和第X(k)列,则返回true,否则返回falseX是全程数组,进入此过程时已置入了k个值,ABS是绝对值函数能否放置一个新皇后的算法描述:注:两个皇后被放置在(i,j)和(k,l)位置上所以j=X[i],l=X[k],|j-l|=|i-k|

即为ABS(X[i]-X[k])==ABS(i-k)//若两个皇后在同一列上,或在同一对角线上,则说明该位置不能放皇后,应返回false值26求n-皇后问题的回溯算法描述procedureNQUEENS(n)intk,n,X(1:n);X[1]=0;k=1;while(k>0)do{X[k]=X[k]+1;while(X[k]<=n

and

NotPLACE(k)

)do{X[k]=X[k]+1;}if(X[k]<=n)then{if(k==n)thenprint(X);else{k=k+1;X[k]=0;}}elsek=k-1;}endNQUEENS//若是一个完整的解则打印数组X//k是当前行;X(k)是当前列//对所有的行执行循环语句//移到下一列当该位置不能放皇后时转到下一列//找到一个位置//否则转到下一行//没有合适的位置,回溯271234X001Q1PLACE(1)i=1;while(i<k)do1<1,循环不执行return(true);X[1]=0;k=1;

while(k>0)do{X[k]=X[k]+1;while(X[k]<=nandNotPLACE(k))do1<=nandNottrue,循环不执行if(X[k]<=n)thenif(k≠n)then不执行

else{k=k+1=2;X[2]=0;}}endwhilek=2;

while(k>0)do{X[k]=X[k]+1;while(X[k]<=nandNotPLACE(k)

)do1<=nandNotfalse,X[k]=X[k]+1=2;2<=nandNotfalse,X[k]=X[k]+1=3;3<=nandNottrue,循环不执行123if(X[k]<=n)thenif(k≠n)then不执行

else{k=k+1=3;X[3]=0;}0}endwhileQ2PLACE(2)i=1;while(i<k)doif(X[i]==X[k])thenreturn(false);PLACE(2)i=1;while(i<k)doif(|X[i]-X[k]|==|i-k|)

thenreturn(false);PLACE(2)i=1;while(i<k)do{if(X[i]≠X[k]or|X[i]-X[k]|≠|i-k|)then不执行

i=i+1=2;结束循环}return(true);281234X130Q1Q2k=3;

while(k>0)do{X[k]=X[k]+1;while(X[k]<=nandNotPLACE(k))doif(X[k]≮n)then不执行elsek=k-1=2;

//回溯}endwhilek=2;

while(k>0)do{X[k]=X[k]+1=3+1=4;while(X[k]<=nandNotPLACE(k)

)do1<=nandNotfalse,X[k]=X[k]+1=2;2<=nandNotfalse,X[k]=X[k]+1=3;4<=nandNottrue,循环不执行if(X[k]<=n)thenif(k≠n)then不执行

else{k=k+1=3;X[3]=0;}}endwhileQ213<=nandNotfalse,X[k]=X[k]+1=4;4<=nandNotfalse,X[k]=X[k]+1=5;2345405≮n,循环不执行298.3子集和数问题子集和数问题:假定有n个不同的正数,要求找出这些数中所有使得某和数为M的组合问题描述:已知n+1个正数:wi(1≤i≤n)和M,要求找出wi的和数是M的所有子集本节将利用大小固定的元组来研究一种回溯算法，解决这一问题

例:n=4,(w1,

w2,

w3,w4)=(7,11,13,24),M=31

满足要求的子集是(1,1,1,0)和(1,0,0,1)30生成图中任一结点的儿子:对于i级上的一个结点,其左儿子对应于X(i)=1,右儿子对应于X(i)=0对于限界函数的一种简单选择是:当且仅当∑W(i)X(i)+∑W(i)≥M时,

B(X(1)…X(k))=truei=1ki=k+1n若W(i)按升序排列,则限界函数可以被强化:1x1=1x1=02311161213101415478956x2=1x3=1101010x2=0x3=0x3=1x3=010211718251922232420x2=1x2=0x3=1x3=01010……当且仅当∑W(i)X(i)+∑W(i)≥Mi=1ki=k+1nB(X(1)…X(k))=true且∑W(i)X(i)+W(k+1)≤M时i=1k31procedureSUMOFSUB(s,k,r)globalfloatW(1:n);globalintX(1:n);floatr,s;intk,j;X[k]=1;if(s+W[k]==M)then {print(X[j],j=1tok);print(X[j]=0,j=k+1ton);

return;}elseif(s+W[k]+W[k+1]<=M)then

callSUMOFSUB(s+W[k],k+1,r-W[k]);if(s+r-W[k]>=Mands+W[k+1]<=M)then{X[k]=0;

callSUMOFSUB(s,k+1,r-W[k]);

}endSUMOFSUB 子集和数问题的递归回溯算法//进入此过程时X(1)…X(k)的值已确定;W(j)按非降次序排列;假定W(1)≤M,∑W(i)≥M(i=1…n);j=1j=kk-1ns=∑W(j)X(j);r=∑W(j)//生成左儿子//若找到子集,则打印//否则当Bk=true时,

递归生成左儿子//当Bk=true时递归生成右儿子32实例:n=6,M=30,W(1:n)=(5,10,12,13,15,18)j=1j=kk-1ns=∑W(j)X(j);r=∑W(j)SUMOFSUB(s,k,r)开始调用时k=1,由公式算出s=0,r=73(注:为书写简便将SUMOFSUB缩写为SB)①SB(0,1,73)//s=0,k=1,r=73X[1]=1;if(s+W[k]==M)then0+5=5≠300+5+10=15<300+5=5,1+1=2,73-5=68等待执行的部分:if(s+r-W[k]>=Mands+W[k+1]<=M)then{X[k]=0;callSB(s,k+1,r-W[k]);}end①SB0,1,735,2,68X[1]=1不执行elseif(s+W[k]+W[k+1]<=M)thencall②SB(s+W[k],k+1,r-W[k]);33②SB(5,2,68)//s=5,k=2,r=68X[2]=1;if(s+W[k]==M)then5+10=15≠305+10+12=27<305+10=15,2+1=3,68-10=58等待执行的部分:if(s+r-W[k]>=Mands+W[k+1]<=M)then{X[k]=0;callSB(s,k+1,r-W[k]);}end②SB不执行else

if(s+W[k]+W[k+1]<=M)thencall③SB(s+W[k],k+1,r-W[k]);0,1,735,2,68X[1]=115,3,58X[2]=134else

if(s+W[k]+W[k+1]<=M)then③SB(15,3,58)//s=15,k=3,r=58X[3]=1;if(s+W[k]==M)then15+12=27≠3015+12+13=40>3015+58-12=61>30and15+13=28<30不执行不执行if(s+r-W[k]>=Mands+W[k+1]<=M)then{X[3]=0;call④SB(s,k+1,r-W[k]);}15,3+1=4,58-12=46end③SB15,4,46X[3]=00,1,735,2,68X[1]=115,3,58X[2]=135④SB(15,4,46)//s=15,k=4,r=46X[4]=1;if(s+W[k]==M)then15+13=28≠3015+13+15=43>30不执行else

if(s+W[k]+W[k+1]<=M)then不执行if(s+r-W[k]>=Mands+W[k+1]<=M)then{X[4]=0;call⑤SB(s,k+1,r-W[k]);}15,4+1=5,46-13=33end④SB15+46-13=48>30and15+15=30=300,1,735,2,68X[1]=115,3,58X[2]=115,4,46X[3]=015,5,33X[4]=036⑤SB(15,3,33)//s=15,k=5,r=33X[5]=1;if(s+W[k]==M)then15+15=30==M{forj=1tokdoprint(X[j]);forj=k+1tondo

print(X[j]=0);

return;

}打印X=(1,1,0,0,1,0)end⑤S