算法分析与设计-第五章

第五章回溯法面向的问题：回溯法基本方法：硬性处理。回溯法的关键问题约束条件显式约束和隐式约束QQQQQQQQ将其加入到显式条件中，于是解空间的大小由88个元组减少到8！个元组。静态树动态树问题状态。状态空间解状态答案状态914

1615

172120

22

25

27

30

3223

26

28

31

33383450例：4-皇后问题的解空间树结构（p195）系统地生成问题状态活结点死结点E-结点生成问题状态空间的两种方法：限界回溯法分枝－限界法123kill11281x1=12x2=

23kill9

11kill

kill1121231231381x1=12x2=

23kill9

11

14kill

kill15kill112123412316kill18x1=

213x2=

41x2=

2x1=123killx3=4x3=2x2=

38x3=29

11

14kill

killx4=315kill16kill19killx3=324kill1121213118x1=

213x2=

41x2=

2x1=123killx3=4x3=2x2=

389

11

14kill

killx4=3x3=215kill16kill19killx3=324kill1212312342930可行解从根结点出发,以深度优先方式搜索整个解空间。回溯法以这种方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。(还剩有没检验的X(k)使得X(k)∈T(X(1)…X(k-1))

andB(X(1)…X(k))==TRUE){if(X(1)…X(k))是一条抵达答案结点的路径)then print

(

X(1)…X(k));k=k+1;}在X(1)…X(k-1)已经被选定的情况下,T(X(1)…X(k-1))给出X(k)的所有可能的取值,限界函数B(X(1)…X(k))判断哪些X(k)满足隐式约束条件(

满足下式的每个X(k),

X(k)

∈T(X(1)…X(k-1))and

B(X(1),…B(k))==true)(X(1),…,X(k))是一条抵达答案结点的路径call

RBACKTRACK(k+1);进入算法时,解向量X中的前k-1个分量X(1)…X(k-1)已经被赋值对于所有可以由根结点到达,并可能使限界函数B为真的结点X(k),判断(X(1)…X(k))是否是一条能抵达答案结点的路径生成下一个X(k)的时间满足显式约束条件的X(k)的数目限界函数Bi的计算时间对于所有的i，满足Bi的X(k)的数目a11a12a13a14a15a16a17a18a21a22a23a24a25a26a27a28a31a32a33a36a37a38a41a42a43a44a45a46a47a48a51a52a53a54a55a56a57a58a61A62a63a64a65a66a67a68a71a72a73a74a75a76a77a78a81a82a83a84a85a86a87a88用二维数组A(1:8,1:8)的下标来标记每个皇后的位置，那么可以看到:对于在由左到右的同一条斜角线上的每个元素具有相同的“行-列”值;对于在由右到左的同一条斜角线上的每个元素则具有相同的“行+列”值若一个皇后能放在第k行和第X(k)列,则返回true,

否则返回falseX是全程数组,进入此过程时已置入了k个值,ABS是绝对值函数置上注

位所A//若两个皇后在同一列上,或在同一对角线上,则说明该位置为不能放皇后,应返回false值//找到一个位置//若是一个完整的解则打印数组X//否则转到下一行//没有合适的位置,回溯//k是当前行;X(k)是当前列//对所有的行执行循环语句//移到下一列当该位置不能放皇后时转到下一列1234X130Q1Q2PLACE(1)1<=n

andNot true,循环不执行if

(X[k]<=n)

thenif

(k≠n)

then

不执行else {

k=k+1=2; X[2]=0;

}PLACE(2)i=1;3<=n

an

while

(

i<k)

do{if

(X[i]≠X[k]

or

|X[i]-X[k]|≠|i-k|)then

不执行i=i+1=2;

结束循环}return

(true);1234X1Q1Q24<=n

andNot true,循环不执行405≮n,循环不执行1234

5678

9

10

1112

13

141516=3121318201921262730

31

28

29

24

25

22

23

1614

15

11

8

9注:结点按D-检索方式从根结点到叶结点的一条路径确定解空间中的一个元组树中红色路径表示元组(1,1,0,1)111231175

6

8

9

121112117182511当且仅当∑W(i)X(i)+∑W(i)≥Mki=1

i=k+1n且∑W(i)X(i)+W(k+1)≤M

时i=1kif

(s+W[k]==M)

then{

print(X[j],

j=1

tok);

print(X[j]=0,

j=k+1

to

n);

return;

}else

if

(s+W[k]+W[k+1]<=M)

thencall SUMOFSUB(s+W[k],k+1,r-W[k]);end

SUMOFSUBif

(s+r-W[k]>=M

and

s+W[k+1]<=M)

then{

X[k]=0;call SUMOFSUB(s,k+1,r-W[k]);}//当Bk=true时递归生成右儿子//进入此过程时X(1)…X(k)的值已确定;W(j)按非降次序排列;假定W(1)≤M,∑W(i)≥M

(i=1…n);j=1j=kk-1

ns=

∑W(j)X(j)

;

r

=

∑W(j)//生成左儿子//若找到子集,则打印k//否则当B

=true时,递归生成左儿子实例:n=6,M=30,W(1:n)=(5,10,12,13,15,18)j=1j=kk-1

ns=

∑W(j)X(j)

;r

=∑W(j)开始调用时k=1,由公式算出s=0,r=73(注:为书写简便将SUMOFSUB缩写为SB)0+5=5≠300+5+10=15<300+5=5,1+1=2,73-5=680,1,

735,2,68不执行else

]

W[

]call

②

SB(s+W[k],

k+1,

r-W[k]);等待执行的部分:if

(s+r-W[k]>=M

and

s+W[k+1]<=M)

then{

X[k]=0;

call SB(s,

k+1,

r-W[k]);

}end

①SB5+10=15≠305+10+12=27<305+10=15,2+1=3,68-10=58call

③

SB(s+W[k],

k+1,

r-W[k]);等待执行的部分:if

(s+r-W[k]>=M

and

s+W[k+1]<=M)

then{

X[k]=0;

call SB(s,

k+1,r-W[k]);

}end

②SB不执行else0,1,

735,2,6815,3,58else15+12=27≠3015+12+13=40>3015+58-12=61>30

and

15+13=28<30不执行不执行call

④

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

}15,3+1=4,58-12=4615,

4,

460,1,735,2,6815,3,5815+13=28≠3015+13+15=43>30不执行else不执行call

⑤

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

}15,4+1=5,46-13=3315+46-13=48>30

and

15+15=30=300,1,735,2,6815,3,5815,

4,

4615,5,3315+15=30==Mfor

j=k+1

ton

doprint(X[j]=0);return;打印X=(1,1,0,0,1,0)A0,1,

735,2,6815,3,5815,4,4615,5,335,3,58从⑤SB(15,3,

33)返回到④SB(15,4,46),再返回到③SB(15,3,58),最后返回到②SB(5,2,

68),执行剩余的代码5+68-10=63>30

and

5+12=17<30call

⑥

SB(s,k+1,r-W[k]);5,2+1=3,68-10=58已经执行的部分:X[2]=1;if

(s+W[k]==M)

thenelse

if

(s+W[k]+W[k+1]<=M)

thencall

③

SB(s+W[k],

k+1,

r-W[k]);A0,1,735,2,6815,3,5815,4,4615,5,33else17,

4,

465+12=17≠305+12+13=30=305+12=17,3+1=4,58-12=46等待执行的部分:if

(s+r-W[k]>=Mand

s+W[k+1]<=M

then{

X[k]=0;

call SB(s,

k+1,r-W[k]);

}end

⑥SB不执行call

⑦

SB(s+W[k],

k+1,

r-W[k]);0,1,735,2,6815,3,5815,4,4615,5,33XA5,3,58B17+13=30==M打印X=(1,0,1,1,0,0)17,4,460,1,

735,2,6815,3,5815,4,4615,5,33A5,3,58for

j=k+1

ton

doprint(X[j]=0);return;mm-

判定问题最优化问题:四色问题四色问题可以转换成对一平面图的4-判定问题F

T

T

T

FT

F

T

T

TT

T

F

T

TT

T

T

F

TF

T

F

T

FGRAPH=图算法的解空间树是一棵度数为m,高为n+1的树在i级上的每个结点有m个儿子,它们与Xi的m种可能的赋值相对应(1≤i≤n),

在n+1级上的结点都是叶结点。例:

4-

问题,

n=5

,m=42

3

42

3

4……2callNEXTVALUE(k);

//将一种合法的颜色分配给X[k]//对结点k+1进行//

对结点k进行

,

调用从MCOLORING(1)开始//数组X用来存放各结点的颜色初始将数组X置0//产生对X[k]所有的合法赋值//若X[k]为0表示没有可用的颜色则结束这次函数调用//若n个结点都已分配了颜色则打印call

MCOLORING(k+1);}k-1GRAPH[k,j]

andX[k]==X[j])break;j==kX[k]);//进入此过程前X[1]…X[k-1]已分配了颜色;本过程给X[k]确定一个颜色：若还剩下一些颜色,它们与结点

k相邻结点的颜色不同,则将其中最高标值的颜色分配给结点k;若没剩下可用的颜色,则置X[k]为0X[k]=(X[k]+1)mod(m+1);

//给结点k分配颜色//表示没有可用的颜色//检查分给k的颜色是否与其相邻结点的颜色不同//若(k,j)是一条边(即k与j相邻),且它们具有相同的颜色,则结束for循环(当前分给k的颜色不能用)//分给结点k的颜色可用,返回其值//继续loop循环试着找另一种颜色①

NE(1) //

k=1,

X[k]=0loop{

X[k]=(X[k]+1)

mod(m+1);1234T

TT

TT

TT

T为书写简便:MCOLORING缩写为MCNEXTVALUE缩写为NEGRAPH缩写为Gcall

①NE(k);X[1]=(0+1)

mod

(3+1)=1;1≠0if

(X[k]==0) then

不执行for

j=1

to

k-1

do

不执行循环if(j==k)

then

return(X[k]);end

①NEcall

②MC(k+1);不执行1≠n得到X[1]=1X[k]≠0不执行call

②NE(k);(X[k]≠0)2≠n不执行call

③MC(k+1);②

NE(2) //

k=2,

X[k]=1loop2{

X[k]=(X[k]+1)

mod

(m+1)

//

2

mod

4=2得到X[2]=2T

TTTT

TT

Tif

(X[k]≠0)

thenfor

j=1

to

k-1=1

do不执行G[2,1]=T

andX[2]≠X[1]j=2==kend

②NEif

(G[k,

j]andX[k]==X[j]) then

不执行;if(j==k)

then

return(X[k]);不执行call

③

NE(k);(X[k]≠0)if

(X[k]≠0)

thenfor

j=1

to

k-1=2

doend③

NE不执行不执行call

④MC(k+1);③

NE(3) //

k=3,X[k]=0loop{X[k]=(X[k]+1)

mod

(m+1)

//1

mod4

=13≠nif(G[k,

j]andX[k]==X[j]) then

不执行if(j==k)

then

return(X[k]);得到X[3]=1j=3==kG[3,2]=T

andX[3]≠X[2]不执行T

TT

TT

TT

TX[1]=12call

④

NE(k);X[k]≠0if

(X[k]≠0)

thenfor

j=1to

k-1=3

doif(j==k)

thenj=print(X)即(1,2,1,2)4==n得到X[4]=2④

NE(4) //

k=4,

X[k]=1loop2{

X[k]=(X[k]+1)

mod(m+1)

//

2mod4=2if

(X[k]≠0)

thenfor

j=1t