《算法设计与分析基础》（Python语言描述） 课件 第5章回溯法(1).pptx

第5章走不下去就回退—回溯法;5.1.1问题的解空间;一个复杂问题的解决方案往往是由若干个小的决策（即选择）步骤组成的决策序列。

问题的解可以表示成解向量x=（x0，x1，…，xn-1），其中分量xi对应第i步的选择，xi∈Si（0≤i≤n-1）。

x中各个分量xi所有的取值的组合构成问题的解向量空间，简称为解空间，解空间一般用树形式来组织，也称为解空间树或者状态空间树。;解空间的一般结构;;;;回溯法是在解空间树中按照深度优先有哪些信誉好的足球投注网站方法从根结点出发有哪些信誉好的足球投注网站解。;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;1）无剪支;;;;2）左剪支;1 defdfs2(a,t,cs,i): #回溯算法

2 globalsum,x

3 sum+=1

4 ifi=len(a): #到达一个叶子结点

5 ifcs==t:disp(a) #找到一个满足条件的解,输出

6 else: #没有到达叶子结点

7 ifcs+a[i]=t: #左孩子结点剪支

8 x[i]=1 #选取整数a[i]

9 dfs2(a,t,cs+a[i],i+1)

10x[i]=0 #不选取整数a[i]

11dfs2(a,t,cs,i+1);3）右剪支;1 defdfs3(a,t,cs,rs,i): #回溯算法

2 globalsum,x

3 sum+=1

4 ifi=len(a): #到达一个叶子结点

5 ifcs==t:disp(a) #找到一个解,输出

6 else: #没有到达叶子结点

7 rs-=a[i] #求剩余的整数和

8 ifcs+a[i]=t: #左孩子结点剪支

9 x[i]=1 #选取整数a[i]

10 dfs3(a,t,cs+a[i],rs,i+1)

11 ifcs+rs=t: #右孩子结点剪支

12 x[i]=0 #不选取整数a[i]

13 dfs3(a,t,cs,rs,i+1)

14 rs+=a[i] #恢复剩余整数和(回溯);16 defsubs3(a,t): #求解子集和问题

17 globalx

18 x=[0]*len(a) #解向量

19 rs=0

20 foreina:rs+=e #或者rs=sum(a)

21 print(求解结果)

22 dfs3(a,t,0,rs,0) #i从0开始

23 print(sum=,sum);尽管通过剪支提高了算法的性能，但究竟剪去了多少结点与具体的实例数据相关。

上述算法最坏情况下算法的时间复杂度仍然为O(n×2n)。;;;;;;;;;;2）左剪支;3）右剪支;第i层结点出发的最大可能价值：cw表示当???选择的物品重量和（不含w[i]），cv表示当前选择的物品价值和（不含v[i]）。

此时背包剩余容量为rw=W-cw，如果按背包容量连续选择物品i及其后面的物品，直到装满，其价值一定是最大的（因为物品按v/w递减排序），最大价值为r(i)：;第i层结点：如果不选择物品i时，此时背包剩余容量为rw=W-cw。余下重量的物品的最大价值r(i+1)：;;;1 defdfs(cw,cv,i): #回溯算法

2 globalg,W,n,x,bestx,bestv,sum

3 sum+=1

4 ifi=n: #到达一个叶子结点

5 ifcw=Wandcvbestv: #找到一个更优解,保存它

6 bestv=cv

7 bestx=copy.deepcopy(x)

8 else: #没有到达叶子结点

9 ifcw+g[i].w=W: #左剪支

10 x[i]=1 #选取物品i

11 dfs(cw+g[i].w,cv+g[i].v,i+1)

12 b=bound(cw,cv,i+1) #计算限界函数值

13 ifbbestv: #右