第5章〓走不下去就回退——回溯法




















回溯法采用类似穷举法的搜索尝试过程，在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时就“回溯”(即回退)，尝试其他路径，所以回溯法有“通用解题法”之称。本章介绍回溯法求解问题的一般方法，并给出一些用回溯法求解的经典示例。本章的学习要点和学习目标如下： 

(1) 掌握问题的解空间的结构和深度优先搜索过程。

(2) 掌握回溯法的原理和算法的框架。

(3) 掌握剪支函数(约束函数和限界函数)的一般设计方法。

(4) 掌握各种回溯法经典算法的设计过程和算法分析方法。

(5) 综合运用回溯法解决一些复杂的实际问题。


5．1回溯法概述
5．1．1问题的解空间

先看求解问题的类型，通常求解问题分为两种类型，一种类型是给定一个约束函数，需要求所有满足约束条件的解，称为求所有解类型。例如在鸡兔同笼问题中，所有鸡兔头数为a，所有腿数为b，求所有头数为a、腿数为b的鸡兔数，设鸡兔数分别为x和y，则约束函数是x+y=a，2x+4y=b。另一种类型是除了约束条件以外还包含目标函数，最后是求使目标函数最大或者最小的最优解，称为求最优解类型。例如在鸡兔同笼问题中，求所有鸡兔头数为a、所有腿数为b并且鸡最少的解，这就是一个求最优解问题，除了前面的约束函数以外还包含目标函数min(x)。这两类问题本质上是相同的，因为只有求出所有解再按目标函数进行比较才能求出最优解。

求问题的所有解涉及解空间的概念，在3．1节中讨论穷举法时简要介绍了解空间，这里作进一步讨论。实际上问题的一个解是由若干决策(即选择)步骤组成的决策序列，可以表示成解向量x=(x0，x1，…，xn-1)，其中分量xi对应第i步的选择，通常可以有两个或者多个取值，表示为xi∈Si(0≤i≤n-1)，Si为xi的取值候选集，即Si=(vi,0，vi,1，…，vi,|Si|-1)。x中各分量xi的所有取值的组合构成问题的解向量空间，简称为解空间，解空间一般用树形式来组织，树中的每个结点对应问题的某个状态，所以解空间也称为解空间树或者状态空间树。

例如，对于如图5．1(a)所示的连通图，现在要求从顶点0到顶点4的所有路径(默认为简单路径)，这是一个求所有解的问题，约束条件就是0→4的路径，由于路径是一个顶点序列，所以对应的解向量x=(x0，x1，…，xn-1)表示一条路径，这里x0=0(没有其他选择)，需要求出满足约束条件的其他xi(i≥1)，这里的路径有多条，每条路径对应一个解向量，对应的解空间如图5．1(b)所示，图中i表示结点的层次，由于x0是固定的，只需要从x1开始求，所有根结点层次i=1，从中看出S1={1，3}，S2={2，4}，S3={4}。在确定解空间后该问题转换为在其中求从根结点出发搜索到叶子结点并且叶子结点为顶点4的所有解，对应的两个解为x={0，3，2，4}和x={0，3，4}。如果问题是求从顶点0到顶点4的一条最短路径，属于求最优解问题，同样需要求从顶点0到顶点4的所有路径，通过比较路径长度得到一条最短路径是x={0，3，4}。



图5．1一个连通图及其问题的解空间


归纳起来，解空间的一般结构如图5．2所示，根结点(为第0层)的每个分支对应分量x0的一个取值(或者说x0的一个决策)，若x0的候选集为S0={v0，1，…，v0，a}，即根结点的子树的个数为|S0|，例如x0=v0，0时对应第1层的结点A0，x0=v0，1时对应第1层的结点A1，…。对于第1层的每个结点Ai，Ai的每个分支对应分量x1的一个取值，若x1的取值候选集为S1={v1，0，…，v1，b}，Ai的分支数为|S1|，例如对于结点A1，当x1=v1，0时对应第2层的结点B0，…。以此类推，最底层是叶子结点层，叶子结点的层次为n，解空间的高度为n+1。从中看出，第i层的结点对应xi的各种选择，从根结点到每个叶子结点有一条路径，路径上的每个分支对应一个分量的取值，这是理解解空间的关键。



图5．2解空间的一般结构


从形式化角度看，解空间是S0×S1×…×Sn-1的笛卡儿积，例如当|S0|=|S1|=…|Sn-1|=2时，解空间是一棵高度为n+1的满二叉树。需要注意的是，问题的解空间是虚拟的，并不需要在算法运行中真正地构造出整棵树结构，然后在该解空间中搜索问题的解。实际上，有些问题的解空间因过于复杂或结点过多难以画出来。

5．1．2什么是回溯法

从前面的讨论看出问题的解包含在解空间中，剩下的问题就是在解空间中搜索满足约束条件的解。所谓回溯法，就是在解空间中采用深度优先搜索方法从



图5．3求解的搜索空间

根结点出发搜索解，与树的遍历类似，当搜索到某个叶子结点时对应一个可能解，如果同时又满足约束条件，则该可能解是一个可行解。所以一个可行解就是从根结点到对应叶子结点的路径上所有分支的取值，例如一个可行解为(a0，a1，…，an-1)，其图示如图5．3所示，在解空间中搜索到可行解的部分称为搜索空间。简单地说，回溯法采用深度优先搜索方法寻找从根结点到每个叶子结点的路径，判断对应的叶子结点是否满足约束条件，如果满足，该路径就构成一个解(可行解)。


回溯法在搜索解时首先让根结点成为活结点，所谓活结点，是指自身已生成但其孩子结点没有全部生成的结点，同时也成为当前的扩展结点，所谓扩展结点，是指正在产生孩子结点的结点。在当前扩展结点处沿着纵深方向移至一个新结点，这个新结点又成为新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点，所谓死结点，是指其所有子结点均已产生的结点，此时应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前扩展结点。



图5．4回溯过程

如图5．4所示，从结点A扩展出子结点B，从结点B继续扩展，当结点B的所有子结点扩展完毕，结点B变为死结点，从结点B回退到结点A(即回溯)，通过回溯使结点A恢复为扩展结点B之前的状态，再扩展出子结点C，此时开始做结点C的扩展，结点C就是扩展结点，由于结点A可能还有尚未扩展的其他子结点，结点A称为活结点。


从上看出，求问题的解的过程就是在解空间中搜索满足约束条件和目标函数的解。所以设计搜索算法的关键点有以下3个。

① 根据问题的特性确定结点是如何扩展的，不同问题的扩展方式是不同的。例如，在求图中从顶点s到顶点t的路径时，其扩展十分简单，就是从一个顶点找所有相邻顶点。

② 在解空间中按什么方式搜索解？实际上树的遍历主要有先根遍历和层次遍历，前者就是深度优先搜索(DFS)，后者就是广度优先搜索(BFS)。回溯法就是采用深度优先搜索解，第6章介绍的分支限界法则是采用广度优先搜索解。

③ 解空间通常十分庞大，如何高效地找到问题的解？通常采用一些剪支的方法实现。

所谓剪支，就是在解空间中搜索时提早终止某些分支的无效搜索，减少搜索的结点个数但不影响最终结果，从而提高了算法的时间性能。常用的剪支策略如下。

① 可行性剪支： 在扩展结点处剪去不满足约束条件的分支。例如，在鸡兔同笼问题中，若a=3，b=8，兔数的取值范围只能是0~2，因为有3只或者更多只兔时腿数就超过8了，不再满足约束条件。

② 最优性剪支： 用限界函数剪去得不到最优解的分支。例如，在求鸡最少的鸡兔同笼问题中，若已经求出一个可行解的鸡数为3，后面就不必再搜索鸡数大于3的结点。

③ 交换搜索顺序： 在搜索中改变搜索的顺序，比如原先是递减顺序，可以改为递增顺序，或者原先是无序，可以改为有序，这样可能减少搜索的结点总数。

严格来说，交换搜索顺序并不是一种剪支策略，而是一种对搜索方式的优化。前两种剪支策略采用的约束函数和限界函数统称为剪支函数。归纳起来，回溯法可以简单地理解为深度优先搜索加上剪支。因此用回溯法求解的一般步骤如下。

① 针对给定的问题确定其解空间，其中一定包含所求问题的解。

② 确定结点的扩展规则。

③ 采用深度优先搜索方法搜索解空间，并在搜索过程中尽可能采用剪支函数避免无效搜索。

5．1．3回溯法算法的时间分析

通常以回溯法的解空间中的结点个数作为算法的时间分析依据。假设解空间树共有n+1层(根结点为第0层，叶子结点为第n层)，第1层有m0个结点，每个结点有m1个子结点，则第2层有m0m1个结点，同理，第3层有m0m1m2个结点，以此类推，第n层有m0m1…mn-1个结点，则采用回溯法求所有解的算法的执行时间为T(n)=m0+m0m1+m0m1m2+…+m0m1m2…mn-1。这是一种最坏情况下的时间分析方法，在实际中可以通过剪支提高性能。为了使估算更精确，可以选取若干条不同的随机路径，分别对各随机路径估算结点总数，然后取这些结点总数的平均值。在通常情况下，回溯法的效率通常会高于穷举法。

5．2深度优先搜索
深度优先搜索是在访问一个顶点v之后尽可能地先对纵深方向进行搜索，在解空间中搜索时类似树的先根遍历方式。

5．2．1图的深度优先遍历

图的遍历是从图中某个起始点出发访问图中所有顶点并且每个顶点仅访问一次的过程，其顶点访问序列称为图的遍历序列。采用深度优先搜索方法遍历图称为图的深度优先遍历，得到的遍历序列称为深度优先遍历序列，其过程是从起始点v出发，以纵向方式一步一步沿着边访问各个顶点。例如，对于如图5．1(a)所示的连通图，采用如下邻接表存储： 


adj=［［1,3］,［0］,［3,4］,［0,2,4］,［2,3］］



从顶点v出发求深度优先遍历序列ans的算法如下： 


1def DFS1(adj,v):  				#深度优先遍历

2global visited,ans

3ans.append(v)                     #访问顶点v

4visited［v］=1

5for u in adj［v］:          #找到v的相邻点u

6if visited［u］==0:               #若顶点u尚未访问

7DFS1(adj,u)                 #从u出发继续搜索

8

9def DFS(adj,v):

10global visited,ans

11ans=［］ 							#存放一个DFS序列

12visited=［0］*len(adj)      #初始化所有元素为0

13DFS1(adj,v)

14return ans



上述算法求得一个深度优先遍历序列为{0，1，3，2，4}。需要注意的是，深度优先遍历特指图的一种遍历方式，而深度优先搜索是一种通用的搜索方式，前者是后者的一种应用，目前人们往往将两者等同为一个概念。

5．2．2深度优先遍历和回溯法的差别

深度优先遍历和回溯法都是基于深度优先搜索，但两者在处理方式上存在差异，下面通过一个示例进行说明。

【例51】对于如图5．1(a)所示的连通图，求从顶点0到顶点4的所有路径。

解在采用深度优先遍历求u到v的所有路径时是从顶点u出发以纵向方式进行顶点的搜索，用x存放一条路径，用ans存放所有的路径，如果当前访问的顶点u=v，将找到的一条路径x添加到ans中，同时从顶点u回退，以便找其他路径，否则找到u的所有相邻点w，若顶点w尚未访问，则从w出发继续搜索路径，当从u出发的所有路径搜索完毕，再从u回退。对应的算法如下： 


1import copy

2def dfs11(adj,u,v,x):					#深度优先搜索

3global visited,ans

4x.append(u)            #访问顶点u

5visited［u］=1

6if u==v:                #找到一条路径

7ans.append(copy.deepcopy(x))#将路径x添加到ans中

8visited［u］=0                    #置u可以重新访问

9x.pop()     				#路径回退

10return

11for w in adj［u］:         #找到u的相邻点w

12if visited［w］==0:               #若顶点w尚未访问

13dfs11(adj,w,v,x)             #从w出发继续搜索

14visited［u］=0                       #从u出发的所有路径找完后回退

15x.pop()        			#路径回退

16

17def dfs1(adj,u,v):					#求u到v的所有路径

18global visited,ans

19ans=［］

20visited=［0］*len(adj)      #初始化所有元素为0

21x=［］

22dfs11(adj,u,v,x)

23return ans



在调用上述dfs1(adj,0,4)时求出的两条路径是0→3→2→4和0→3→4。现在采用回溯法，对应的解空间如图5．1(b)所示，解向量x表示一条路径，首先将起始点u(初始u=0)添加到x中，再求xi(i≥1)，当u=v(v=4)时对应解空间的一个叶子结点，此时x中就是一条满足约束条件的路径，将其添加到ans中，否则从顶点u进行扩展，若相邻点w尚未访问，将w添加到x中，然后从w出发进行搜索，当从w出发的路径搜索完后再回退到顶点u，简单地说从u出发搜索再回到u，这就是回溯法的核心。对应的算法如下： 


1def dfs21(adj,u,v,x):				#回溯法

2global visited,ans

3if u==v:                          #找到一条路径

4ans.append(copy.deepcopy(x))     #将路径x添加到ans中

5else:

6for w in adj［u］:        #找到u的相邻点w

7if visited［w］==0:             #若顶点w尚未访问

8x.append(w)               #访问v,将v添加到ans中

9visited［w］=1

10dfs21(adj,w,v,x)            #从w出发继续搜索

11visited［w］=0              #从w回退到u

12x.pop()

13

14def dfs2(adj,u,v):                    #求u到v的所有路径





15global visited,ans

16ans=［］                          #存放所有路径

17visited=［0］*len(adj)      #初始化所有元素为0

18x=［］

19x.append(u)             #将起始点u添加到x中

20visited［u］=1

21dfs21(adj,u,v,x)

22return ans



在调用上述dfs2(adj,0,4)时求出的两条路径同样是0→3→2→4和0→3→4。从中看出，深度优先遍历主要考虑顶点u的前进和回退，不需要专门表示回退到哪个顶点，而回溯法主要考虑顶点u扩展的子结点以及从子结点的回退，需要专门处理出发点u和子结点w之间的扩展和回退关系。尽管都是采用深度优先搜索，但后者解决问题的思路更清晰，特别是对于复杂的问题求解要方便得多。

5．2．3实战——二叉树的所有路径(LeetCode257★)

1. 问题描述

扫一扫



视频讲解


给定一棵含n(1≤n≤100)个结点的二叉树的根结点 root，结点值在［-100，100］内，设计一个算法按任意顺序返回从根结点到叶子结点的所有路径。


图5．5一棵二叉树

例如，对于如图5．5所示的二叉树，返回结果是{"1>2>5"，"1>3"}。

2. 问题求解——深度优先遍历
采用深度优先遍历。从根结点root出发搜索到每个叶子结点时构成一条路径x，将其转换为字符串tmp后添加到ans中，由于是树结构，不会重复访问顶点，所以不必设置访问标记数组。对应的算法如下： 


1class Solution:

2def binaryTreePaths(self, root: Optional［TreeNode］) > List［str］:

3if root==None:return ［］

4self.ans=［］

5x=［］                      						#存放一条路径

6self.dfs(root,x)           					#求ans

7return self.ans

8

9def dfs(self,root,x):          					#深度优先遍历

10x.append(root.val)

11if root.left==None and root.right==None:    #找到一条路径

12tmp=str(x［0］)                      		#将路径转换为字符串

13for i in range(1,len(x)):

14tmp+=">"+str(x［i］)

15self.ans.append(tmp)

16else:

17if root.left!=None:

18self.dfs(root.left,x)

19if root.right!=None:

20self.dfs(root.right,x)

21x.pop()                    						#从结点root回退



上述程序的提交结果为通过，运行时间为40ms，消耗的空间为14．9MB。

3. 问题求解——回溯法
在采用回溯法时将给定的一棵树看成解空间，存放一条路径的x就是一个解向量。从根结点root出发搜索，当到达一个叶子结点时构成一条路径，将解向量x转换为字符串tmp后添加到ans中，否则从root扩展出左、右孩子结点，并从孩子结点回退到root。对应的算法如下： 


1class Solution:

2def binaryTreePaths(self, root: Optional［TreeNode］) > List［str］:

3if root==None:return ［］

4self.ans=［］

5x=［］                      						#存放一条路径

6x.append(root.val)

7self.dfs(root,x)           					#求ans

8return self.ans

9

10def dfs(self,root,x):          					#回溯算法

11if root.left==None and root.right==None:    #找到一条路径

12tmp=str(x［0］)                      		#将路径转换为字符串

13for i in range(1,len(x)):

14tmp+=">"+str(x［i］)

15self.ans.append(tmp)

16 else:

17if root.left!=None:

18x.append(root.left.val)

19self.dfs(root.left,x)

20x.pop()											#回溯

21if root.right!=None:

22x.append(root.right.val)

23self.dfs(root.right,x)

24x.pop()                 			#回溯



上述程序的提交结果为通过，运行时间为44ms，消耗的空间为14．9MB。

5．3基于子集树框架的问题求解
5．3．1子集树算法框架概述

通常求解问题的解空间分为子集树和排列树两种类型。当求解问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树，在子集树中每个结点的扩展方式是相同的，也就是说每个结点的子结点的个数相同。例如在整数数组a中求和为目标值target的所有解，每个元素a［i］只有选择和不选择两种方式，对应的解空间就是子集树。假设子集树的解空间的高度为n+1，每个非叶子结点有c个子结点，对应算法的时间复杂度为O(cn)。

设问题的解是一个n维向量(x1，x2，…，xn)，约束函数为constraint(i，j)，限界函数为bound(i，j)，解空间为子集树的递归回溯框架如下： 


x=［0］*MAXN									#x存放解向量，这里作为全局变量

def dfs(i):										#求解子集树的递归框架

if i>n:										#搜索到叶子结点,输出一个可行解

输出一个解

else:

forj in range(下界,上界+1):		#用j表示x［i］的所有可能候选值

x［i］=j									#产生一个可能的解分量

…										#其他操作

if constraint(i,j) and bound(i,j):

dfs(i+1)							#满足约束条件和限界函数,继续下一层

回溯x［i］

…



在采用上述算法框架时需要注意以下几点。

① 如果i从1开始调用上述递归框架，此时根结点为第1层，叶子结点为第n+1层。当然i也可以从0开始，这样根结点为第0层，叶子结点为第n层，所以需要将上述代码中的“if i>n”改为“if i>=n”。

② 在上述递归框架中通过for循环用j枚举xi的所有可能候选值，如果扩展路径只有两条，可以改为两次递归调用(例如求解0/1背包问题、子集和问题等都是如此)。

③ 这里递归框架只有i一个参数，在实际应用中可以根据具体情况设置多个参数。

5．3．2实战——子集(LeetCode78★★)

1. 问题描述
见3．3．5节，这里采用回溯法求解。


扫一扫



视频讲解


2. 问题求解1

本问题的解空间是典型的子集树，假设求集合a的所有子集(即幂集)，集合a中的每个元素只有两种选择，要么选取，要么不选取。设解向量为x，x［i］=1表示选取a［i］，x［i］=0表示不选取a［i］。用i遍历数组a，i从0开始(与解空间中根结点的层次为0相对应)，根结点为初始状态(i=0，x的元素均为0)，叶子结点为目标状态(i=n，x为一个可行解，即一个子集)。从状态(i，x)可以扩展出两个状态。

① 选择a［i］元素  下一个状态为(i+1，x［i］=1)。

② 不选择a［i］元素  下一个状态为(i+1，x［i］=0)。

这里i总是递增的，所以不会出现状态重复的情况。如图5．6所示为求{1，2，3}幂集的解空间，每个叶子结点对应一个子集，所有子集构成幂集。



图5．6求a={1，2，3}幂集的解空间(1)


对应的递归回溯算法如下： 


1def subset1(a):										#解法1：求a的幂集

2x=［0］*len(a)										#解向量

3dfs1(a,x,0)

4

5def dfs1(a,x,i):							#回溯算法

6if i>=len(a):	   				#到达一个叶子结点





7print("［",end='')								#输出一个子集

8for j in range(0,len(x)):

9if x［j］==1:print(a［j］,end=' ')

10print("］",end='  ')

11else:

12x［i］=1

13dfs1(a,x,i+1)									#选择a［i］

14x［i］=0

15dfs1(a,x,i+1)									#不选择a［i］



回到本问题，用双层列表类型的ans变量存放幂集，将解向量x改为直接存放一个子集，在解空间中搜索时，每次到达一个叶子结点得到一个子集x，将其深复制到ans中，否则对于第i层的某个结点A，左分支是选择nums［i］，将nums［i］添加到x中，当返回到A时将nums［i］从x中删除； 右分支是不选择nums［i］。对应的算法如下： 


1class Solution:

2def subsets(self, nums: List［int］) > List［List［int］］:

3self.ans,self.x=［］,［］

4self.dfs(nums,0)

5return self.ans

6

7def dfs(self,nums,i):      			#回溯算法

8if i==len(nums):                                    #到达一个叶子结点

9self.ans.append(copy.deepcopy(self.x))

10else:

11self.x.append(nums［i］)           #选择nums［i］, x中添加nums［i］

12self.dfs(nums,i+1)

13self.x.pop()                           #回溯，即删除前面添加的nums［i］

14self.dfs(nums,i+1)         	#不选择nums［i］,x中不添加nums［i］



上述程序提交时通过，执行用时为44ms，内存消耗为15MB。


扫一扫



视频讲解


3. 问题求解2

在前面求a的幂集的回溯算法中用解向量x间接存放一个子集(每个子集对应的x的长度相同，分量xi中的下标i既表示结点的层次，同时又用于访问ai)，现在将x改为直接存放a的一个子集。设解向量x={x0，…，xi，…，xm-1}(m为x的长度，0≤m≤n)，仍以a={1，2，3}为例，对应的解空间如图5．7所示，每个结点的状态为“i，j，x”，其中i为结点的层次，j表示xi的取值范围为a［j．．n-1］，x为解向量。

根结点的状态为“0，0，{}”，即表示x0的取值范围是a［0．．2］，每个取值对应一个分支，共3个分支。

① 当x0=a0=1时(i=0，j=0)，对应的子结点状态为“i+1，j+1，x∪{1}”，即“1，1，{1}”，这里i<3同时j=1没有超界(j=3时超界)，继续向下扩展。

② 当x0=a1=2时(i=0，j=1)，对应的子结点状态为“i+1，j+1，x∪{2}”，即“1，2，{2}”，这里i<3同时j=2没有超界，继续向下扩展。

③ 当x0=a2=3时(i=0，j=2)，对应的子结点状态为“i+1，j+1，x∪{3}”，即“1，3，{3}”，这里i<3，但j=3超界，不再向下扩展。



图5．7求a={1，2，3}幂集的解空间(2)


不同于解法1，这里解空间中每个结点的x都是一个子集，因此解空间中结点的个数相对较少，性能更高。对应的递归回溯算法如下： 


1def subsets2(a):							#解法2:求a的幂集

2x=［］		       				#解向量

3dfs2(a,x,0)

4

5def dfs2(a,x,i):	   				#回溯算法

6print(x,end='  ')									#输出一个子集

7for j in range(i,len(a)):

8x.append(a［j］) 				#向x中添加a［j］

9dfs2(a,x,j+1)

10x.pop()								#回溯，即删除前面添加的a［j］



回到本问题，同样用双层列表类型的ans变量存放幂集，将每次找到的解x深复制到ans中。对应的算法如下： 


1class Solution:

2def subsets(self, nums: List［int］) > List［List［int］］:

3self.ans,x=［］,［］

4self.dfs(nums,x,0)

5return self.ans

6

7def dfs(self,nums,x,i):							#回溯算法

8self.ans.append(copy.deepcopy(x))	#找到一个解





9for j in range(i,len(nums)):

10x.append(nums［j］)

11self.dfs(nums,x,j+1)

12x.pop()										#回溯，即删除前面添加的nums［j］



上述程序提交时通过，执行用时为40ms，内存消耗为14．8MB。

5．3．3实战——子集Ⅱ(LeetCode90★★)

1. 问题描述
给定一个含n个整数的数组nums(1≤n≤10，-10≤nums［i］≤10)，其中可能包含重复元素，请设计一个算法返回该数组的所有可能的子集(幂集)。解集不能包含重复的子集，在返回的解集中子集可以按任意顺序排列。例如，nums={1，2，2}，结果为{{}，{1}，{1，2}，{1，2，2}，{2}，{2，2}}。


扫一扫



视频讲解


2. 问题求解1

由于这里nums中包含重复元素，如果直接采用5．3．2节中的解法1会得到重复的子集，例如，nums［］={1，2，1}时，求解结果为{{1，2，1}，{1，2}，{1，1}，{1}，{2，1}，{2}，{1}，{}}，其中{1，2}和{2，1}重复，并且{1}出现两次。两个相同的{1}容易消除，但{1，2}和{2，1}如何消除呢？可以采用先将nums排序的方法，例如nums［］={1，1，2}，其结果为{{1，1，2}，{1，1}，{1，2}，{1}，{1，2}，{1}，{2}，{}}，这样重复的子集的顺序均相同，剩下的问题是消除顺序相同的重复子集。

采用5．3．2节中求a的幂集的解法1的思路，利用集合set实现去重(其元素为由x转换的元组)。对应的算法如下： 


1class Solution:

2def subsetsWithDup(self, nums: List［int］) > List［List［int］］:

3nums.sort()                                          #nums递增排序

4self.ans,self.x=set(),［］

5self.dfs(nums,0)

6return list(self.ans)

7

8def dfs(self,nums,i):                      		#回溯算法

9if i==len(nums):                        		#到达一个叶子结点

10self.ans.add(tuple(self.x))

11else:

12self.x.append(nums［i］)             	#选择nums［i］, x中添加nums［i］

13self.dfs(nums,i+1)

14self.x.pop()                         		#回溯

15self.dfs(nums,i+1)                 	#不选择nums［i］,x中不添加nums［i］



上述程序提交时通过，执行用时为44ms，内存消耗为16．3MB。

3. 问题求解2

扫一扫



视频讲解


采用5．3．2节中求a的幂集的解法2的思路，对于解空间中状态为“i，j，x”的结点，表示xi可能的取值范围是nums［j．．n-1］，如果j>i时nums［j］和nums［j-1］相同，则xi同时取值为nums［j］和nums［j-1］时会导致出现重复的子集，因此只要跳过这样的重复情况即可。对应的算法如下： 


1class Solution:

2def subsetsWithDup(self, nums: List［int］) > List［List［int］］:

3nums.sort()												#nums递增排序

4self.ans,x=［］,［］

5self.dfs(nums,x,0)

6return self.ans

7

8def dfs(self,nums,x,i):									#回溯算法

9self.ans.append(copy.deepcopy(x))

10for j in range(i,len(nums)):

11if j>i and nums［j］==nums［j-1］: continue

13x.append(nums［j］)

14self.dfs(nums,x,j+1)

15x.pop()



上述程序提交时通过，执行用时为36ms，内存消耗为15．2MB。

5．3．4实战——目标和(LeetCode494★★)

1. 问题描述

扫一扫



视频讲解


给定一个含n个整数的数组 nums(1≤n≤20，0≤nums［i］≤1000)和一个整数 target(-1000≤target≤1000)，在数组中的每个整数前添加 '+' 或 '-'，然后串联起来所有整数，可以构造一个表达式。例如，nums={2，1}，可以在2之前添加 '+'，在1之前添加'-'，然后串联起来得到表达式 "+2-1"。设计一个算法求可以通过上述方法构造的运算结果等于 target 的不同表达式的数目。

2. 问题求解
用ans表示满足要求的解的个数(初始为0)，设置解向量x=(x0，x1，…，xn-1)，xi表示nums［i］(0≤i≤n-1)前面添加的符号，xi只能在'+'和'-'符号中二选一，所以该问题的解空间为子集树。用expv表示当前运算结果(初始为0)。对于解空间中第i层的结点A，若xi选择'+'，则expv+=nums［i］，若xi选择'-'，则expv-=nums［i］，在回退到A时要恢复expv。当到达一个叶子结点时，如果expv=target，说明找到一个解，置ans++。

由于该问题只需要求最后的解个数，所以不必真正设计解向量x，仅设计expv即可。对应的算法如下： 


1class Solution:

2def findTargetSumWays(self, nums: List［int］, target: int) > int:

3self.ans=0

4self.dfs(nums,target,0,0)

5return self.ans

6

7def  dfs(self,nums,target,i,expv):			#回溯算法

8if i==len(nums):               				#到达一个叶子结点

9if expv==target:self.ans+=1        #找到一个解

10else:

11expv+=nums［i］                              #nums［i］前选择'+'

12self.dfs(nums,target,i+1,expv)





13expv-=nums［i］                                #回溯：恢复expv

14expv-=nums［i］                                #nums［i］前选择'-'

15self.dfs(nums,target,i+1,expv)

16expv+=nums［i］                                #回溯：恢复expv



说明： 上述程序提交时出现超时现象，但同样的思路采用C/C++或者Java编程提交时通过。

5．3．5子集和问题

1. 问题描述

扫一扫



视频讲解


给定n个不同的正整数集合a=(a0，a1，…，an-1)和一个正整数t，要求找出a的子集s，使该子集中所有元素的和为t。例如，当n=4时，a=(3，1，5，2)，t=8，则满足要求的子集s为(3，5)和(1，5，2)。

2. 问题求解
与求幂集问题一样，该问题的解空间是一棵子集树(因为每个整数要么选择，要么不选择)，并且是求满足约束函数的所有解。

1) 无剪支

设解向量x=(x0，x1，…，xn-1)，xi=1表示选择ai元素，xi=1表示不选择ai元素。在解空间中按深度优先方式搜索所有结点，并用cs累计当前结点之前已经选择的所有整数的和，一旦到达叶子结点(即i≥n)，表示a的所有元素处理完毕，如果相应的子集和为t(即约束函数cs=t成立)，则根据解向量x输出一个解。当解空间搜索完后便得到所有解。

例如a=(3，1，5，2)，t=8，其解空间如图5．8所示，图中结点上的数字表示cs，利用深度优先搜索得到两个解，解向量分别是(1，0，1，0)和(0，1，1，1)，对应图中两个带阴影的叶子结点，图中共31个结点，每个结点都要搜索。实际上，解空间是一棵高度为5的满二叉树，从根结点到每个叶子结点都有一条路径，每条路径是一个决策向量，满足约束函数的决策向量就是一个解向量。



图5．8求a=(3，1，5，2)、t=8时子集和的解空间


对应的递归回溯算法如下： 


1cnt=0													#累计解的个数

2sum=0                    #累计搜索的结点的个数





3def disp(a):										#输出一个解

4global cnt,x

5cnt+=1;print("  第%d个解,"%(cnt),end=")

6print("选取的数为: ",end=")

7for i in range(0,len(x)):

8if x［i］==1:print(a［i］,end=")

9print()

10

11def dfs1(a,t,cs,i):						#回溯算法

12global sum,x

13sum+=1

14if i>=len(a):									#到达一个叶子结点

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

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

17x［i］=1									#选取整数a［i］

18dfs1(a,t,cs+a［i］,i+1)

19x［i］=0										#不选取整数a［i］

20dfs1(a,t,cs,i+1)

21

22def subs1(a,t):										#求解子集和问题

23global x

24x=［0］*len(a)				#解向量

25print("求解结果")

26dfs1(a,t,0,0)   				#i从0开始

27print("sum=",sum)



当a=［3，1，5，2］、t=8时调用subs1(a，t)算法的求解结果如下： 


求解结果

第1个解,选取的数为: 3 5

第2个解,选取的数为: 1 5 2

sum=31



【算法分析】上述算法的解空间是一棵高度为n+1的满二叉树，共有2n+1-1个结点，递归调用2n+1-1次，每找到一个满足条件的解就调用disp()输出，而执行disp()的时间为O(n)，所以subs()算法的最坏时间复杂度为O(n×2n)。

2) 左剪支

由于a中的所有元素是正整数，每次选择一个元素时cs都会变大，当cs>t时沿着该路径继续找下去一定不可能得到解。利用这个特点减少搜索的结点的个数。当搜索到第i(0≤i<n)层的某个结点时，cs表示当前已经选取的整数的和(其中不包含a［i］)，判断选择a［i］是否合适： 

① 若cs+a［i］>t，表示选择a［i］后子集和超过t，不必继续沿着该路径求解，终止该路径的搜索，也就是左剪支。

② 若cs+a［i］≤t，沿着该路径继续下去可能会找到解，不能终止。

简单地说，仅扩展满足cs+a［i］≤t的左孩子结点。

例如a=(3，1，5，2)，t=8，其搜索空间如图5．9所示，图中共29个结点，除去两个被剪支的结点(用虚框结点表示)，剩下27个结点，也就是说递归调用27次，性能得到了提高。



图5．9求a=(3，1，5，2)、t=8时子集和的搜索空间(1)


对应的递归回溯算法如下： 


#前面部分与无剪支算法的1~10行相同

1def dfs2(a,t,cs,i):						#回溯算法

2global sum,x

3sum+=1

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

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

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

7if cs+a［i］<=t:								#左孩子结点剪支

8x［i］=1								#选取整数a［i］

9dfs2(a,t,cs+a［i］,i+1)

10x［i］=0										#不选取整数a［i］

11dfs2(a,t,cs,i+1)

12

13def subs2(a,t):										#求解子集和问题

14global x

15x=［0］*len(a)				#解向量

16print("求解结果")

17dfs2(a,t,0,0)   				#i从0开始

18rint("sum=",sum)



当a=［3，1，5，2］、t=8时调用subs2(a，t)算法的求解结果如下： 


求解结果

第1个解,选取的数为: 3 5

第2个解,选取的数为: 1 5 2

sum= 27



3) 右剪支

左剪支仅考虑是否扩展左孩子结点，可以进一步考虑是否扩展右孩子结点。当搜索到第i(0≤i<n)层的某个结点时，用rs表示余下的整数的和，即rs=a［i］+…+a［n-1］(其中包含a［i］)，因为右孩子结点对应不选择整数a［i］的情况，如果不选择a［i］，此时剩余的所有整数的和为rs=rs-a［i］(a［i+1］+…+a［n-1］)，若cs+rs<t成立，说明即使选择所有剩余整数，其和也不可能达到t，所以右剪支就是仅扩展满足cs+rs≥t的右孩子结点，注意在左、右分支处理完后需要恢复rs，即执行rs=+a［i］。

例如a=(3，1，5，2)，t=8，其搜索过程如图5．10所示，图中共17个结点，除去7个被剪支的结点(用虚框结点表示)，剩下10个结点，也就是说递归调用10次，性能得到更有效的提高。



图5．10求a=(3，1，5，2)、t=8时子集和的搜索空间(2)


说明： 本例给定a中的所有整数为正整数，如果a中有负整数，这样的左、右剪支是不成立的，因此无法剪支，算法退化为基本深度优先遍历。

对应的递归回溯算法如下： 


#前面部分与无剪支算法的1~10行相同

1def dfs3(a,t,cs,rs,i):								#回溯算法

2global sum,x

3sum+=1

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

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

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

7rs-=a［i］										#求剩余的整数的和

8if cs+a［i］<=t:								#左孩子结点剪支

9x［i］=1								#选取整数a［i］

10dfs3(a,t,cs+a［i］,rs,i+1)

11if cs+rs>=t:					#右孩子结点剪支

12x［i］=0					#不选取整数a［i］

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

14rs+=a［i］										#恢复剩余整数和(回溯)

15

16def subs3(a,t):										#求解子集和问题

17global x

18x=［0］*len(a)				#解向量

19rs=0

20for e in a:rs+=e

21print("求解结果")

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

23print("sum=",sum)



当a=［3，1，5，2］、t=8时调用subs3(a，t)算法的求解结果如下： 


求解结果

第1个解,选取的数为: 3 5 

第2个解,选取的数为: 1 5 2 

sum=10



【算法分析】尽管通过剪支提高了算法的性能，但究竟剪去多少结点与具体的实例数据相关，所以上述算法在最坏情况下的时间复杂度仍然为O(n×2n)。从上述实例可以看出剪支在回溯法算法中的重要性。

5．3．6简单装载问题

1. 问题描述

扫一扫



视频讲解


有n个集装箱要装上一艘载重量为t的轮船，其中集装箱i(0≤i≤n-1)的重量为wi。不考虑集装箱的体积限制，现要选出重量和小于或等于t并且尽可能重的若干集装箱装上轮船。例如，n=5，t=10，w={5，2，6，4，3}时，其最佳装载方案有两种，即(1，1，0，0，1)和(0，0，1，1，0)，对应的集装箱重量和达到最大值t。

2. 问题求解
与求幂集问题一样，该问题的解空间树是一棵子集树(因为每个集装箱要么选择，要么不选择)，但要求求最佳装载方案，属于求最优解类型。设当前解向量x=(x0，x1，…，xn-1)，xi=1表示选择集装箱i，xi=1表示不选择集装箱i，最优解向量用bestx表示，最优重量和用bestw表示(初始为0)，为了简洁，将bestx和bestw设计为全局变量。

当搜索到第i(0≤i<n)层的某个结点时，cw表示当前选择的集装箱重量和(其中不包含w［i］)，rw表示余下集装箱的重量和，即rw=w［i］+…+w［n-1］(其中包含w［i］)，此时处理集装箱i，先从rw中减去w［i］，即置rw-=w［i］，采用的剪支函数如下。

① 左剪支： 判断选择集装箱i是否合适。检查当前集装箱被选中后总重量是否超过t，若是则剪支，即仅扩展满足cw+w［i］≤t的左孩子结点。

② 右剪支： 判断不选择集装箱i是否合适。如果不选择集装箱i，此时剩余的所有整数的和为rw，若cw+rw≤bestw成立(bestw是当前找到的最优解的重量和)，说明即使选择所有剩余集装箱，其重量和也不可能达到bestw，所以仅扩展满足cw+rw>bestw的右孩子结点。

说明： 由于深度优先搜索是纵向搜索的，可以较快地找到一个解，以此作为bestw，再对某个搜索结点(cw，rw)做cw+rw>bestw的右剪支通常比广度优先搜索的性能更好。

当第i层的这个结点扩展完成后需要恢复rs，即置rs+=a［i］(回溯)。如果搜索到某个叶子结点(即i≥n)，得到一个可行解，其选择的集装箱的重量和为cw(由于是左剪支，cw一定小于或等于t)，若cw>bestw，说明找到一个满足条件的更优解，置bestw=cw，bestx=x。全部搜索完毕，bestx就是最优解向量。


扫一扫



程序代码


说明：看完整的源程序请扫描右侧二维码。

【算法分析】在该算法中解空间树有2n+1-1个结点，每找到一个更优解时需要将x复制到bestx(执行时间为O(n))，所以最坏情况下算法的时间复杂度为O(n×2n)。在前面的实例中，n=5，解空间树中结点的个数应为63，采用剪支后结点的个数为16(不计虚框中被剪支的结点)，如图5．11所示。



图5．11装载实例的搜索空间



扫一扫



视频讲解


5．3．70/1背包问题

1. 问题描述
有n个编号为0~n-1的物品，重量为w={w0，w1，…，wn-1}，价值为v={v0，v1，…，vn-1}，给定一个容量为W的背包。从这些物品中选取全部或者部分物品装入该背包中，每个物品要么选中，要么不选中，即物品不能被分割，找到选中物品不仅能够放到背包中而且价值最大的方案，并对表5．1所示的4个物品求出W=6时的一个最优解。


表5．14个物品的信息



物 品 编 号重量价值


054

134

223

311


2. 问题求解
该问题的解空间树是一棵子集树(因为每个物品要么选择，要么不选择)，要求求价值最大的装入方案，属于求最优解类型。

1) 存储结构设计

每个物品包含编号、重量和价值，为此采用结构体数组存放所有物品，因为后面涉及按单位重量价值递减排序，所以设计物品结构体类型如下： 


1class Goods:							#物品类

2def __init__(self,x,y,z):

3self.no=x							#物品的编号

4self.w=y											#物品的重量

5self.v=z											#物品的价值

6def __lt__(self,other):	#用于按v/w递减排序

7return 1.0*self.v/self.w>=1.0*other.v/other.w



例如，表5．1中的4个物品用向量g存放： 


g=［Goods(0,5,4),Goods(1,3,4),Goods(2,2,3),Goods(3,1,1)］



设当前解向量x=(x0，x1，…，xn-1)，xi=1表示选择物品i，xi=1表示不选择物品i，最优解向量用bestx表示，最大价值用bestv表示(初始为0)，为了简洁，将n、W、bestx和bestv均设计为全局变量。

2) 左剪支

由于所有物品的重量为正数，采用左剪支与子集和问题类似。当搜索到第i(0≤i<n)层的某个结点时，cw表示当前选择的物品的重量和(其中不包含w［i］)。检查当前物品被选中后总重量是否超过W，若超过则剪支，即仅扩展满足cw+w［i］≤W的左孩子结点。

3) 右剪支

这里右剪支相对复杂一些，题目求的是价值最大的装入方案，显然优先选择单位重量价值大的物品，为此将g中的所有物品按单位重量价值递减排序，例如表5．1中的物品排序后的结果如表5．2所示，序号i发生了改变，后面改为按i而不是按物品编号no的顺序依次搜索。


表5．24个物品按v/w递减排序后的结果



序号i物品编号no重量w价值vv/w


02231．5

11341．3

23111

30540．8


先看这样的问题，对于第i层的某个结点A，cw表示当前选择的物品的重量和(其中不包含w［i］)，cv表示当前选择的物品的价值和(其中不包含v［i］)，那么继续搜索下去能够得到的最大价值是多少？由于所有物品已按单位重量价值递减排序，显然在背包容量允许的前提下应该依次连续地选择物品i、物品i+1、……，直到物品k装不进背包，假设再将物品k的一部分装进背包，直到背包装满，此时一定会得到最大价值。从中看出，从物品i开始选择的物品的价值和的最大值为r(i)： 
r(i)=∑k-1j=ivj+rw-∑k-1j=iwj(vk/wk)
也就是说，从结点A出发的所有路径中最大价值bound(cw,cv,i)=cv+r(i)，如图5．12所示。对应的求上界函数值的算法如下： 


1def bound(cw,cv,i):									#计算第i层结点的上界函数值

2global g,W,n

3rw=W-cw											#背包的剩余容量

4b=cv													#表示物品价值的上界值

5j=i

6while j<n and g［j］.w<=rw:

7rw-=g［j］.w										#选择物品j

8b+=g［j］.v										#累计价值

9j+=1

10if j<n:												#最后物品k=j+1，只能部分装入

11b+=1.0*g［j］.v/g［j］.w*rw

12return b





图5．12bound(cw,cv,i)


再回过来讨论右剪支，右剪支是判断不选择物品i时是否能够找到更优解。如果不选择物品i，按上述讨论可知在背包容量允许的前提下依次选择物品i+1、物品i+2、……，可以得到最大价值，并且从物品i+1开始选择的物品的价值和的最大值为r(i+1)。如果之前已经求出一个最优解bestv，当cv+r(i+1)≤bestv时说明若不选择物品i，后面无论如何也找不到更优解。所以当搜索到第i层的某个结点时，对应的右剪支就是仅扩展满足bound(cw,cv,i+1)>bestv的右孩子结点。

例如，对于根结点，cw=0，cv=0，若不选择物品0(对应根结点的右孩子结点)，剩余背包容量为rw=W=6，b=cv=0，考虑物品1，g［1］．w<rw，可以装入，b=b+g［1］．v=4，rw=rw-g［1］．w=3； 考虑物品2，g［2］．w<rw，可以装入，b=b+g［2］．v=5，rw=rw-g［2］．w=2； 考虑物品3，g［3］．w>rw，只能部分装入，b=b+rw×(g［3］．v/g［3］．w)=6．6。

右剪支是求出第i层的结点，b=bound(cw,cv,i)，若b≤bestv，则停止右分支的搜索，也就是说仅扩展满足b>bestv的右孩子结点。

对于表5．1所示的实例，n=4，按v/w递减排序后为表5．2，初始时bestv=0，求解过程如图5．13所示，图中两个数字的结点为(cw,cv)，只有右结点标记为(cw,cv,ub)，其中虚结点为被剪支的结点，带阴影的结点是最优解结点，其求解结果与回溯法的完全相同，图中结点的数字为(cw，cv)，求解步骤如下。

① i=0，根结点为(0，0)，cw=0，cv=0，cw+w［0］≤W成立，扩展左孩子结点，cw=cw+w［0］=2，cv=cv+v［0］=3，对应结点(2，3)。

② i=1，当前结点为(2，3)，cw+w［1］(5)≤W成立，扩展左孩子结点，cw=cw+w［1］=5，cv=cv+v［1］=7，对应结点(5，7)。

③ i=2，当前结点为(5，7)，cw+w［2］(6)≤W成立，扩展左孩子结点，cw=cw+w［2］=6，cv=cv+v［1］=7，对应结点(6，8)。

④ i=3，当前结点为(6，8)，cw+w［2］(6)≤W不成立，不扩展左孩子结点。

⑤ i=3，当前结点为(6，8)，不选择物品3时计算出b=cv+0=8，而b>bestv(0)成立，扩展右孩子结点。

⑥ i=4，当前结点为(6，8)，由于i≥n成立，它是一个叶子结点，对应一个解bestv=8。

⑦ 回溯到i=2层次，当前结点为(5，7)，不选择物品2时计算出b=7．8，b>bestv不成立，不扩展右孩子结点。

⑧ 回溯到i=1层次，当前结点为(2，3)，不选择物品1时计算出b=6．4，b>bestv不成立，不扩展右孩子结点。

⑨ 回溯到i=0层次，当前结点为(0，0)，不选择物品0时计算出b=6．6，b>bestv不成立，不扩展右孩子结点。



图5．130/1背包问题实例的搜索空间


解空间搜索完，最优解为bestv=8，装入方案是选择编号为2、1、3的3个物品。从中看出，如果不剪支搜索的结点的个数为31，剪支后搜索的结点的个数为5。

对应的递归回溯算法如下： 


1def dfs(cw,cv,i):							#回溯算法

2global g,W,n,x,bestx,bestv,sum

3sum+=1

4if i>=n:												#到达一个叶子结点

5if cw<=W and cv>bestv:					#找到一个满足条件的更优解,保存它

6bestv=cv

7bestx=copy.deepcopy(x)

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

9if cw+g［i］.w<=W:					#左剪支

10x［i］=1									#选取物品i

11dfs(cw+g［i］.w,cv+g［i］.v,i+1)

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

13if b>bestv:			     	#右剪支

14x［i］=0								#不选取物品i

15dfs(cw,cv,i+1)

16

17def knap(g,W):							#求0/1背包问题

18global n,x,bestx,bestv,sum

19n=len(g)               	#物品的个数

20x=［0］*n                	#解向量

21bestx=［0］*n					 	#存放最优解向量

22bestv=0						#存放最大价值,初始为0

23sum=0												#累计搜索的结点的个数 

24print("求解结果")

25g.sort()

26dfs(0,0,0)				        #i从0开始

27for i in range(0,n):





28if bestx［i］==1:print("  选取第%d个物品"%(g［i］.no))

29print("  总重量=%d,总价值=%d"%(W,bestv))

30print("sum=",sum)



对于表5．1中的4个物品，W=6时调用上述knap()算法的求解结果如下： 


求解结果

选取第2个物品

选取第1个物品

选取第3个物品

总重量=6,总价值=8

sum=5



【算法分析】上述算法在不考虑剪支时解空间树中有2n+1-1个结点，求上界函数值和保存最优解的时间为O(n)，所以最坏情况下算法的时间复杂度为O(n×2n)。

5．3．8完全背包问题

1. 问题描述

扫一扫



视频讲解


有n种重量和价值分别为wi、vi(0≤i<n)的物品，从这些物品中挑选总重量不超过W的物品，每种物品可以挑选任意多件，求挑选物品的最大价值。该问题称为完全背包问题。

2. 问题求解
与0/1背包问题不同，在完全背包问题中物品i指的是第i种物品，每种物品可以取任意多件。对于解空间中第i层的结点，用cw、cv表示选择物品的总重量和总价值，这样处理物品i的方式如下。

① 不选择物品i。

② 当cw+w［i］≤W时，选择一件物品i，下一步继续选择物品i。

③ 当cw+w［i］≤W时，选择一件物品i，下一步开始选择物品i+1。

例如，n=2，W=2，w=(1，2)，v=(2，5)，对应的搜索空间如图5．14所示，结点对应的状态是“(cw，cv，i)”，每个分支结点的3个分支分别对应上述3种处理方式。所有阴影结点是叶子结点，其中深阴影结点是最优解结点，虚框结点为被剪支的结点。求出该问题的最大价值为5。

仅求最大价值的回溯算法如下： 


1def dfs(cw,cv,i):						#回溯算法

2global w,v,n,W,bestv

3if i>=n:

4if cw<=W and cv>bestv:           #找到一个更优解

5bestv=cv

6else:

7dfs(cw,cv,i+1)          #不选择物品i

8if cw+w［i］<=W:

9dfs(cw+w［i］,cv+v［i］,i)  #剪支:选择物品i,然后继续选择物品i





10if cw+w［i］<=W:

11dfs(cw+w［i］,cv+v［i］,i+1)#剪支:选择物品i,然后选择下一件

12

13def compknap(w,v,n,W):							#求解完全背包问题

14global bestv

15bestv=0            		#存放最大价值,初始为0

16dfs(0,0,0)

17print("最大价值=",bestv)





图5．14完全背包问题实例的搜索空间


5．3．9实战——皇后Ⅱ(LeetCode52★★★)

1. 问题描述

扫一扫



视频讲解


在n×n(1≤n≤9)的方格棋盘上放置n个皇后，每个皇后不同行、不同列、不同对角线(否则称为有冲突)。如图5．15所示为6皇后问题的一个解。设计一个算法求n个皇后的解的个数，例如n=6时6皇后问题有4个解，因此返回结果为4。



图5．156皇后问题的

一个解

2. 问题求解
本问题的解空间是一棵子集树(每个皇后在1~n列中找到一个适合的列号，即n选一)，并且要求求所有解。采用整数数组q［N］存放n皇后问题的求解结果，因为每行只能放一个皇后，q［i］(1≤i≤n)的值表示第i个皇后所在的列号，即第i个皇后放在(i，q［i］)的位置上。对于图5．15所示的解，q［1．．6］={2，4，6，1，3，5}(为了简便，不使用q［0］元素)。

若在(i，j)位置上放第i个皇后，是否与已放好的i-1个皇后(k，q［k］)(1≤k≤i-1)有冲突？显然它们是不同行的(因为皇后的行号i总是递增的)，所以不必考虑行冲突，对是否存在列冲突和对角线冲突的判断如下。

① 如果(i，j)位置与前面的某个皇后k(1≤k≤i-1)同列，则有q［k］==j成立。

② 如果(i，j)位置与前面的某个皇后同对角线，如图5．16所示，则恰好构成一个等腰直角三角形，即有|q［k］-j|==|i-k|成立。

归纳起来，只要(i，j)位置满足以下条件，则存在冲突(有冲突时说明第i个皇后不能放在第i行的第j列)，否则不存在冲突： 


(q［k］==j) || (abs(q［k］-j)==abs(i-k))1≤k≤i-1



现在采用递归回溯框架求解。设f(i，n)是在1~i-1行上已经放好了i-1个皇后，用于在i~n行放置剩下的n-i+1个皇后，为大问题，f(i+1，n)表示在1~i行上已经放好了i个皇后，用于在i+1~n行放置n-i个皇后，为小问题，则求解皇后问题的所有解的递归模型如下： 

f(i，n)≡n个皇后放置完毕，输出一个解若i>n

f(i，n)≡在第i行找到一个合适的位置(i，j)放置一个皇后； f(i+1，n)其他



图5．16两个皇后构成对角线的情况


对应的算法如下： 


1MAXN=20               		#最多皇后个数

2q=［0］*MAXN             		#q［i］存放第i个皇后的列号

3class Solution:

4def totalNQueens(self, n: int) > int:

5self.cnt=0                 #累计解的个数

6self.dfs(1,n)

7return self.cnt

8

9def place(self,i,j):            #测试(i,j)位置能否放置皇后

10if i==1: return True     #第一个皇后总是可以放置

11k=1

12while k<i:                 #k=1~i-1是已放置了皇后的行

13if q［k］==j or (abs(q［k］-j)==abs(i-k)):

14return False

15k+=1

16return True

17

18def dfs(self,i,n):               #回溯算法

19if i>n:                    	#所有皇后放置结束

20self.cnt+=1

21else:

22for j in range(1,n+1):          #在第i行上试探每个列j





23if self.place(i,j):            #在第i行上找到一个合适位置(i,j)

24q［i］=j

25self.dfs(i+1,n)



上述程序提交时通过，执行用时为72ms，内存消耗为15MB。

【算法分析】在该算法中每个皇后都要试探n列，共n个皇后，其解空间是一棵子集树，每个结点可能有n棵子树，考虑每个皇后试探一个合适位置的时间为O(n)，所以算法的最坏时间复杂度为O(n×nn)。

5．3．10任务分配问题

1. 问题描述

扫一扫



视频讲解


有n(n≥1)个任务需要分配给n个人执行，每个任务只能分配给一个人，每个人只能执行一个任务，第i个人执行第j个任务的成本是c［i］［j］(0≤i，j≤n-1)，求出总成本最小的一种分配方案。如表5．3所示为4个人员、4个任务的信息。


表5．34个人员、4个任务的信息



人员任务0任务1任务2任务3


09278

16437

25818

37694


2. 问题求解
n个人和n个任务的编号均用0~n-1表示。所谓一种分配方案，就是由第i个人执行第j个任务，也就是说每个人从n个任务中选择一个任务，即n选一，所以本问题的解空间树可以看成一棵子集树，并且要求求总成本最小的解(最优解是最小值)，属于求最优解类型。

设计解向量x=(x0，x1，…，xn-1)，这里以人为主，即人找任务(也可以以任务为主，即任务找人)，也就是第i个人执行第xi个任务(0≤xi≤n-1)。bestx表示最优解向量，bestc表示最优解的成本(初始值为∞)，x表示当前解向量，cost表示当前解的总成本(初始为0)，另外设计一个used数组，其中used［j］表示任务j是否已经分配(初始时所有元素均为False)，为了简单，将这些变量均设计为全局变量。

在解空间中根结点的层次i为0，当搜索到第i层的每个结点时，表示为第i个人分配一个没有分配的任务，即选择满足used［j］=0(0≤j≤n-1)的任务j。对应的递归回溯算法如下： 


1import copy

2INF=0x3f3f3f3f           #表示∞

3def dfs1(cost,i):									#回溯算法

4global c,n,x,bestx,bestc,used,sum

5sum+=1

6if i>=n:			       	#到达一个叶子结点

7if cost<bestc:		   	#通过比较求最优解





8bestc=cost; bestx=copy.deepcopy(x)

9else:

10for j in range(0,n):						#为人员i试探任务j:0到n-1

11if used［j］:continue					#跳过已经分配的任务j

12used［j］=True

13x［i］=j					 	#任务j分配给人员i

14cost+=c［i］［j］

15dfs1(cost,i+1)					#为人员i+1分配任务

16used［j］=False							#回溯

17x［i］=-1

18cost-=c［i］［j］

19

20def allocate1(c,n):				#求解任务分配问题

21global x,bestx,bestc,used,sum

22x=［0］*n

23bestx=［0］*n

24bestc=INF           	#初始化为∞

25used=［False］*n

26sum=0

27dfs1(0,0)										#从人员0开始

28print("求解结果")

29for k in range(0,n):

30print("人员%d分配任务%d"%(k,bestx［k］))

31print("总成本=",bestc)

32print("sum=",sum)



对于表5．3，调用上述allocate1算法的执行结果如下： 


求解结果

人员0分配任务1

人员1分配任务0

人员2分配任务2

人员3分配任务3

总成本=13

sum=65



【算法分析】算法的解空间是一棵n叉树(子集树)，所以最坏的时间复杂度为O(n×nn)。例如，在上述实例中n=4，经测试搜索的结点的个数为65。

现在考虑采用剪支提高性能，该问题是求最小值，所以设计下界函数。当搜索到第i层的某个结点时，前面人员0~人员i-1已经分配好了各自的任务，已经累



图5．17为人员i安排任务j的情况

计的成本为cost，现在要为人员i分配任务，如果为其分配任务j，即置x［i］=j，cost+=c［i］［j］，此时部分解向量为P=(x0，x1，…，xi)。那么沿着该路径走下去的最小成本是多少呢？后面人员i+1~n-1尚未分配任务，如果为每个人员分配一个尚未分配的最小成本的任务(其总成本为minsum)，则一定能构成该路径的总成本下界。minsum的计算公式如下： 
minsum=∑n-1i1=i+1minj1P{ci1,j1}
总成本下界b=cost+minsum，如图5．17所示。显然如果b≥bestc(bestc是当前已经求出的一个最优成本)，说明x［i］=j这条路径走下去一定不能找到更优解，所以停止该分支的搜索。这里的剪支就是仅扩展b<bestc的孩子结点。


求一个结点的总成本下界的算法如下： 


1def bound(cost,i):								#求下界算法

2global c,n,used

3minsum=0

4for i1 in range(i,n):							#求c［i..n-1］行中未分配的最小成本和

5minc=INF									#置为∞

6for j1 in range(0,n):

7if not used［j1］ and c［i1］［j1］<minc:minc=c［i1］［j1］

8minsum+=minc

9return cost+minsum



带剪支的递归回溯算法如下： 


1def dfs2(cost,i):									#回溯算法

2global c,n,x,bestx,bestc,used,sum

3sum+=1

4if i>=n:			       	#到达一个叶子结点

5if cost<bestc:		   	#通过比较求最优解

6bestc=cost;bestx=copy.deepcopy(x)

7else:

8for j in range(0,n):					#为人员i试探任务j:0到n-1

9if used［j］:continue				#跳过已经分配的任务j

10used［j］=True

11x［i］=j					 #将任务j分配给人员i

12cost+=c［i］［j］

13if bound(cost,i+1)<bestc:		#剪支(考虑c［i+1..n-1］行中的最小成本)

14dfs2(cost,i+1)			#为人员i+1分配任务

15used［j］=False						#回退

16x［i］=-1

17cost-=c［i］［j］

18

19def allocate2(c,n):				#求解任务分配问题

20global x,bestx,bestc,used,sum

21x=［0］*n

22bestx=［0］*n

23bestc=INF                      #初始化为∞

24used=［False］*n

25sum=0

26dfs2(0,0)										#从人员0开始

27print("求解结果")

28for k in range(0,n):

29print("人员%d分配任务%d"%(k,bestx［k］))

30print("总成本=",bestc)

31print("sum=",sum)



对于表5．3，调用上述allocate2算法的执行结果如下： 


求解结果

人员0分配任务1





人员1分配任务0

人员2分配任务2

人员3分配任务3

总成本=13

sum=9



从中看出，采用剪支后搜索的结点的个数为9，算法的时间性能得到明显提高。

【算法分析】算法的解空间是一棵n叉树(子集树)，剪支的时间为O(n2)，所以最坏的时间复杂度为O(n2×nn)。

5．3．11*实战——完成所有工作的最短时间
(LeetCode1723★★★)

1. 问题描述

扫一扫



视频讲解


给定一个整数数组 jobs，其中jobs［i］是完成第i项工作要花费的时间(1≤jobs．length≤12，1≤jobs［i］≤107)。将这些工作分配给 k(1≤k≤jobs．length)位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人，每个工人至少完成一项工作。工人的工作时间是完成分配给他们的所有工作所花费时间的总和。设计一套最佳的工作分配方案，使工人的最大工作时间得以最小化，返回分配方案中尽可能最小的最大工作时间。例如，jobs={1，2，4，7，8}，k=2，结果为11，对应的一种分配方案是1号工人分配时间为1、2、8的任务(工作时间为1+2+8=11)，2号工人分配时间为4、7的任务(工作时间为4+7=11)，最大工作时间是11。

2. 问题求解1
用times［0．．k-1］表示所有工人分配工作的总时间(初始时所有元素均为0)，其中times［j］表示工人j的总时间，用ans存放最优解(初始为∞)，按工作序号i从0到n-1遍历，解空间中根结点对应的i=0，ct表示当前的总时间，采用基于k选一的子集树框架求解。显然到达一个叶子结点后，ct=max0≤j≤k-1{times［j］}，ans=min{ct}。第i层的结点用于为工作i寻找工人j，ct即为完成0~i-1共 i个任务的时间。例如，jobs={1，2，4}，k=2的搜索空间如图5．18所示，图中结点为(times［0］，times［1］)，对应的最优解ans=4。



图5．18搜索空间


从中看出，解空间是一棵高度为n+1的满k叉树，这样搜索会超时,可以采用如下剪支方法提高性能。

剪支1： 从图5．18看出，k=2时左、右子树是对称的，当k>2时存在更多的重复子树，同时题目中规定每个工人至少分配一个工作，所以当给某个工人j分配任务i时，若他是初次分配(times［j］=0)，并且前面已有工人没有分配任务，则不必继续搜索下去，这样就剪去了(0，1)的分支。

剪支2： 采用常规的限界函数剪支，若已经求出一个解ans，如果将任务i分配给工人j，完成0~i任务的时间和curtime=max(ct，times［j］)，若curtime>ans，则不必继续搜索下去。

由于采用了剪支2，ct会越来越小，那么满足ct≤ans的最后一个ct就是ans。前面的示例采用剪支后的搜索空间如图5．19所示，从中看出几乎剪去了一半的结点。



图5．19剪支后的搜索空间(1)


对应的算法如下： 


1class Solution:

2def minimumTimeRequired(self,_jobs:List［int］,_k:int)>int:

3self.ans=0x3f3f3f3f                    #存放最优解，初始为∞

4self.times=［0］*_k

5self.jobs=_jobs

6self.k=_k

7self.dfs(0,0)

8return self.ans

9

10def dfs(self,ct,i):                    		#回溯算法

11if i==len(self.jobs):                  	#到达一个叶子结点

12self.ans=ct                           	#求得一个解

13else:

14flag=True

15for j in range(0,self.k):

16if self.times［j］==0:

17if not flag:return             #剪支1

18flag=False

19self.times［j］+=self.jobs［i］     #将工作i分配给工人j

20curtime=max(ct,self.times［j］) 

21if curtime<=self.ans:					#剪支2

22self.dfs(curtime,i+1)

23self.times［j］-=self.jobs［i］        #回溯





图5．20剪支后的搜索空间（2）

上述程序提交时通过，执行用时为6536ms，内存消耗为14．9MB。

3. 问题求解2
当然也可以采用这样的分配方式，即优先分配给空闲的工人，之后再给已经分配工作的工人分配工作(保证每个工人至少分配一个工作)。用cnt累计已经分配工作的人数。对于第i层的结点，当cnt<k时，说明工人cnt一定是空闲工人，优先给他分配工作i并回溯，然后试探为0到cnt-1的工人分配工作i再回溯。前面的示例采用该方法的搜索空间如图5．20所示，图中结点为(times［0］，times［1］： cnt)，从中看出工作0只会分配给工人0，从而剪去一半的结点。


对应的算法如下： 


1class Solution:

2def minimumTimeRequired(self,_jobs:List［int］,_k:int)>int:

3self.ans=0x3f3f3f3f                    #存放最优解，初始为∞

4self.times=［0］*_k

5self.jobs=_jobs

6self.k=_k

7self.dfs(0,0,0)

8return self.ans

9

10def dfs(self,cnt,ct,i):                    	#回溯算法

11if i==len(self.jobs):                  	#到达一个叶子结点

12self.ans=ct                            	#求得一个解

13else:

14if cnt<self.k:                                             #剪支1:优先分配给空闲工人

15self.times［cnt］=self.jobs［i］

16self.dfs(cnt+1,max(self.times［cnt］,ct),i+1)

17self.times［cnt］=0                                #回溯

18for j in range(0,cnt):         		#给已有工作的工人分配工作

19self.times［j］+=self.jobs［i］

20curtime=max(ct,self.times［j］) 

21if curtime<=self.ans:                         #剪支2

22self.dfs(cnt,curtime,i+1)                #cnt不变

23self.times［j］-=self.jobs［i］                   #回溯



上述程序提交时通过，执行用时为1ms，内存消耗为35．8MB。

说明： 本题等同于将n个正整数分为k份，使得每份的整数和最接近，求其中最大的整数和。


扫一扫



视频讲解


5．3．12图的m着色

1. 问题描述
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中每条边的两个顶点着不同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。

2. 问题求解
对于含n个顶点的无向连通图G，顶点的编号是0~n-1，采用邻接表A存储，其中A［i］向量为顶点i的所有相邻顶点。例如，如图5．21所示的无向连通图，对应的邻接表如下： 


A=［［1,2,3］,［0］,［0,3］,［0,2］］






图5．21一个无向连通图

m种颜色的编号为0~m-1，这里实际上就是为每个顶点i选择m种颜色中的一种(m选一)，使得任意两个相邻顶点的着色不同，所以将解空间树看成一棵子集树，并且求解个数，属于求所有解类型。

设计解向量为x=(x0，x1，…，xn-1)，其中xi表示顶点i的着色(0≤xi≤m-1)，初始时置x的所有元素为-1，表示所有顶点均没有着色，用ans累计解个数(初始为0)。采用递归回溯方法从顶点0开始试探(i=0对应根结点)，当i≥n时表示找到一种着色方案(对应解空间中的一个叶子结点)。

对于顶点i，所有可能的着色j为0到m-1中的一种，如果顶点i的所有相邻顶点的颜色均不等于j，说明顶点i着色j是合适的，只要有一个相邻顶点的颜色等于j，则顶点i着色j就是不合适的，需要回溯。对应的算法如下： 


1def judge(i,j):									#判断顶点i是否可以着色j

2global A,n,m,x,ans

3for k in range(0,len(A［i］)):

4if x［A［i］［k］］==j:return False			#存在相同颜色的顶点

5return True

6

7def dfs(i):											#回溯算法

8global m,x,ans

9if i>=n:ans+=1							#到达一个叶子结点

10else:

11for j in range(0,m):

12x［i］=j										#置顶点i为颜色j

13if judge(i,j):dfs(i+1)					#若顶点i可以着色j

14x［i］=-1							#回溯

15

16def colors(A,n,m):								#求图的m着色问题

17global x,ans

18x=［-1］*n   					#解向量元素初始化为-1

19ans=0											#着色方案数

20dfs(0)			   			#从顶点0开始搜索

21return ans



对于图5．21，m=3时调用上述colors()算法求出有12种不同的着色方案。

【算法分析】解空间中最多生成O(mn)个结点，每个结点花费O(n)的时间判断当前颜色是否合适，所以算法的最坏时间复杂度为O(n×mn)。

5．4基于排列树框架的问题求解
5．4．1排列树算法框架概述

当求解问题是确定n个元素满足某种条件的排列时，相应的解空间树称为排列树。解空间为排列树的递归框架是以求全排列为基础的，下面通过示例讨论一种不同于第3章中求全排列的递归算法。


扫一扫



视频讲解


【例52】(LeetCode46★★)有一个含n个整数的数组a，所有元素均不相同，求其所有元素的全排列。例如，a={1，2，3}，得到的结果是(1，2，3)，(1，3，2)，(2，3，1)，(2，1，3)，(3，1，2)，(3，2，1)。


解用数组a存放初始数组a的一个排列，采用递归法求解。设f(a，n，i)表示求a［i．．n-1］(共n-i个元素)的全排列，为大问题，f(a，n，i+1)表示求a［i+1．．n-1］(共n-i-1个元素)的全排列，为小问题，如图5．22所示。



图5．22求f(a，n，i)的过程


显然i越小求全排列的元素个数越多，当i=0时求a［0．．n-1］的全排列。当i=n-1时求a［n-1．．n-1］的全排列，此时序列中只有一个元素(单个元素的全排列就是该元素)，再合并a［0．．n-2］(n-1个元素的排列)就得到n个元素的一个排列。当i=n时求a［n．．n-1］的全排列，此时序列为空，说明a［0．．n-1］是一个排列，后面两种情况均可以作为递归出口。所以求a中全排列的过程是f(a，n，0)→f(a，n，1)→f(a，n，2)→…→f(a，n，n-1)。

那么如何由小问题f(a，n，i+1)求大问题f(a，n，i)呢？假设由f(a，n，i+1)求出了a［i+1．．n-1］的全排列，考虑ai的位置，该位置可以取a［i．．n-1］中的任何一个元素，但是排列中元素不能重复，为此采用交换方式，即j=i到n-1循环，每次循环将a［i］与a［j］交换，合并子问题的解得到一个大问题的排列，再恢复成循环之前的顺序，即将a［i］与a［j］再次交换，然后进入下一轮求其他大问题的排列。注意，如果不做再次交换(即恢复)会出现重复的排列情况，例如a={1，2，3}，在不做恢复时的输出结果为(1，2，3)，(1，3，2)，(3，1，2)，(3，2，1)，(1，2，3)，(1，3，2)，显然是错误的。

归纳起来，求a的全排列的递归模型f(a，n，i)如下： 

f(a，n，i)≡输出产生的解当i=n-1时

f(a，n，i)≡对于j=i~n-1： 其他

a［i］与a［j］交换位置; 

f(a，n，i+1); 

将a［i］与a［j］交换位置(回溯)

例如a={1，2，3}时，求全排列的解空间如图5．23所示，数组a的下标从0开始，所以根结点“a={1，2，3}”的层次为0，同时a数组也作为解向量，由根结点扩展出3个子结点，分别对应a［0］位置选择a［0］、a［1］和a［2］元素，采用交换方式实现，当从子结点返回时需要恢复，采用再次交换的方式实现。实际上，对于第i层的结点，其子树分别对应a［i］位置选择a［i］、a［i+1］、……、a［n-1］元素。树的高度为n+1，叶子结点的层次是n。



图5．23求a={1，2，3}的全排列的解空间


对应的递归算法如下： 


1def dfs(x,i):									#回溯算法

2if i==len(x):

3print(x)

4else:

5for j in range(i,len(x)):

6x［i］,x［j］=x［j］,x［i］	#x［i］与x［j］交换

7dfs(x,i+1)

8x［i］,x［j］=x［j］,x［i］	#回溯

9

10def perm(a):       			#求a的全排列

11x=a            			#解向量

12dfs(x,0)



LeetCode46用于求数组nums的全排列，并且返回该全排列，按照上述过程设计求解程序如下： 


1class Solution:

2def permute(self, nums: List［int］) > List［List［int］］:

3self.ans=［］   					#存放nums的全排列

4x=nums

5self.dfs(x,0)

6return self.ans

7

8def dfs(self,x,i): 					#回溯算法

9if i==len(x):





10self.ans.append(copy.deepcopy(x))

11else:

12for j in range(i,len(x)):

13x［i］,x［j］=x［j］,x［i］

14self.dfs(x,i+1)

15x［i］,x［j］=x［j］,x［i］



上述程序提交时通过，执行用时为32ms，内存消耗为15．2MB。

现在证明上述算法的正确性。实际上在递归算法中求值顺序与递推顺序相反，求a的全排列是从f(a，n，0)开始的，求值顺序是f(a，n，n-1)→f(a，n，n-2)→…→f(a，n，1)→f(a，n，0)。循环不变量是f(a，n，i)，用于求a［i．．n-1］的全排列，证明如下。

初始化： 在循环的第一轮迭代开始之前，i=n-1，表示求a［n-1．．n-1］的全排列，而一个元素就是该元素，显然是正确的。

保持： 若前面f(a，n，i+1)正确，表示求出了a［i+1．．n-1］的全排列，将a［i］与a［i．．n-1］中的每个元素交换，合并a［i+1．．n-1］的一个排列得到f(a，n，i)的一个排列，在恢复后继续做完，从而得到f(a，n，i)的全排列。

终止： 当求值结束时i=0，得到f(a，n，0)即a的全排列。

从上述求a的全排列的示例可以归纳出解空间为排列树的递归回溯框架如下： 


x=［］												#x存放解向量，需要初始化

def dfs(i):										#求解排列树的递归框架

if i>=n:										#到达一个叶子结点,输出一个可行解

输出结果

else:

for j in range(i,n):					#用j枚举x［i］的所有可能候选值

…										#第i层的结点选择x［j］的操作

swap(x［i］,x［j］)					#为保证排列中的每个元素不同,通过交换来实现

if constraint(i,j) and bound(i,j):

dfs(i+1)							#满足约束条件和限界函数，进入下一层

swap(x［i］,x［j］)					#恢复状态:回溯

…										#第i层的结点选择x［j］的恢复操作

}

}

}



如何进一步理解上述算法呢？假设解向量为(x0，x1，…，xi，…，xj，…，xn-1)，当从解空间的根结点出发搜索到达第i层的某个结点时，对应的部分解向量为(x0，x1，…，xi-1)，其中每个分量已经取好值了，现在为该结点的分支选择一个xi值(每个不同的取值对应一个分支，xi有n-i个分支)，前一个swap(x［i］,x［j］)表示为xi取xj值，后一个swap(x［i］,x［j］)用于状态恢复，这一点是利用排列树的递归回溯框架求解实际问题的关键。另外几点需要注意的说明事项与解空间为子集树的递归回溯框架相同。

在排列树中有m0=n，m1=n-1，…，mn-1=1，假设输出一个排列的时间为O(n)，对应算法的时间复杂度为O(n×n!)。


扫一扫



视频讲解


5．4．2实战——含重复元素的全排列Ⅱ(LeetCode47★★)

1. 问题描述
给定一个可包含重复数字的序列 nums，设计一个算法按任意顺序返回所有不重复的全排列。例如，nums={1，1，2}，输出结果是{{1，1，2}，{1，2，1}，{2，1，1}}。

2. 问题求解
该问题与求非重复元素的全排列的问题类似，解空间是排列树，并且属于求所有解类型。先按求非重复元素的全排列的一般过程来求含重复元素的全排列，假设a={1，1，2}，其中包含两个1，为了区分，后面一个1加上一个框，求其全排列的过程如图5．24所示，从中看出，11的分支和11的分支产生的所有排列是相同的，属于重复的排列，应该剪去后者，再看第1层的“{2,1,1}”结点，同样它扩展的两个分支分别是11和11，也是相同的，也应该剪去后者。这样剪去后得到的结果是{1，1，2}，{1，2，1}，{2，1，1}，也就是不重复的全排列。



图5．24求a={1，1，2}的全排列的过程




图5．25xi的各种取值

同样设解向量为x=(x0，x1，…，xn)，每个x表示一个排列，xi表示该排列中i位置所取的元素，初始时x=nums。在解空间中搜索到第i层的某个结点C时，如图5．25所示，C结点的每个分支对应xi的一个取值，从理论上讲xi可以取xi~xn-1中的每一个值，也就是说从根结点经过结点C到达第i+1层的结点有n-1-i+1=n-i条路径，这些路径中从根结点到C结点都是相同的。当xi取值xj时(对应图中粗分支)走到B结点，如果xj与前面xi~xj-1中的某个值xk相同，当xi取值xk时走到A结点，显然根结点到A和B结点的路径完全相同，而且它们的层次相同，后面的操作也相同，则所有到达叶子结点产生的解必然相同，属于重复的排列，需要剪去。


剪去重复的解的方法是，当j从i到n-1循环时，每次循环执行swap(x［i］，x［j］)为i位置选取元素x［j］，如果x［j］与x［i．．j-1］中的某个元素相同会出现重复的排列，则跳过(称为同层去重)，也就是说在执行swap(x［i］，x［j］)之前先判断x［j］是否在前面的元素x［i．．j-1］中出现过，如果没有出现过，则继续做下去，否则跳过x［j］的操作。对应的算法如下： 


1class Solution:

2def permuteUnique(self, nums: List［int］) > List［List［int］］:





3self.ans=［］   					#存放nums的全排列

4x=nums

5self.dfs(x,0)

6return self.ans

7

8def dfs(self,x,i): 					#回溯算法

9if i==len(x):

10self.ans.append(copy.deepcopy(x))

11else:

12for j in range(i,len(x)):

13if self.judge(x,i,j):continue      #检测x［j］

14x［i］,x［j］=x［j］,x［i］

15self.dfs(x,i+1)

16x［i］,x［j］=x［j］,x［i］

17

18def judge(self,x,i,j):     		#判断x［j］是否在x［i..j-1］中出现过

19if j>i:

20for k in range(i,j):           #判断x［j］是否与x［i..j-1］中的元素相同 

21if x［k］==x［j］:return True#若相同则返回真

22return False                       #若全部不相同返回假



上述程序提交时通过，执行用时为52ms，内存消耗为15．2MB。

5．4．3任务分配问题

1. 问题描述

扫一扫



视频讲解


见5．3．10节，这里采用基于排列树框架求解。

2. 问题求解
n个人和n个任务的编号均为0~n-1，设计解向量x=(x0，x1，…，xn-1)，同样以人为主，也就是第i个人执行第xi个任务(0≤xi≤n-1)，显然每个合适的分配方案x一定是0~n-1的一个排列，可以求出0~n-1的全排列，每个排列作为一个分配方案，求出其成本，通过比较找到一个最小成本bestc即可。




图5．26为人员i安排任务x［j］的情况

用bestx表示最优解向量，bestc表示最优解的成本，x表示当前解向量，cost表示当前解的总成本(初始为0)，另外设计一个used数组，其中used［j］表示任务j是否已经分配(初始时所有元素均为False)，为了简单，将这些变量均设计为全局变量。

根据排列树的递归算法框架，当搜索到第i层的某个结点时，第一个swap(x［i］,x［j］)表示为人员i分配任务x［j］(注意不是任务j)，成本是c［i］［x［i］］(因为x［i］就是交换前的x［j］)，所以执行used［x［i］］=True，cost+=c［i］［x［i］］，调用dfs(x,cost,i+1)继续为人员i+1分配任务，回溯操作是cost-=c［i］［x［i］］，used［x［i］］=False和swap(x［i］,x［j］)(正好与调用dfs(x,cost,i+1)之前的语句顺序相反)。

考虑采用剪支提高性能，设计下界函数，与5．3．10节中的bound算法相同，仅需要将j(指任务编号)改为x［j］即可，如图5．26所示，这样仅扩展bound(x,cost,i+1)<bestc的孩子结点。


带剪支的排列树的递归回溯算法如下： 


1import copy

2INF=0x3f3f3f3f           	#表示∞

3def dfs3(cost,i):										#回溯算法

4global c,n,x,bestx,bestc,used,sum

5sum+=1

6if i>=n:			       		#到达一个叶子结点

7if cost<bestc:		   		#通过比较求最优解

8bestc=cost

9bestx=copy.deepcopy(x)

10else:

11for j in range(i,n):							#为人员i试探任务x［j］

12if used［x［j］］:continue			      #跳过已经分配的任务j

13x［i］,x［j］=x［j］,x［i］							#swap(x［i］,x［j］):为人员i分配任务x［j］

14used［x［i］］=True

15cost+=c［i］［x［i］］

16if bound(cost,i+1)<bestc:				#剪支

17dfs3(cost,i+1)				#继续为人员i+1分配任务

18cost-=c［i］［x［i］］							#cost回溯

19used［x［i］］=False							#used回溯

20x［i］,x［j］=x［j］,x［i］                #x回溯

21

22def bound(cost,i):									#求下界算法

23global c,n,x,used

24minsum=0

25for i1 in range(i,n):								#求c［i..n-1］行中的最小元素和

26minc=INF

27for j1 in range(0,n):

28if not used［x［j1］］ and c［i1］［x［j1］］<minc:minc=c［i1］［x［j1］］

29minsum+=minc

30return cost+minsum

31

32def allocate3(c,n):					#求解任务分配问题

33global x,bestx,bestc,used,sum

34x=［］

35for i in range(0,n):x.append(i)#初始化解向量x

36bestx=［0］*n                         #最优解向量

37bestc=INF                         #将最优成本初始化为∞

38used=［False］*n

39sum=0

40dfs3(0,0)											#从人员0开始

41print("求解结果")

42for k in range(0,n):

43print("人员%d分配任务%d"%(k,bestx［k］))

44print("总成本=",bestc)

45print("sum=",sum)



对于表5．3，调用上述allocate3算法的执行结果如下： 


求解结果

人员0分配任务1

人员1分配任务0





人员2分配任务2

人员3分配任务3

总成本=13

sum=9



【算法分析】算法的解空间是一棵排列树，同时复制更优解和求下界的时间为O(n2)，所以最坏的时间复杂度为O(n2×n!)。例如，在上述实例中n=4，经测试不剪支(除去dfs3中的if(bound(cost,i)<bestc))时搜索的结点个数为65，而剪支后搜索的结点个数为9。

说明： 任务分配问题在5．3．10节采用基于子集树框架时最坏时间复杂度为O(nn)，这里采用基于排列树框架的最坏时间复杂度为O(n!)，显然n>2时O(n!)优于O(nn)，实际上由于前者通过used判重剪去了重复的分支，其解空间本质上也是一棵排列树，两种算法的最坏时间复杂度都是O(n!)。

5．4．4货郎担问题

1. 问题描述

扫一扫



视频讲解


货郎担问题又称为旅行推销员问题(TSP)，是数学领域中著名的问题之一。假设有一个货郎担要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市，要求求出路径长度最短的路径。



图5．27一个4城市的道路图

以图5．27所示的一个4城市的道路图为例，假设起点s为0，所有从顶点0回到顶点0并通过所有顶点的路径如下： 

路径1： 0→1→2→3→0： 28

路径2： 0→1→3→2→0： 29

路径3： 0→2→1→3→0： 26

路径4： 0→2→3→1→0： 23

路径5： 0→3→2→1→0： 59

路径6： 0→3→1→2→0： 59

最后求得的最短路径长度为23，最短路径为0→2→3→1→0。

2. 问题求解
本问题是求路径长度最短的路径，属于求最优解类型。假设图中有n个顶点，顶点的编号为0~n-1，采用邻接矩阵A存储。显然TSP路径是简单回路(除了起始点和终点相同，其他顶点不重复)，可以采用穷举法，以全排列的方式求出所有路径及其长度，再加上回边，在其中找出长度最短的回路即为TSP路径，但这样做难以剪支，时间性能较低。

现在采用基于排列树的递归回溯算法，设计当前解向量x=(x0，x1，…，xn-1)，每个xi表示图中一个顶点，实际上每个x表示一条路径，初始时将x0置为起点s，x1~xn-1为其他n-1个顶点的编号，d表示当前路径的长度，用bestx保存最短路径，bestd表示最短路径长度，将其初始值置为∞。算法dfs(x，d，s，i)设计的几个重点如下。



图5．28x1的各种取值情况

① x0固定作为起点s，不能取其他值，所以不能从i=0开始调用dfs，应该改为从i=1(此时d=0)开始调用dfs。为了简单，假设s=0，x初始时为(0，1，…，n-1)，i=1时x1会取x［1．．n-1］中的每一个值(共n-1种取值)，如图5．28所示，当x1=x1(1)时，对应路径长度为d+A［0］［1］，当x1=x2(2)时，对应路径长度为d+A［0］［2］，以此类推。归纳起来，当搜索到解空间的第i层的某个结点时，xi取x［i．．n-1］中的某个值后当前路径长度为d+A［x［i-1］］［x［i］］。

② 当搜索到达某个叶子结点时(i≥n)，对应的TSP路径长度应该是d+A［x［n-1］］［s］(因为TSP路径是闭合的回路)，对应的路径是x∪{s}。通过比较所有回路的长度求最优解。

③ 如何剪支呢？若当前已经求出最短路径长度bestd，如果xi取xj值，对应的路径长度为d+A［x［i-1］］［x［j］］，若d+A［x［i-1］］［x［j］］≥bestd，说明该路径走下去不可能找到更短路径，终止该路径的搜索，也就是说仅扩展满足d+A［x［i-1］］［x［j］］<bestd的路径。


对应的回溯法求TSP问题的算法如下： 


1import copy

2INF=0x3f3f3f3f

3def dfs(d,s,i):															#回溯算法

4global A,n,x,bestx,bestd

5if i>=n:																#到达一个叶子结点

6if d+A［x［n-1］］［s］<bestd:									#通过比较求最优解

7bestd=d+A［x［n-1］］［s］						#求TSP路径长度

8bestx=copy.deepcopy(x)					#更新bestx

9else:

10for j in range(i,n):											#试探x［i］走到x［j］的分支

11if A［x［i-1］］［x［j］］!=0 and A［x［i-1］］［x［j］］!=INF:	#若x［i-1］到x［j］有边

12if d+A［x［i-1］］［x［j］］<bestd:						#剪支

13x［i］,x［j］=x［j］,x［i］				#swap(x［i］,x［j］)

14dfs(d+A［x［i-1］］［x［i］］,s,i+1)

15x［i］,x［j］=x［j］,x［i］				#swap(x［i］,x［j］)

16

17def TSP1(A,n,s):														#求解TSP(起始点为s)

18global x,bestx,bestd

19x=［s］      										#x［0］=s,解向量初始化

20for i in range(0,n):												#将非s的顶点添加到x中

21if i==s:continue

22x.append(i)

23bestx=［0］*n

24bestd=INF

25dfs(0,s,1)

26bestx.append(s)			       			#bestx的末尾添加起始点

27print("求解结果")

28print("  最短路径: ",end='')									#输出最短路径

29for j in range(0,len(bestx)):

30if j==0:print(bestx［j］,end='')

31else:print(">%d"%(bestx［j］),end='')

32print("＼n  路径长度:",bestd)



当A=［［0，8，5，36］，［6，0，8，5］，［8，9，0，5］，［7，7，8，0］］、n=4、s=1时调用TSP1(A，n，s)的输出结果如下： 


求解结果

最短路径: 1>0>2>3>1

路径长度: 23



【算法分析】上述算法的解空间是一棵排列树，由于是从第一层开始搜索的，排列树的高度为n(含叶子结点层)，同时复制更优解的时间为O(n)，所以最坏的时间复杂度为O(n×(n-1)!)，即O(n!)。

思考题： TSP问题是在一个图中查找从起点s经过其他所有顶点又回到顶点s的最短路径，在上述算法中为什么不考虑路径中出现重复顶点的情况？

习题5


扫一扫



练习题




扫一扫



自测题