第5章回溯法——深度优先搜索
深度优先搜索是在明确给出了图中的各顶点及边(显式图)的情况下，按照深度优先搜索的思想对图中的每个顶点进行搜索，最终得出图的结构信息。回溯法是在仅给出初始节点、目标节点及产生子节点的条件(一般由问题题意隐含给出)的情况下，构造一个图(隐式图)，然后按照深度优先搜索的思想，在有关条件的约束下扩展到目标节点，从而找出问题的解。换言之，回溯法从初始状态出发，在隐式图中以深度优先的方式搜索问题的解。当发现不满足求解条件时，就回溯，并尝试其他路径。通俗地讲，回溯法是一种“能进则进，进不了则换，换不了则退”的基本搜索方法。


视频讲解



5.1概述
1. 回溯法的算法框架及思想

（1） 回溯法的算法框架。
回溯法是一种搜索方法。用回溯法解决问题时，首先应明确搜索范围，即问题所有可能解组成的范围。这个范围越小越好，且至少包含问题的一个(最优)解。为了定义搜索范围，需要明确以下4个方面。
① 问题解的形式： 回溯法希望问题的解能够表示成一个n元组(x1,x2,…,xn)的形式。
② 显约束： 对分量xi(i=1,2,…,n)的取值范围限定。
③ 隐约束： 为满足问题的解而对不同分量之间施加的约束。
④ 解空间： 对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间。
注意： 同一个问题的显约束可能有多种，相应解空间的大小就会不同，通常情况下，解空间越小，算法的搜索效率就越高。
【例51】n皇后问题。在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。换句话说，n皇后问题等价于在n×n格的棋盘上放置n个皇后，任意两个皇后不同行、不同列、不同斜线。
问题分析： 根据题意，首先考虑显约束为不同行的解空间。
① 问题解的形式： n皇后问题的解表示成n元组(x1,x2,…,xn)的形式，其中xi(i=1,2,…,n)表示第i个皇后放置在第i行第xi列的位置。
② 显约束： n个皇后不同行。
③ 隐约束： n个皇后不同列或不同斜线。
④ 解空间： 根据显约束，第i(i=1,2,…,n)个皇后有n个位置可以选择，即第i行的n个列位置，即xi∈{1,2, …,n}，显然满足显约束的n元组共有nn种，它们构成了n皇后问题的解空间。
如果将显约束定义为不同行且不同列，则问题的隐约束为不同斜线，问题的解空间为第i个皇后不能放置在前i-1个皇后所在的列，故第i个皇后有n-i+1个位置可以选择，令S={1,2,3,…,n}，则xi∈S-{x1,x2,…,xi-1}。因此，n皇后问题解空间由n！个n元组组成。
显然，第二种表示方法使得问题的解空间明显变小，因此搜索效率更高。
其次，为了方便搜索，一般用树或图的形式将问题的解空间有效地组织起来。如例51的n皇后问题： 显约束为不同行的解空间树(n=4)，如图51所示，显约束为不同行且不同列的解空间树(n=4)，如图52所示。树的节点代表状态，树根代表初始状态，树叶代表目标状态； 从树根到树叶的路径代表放置方案； 分支上的数据代表xi的取值，也可以说是将第i个皇后放置在第i行，第xi列的动作。


图51显约束为不同行的解空间树(n=4)



图52显约束为不同行且不同列的解空间树(n=4)

最后，搜索问题的解空间树。在搜索的过程中，需要了解以下3个名词。
① 扩展节点： 一个正在生成孩子的节点称为扩展节点。
② 活节点： 一个自身已生成但其孩子还没有全部生成的节点称为活节点。
③ 死节点： 一个所有孩子已经生成的节点称为死节点。
(2) 搜索思想。从根开始，以深度优先搜索的方式进行搜索。根节点是活节点并且是当前的扩展节点。在搜索过程中，当前的扩展节点沿纵深方向移向一个新节点，判断该新节点是否满足隐约束，如果满足，那么新节点成为活节点，并且成为当前的扩展节点，继续深一层的搜索； 如果不满足，那么换到该新节点的兄弟节点(扩展节点的其他分支)继续搜索； 如果新节点没有兄弟节点，或其兄弟节点已全部搜索完毕，那么扩展节点成为死节点，搜索回溯到其父节点处继续进行。搜索过程直到找到问题的解或根节点变成死节点为止。
从回溯法的搜索思想可知，搜索开始之前必须确定问题的隐约束。隐约束一般是考查解空间结构中的节点是否有可能得到问题的可行解或最优解。如果不可能得到问题的可行解或最优解，就不用沿着该节点的分支继续搜索了，需要换到该节点的兄弟节点或回到上一层节点。也就是说，在深度优先搜索的过程中，不满足隐约束的分支被剪掉，只沿着满足隐约束的分支搜索问题的解，从而避免了无效搜索，加快了搜索速度。因此，隐约束又称为剪枝函数。隐约束(剪枝函数)一般有两种： 一是判断是否能够得到可行解的隐约束，称之为约束条件(约束函数)； 二是判断是否有可能得到最优解的隐约束，称之为限界条件(限界函数)。可见，回溯法是一种具有约束函数或限界函数的深度优先搜索方法。
总之，回溯法的算法框架主要包括以下3部分。
① 针对所给问题，定义问题的解空间。
② 确定易于搜索的解空间组织结构。
③ 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
2. 回溯法的构造实例
【例52】用回溯法解决4皇后问题。
其实，按照回溯法的搜索思想，首先确定根节点是活节点，并且是当前的扩展节点R。它扩展生成一个新节点C，若C不满足隐约束，则舍弃； 若满足，则C成为活节点并成为当前的扩展节点，搜索继续向纵深处进行(此时节点R不再是扩展节点)。在完成对子树C(以C为根的子树)的搜索之后，节点C变成了死节点。开始回溯到离死节点C最接近的活节点R，节点R再次成为扩展节点。若扩展节点R还存在未搜索过的孩子节点，则继续沿R的下一个未搜索过的孩子节点进行搜索； 直到找到问题的解或者根节点变成死节点为止。
用回溯法解决4皇后问题的求解过程设计如下： 
第一步，定义问题的解空间。
设4皇后问题解的形式是4元组(x1,x2,x3,x4)，其中xi(i=1,2,3,4)代表第i个皇后放置在第i行第xi列，xi的取值为1,2,3,4。
第二步，确定解空间的组织结构。
确定显约束： 第i个皇后和第j个皇后不同行，即i≠j，对应的解空间的组织结构如图51所示。
第三步，搜索解空间。
（1） 确定约束条件。第i个皇后和第j个皇后不同列且不同斜线，即xi≠xj并且|i-j|≠|xi-xj|。
（2） 确定限界条件。该问题不存在放置方案是否好坏的情况，所以不需要设置限界条件。
（3） 搜索过程。如图53~图58所示： 根节点A是活节点，也是当前的扩展节点，如图53(a)所示。扩展节点A沿着x1=1的分支生成孩子节点B，节点B满足隐约束，B成为活节点，并成为当前的扩展节点，如图53(b)所示。扩展节点B沿着x2=1，2和x2=2的分支生成的孩子节点不满足隐约束，舍弃； 沿着x2=3的分支生成的孩子节点C满足隐约束，C成为活节点，并成为当前的扩展节点，如图53(c)所示。扩展节点C沿着所有分支生成的孩子节点均不满足隐约束，全部舍弃，活节点C变成死节点。开始回溯到离它最近的活节点B，节点B再次成为扩展节点，如图53(d)所示。


图534皇后问题的搜索过程（一）



图544皇后问题的搜索过程（二）

扩展节点B沿着x2=4的分支继续生成的孩子节点D满足隐约束，D成为活节点，并成为当前的扩展节点，如图54(a)所示。扩展节点D沿着x3=1的分支生成的孩子节点不满足隐约束，舍弃； 沿着x3=2的分支生成的孩子节点E满足隐约束，E成为活节点，并成为当前的扩展节点，如图54(b)所示。扩展节点E沿着所有分支生成的孩子节点均不满足隐约束，全部舍弃，活节点E变成死节点。开始回溯到最近的活节点D，D再次成为扩展节点，如图54(c)所示。扩展节点D沿着x3=3，4的分支生成的孩子节点均不满足隐约束，舍弃，活节点D变成死节点。开始回溯到最近的活节点B，B再次成为扩展节点，如图54(d)所示。
此时扩展节点B的孩子节点均搜索完毕，活节点B成为死节点。开始回溯到最近的活节点A，节点A再次成为扩展节点，如图55(a)所示。扩展节点A沿着x1=2的分支继续生成的孩子节点F满足隐约束，节点F成为活节点，并成为当前的扩展节点，如图55(b)所示。扩展节点F沿着x2=1,2,3的分支生成的孩子节点均不满足隐约束，全部舍弃； 继续沿着x2=4的分支生成的孩子节点G满足隐约束，节点G成为活节点，并成为当前的扩展节点，如图55(c)所示。


图554皇后问题的搜索过程（三）


扩展节点G沿着x3=1的分支生成的孩子节点H满足隐约束，节点H成为活节点，并成为当前的扩展节点，如图56(a)所示。扩展节点H沿着x4=1,2的分支生成的孩子节点均不满足隐约束，舍弃； 沿着x4=3的分支生成的孩子节点I满足隐约束。此时搜索过程搜索到了叶子节点，说明已经找到一种放置方案，即(2,4,1,3)，如图56(b)所示。继续搜索其他放置方案，从叶子节点I回溯到最近的活节点H，H又成为当前扩展节点，如图56(c)所示。


图564皇后问题的搜索过程（四）

扩展节点H继续沿着x4=4的分支生成的孩子节点不满足隐约束，舍弃； 此时节点H的4个分支全部搜索完毕，H成为死节点，回溯到活节点G，如图57(a)所示。节点G又成为当前的扩展节点，沿着x3=2,3,4的分支生成的孩子节点均不满足隐约束，舍弃； 节点G成为死节点，回溯到活节点F，如图57(b)所示。节点F的4个分支均搜索完毕，继续回溯到活节点A，节点A再次成为当前的扩展节点，如图57(c)所示。


图574皇后问题的搜索过程（五）




图584皇后问题的搜索过程（六）

扩展节点A沿着x1=3,4分支的扩展过程与沿着x1=1,2分支的扩展过程类似，这里不再详述。最终形成的树如图58所示。
通常将搜索过程中形成的树型结构称为问题的搜索树。在例51中的4皇后问题对应的搜索树如图58所示。简单地讲，搜索树上的节点全部是解空间树中满足隐约束的节点，而不满足隐约束的节点被全部剪掉。
对显约束为不同行且不同列的4皇后问题的解空间树(如图52所示)进行搜索的过程与上述搜索过程类似。二者最终形成的搜索树完全相同，只有搜索过程中检查的隐约束和分支数不同，留给读者练习。
3. 回溯法的算法描述模式
回溯法是一种带有约束函数或限界函数的深度优先搜索方法，搜索过程是在问题的解空间树中进行的。算法描述通常采用递归技术，也可以选用非递归技术。
(1) 递归算法描述模式。递归算法描述如下： 





def Backtrack (t):

if (t>n):

output(x)

else:

for  i  in range(s(n,t),e(n,t)+1):

x［t］=d(i)

if (constraint(t) and bound(t)): 

Backtrack(t+1)




这里，形参t代表当前扩展节点在解空间树中所处的层次。解空间树的根节点为第1层，根节点的孩子节点为第2层，以此类推，深度为n的解空间树的叶子节点为第n+1层。注意： 在解空间树中，节点所处的层次比该节点所在的深度大1。解空间树中节点的深度与层次之间的关系如图59所示。


图59解空间树中节点的深度与层次关系

变量n代表问题的规模，同时也是解空间树的深度。注意区分树的深度和树中节点的深度两个概念，树的深度指的是树中深度最大的节点深度。s(n,t)代表当前扩展节点处未搜索的子树的起始编号。e(n,t)代表当前扩展节点处未搜索的子树的终止编号。d(i)代表当前扩展节点处可选的分支上的数据。x是用来记录问题当前解的数组。constraint(t)代表当前扩展节点处的约束函数。bound(t)代表当前扩展节点处的限界函数。满足约束函数或限界函数则继续深一层次的搜索； 否则，剪掉相应的子树。Backtrack(t)代表从第t层开始搜索问题的解。由于搜索是从解空间树的根节点开始，即从第1层开始搜索，因此函数调用为Backtrack(1)。
(2) 非递归算法描述模式。非递归算法描述如下： 





def  NBacktrack ():

t=1

while (t>0):

if (s(n,t)<=e(n,t)):#从起始分支s(n,t)到结束分支e(n,t)

for i in range(s(n,t),e(n,t)+1):

x［t］=d(i)

if (constraint(t) and bound(t)):

if (t>n):

output(x)

else:

t+=1#更深一层

else:

t -=1#回溯到上一层的活节点




这里出现的函数和变量均和递归算法描述模式中出现的含义相同。
5.2典型的解空间结构



视频讲解



5.2.1子集树
1. 概述

子集树是使用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。此类问题解的形式为n元组(x1,x2,…,xn)，分量xi(i=1,2,…,n)表示第i个元素是否在要找的子集中。xi的取值为0或1，xi=0表示第i个元素不在要找的子集中； xi=1表示第i个元素在要找的子集中。如图510所示是n=3时的子集树。


图510n=3时的子集树

子集树中所有非叶子节点均有左右两个分支，左分支为1，右分支为0，反之也可以。本书约定子集树的左分支为1，右分支为0。树中从根到叶子的路径描述了一个n元01向量，这个n元01向量表示集合S的一个子集，这个子集由对应分量为1的元素组成。如假定3个元素组成的集合S为{1,2,3}，从根节点A到叶节点I的路径描述的n元组为(1,1,0)，它表示S的一个子集{1,2}。从根节点A到叶节点M的路径描述的n元组为(0,1,0)，它表示S的另一个子集{2}。
在子集树中，树的根节点表示初始状态，中间节点表示某种情况下的中间状态，叶子节点表示结束状态。分支表示从一个状态过渡到另一个状态的行为。从根节点到叶子节点的路径表示一个可能的解。子集树的深度等于问题的规模。
解空间树为子集树的问题有很多，如： 
（1） 01背包问题： 从n个物品组成的集合S中找出一个子集，这个子集内所有物品的总重量不超过背包的容量，并且这些物品的总价值在S的所有不超过背包容量的子集中是最大的。显然，这个问题的解空间树是一棵子集树。
（2） 子集和问题： 给定n个整数和一个整数C，要求找出n个数中哪些数相加的和等于C。这个问题实质上是要求从n个数组成的集合S中找出一个子集，这个子集中所有数的和等于给定的C。因此，子集和问题的解空间树也是一棵子集树。
（3） 装载问题： n个集装箱要装上两艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且∑ni=1wi≤c1+c2。装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这两艘轮船，如果有，找出一种装载方案。
这个问题如果有解，就采用下面的策略可得到最优装载方案。
① 首先将第一艘轮船尽可能装满。
② 将剩余的集装箱装上第二艘轮船。如果剩余的集装箱能够全部装上船，则找到一个合理的方案，如果不能全部装上船，则不存在装载方案。
将第一艘轮船尽可能装满等价于从n个集装箱组成的集合中选取一个子集，该子集中集装箱重量之和小于或等于第一艘船的载重量且最接近第一艘船的载重量。由此可知，装载问题的解空间树也是一棵子集树。
（4） 最大团问题： 给定一个无向图，找出它的最大团。这个问题等价于从给定无向图的n个顶点组成的集合中找出一个顶点子集，这个子集中的任意两个顶点之间有边相连且包含的顶点个数是所有该类子集中包含顶点个数最多的。因此，这个问题也是从整体中取出一部分，这一部分构成整体的一个子集且满足一定的特性，它的解空间树是一棵子集树。
可见，对于要求从整体中取出一部分，这一部分需要满足一定的特性，整体与部分之间构成包含与被包含的关系，即子集关系的一类问题，均可采用子集树来描述它们的解空间树。这类问题在解题时可采用统一的算法设计模式。
2. 子集树的算法描述模式
子集树的算法描述如下： 




def Backtrack (t):

if (t>n):

output(x)

if(constraint(t)):  

#做相关标识

Backtrack(t+1)

#做相关标识的反操作

if(bound(t)):

#做相关标识

Backtrack(t+1)

#做相关标识的反操作





这里，形式参数t表示扩展节点在解空间树中所处的层次； n表示问题的规模，即解空间树的深度； x是用来存放当前解的一维数组，初始化为x［i］=0(i=1,2,…,n)； constraint()函数为约束函数； bound()函数为限界函数。
5.2.2排列树
1. 概述

排列树是用回溯法解题时经常遇到的第二种典型的解空间树。当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。此类问题解的形式为n元组(x1,x2,…,xn)，分量xi(i=1,2,…,n)表示第i个位置的元素是xi。n个元素组成的集合为S={1,2,…,n}，xi∈S-{x1,x2,…,xi-1}，i=1,2,…,n。



图511n=3的排列树

n=3时的排列树如图511所示。
在排列树中从根到叶子的路径描述了n个元素的一个排列。如3个元素的位置为{1,2,3}，从根节点A到叶节点L的路径描述的一个排列为(1,3,2)，即第1个位置的元素是1，第2个位置的元素是3，第3个位置的元素是2； 从根节点A到叶节点M的路径描述的一个排列为(2,1,3)； 从根节点A到叶节点P的路径描述的一个排列为(3,2,1)。
在排列树中，树的根节点表示初始状态(所有位置全部没有放置元素)； 中间节点表示某种情况下的中间状态(中间节点之前的位置上已经确定了元素，中间节点之后的位置上还没有确定元素)； 叶子节点表示结束状态(所有位置上的元素全部确定)； 分支表示从一个状态过渡到另一个状态的行为(在特定位置上放置元素)； 从根节点到叶子节点的路径表示一个可能的解(所有元素的一个排列)。排列树的深度等于问题的规模。
解空间树为排列树的问题有很多种，如下所述。
（1） n皇后问题： 满足显约束为不同行、不同列的解空间树。约定不同行的前提下，n个皇后的列位置是n个列的一个排列，这个排列必须满足n个皇后的位置不在一条斜线上。
（2） 旅行商问题： 找出n个城市的一个排列，沿着这个排列的顺序遍历n个城市，最后回到出发城市，求长度最短的旅行路径。
（3） 批处理作业调度问题： 给定n个作业的集合{J1,J2,…,Jn}，要求找出n个作业的一个排列，按照这个排列进行调度，使得完成时间和达到最小。
（4） 圆排列问题： 给定n个大小不等的圆c1,c2,…,cn，现要将这n个圆放入一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出具有最小长度的圆排列。
（5） 电路板排列问题： 将n块电路板以最佳排列方式插入带有n个插槽的机箱中。n块电路板的不同排列方式对应于不同的电路板插入方案。设B={1,2,…,n}是n块电路板的集合，L={N1,N2,…,Nm}是连接这n块电路板中若干电路板的m个连接块。Ni是B的一个子集，且Ni中的电路板用同一条导线连接在一起。 设x表示n块电路板的一个排列，即在机箱的第i个插槽中插入的电路板编号是xi。x所确定的电路板排列Density(x)密度定义为： 跨越相邻电路板插槽的最大连线数。在设计机箱时，插槽一侧的布线间隙由电路板排列的密度确定。因此，电路板排列问题要求对于给定的电路板连接条件，确定电路板的最佳排列，使其具有最小排列密度。
可见，对于要求从n个元素中找出它们的一个排列，该排列需要满足一定的特性这类问题，均可采用排列树来描述它们的解空间结构。这类问题在解题时可采用统一的算法设计模式。
2. 排列树的算法描述模式
排列树的算法描述如下： 




def Backtrack (t):

if (t>n):

output(x)

else:

for i in range(t,n+1):

x［t］, x［i］←x［i］, x［t］#x初始化为x［i］=i

if (constraint(t) and bound(t)):

Backtrack(t+1)

x［t］, x［i］←x［i］, x［t］




这里，形式参数t表示扩展节点在解空间树中所处的层次； n表示问题的规模，即解空间树的深度； x是用来存储当前解的数组，初始化x［i］=i(i=1,2,…,n)，constraint()函数为约束函数； bound()函数为限界函数； swap()函数实现两个元素位置的交换。

5.2.3满m叉树
1. 概述

满m叉树是用回溯法解题时经常遇到的第三种典型的解空间树，也可以称为组合树。当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合。这类问题的解空间树称为满m叉树。此类问题解的形式为n元组(x1,x2,…,xn)，分量xi(i=1,2,…,n)表示第i个元素的选择为xi。n=3时的满m=3叉树如图512所示。


图512满3叉树

在满m叉树中从根到叶子的路径描述了n个元素的一种选择。树的根节点表示初始状态(任何一个元素都没有确定)，中间节点表示某种情况下的中间状态(一些元素的选择已经确定，另一些元素的选择没有确定)，叶子节点表示结束状态(所有元素的选择均已确定)，分支表示从一个状态过渡到另一个状态的行为(特定元素做何种选择)，从根节点到叶子节点的路径表示一个可能的解(所有元素的一个排列)。满m叉树的深度等于问题的规模n。
解空间树为满m叉树的问题有很多种，如下所述。
（1） n皇后问题： 显约束为不同行的解空间树，在不同行的前提下，任何一个皇后的列位置都有n种选择。n个列位置的一个组合必须满足n个皇后的位置不在同一列或不在同一条斜线上的性质。这个问题的解空间便是一棵满m(m=n)叉树。
（2） 图的m着色问题： 给定无向连通图G 和m 种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G 中有边相连的两个顶点着不同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图G和m 种颜色，找出所有不同的着色法。这个问题实质上是用给定的m种颜色给无向连通图G的顶点着色。每一个顶点所着的颜色有m种选择，找出n个顶点着色的一个组合，使其满足有边相连的两个顶点之间所着颜色不相同。很明显，这是一棵满m叉树。
（3） 最小质量机器设计问题： 可以看作给机器的n个部件找供应商，也可以看作m个供应商供应机器的哪个部件。如果看作给机器的n个部件找供应商，那么问题的实质为n个部件中的每一个部件均有m种选择，找出n个部件供应商的一个组合，使其满足n个部件的总价格不超过c且总重量是最小的。问题的解空间是一棵满m叉树。如果看作m个供应商供应机器的哪个部件，那么问题的解空间是一棵排列树，读者可以自己思考一下原因。 
可见，对于要求找出n个元素的一个组合，该组合需要满足一定特性这类问题，均可采用满m叉树来描述它们的解空间结构。这类问题在解题时可采用统一的算法设计模式。
2. 满m叉树的算法描述模式
满m叉树的算法描述如下： 




def Backtrack (t):

if (t>n):

output(x)

else:

for i in range(1,m+1):

if (constraint(t) and bound(t)):

x［t］=i

#做其他相关标识

Backtrack(t+1)

#做其他相关标识的反操作




这里，形式参数t表示扩展节点在解空间树中所处的层次； n表示问题的规模，即解空间树的深度； m表示每一个元素可选择的种数； x是用来存放解的一维数组，初始化为x［i］=0(i=1,2,…,n)； constraint()函数为约束函数； bound()函数为限界函数。

5.301背包问题——子集树
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为W。一种物品要么全部装入背包，要么全部不装入背包，不允许部分装入。装入背包的物品的总重量不超过背包的容量。问应如何选择装入背包的物品，使得装入背包中的物品总价值最大?


视频讲解



5.3.1问题分析——解空间及搜索条件
根据问题描述可知，01背包问题要求找出n种物品集合{1,2,…,n}中的一部分物品，将这部分物品装入背包。装进去的物品总重量不超过背包的容量且价值之和最大，即找到n种物品集合{1,2,…,n}的一个子集，这个子集中的物品总重量不超过背包的容量，且总价值是集合{1,2,…,n}的所有不超过背包容量的子集中物品总价值最大的。
按照回溯法的算法框架，首先需要定义问题的解空间，然后确定解空间的组织结构，最后进行搜索。搜索前要解决两个关键问题，一是确定问题是否需要约束条件(用于判断是否有可能产生可行解)，如果需要，那么应如何设置？二是确定问题是否需要限界条件(用于判断是否有可能产生最优解)，如果需要，那么应如何设置？
1. 定义问题的解空间
01背包问题是要将物品装入背包，并且物品有且只有两种状态。第i(i=1,2,…,n)种物品是装入背包能够达到目标要求，还是不装入背包能够达到目标要求呢？很显然，目前还不确定。因此，可以用变量xi表示第i种物品是否被装入背包的行为，如果用“0”表示不被装入背包，用“1”表示装入背包，则xi的取值为0或1。该问题解的形式是一个n元组，且每个分量的取值为0或1。由此可得，问题的解空间为： (x1,x2,…,xn)，其中xi=0或1，(i=1,2,…,n)。
2. 确定解空间的组织结构
问题的解空间描述了2n种可能的解，也可以说是n个元素组成的集合的所有子集个数。可见，问题的解空间树为子集树。采用一棵满二叉树将解空间有效地组织起来，解空间树的深度为问题的规模n。图513所示描述了n=4时的解空间树。


图513n=4时的解空间树

3. 搜索解空间
(1) 是否需要约束条件？如果需要，那么应如何设置？
01背包问题的解空间包含2n个可能的解，是不是每一个可能的解描述的装入背包的物品的总重量都不超过背包的容量呢？显然不是，这个问题存在某种或某些物品无法装入背包的情况。因此，需要设置约束条件来判断所有可能的解描述的装入背包的物品总重量是否超出背包的容量，如果超出，就为不可行解； 否则，为可行解。搜索过程将不再搜索那些导致不可行解的节点及其节点。约束条件的形式化描述为


∑ni=1wixi≤W(51)


(2) 是否需要限界条件？如果需要，那么应如何设置？
01背包问题的可行解可能不止一个，问题的目标是找一个所描述的装入背包的物品总价值最大的可行解，即最优解。因此，需要设置限界条件来加速找出该最优解的速度。
如何设置限界条件呢？根据解空间的组织结构可知，任何一个中间节点z(中间状态)均表示从根节点到该中间节点的分支所代表的行为已经确定，从z到其子孙节点的分支的行为是不确定的。也就是说，如果z在解空间树中所处的层次是t，从第1种物品到第t-1种物品的状态已经确定，接下来要确定第t种物品的状态。无论沿着z的哪一个分支进行扩展，第t种物品的状态就确定了。那么，从第t+1种物品到第n种物品的状态还不确定。这样，可以根据前t种物品的状态确定当前已装入背包的物品的总价值，用cp表示。第t+1种物品到第n种物品的总价值用rp表示，则cp+rp是所有从根出发的路径中经过中间节点z的可行解的价值上界。如果价值上界小于或等于当前搜索到的最优解描述的装入背包的物品总价值(用bestp表示，初始值为0)，就说明从中间节点z继续向子孙节点搜索不可能得到一个比当前更优的可行解，没有继续搜索的必要； 反之，则继续向z的子孙节点搜索。因此，限界条件可描述为


cp+rp>bestp(52)


5.3.2算法设计
从根节点开始，以深度优先的方式进行搜索。根节点首先成为活节点，也是当前的扩展节点。由于子集树中约定左分支上的值为“1”，因此沿着扩展节点的左分支扩展，则代表装入物品，此时，需要判断是否能够装入该物品，即判断约束条件成立与否，如果成立，就进入左孩子节点，左孩子节点成为活节点，并且是当前的扩展节点，继续向纵深节点扩展； 如果不成立，就剪掉扩展节点的左分支，沿着其右分支扩展。右分支代表物品不装入背包，肯定有可能导致可行解。但是沿着右分支扩展有没有可能得到最优解呢？这一点需要由限界条件来判断。如果限界条件满足，说明有可能导致最优解，即进入右分支，右孩子节点成为活节点，并成为当前的扩展节点，继续向纵深节点扩展； 如果不满足限界条件，则剪掉扩展节点的右分支，开始向最近的活节点回溯。搜索过程直到所有活节点变成死节点后结束。
算法伪码描述如下： 





算法：backtrack(t)

输入：当前扩展节点的层次，根节点为0

if t≥n then//搜索到叶子节点

if bestp < cp then

bestp ← cp//记录当前最优值

bestx ← x［:］//记录当前最优解

else

if cw + w［t］ ≤ W then//判断左分支是否满足约束条件

x［t］ ←1

cw ←cw+w［t］

cp ←cp+v［t］

rp ←rp-v［t］

backtrack(t+1)

cw ←cw-w［t］

cp ←cp-v［t］

rp ←rp+v［t］

if cp+rp > bestp then//判断右分支是否满足限界条件

x［t］←0

backtrack(t+1)



5.3.3实例构造
令n=4，W=7，w=(3,5,2,1)，v=(9,10,7,4)。搜索过程如图514~图518所示。(注： 图中节点旁括号内的数据表示背包的剩余容量和已装入背包的物品价值。)
首先，搜索从根节点开始，即根节点是活节点，也是当前的扩展节点。它代表初始状态，即背包是空的，如图514(a)所示。扩展节点1先沿着左分支扩展，此时需要判断式(51)约束条件，第一种物品的重量为3，3<7，满足约束条件，因此节点2成为活节点，并成为当前的扩展节点。它代表第1种物品已装入背包，背包剩余容量为4，背包内物品的总价值为9，如图514(b)所示。扩展节点2继续沿着左分支扩展，此时需要判断第2个物品能否装入背包，第2个物品的重量为5，背包的剩余容量为4。显然，该物品无法装入，故剪掉扩展节点2的左分支。此时，需要选择扩展节点2的右分支继续扩展，判断式(52)限界条件，cp=9，rp=11，bestp=0，cp+rp>bestp限界条件成立，则节点2沿右分支扩展的节点3成为活节点，并成为当前的扩展节点。扩展节点3代表背包剩余容量为4，背包内物品的总价值为9，如图514(c)所示。以此类推，扩展节点3沿着左分支扩展，第3种物品的重量是2，背包的剩余容量为4，满足约束条件，节点4成为活节点，并成为当前的扩展节点。节点4代表背包剩余容量为2，背包内物品总价值为16，如图514(d)所示。


图51401背包问题的搜索过程（一）


扩展节点4沿着左分支扩展，此时第4种物品的重量为1，背包的剩余容量为2，节点5满足约束条件。节点5已是叶子节点，故找到一个当前最优解，将其记录并修改bestp的值为当前最优解描述的装入背包的物品总价值20，如图515(a)所示。由于节点5已是叶子节点，不具备扩展能力，此时要回溯到离节点5最近的活节点4，节点4再次成为扩展节点，如图515(b)所示。扩展节点4沿着右分支继续扩展，此时要判断限界条件是否满足，cp=16，rp=0，bestp=20，cp+rp<bestp，限界条件不满足，故剪掉节点4的右分支。扩展节点4的左右两个分支均搜索完毕，回溯到最近的活节点3，节点3再次成为扩展节点，如图515(c)所示。扩展节点3沿着右分支继续扩展，此时要判断限界条件是否满足，cp=9，rp=4，bestp=20，cp+rp<bestp，限界条件不满足，故剪掉节点3的右分支。扩展节点3的左右两个分支均搜索完毕，回溯到最近的活节点2，节点2再次成为扩展节点。扩展节点2的两个分支均搜索完毕，故继续回溯到节点1，如图515(d)所示。


图51501背包问题的搜索过程（二）

扩展节点1沿着右分支继续扩展，判断限界条件是否满足，cp=0，rp=21，bestp=20，cp+rp>bestp，限界条件满足，则扩展的节点6成为活节点，并成为当前的扩展节点，如图516(a)所示。扩展节点6沿着左分支继续扩展，判断约束条件，当前背包剩余容量为7，第2种物品的重量为5，5<7，满足约束条件，扩展生成的节点7成为活节点，并且是当前的扩展节点。此时背包的剩余容量为2，装进背包的物品总价值为10，如图516(b)所示。扩展节点7沿着左分支继续扩展，判断约束条件，当前背包剩余容量为2，第3种物品的重量为2，满足约束条件，扩展生成的节点8成为活节点，并且是当前的扩展节点。此时背包的剩余容量为0，装入背包的物品总价值为17，如图516(c)所示。


图51601背包问题的搜索过程（三）

扩展节点8沿着左分支继续扩展，判断约束条件，当前背包剩余容量为0，第4种物品的重量为1，0<1，不满足约束条件，扩展生成的节点被剪掉。接下来沿着扩展节点8的右分支进行扩展，判断限界条件，cp=17，rp=0，bestp=20，cp+rp<bestp，不满足限界条件，沿右分支扩展生成的节点也被剪掉。扩展节点8的所有分支均搜索完毕，回溯到最近的活节点7，节点7又成为扩展节点，如图517(a)所示。扩展节点7沿着右分支继续扩展，判断限界条件，当前cp=10，rp=4，bestp=20，cp+rp<bestp，限界条件不满足，扩展生成的节点被剪掉。扩展节点7的所有分支均搜索完毕，回溯到活节点6，节点6又成为扩展节点，如图517(b)所示。扩展节点6沿着右分支继续扩展，判断限界条件，当前cp=0，rp=11，bestp=20，cp+rp<bestp，限界条件不满足，扩展生成的节点被剪掉。扩展节点6的所有分支均搜索完毕，回溯到活节点1，节点1又成为扩展节点，如图517(c)所示。


图51701背包问题的搜索过程（四）

扩展节点1的两个分支均搜索完毕，它成为死节点，搜索过程结束，找到的问题的解为从根节点1到叶子节点5的路径(1,0,1,1)，即将第1,3,4三种物品装入背包，装进去物品总价值为20，如图518所示。


图51801背包问题的搜索过程（五）




视频讲解



5.3.4算法的改进
在上述限界条件中，rp表示第t+1种物品到第n种物品的总价值。事实上，背包的剩余容量不一定能够容纳从第t+1种物品到第n种物品的全部物品，那么剩余容量所能容纳的从第t+1种物品到第n种物品的最优值(用brp表示)肯定小于或等于rp，用brp取代rp，则式(52)改写为



cp+brp>bestp(53)


01背包问题最终不一定能够将背包装满，因此，cp+brp同样是所有路径经过中间节点z的可行解的价值上界，且这个价值上界小于或等于cp+rp。因此，表达式cp+brp>bestp成立的可能性比cp+rp>bestp成立的可能性要小。用cp+brp>bestp作为限界条件，从中间节点z沿右分支继续向纵深搜索的可能性就小。也就是说，中间节点z的右分支剪枝的可能性就越大，搜索速度也会加快。
以式(53)作为限界条件的搜索过程与以式(52)作为限界条件的搜索过程只有在搜索右分支时进行的判断不同。在以式(53)作为限界条件的搜索过程中，需要求出brp的值，为方便起见，事先计算出所给物品单位重量的价值93,105,72,41。针对剩余的物品，单位重量价值大的物品优先装入背包，将背包剩余容量装满所得的价值即为brp的值。在图514(b)中，扩展节点2沿右分支扩展，判断限界条件，当前cp=9，剩余的不确定状态的物品为第3、4种物品，背包剩余容量为4，将背包装满装入的最优值为第3、4种物品的价值之和，即brp=11，bestp=0，cp+brp>bestp，限界条件成立，扩展的节点3成为活节点，并成为当前的扩展节点，继续向纵深处扩展。式(53)限界条件的搜索与式(52)限界条件的搜索直到图515(b)(找到一个当前最优解后回溯到最近的活节点4)均相同，其后在式(53)限界条件下的搜索过程如图519所示。


图519算法改进后的01背包问题的搜索过程

扩展节点4沿右分支扩展，判断限界条件，cp=16，背包的剩余容量为2，没有剩余物品，故brp=0，bestp=20，cp+brp<bestp，限界条件不满足，扩展生成的节点被剪掉。此时，左右分支均检查完毕，开始回溯到活节点3，节点3又成为扩展节点，如图519(a)所示。扩展节点3沿右分支扩展，判断限界条件，cp=9，剩余容量为4，剩余物品为第4种物品，其重量为1，能够全部装入，故brp=4。bestp=20，cp+brp<bestp，限界条件不满足，扩展生成的节点被剪掉。此时，节点3的左右分支均搜索完毕，回溯到活节点2。节点2的两个分支已搜索完毕，继续回溯到活节点1，活节点1再次成为扩展节点，如图519(b)所示。扩展节点1继续沿右分支扩展，判断限界条件，cp=0，剩余容量为7，剩余物品为第2、3、4种物品，按照单位重量的价值大的物品优先的原则，将第3、4种物品全部装入背包。此时，背包剩余容量为4，第2种物品的重量为5，无法全部装入，只需装入第2种物品的45，那么装进去的价值为10×45=8，故brp=7+4+8=19，cp+brp=19<besp(20)，限界条件不满足，扩展生成的节点被剪掉。此时，左右分支均搜索完毕，搜索过程结束，找到的当前最优解为(1,0,1,1)，最优值为20，如图519(c)所示。
5.3.5算法分析
判断约束函数需O(1)，在最坏情况下有2n-1个左孩子，约束函数耗时最坏为O(2n)。计算上界限界函数需要O(n)时间，在最坏情况下有2n-1个右孩子需要计算上界，限界函数耗时最坏为O(n2n)。01背包问题的回溯算法所需的计算时间为O(2n)+O(n2n)=O(n2n)。
5.3.6Python实战
1. 改进前的算法编码实现


首先定义一个backtrack()递归函数，用于深度优先搜索问题的解，接收当前扩展节点在子集树中所处的层次t，根节点所处的层次为0(考虑到数组下标从0开始，这里将根节点的层次记为0)。搜索过程中记录最优解bestp和最优值bestx。
改进前的算法描述如下： 





def backtrack(t):

global bestp,cw,cp,x,bestx,rp

if t>=n:

if bestp < cp:

bestp = cp

bestx = x［:］

else:

if cw + w［t］ <= W:

x［t］ = 1

cw += w［t］

cp += v［t］

rp -= v［t］

backtrack(t+1)

cw -= w［t］

cp -= v［t］

rp += v［t］

if cp + rp > bestp:

x［t］=0

backtrack(t+1)




Python的入口——main()函数，在main()函数中，提供物品的重量w、物品的价值v和背包的容量W，并做初始化工作，调用backtrack()函数，最后将结果打印输出到显示器上。其代码如下： 





if __name__=="__main__":

bestp=0#当前最优值

cw=0#当前装入背包的重量

cp=0#当前装入背包的价值

bestx=None#记录当前最优解

n=5#物品个数

W=10#背包容量

w=［2,2,6,5,4］#物品重量

v=［6,3,5,4,6］#物品价值

x=［0 for i in range(n)］#当前可行解

rp = 0#剩余物品的价值

for i in range(len(v)):

rp += v［i］

backtrack(0)#从根节点开始搜索

print("最优值为：",bestp)

print("最优解为：",bestx)




输出结果为
最优值为： 15
最优解为： ［1, 1, 0, 0, 1］
2. 改进后算法编码实现
由于要将物品按照单位重量的价值非升序排列，排序后，数组下标不能表示物品编号了，所以采用三元组(物品编号、物品重量和物品价值)数组表示物品，Python中用list列表goods存储所有物品的三元组。
首先定义一个计算价值上界的bound()函数，接收当前剩余的起始物品位置，返回当前节点的价值上界。其代码如下： 





def bound(i):

global c,cw,goods,cp,n

Wleft = c - cw

b=cp

while(i<=n and goods［i］［1］<=Wleft):

Wleft -= goods［i］［1］

b +=goods［i］［2］

i +=1

if(i<=n):

b += goods［i］［2］/goods［i］［1］*Wleft;

return b




定义一个backtrack()递归函数，用于深度优先搜索问题的解，接收当前扩展节点的在子集树中所处的层次t，根节点所处的层次为0(考虑到数组下标从0开始，这里将根节点的层次记为0)。搜索过程中记录最优值bestp和最优解bestx。其代码如下： 





def backtrack(t):

global bestp,c,cw,cp,x,bestx,n,goods

if t>=n:

if bestp < cp:

bestp = cp

bestx = x［:］

else:

if cw + goods［t］［1］ <= c:#左分支判断约束条件

x［goods［t］［0］］ = 1

cw += goods［t］［1］

cp += goods［t］［2］

backtrack(t+1)

cw -= goods［t］［1］

cp -= goods［t］［2］

if bound(t) > bestp:#计算价值上界，并判断限界条件

x［goods［t］［0］］=0

backtrack(t+1)




Python的入口——main()函数，在main()函数中，goods用于存储物品的三元组(物品编号、物品重量和物品价值)，W为背包的容量，初始化求解中用到的其他变量，调用backtrack()重量，最后将结果打印输出到显示器上。其代码如下： 





if __name__=="__main__":

bestp=0#当前最优值

cw=0#当前重量

cp=0#当前价值

bestx=None#最优解

n=5#问题规模

c=10#背包容量

goods = ［(0,2,6),(1,2,3),(2,6,5),(3,5,4),(4,4,6)］#记录物品的编号、重量、价值

x=［0 for i in range(n)］#当前解

goods.sort(key = lambda x:x［2］/x［1］,reverse=True)#按照物品的单位重量的价值由
#大到小排序

backtrack(0)

print("最优值为：",bestp)

print("最优解为：",bestx)




输出结果为
最优值为： 15
最优解为： ［1, 1, 0, 0, 1］



视频讲解



5.4最大团问题——子集树
给定无向图G=(V，E)。如果UV，且对任意u，v∈U，有(u，v)∈E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。最大团问题就是要求找出无向图G的包含顶点个数最多的团。
5.4.1问题分析——解空间及搜索条件
根据问题描述可知，最大团问题就是要求找出无向图G=(V，E)的n个顶点集合{1,2,3,…,n}的一部分顶点V′，即n个顶点集合{1,2,3,…,n}的一个子集，这个子集中的任意两个顶点在无向图Ｇ中都有边相连，且包含顶点个数是n个顶点集合{1,2,3,…,n}所有同类子集中包含顶点个数最多的。显然，问题的解空间是一棵子集树，解决方法与解决01背包问题类似。
1. 定义问题的解空间
问题解的形式为n元组，每一个分量的取值为0或1，即问题的解是一个n元01向量。具体形式为(x1,x2,…,xn)，其中xi=0或1，i=1,2,…,n。xi=1表示图G中第i个顶点在团里，xi=0表示图G中第i个顶点不在团里。
2. 确定解空间的组织结构
解空间是一棵子集树，树的深度为n。
3. 搜索解空间
(1) 确定是否需要约束条件？如果需要，那么应如何设置？
最大团问题的解空间包含2n个子集，这些子集中存在集合中的某两个顶点没边相连的情况。显然，这种情况下的可能解不是问题的可行解。故需要设置约束条件来判断是否有可能导致问题的可行解。
假设当前扩展节点处于解空间树的第t层，那么从第1个顶点到第t-1个顶点的状态(有没有在团里)已经确定。接下来沿着扩展节点的左分支进行扩展，此时需要判断是否将第t个顶点放入团里。只要第t个顶点与第t-1个顶点中的在团里的顶点有边相连，就能放入团中； 否则，就不能放入团中。因此，约束函数描述如下： 





def place(t):

global x

global a

OK=True

for j in range(t):

if x［j］ and a［t］［j］==0:

OK=False

break

return OK




其中，形式参数t表示第t个顶点； place(t)用来判断第t个顶点能否放入团里； 二维数组a是图G的邻接矩阵； 一维数组x记录当前解。搜索到第t层时，从第1个顶点到第t-1个顶点的状态存放在x［1:t-1］中。
(2) 确定是否需要限界条件？如果需要，那么应如何设置？
最大团问题的可行解可能不止一个，问题的目标是找一个包含的顶点个数最多的可行解，即最优解。因此，需要设置限界条件来加速寻找该最优解的速度。
如何设置限界条件呢？与01背包问题类似。假设当前的扩展节点为z，如果z处于第t层，从第1个顶点到第t-1个顶点的状态已经确定，接下来要确定第t个顶点的状态，无论沿着z的哪一个分支进行扩展，第t个顶点的状态就确定了。那么，从第t+1个顶点到第n个顶点的状态还不确定。这样，可以根据前t个顶点的状态确定当前已放入团内的顶点个数(用cn表示)，假想从第t+1个顶点到第n个顶点全部放入团内，放入的顶点个数(用fn表示)fn=n-t，则cn+fn是所有从根出发的路径中经过中间节点z的可行解所包含顶点个数的上界。如果cn+fn小于或等于当前最优解包含的顶点个数(用bestn表示，初始值为0)，就说明从中间节点z继续向子孙节点搜索不可能得到一个比当前更优的可行解，没有继续搜索的必要； 反之，则继续向z的子孙节点搜索。因此，限界条件可描述为cn+fn>bestn。
5.4.2算法设计

最大团问题的搜索和01背包问题的搜索相似，只是进行判断的约束条件和限界条件不同而已。
算法伪码描述如下： 





算法：backtrack(t)

输入：根节点的层次t

输出：全局变量bestx,bestn记录最优解和最优值

if (t > n) then

bestx ← x［:］//记录当前最优解

bestn←cn//记录当前最优值

return

if place(t-1) then //判断t-1号点是否能放到当前表示团的点集，即约
//束条件

x［t-1］←1

cn ← cn + 1

backtrack(t+1)

cn ← cn - 1

if (cn+n-t>bestn) then //判断当前节点有没有可能导致最优解，即限界条件

x［t-1］←0

Backtrack(t+1)



5.4.3实例构造
以图520所示的给定的无向图为例，最大团问题的搜索过程如图521~图527所示。


图520无向图

首先，搜索从根节点开始，即根节点是活节点，也是当前的扩展节点。它代表初始状态，即最大团集合当前是空集，如图521(a)所示。扩展节点A先沿着左分支扩展，此时需要判断约束条件，即1号点能不能放入最大团集合。由于当前集合为空集，满足约束条件，因此节点B成为活节点，并成为当前的扩展节点，它代表1号顶点已经加入最大团集合，如图521(b)所示。扩展节点B继续沿着左分支扩展，此时需要判断2号点能否加入最大团集合，2号点和最大团集合中的1号点有边相连，满足约束条件，因此节点C成为活节点，并成为当前的扩展节点，代表将2号点加入最大团集合，如图521(c)所示。扩展节点C沿着左分支扩展，3号点与最大团集合中的1、2号点都有边相连，满足约束条件，因此节点D成为活节点，并成为当前的扩展节点，节点D代表3号点加入最大团集合，如图521(d)所示。


图521最大团问题的搜索过程（一）


扩展节点D沿着左分支扩展，4号点与最大团集合中的1号点没有边相连，不满足约束条件，D的左孩子被剪掉。沿着D右分支扩展，判断是否满足限界条件，当前最大团集合已经3个点，D的右分支代表4号点不加入最大团集合，剩余没判断是否加入最大团集合的只有5号点，cn(3)+rn(1)>bestn(0)，满足限界条件，因此节点D的右孩子节点E成为活节点，并成为当前的扩展节点，节点E代表4号点不加入最大团集合，如图522(a)所示。


图522最大团问题的搜索过程（二）


扩展节点E沿着左分支扩展，5号点与最大团集合中的1号点没有边相连，不满足约束条件，E的左孩子被剪掉。E的右孩子判断限界条件，当前最大团集合已经3个点，E的右分支代表5号点不加入最大团集合，剩余没判断是否加入最大团集合的点不存在，cn(3)+rn(0)>bestn(0)，满足限界条件，因此节点E的右孩子节点F成为活节点，并成为当前的扩展节点。由于节点E已经是叶子节点，故找到了当前最优解，集合中含有1、2、3节点的团，bestn=3，如图522(b)所示。
开始回溯，节点F回溯到节点E，E的两个分支扩展完毕，E成为死节点。节点E回溯到节点D，D的两个分支扩展完毕，D成为死节点。继续回溯，节点D回溯到节点C，如图522(c)所示。
节点C的右分支还没有扩展，开始扩展C的右分支，判断限界条件： cn(2)+rn(2)>bestn(3)，满足限界条件，节点G成为活节点，并成为当前的扩展节点，如图523(a)所示。开始扩展G的左分支，判断约束条件，4号点与最大团集合中的1号点没有边相连，不满足约束条件，G的左孩子被剪掉。扩展G的右分支，判断限界条件： cn(2)+rn(1)=bestn(3)，不满足限界条件，G的右孩子也被剪掉，节点G成为死节点。算法开始回溯节点C，C的两个分支扩展完毕，C成为死节点，继续回溯到节点B，如图523(b)所示。沿着节点B的右分支扩展，判断限界条件： cn(1)+rn(3)>bestn(3)，满足限界条件，节点H成为活节点，并成为当前的扩展节点，如图523(c)所示。


图523最大团问题的搜索过程（三）


开始扩展H的左分支，判断约束条件，3号点与最大团集合中的1号点有边相连，满足约束条件，H的左孩子节点I成为活节点，并成为当前的扩展节点，如图524(a)所示。扩展I的左分支，判断约束条件，4号点与最大团集合中的1号点没有边相连，不满足约束条件，I的左孩子被剪掉。扩展I的右分支，判断限界条件cn(2)+rn(1)=bestn(3)，不满足限界条件，I的右孩子也被剪掉，节点I成为死节点。算法开始回溯节点H，如图524(b)所示。扩展H的右分支，判断限界条件： cn(1)+rn(2)=bestn(3)，不满足限界条件，H的右分支被剪掉。算法开始回溯节点B，节点B的两个分支都扩展完毕，成为死节点，继续回溯到节点A，如图524(c)所示。


图524最大团问题的搜索过程（四）


开始扩展A的右分支，判断限界条件cn(0)+rn(4)>bestn(3)，满足限界条件，A的右孩子J成为活节点，并成为当前的扩展节点，如图525(a)所示。扩展J的左分支，判断约束条件，当前最大团集合是空集，满足约束条件，J的左孩子节点K成为活节点，并成为当前的扩展节点，2号点加入最大团集合，如图525(b)所示。扩展K的左分支，判断约束条件，3号点与最大团集合中的2号点有边相连，满足约束条件，K的左孩子节点L成为活节点，并成为当前的扩展节点，3号点加入最大团集合，如图525(c)所示。


图525最大团问题的搜索过程（五）


扩展L的左分支，判断约束条件，4号点与最大团集合中的2、3号点有边相连，满足约束条件，L的左孩子节点M成为活节点，并成为当前的扩展节点，4号点加入最大团集合，如图526(a)所示。扩展M的左分支，判断约束条件，5号点与最大团集合中的2、3、4号点有边相连，满足约束条件，M的左孩子节点N成为活节点，并成为当前的扩展节点，5号点加入最大团集合，如图526(b)所示。开始回溯，节点N回溯到M，扩展M的右分支，判断限界条件： cn(3)+rn(0)<bestn(4)，不满足限界条件，M的右分支被剪掉。继续回溯到节点L，扩展L的右分支，判断限界条件： cn(2)+rn(1)<bestn(4)，不满足限界条件，L的右分支被剪掉。继续回溯到节点K，扩展K的右分支，判断限界条件： cn(1)+rn(2)<bestn(4)，不满足限界条件，K的右分支被剪掉。继续回溯到节点J，扩展J的右分支，判断限界条件： cn(0)+rn(3)<bestn(4)，不满足限界条件，J的右分支被剪掉。继续回溯到节点A，如图526(c)所示。


图526最大团问题的搜索过程（六）


A的两个分支都搜索完毕，算法结束，形成的搜索树如图527所示。

找到问题的解是从根节点A到叶子节点N的路径(0,1,1,1,1)已在图527所示中用粗实线画出，求得的最大团如图528所示。



图527最大团问题的搜索树




图528求得的最大团


5.4.4算法分析
判断约束函数需耗时O(n)，在最坏情况下有2n-1个左孩子，耗时最坏为O(n2n)。判断限界函数需要O(1)时间，在最坏情况下有2n-1个右孩子节点需要判断限界函数，耗时最坏为O(2n)。因此，最大团问题的回溯算法所需的计算时间为O(2n)+O(n2n)=O(n2n)。
5.4.5Python实战
首先定义一个place()函数，用于判断指定的点是否能加入到最大团集合中。该函数接收待判定的点，返回True或False，True表示指定点能放入最大团集合，False表示指定点不能放入最大团集合。其代码如下： 





def place(t):

global x

global a

OK=True

for j in range(t):

if x［j］ and a［t］［j］==0:

OK=False

break

return OK




定义一个递归深度优先搜索的backtrack()函数，搜索最优解。代码如下： 





def  backtrack(t):

global cn,bestn,n,bestx,x

if (t > n):

bestx = x［:］

bestn=cn

return

if place(t-1):

x［t-1］=1

cn += 1

backtrack(t+1)

cn -= 1

if (cn+n-t>bestn):

x［t-1］=0

backtrack(t+1)




Python的入口——main()函数，在main()函数中，用邻接矩阵存储给定的图G，调用backtrack（）函数，求最优解和最优值，最后将结果打印输出到显示器上。其代码如下： 





if __name__ =="__main__":

a = ［［0,1,1,0,0］,［1,0,1,1,1］,［1,1,0,1,1］,［0,1,1,0,1］,［0,1,1,1,0］］

n = len(a)

x=［i for i in range(n)］

bestx =None

bestn = cn = 0

backtrack(1)#根节点的层次为1

print("最大团点个数：", bestn)

print("最大团为：", bestx)




输出结果为
最大团点个数： 4
最大团为： ［0, 1, 1, 1, 1］



视频讲解



5.5批处理作业调度问题——排列树
给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，再由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业Ji在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作业，制订出最佳作业调度方案，使其完成时间和达到最小。
5.5.1问题分析——解空间及搜索条件
根据问题描述可知，批处理作业调度问题要求找出n个作业{J1,J2,…,Jn}的一个排列，按照这个排列的顺序进行调度，使得完成n个作业的完成时间和最小。按照回溯法的算法框架，首先需要定义问题的解空间，然后确定解空间的组织结构，最后进行搜索。搜索前要解决两个关键问题，一是确定问题是否需要约束条件(判断是否有可能产生可行解的条件)，如果需要，那么如何设置。由于作业的任何一种调度次序不存在无法调度的情况，均是合法的。因此，任何一个排列都表示问题的一个可行解。故不需要约束条件； 二是确定问题是否需要限界条件，如果需要，那么如何设置。在n个作业的n!种调度方案(排列)中，存在完成时间和多与少的情况，该问题要求找出完成时间和最少的调度方案。因此，需要设置限界条件。
1. 确定问题的解空间
批处理作业调度问题解的形式为(x1,x2,…,xn)，分量xi(i=1,2,…,n)表示第i个要调度的作业编号。设n个作业组成的集合为S={1,2,…,n}，xi∈S-{x1,x2,…,xi-1}，i=1,2,…,n。
2. 解空间的组织结构
解空间的组织结构是一棵排列树，树的深度为n。
3. 搜索解空间
(1)由于不需要约束条件，故无须设置。
(2) 设置限界条件。
用cf表示当前已完成调度的作业所用的时间和，用bestf表示当前找到的最优调度方案的完成时间和。显然，继续向纵深处搜索时，cf不会减少，只会增加。因此当cf≥bestf时，没有继续向纵深处搜索的必要。限界条件可描述为cf<bestf，cf的初始值为0，bestf的初始值为＋∞。
5.5.2算法设计
扩展节点沿着某个分支扩展时需要判断限界条件，如果满足，就进入深一层继续搜索； 如果不满足，就将扩展生成的节点剪掉。搜索到叶子节点时，即找到当前最优解。搜索过程直到全部活节点变成死节点为止。
算法伪码描述如下： 





算法：backtrack(t)

输入：扩展节点的层次i，根节点层次为1

输出：最优解bestx和最优值bestf

if (t ≥ n):

bestx ←x［:］

bestf← f

else:

for j ←t to n-1:

f1 ← f1+ M［x［j］］［1］

k ← t-1

f2［t］ ← max(f2［k］,f1)+M［x［j］］［2］

f ←f+f2［t］

if (f < bestf):

x［t］x［j］

Backtrack(t+1)

x［t］x［j］

f1 ←f1-M［x［j］］［1］

f ← f-f2［t］



5.5.3实例构造
考虑n=3的实例，每个作业在两台机器上的处理时间如表51所示。


表51作业在两台机器上的处理时间


作业机器1机器2


J121
J231
J323
注： 行分别表示作业J1、J2和J3； 列分别表示机器1和机器2。表中数据表示tji，即作业Ji需要机器j的处理时间。

搜索过程如图529~图535所示。从根节点A开始，节点A成为活节点，并且是当前的扩展节点，如图529(a)所示。扩展节点A沿着x1=1的分支扩展，F11=2，F21=3，故cf=3，bestf=+∞，cf<bestf，限界条件满足，扩展生成的节点B成为活节点，并且成为当前的扩展节点，如图529(b)所示。扩展节点B沿着x2=2的分支扩展，F12=5，F22=6，故cf=F21+F22=9，bestf=+∞，cf<bestf，限界条件满足，扩展生成的节点E成为活节点，并且成为当前的扩展节点，如图529(c)所示。扩展节点E沿着x3=3的分支扩展，F13=7，F23=10，故cf=F21+F22+F23=19,bestf=+∞,cf<bestf，限界条件满足，扩展生成的节点K是叶子节点。此时，找到当前最优的一种调度方案(1,2,3)，同时修改bestf=19，如图529(d)所示。


图529批处理作业调度问题的搜索过程（一）

叶子节点K不具备扩展能力，开始回溯到活节点E。节点E只有一个分支，且已搜索完毕，因此节点E成为死节点，继续回溯到活节点B，节点B再次成为扩展节点，如图530(a)所示。扩展节点B沿着x2=3的分支扩展，cf=10，bestf=19，cf<bestf，限界条件满足，扩展生成的节点F成为活节点，并且成为当前的扩展节点，如图530(b)所示。扩展节点F沿着x3=2的分支扩展，cf=18，bestf=19，cf<bestf，限界条件满足，扩展生成的节点L是叶子节点。此时，找到比先前更优的一种调度方案(1,3,2)，修改bestf=18，如图530(c)所示。从叶子节点L开始回溯到活节点F。节点F的一个分支已搜索完毕，节点F成为死节点，回溯到活节点B。节点B的两个分支已搜索完毕，回溯到活节点A，节点A再次成为扩展节点，如图530(d)所示。


图530批处理作业调度问题的搜索过程（二）

扩展节点A沿着x1=2的分支扩展，cf=4，bestf=18，cf<bestf，限界条件满足，扩展生成的节点C成为活节点，并且成为当前的扩展节点，如图531(a)所示。扩展节点C沿着x2=1的分支扩展，cf=10，bestf=18，cf<bestf，限界条件满足，扩展生成的节点G成为活节点，并且成为当前的扩展节点，如图531(b)所示。扩展节点G沿着x3=3的分支扩展，cf=20，bestf=18，cf>bestf，限界条件不满足，扩展生成的节点被剪掉，如图531(c)所示。


图531批处理作业调度问题的搜索过程（三）

节点G的一个分支搜索完毕，节点G成为死节点，继续回溯到活节点C，如图532(a)所示。扩展节点C沿着x2=3的分支扩展，cf=12，bestf=18，cf<bestf，限界条件满足，扩展生成的节点H成为活节点，并且成为当前的扩展节点，如图532(b)所示。扩展节点H沿着x3=1的分支扩展，cf=21，bestf=18，cf>bestf，限界条件不满足，扩展生成的节点被剪掉。节点H的一个分支搜索完毕，开始回溯到活节点C。此时，节点C的两个分支已搜索完毕，继续回溯到活节点A，节点A再次成为当前的扩展节点，如图532(c)所示。


图532批处理作业调度问题的搜索过程（四）

扩展节点A沿着x1=3的分支扩展，cf=5，bestf=18，cf<bestf，限界条件满足，扩展生成的节点D成为活节点，并且成为当前的扩展节点，如图533(a)所示。扩展节点D沿着x2=1的分支扩展，cf=11，bestf=18，cf<bestf，限界条件满足，扩展生成的节点I成为活节点，并且成为当前的扩展节点，如图533(b)所示。


图533批处理作业调度问题的搜索过程（五）

扩展节点I沿着x3=2的分支扩展，cf=19，bestf=18，cf>bestf，限界条件不满足，扩展生成的节点被剪掉，开始回溯到活节点D，节点D再次成为当前的扩展节点，如图534(a)所示。扩展节点D沿着x2=2的分支扩展，cf=11，bestf=18，cf<bestf，限界条件满足，扩展生成的节点J成为活节点，并且成为当前的扩展节点，如图534(b)所示。


图534批处理作业调度问题的搜索过程（六）

扩展节点J沿着x3=1的分支扩展，cf=19，bestf=18，cf>bestf，限界条件不满足，扩展生成的节点被剪掉，开始回溯到活节点D，节点D的两个分支搜索完毕，继续回溯到活节点A，如图535(a)所示。活节点A的三个分支也已搜索完毕，节点A变成死节点，搜索结束。至此，找到的最优的调度方案为从根节点A到叶子节点L的路径(1, 3, 2)，如图535(b)所示。


图535批处理作业调度问题的搜索过程（七）

5.5.4算法分析
计算限界函数需要O(1)时间，需要判断限界函数的节点在最坏情况下有1+n+n(n-1)+n(n-1)(n-2)+…+n(n-1)+…+2≤nn!个，故耗时O(nn!)； 在叶子节点处记录当前最优解需要耗时O(n)，在最坏情况下会搜索到每一个叶子节点，叶子节点有n!个，故耗时为O(nn!)。因此，批处理作业调度问题的回溯算法所需的计算时间为O(nn!)+O(nn!)=O（nn!）。
5.5.5Python实战
定义一个深度优先搜索的backtrack()函数，搜索最优解。其代码如下： 




def backtrack(t):

global f1,f2,f,x,M,bestf,bestx,n

if (t >= n):#搜索到叶子节点

bestx = x［:］#记录当前最优解

bestf = f#记录当前最优值

else:

for j in range(t,n):

f1 += M［x［j］］［1］#计算第一台机器上的完成时间

k = t-1#t号作业的前一个作业

f2［t］ = max(f2［k］,f1)+M［x［j］］［2］#计算第二台机器上的完成时间

f += f2［t］#计算第二台机器上的完成时间和

if (f < bestf):#判断限界条件

x［t］,x［j］ = x［j］,x［t］ 

backtrack(t+1)#递归搜索

x［t］,x［j］ = x［j］,x［t］

f1 -= M［x［j］］［1］

f -= f2［t］




Python的入口——main()函数，在main()函数中，给定各个作业在两台机器上的处理时间M，初始化相关辅助变量，调用backtrack()函数，求最优解和最优值，最后将结果打印输出到显示器上。其代码如下： 





if __name__ =="__main__":

import sys

M = ［［0,0,0］,［0,2,1］,［0,3,1］,［0,2,3］］#牺牲第0行第0列，从下标1开始有效

f = 0#记录完成时间和

f1 = 0#记录第一台机器的完成时间和

n = len(M)

f2 =［i for i in range(n)］#记录各作业在第二台机器上的完成时间和

x = ［i for i in range(n)］

bestf = sys.maxsize#记录最优值，初始化为无穷大

bestx= None#记录最优解

backtrack(1)

print("最优解为:" ,bestx)

print("最优值为：", bestf)




输出结果为
最优解为: ［0, 1, 3, 2］
最优值为： 18



视频讲解



5.6旅行商问题——排列树
设有n个城市组成的交通图，一个售货员从住地城市出发，到其他城市各一次去推销货物，最后回到住地城市。假定任意两个城市i，j之间的距离dij(dij=dji)是已知的，问应该怎样选择一条最短的路线？
5.6.1问题分析——解空间及搜索条件
旅行商问题给定n个城市组成的无向带权图G=(V，E)，顶点代表城市，权值代表城市之间的路径长度。要求找出以住地城市开始的一个排列，按照这个排列的顺序推销货物，所经路径长度是最短的。问题的解空间是一棵排列树。显然，对于任意给定的一个无向带权图，存在某两个城市(顶点)之间没有直接路径(边)的情况。也就是说，并不是任何一个以住地城市开始的排列都是一条可行路径(问题的可行解)，因此需要设置约束条件，判断排列中相邻两个城市之间是否有边相连，有边相连则能走通； 反之，不是可行路径。另外，在所有可行路径中，要找一条最短的路线，因此需要设置限界条件。
1. 定义问题的解空间
旅行商问题的解空间形式为n元组(x1,x2,…,xn)，分量xi(i=1,2,…,n)表示第i个去推销货物的城市号。假设住地城市编号为城市1，其他城市顺次编号为2,3,…,n。n个城市组成的集合为S={1,2,…,n}。由于住地城市是确定的，因此x1的取值只能是住地城市，即x1=1，xi∈S-{x1,x2,…,xi-1}，i=2,…,n。
2. 确定解空间的组织结构
该问题的解空间是一棵排列树，树的深度为n。n=4的旅行商问题的解空间树如图536所示。


图536n=4的解空间树

3. 搜索解空间
(1) 设置约束条件。
用二维数组g［］［］存储无向带权图的邻接矩阵，如果g［i］［j］≠∞表示城市i和城市j有边相连，能走通。
(2) 设置限界条件。
用cl表示当前已走过的城市所用的路径长度，用bestl表示当前找到的最短路径的路径长度。显然，继续向纵深处搜索时，cl不会减少，只会增加。因此当cl≥bestl时，没有继续向纵深处搜索的必要。限界条件可描述为cl<bestl，cl的初始值为0，bestl的初始值为＋∞。
5.6.2算法设计
扩展节点沿着某个分支扩展时需要判断约束条件和限界条件，如果两者都满足，就进入深一层继续搜索。反之，剪掉扩展生成的节点。搜索到叶子节点时，找到当前最优解。搜索过程直到全部活节点变成死节点。
算法伪码描述如下： 





算法：backtrack(t):

输入：节点所处的层次，根节点层次为1

输出：最优解和最优值

g_n ← n-1

if (t == g_n) then //g_n是问题的规模

if (a［x［g_n-1］］［x［g_n］］ != NoEdge and  a［x［g_n］］［1］ != NoEdge and (cc + a［x［g_n-1］］［x［g_n］］ + a［x［g_n］］［1］ < bestc or bestc == NoEdge)) then//判断约束条件和限界条件

bestx ← x［:］//记录当前最优解

bestc← cc + a［x［g_n-1］］［x［g_n］］ + a［x［g_n］］［1］//记录当前最优值

else

for j ←i to n-1 do //控制搜索扩展节点的所有
//分支

if (a［x［i-1］］［x［j］］ != NoEdge and (cc + a［x［i-1］］［x［i］］ < bestc or bestc == NoEdge)) then //判断约束条件和限界条件

x［i］ x［j］ 

cc←cc + a［x［i-1］］［x［i］］

backtrack(i+1)

cc ←cc - a［x［i-1］］［x［i］］

x［i］ x［j］



5.6.3实例构造
考虑n=5的无向带权图，如图537所示。



图537无向带权图


搜索过程如图538~图542所示。由于排列的第一个元素已经确定，即推销员的住地城市1，搜索从根节点A0的孩子节点A开始，节点A是活节点，并且成为当前的扩展节点，如图538(a)所示。扩展节点A沿着x2=2的分支扩展，城市1和城市2有边相连，约束条件满足； cl=10，bestl=∞，cl<bestl，限界条件满足，扩展生成的节点B成为活节点，并且成为当前的扩展节点，如图538(b)所示。扩展节点B沿着x3=3的分支扩展，城市2和城市3有边相连，约束条件满足； cl=25，bestl=∞，cl<bestl，限界条件满足，扩展生成的节点C成为活节点，并且成为当前的扩展节点，如图538(c)所示。扩展节点C沿着x4=4的分支扩展，城市3和城市4有边相连，约束条件满足； cl=32，bestl=∞，cl<bestl，限界条件满足，扩展生成的节点D成为活节点，并且成为当前的扩展节点，如图538(d)所示。


图538旅行商问题的搜索过程（一）

扩展节点D沿着x5=5的分支扩展，城市4和城市5有边相连，约束条件满足； cl=38，bestl=∞，cl<bestl，限界条件满足，扩展生成的节点E是叶子节点。由于城市5与住地城市1有边相连，故找到一条当前最优路径(1,2,3,4,5)，其长度为50，修改bestl=50，如图539(a)所示。接下来开始回溯到节点D，再回溯到节点C，C成为当前的扩展节点，如图539(b)所示。


图539旅行商问题的搜索过程（二）

以此类推，第一次回溯到第二层的节点A时的搜索树如图540所示。节点旁边的“×”表示不能从推销货物的最后一个城市回到住地城市。


图540旅行商问题的搜索过程（三）

第二层的节点A再次成为扩展节点，开始沿着x2=3的分支扩展，城市1和城市3之间没有边相连，不满足约束条件，扩展生成的节点被剪掉。沿着x2=4的分支扩展，满足约束条件和限界条件，进入其扩展的孩子节点继续搜索。搜索过程略。此时，找到当前最优解(1，4，3，2，5)，路径长度为43。直到第二次回溯到第二层的节点A时所形成的搜索树如图541所示。


图541旅行商问题的搜索过程（四）

节点A沿着x2=5的分支扩展，满足约束条件和限界条件，进入其扩展的孩子节点继续搜索，搜索过程略。直到第三次回溯到第二层的节点A时所形成的搜索树如图542所示。此时，搜索过程结束，找到的最优解为图542中粗线条描述的路径(1,4,3,2,5)，路径长度为43。


图542旅行商问题的搜索过程（五）

5.6.4算法分析
判断限界函数需要O(1)时间，在最坏情况下有1+(n-1)+［(n-1)(n-2)］+…+［(n-1)(n-2)·…·2］≤n(n-1)!个节点需要判断限界函数，故耗时O(n!)； 在叶子节点处记录当前最优解需要耗时O(n)，在最坏情况下会搜索到每一个叶子节点，叶子节点有(n-1)!个，故耗时为O(n!)。因此，旅行售货员问题的回溯算法所需的计算时间为O(n!)+O(n!)=O(n!)。
5.6.5Python实战
定义一个深度优先搜索的backtrack()函数，搜索最优解。其代码如下： 





def backtrack(t):

global n,a,x,bestc,NoEdge,cc,bestx

g_n = n-1

if (t == g_n):#g_n是问题的规模

if (a［x［g_n-1］］［x［g_n］］ != NoEdge and  a［x［g_n］］［1］ != NoEdge and (cc + a［x［g_n-1］］［x［g_n］］ + a［x［g_n］］［1］ < bestc or bestc == NoEdge)):

bestx = x［:］

bestc = cc + a［x［g_n-1］］［x［g_n］］ + a［x［g_n］］［1］

else:

for j in range(t,n):

if (a［x［t-1］］［x［j］］ != NoEdge and (cc + a［x［t-1］］［x［t］］ < bestc or bestc == NoEdge)):

x［t］, x［j］ = x［j］, x［t］

cc += a［x［t-1］］［x［t］］

backtrack(t+1)

cc -= a［x［t-1］］［x［t］］

x［t］, x［j］ = x［j］, x［t］




Python的入口——main()函数，在main()函数中，用邻接矩阵a存储无向带权图，牺牲0行0列位置的存储单元，下标从1开始有效。初始化相关辅助变量，调用backtrack()函数，求最优解和最优值，最后将结果打印输出到显示器上，最优解数组bestx的0号单元舍弃，下标也从1开始有效。其代码如下： 





if __name__ == "__main__":

import sys

NoEdge = sys.maxsize

a = ［［0,0,0,0,0,0］,［0,NoEdge,10,NoEdge,4,12］,［0,10,NoEdge,15,8,5］,［0,NoEdge,15,NoEdge,7,30］,［0,4,8,7,NoEdge,6］,［0,12,5,30,6,NoEdge］］

n = len(a)

x = ［i for i in range(n)］

bestx =None

bestc = NoEdge

cc = 0

backtrack(2)#第一个城市固定，所以从第二层开始搜索

print("最短路径长度为：", bestc)

print("最短路径为：", bestx)




输出结果为
最短路径长度为： 43
最短路径为： ［0, 1, 4, 3, 2, 5］



视频讲解



5.7图的m着色问题——满m叉树
给定无向连通图G=(V，E) 和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中有边相连的两个顶点着不同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图G和m 种颜色，找出所有不同的着色方法。
5.7.1问题分析——解空间及搜索条件
该问题中每个顶点所着的颜色均有m种选择，n个顶点所着颜色的一个组合是一个可能的解。根据回溯法的算法框架，定义问题的解空间及其组织结构是很容易的。需不需要设置约束条件和限界条件呢？从给定的已知条件来看，无向连通图G中假设有n个顶点，它肯定至少有n-1条边，有边相连的两个顶点所着颜色不相同，n个顶点所着颜色的所有组合中必然存在不是问题着色方案的组合，因此需要设置约束条件； 而针对所有可行解(组合)，不存在可行解优劣的问题。所以，不需要设置限界条件。
1. 定义问题的解空间
图的m着色问题的解空间形式为(x1,x2,…,xn)，分量xi(i=1,2,…,n)表示第i个顶点着第xi号颜色。m种颜色的色号组成的集合为S={1,2，…,m}，xi∈S，i=1,2,…,n。
2. 确定解空间的组织结构
问题的解空间组织结构是一棵满m叉树，树的深度为n。
3. 搜索解空间
(1) 设置约束条件。
当前顶点要和前面已确定颜色且有边相连的顶点所着颜色不相同。假设当前扩展节点所在的层次为t，则下一步扩展就是要判断第t个顶点着什么颜色，第t个顶点所着的颜色要与已经确定所着颜色的第1~(t-1)个顶点中与其有边相连的颜色不相同。
约束函数代码描述如下：  





def Ok(k):

for j in range(1,k):

if ((a［k］［j］==1) and (x［j］==x［k］)):

return False

return True




(2) 无须设置限界条件。
5.7.2算法设计
扩展节点沿着某个分支扩展时需要判断约束条件，如果满足，就进入深一层继续搜索； 如果不满足，就扩展生成的节点被剪掉。搜索到叶子节点时，找到一种着色方案。搜索过程直到全部活节点变成死节点为止。
算法伪码描述如下： 





算法：backtrack(t)

输入：扩展节点的层次，根节点层次为1

输出：最优解和最优值

if (t>n) then

sum1 ← sum+1//着色方案数

用colors记录着色方案

else

for  i←1 to m do//循环m种颜色

x［t］←i

if (Ok(t)) then //判断约束条件

backtrack(t+1)



5.7.3实例构造

给定如图543所示的无向连通图和m=3。


图543无向连通图

图的m着色问题的搜索过程如图544~图549所示。从根节点A开始，节点A是当前的活节点，也是当前的扩展节点，它代表的状态是给定无向连通图中任何一个顶点还没有着色，如图544(a)所示。沿着x1=1分支扩展，满足约束条件，生成的节点B成为活节点，并且成为当前的扩展节点，如图544(b)所示。扩展节点B沿着x2=1分支扩展，不满足约束条件，生成的节点被剪掉。然后沿着x2=2分支扩展，满足约束条件，生成的节点C成为活节点，并且成为当前的扩展节点，如图544(c)所示。扩展节点C沿着x3=1，2分支扩展，均不满足约束条件，生成的节点被剪掉。然后沿着x3=3分支扩展，满足约束条件，生成的节点D成为活节点，并且成为当前的扩展节点，如图544(d)所示。


图544图的m着色问题的搜索过程（一）

扩展节点D沿着x4=1分支扩展，满足约束条件，生成的节点E成为活节点，并且成为当前的扩展节点，如图545(a)所示。扩展节点E沿着x5=1，2分支扩展，均不满足约束条件，生成的节点被剪掉。然后沿着x5=3分支扩展，满足约束条件，生成的节点F是叶子节点。此时，找到了一种着色方案，如图545(b)所示。从叶子节点F回溯到活节点E，节点E的所有孩子节点已搜索完毕，因此它成为死节点。继续回溯到活节点D，节点D再次成为扩展节点，如图545(c)所示。


图545图的m着色问题的搜索过程（二）

扩展节点D沿着x4=2和x4=3分支扩展，均不满足约束条件，生成的节点被剪掉。再回溯到活节点C。节点C的所有孩子节点搜索完毕，它成为死节点，继续回溯到活节点B，节点B再次成为扩展节点，如图546(a)所示。扩展节点B沿着x2=3分支继续扩展，满足约束条件，生成的节点G成为活节点，并且成为当前的扩展节点，如图546(b)所示。扩展节点G沿着x3=1分支扩展，不满足约束条件，生成的节点被剪掉； 然后沿着x3=2分支扩展，满足约束条件，生成的节点H成为活节点，并且成为当前的扩展节点，如图546(c)所示。


图546图的m着色问题的搜索过程（三）

扩展节点H沿着x4=1分支扩展，满足约束条件，生成的节点I成为活节点，并且成为当前的扩展节点，如图547(a)所示。扩展节点I沿着x5=1分支扩展，不满足约束条件，生成的节点被剪掉； 然后沿着x5=2分支扩展，满足约束条件，J已经是叶子节点，找到第2种着色方案，如图547(b)所示。从叶子节点J回溯到活节点I，节点I再次成为扩展节点，如图547(c)所示。


图547图的m着色问题的搜索过程（四）

沿着节点I的 x5=3分支扩展的节点不满足约束条件，被剪掉。此时节点I成为死节点。继续回溯到活节点H，节点H再次成为扩展节点，如图548(a)所示。沿着节点H的x4=2，3分支扩展的节点不满足约束条件，被剪掉。此时节点H成为死节点。继续回溯到活节点G，节点G再次成为扩展节点，如图548(b)所示。沿着节点G的x3=3分支扩展的节点不满足约束条件，被剪掉。此时节点G成为死节点。继续回溯到活节点B，节点B的孩子节点已搜索完毕，继续回溯到节点A，如图548(c)所示。


图548图的m着色问题的搜索过程（五）

以此类推，扩展节点A沿着x1=2，3分支扩展的情况如图549所示。


图549图的m着色问题的搜索过程（六）

最终找到6种着色方案，分别为根节点A到如图549(b)所示的叶子节点F、J、O、S、X、I的路径，即(1,2,3,1,3)、(1,3,2,1,2)、(2,1,3,2,3)、(2,3,1,2,1)、(3,1,2,3,2)和(3,2,1,3,1)。

5.7.4算法分析
计算限界函数需要O(n)时间，需要判断限界函数的节点在最坏情况下有1+m+m2+m3+…+mn-1=(mn-1)/(m-1)个，故耗时O(nmn)； 在叶子节点处输出着色方案需要耗时O(n)，在最坏情况下会搜索到每一个叶子节点，叶子节点有mn个，故耗时为O(nmn)。图的m着色问题的回溯算法所需的计算时间为O(nmn)+O(nmn)=O(nmn)。
5.7.5Python实战
1. 数据结构选择

选用邻接矩阵a存储图G，用二维列表存储所有的着色方案，用一维列表存储当前着色方案。
2. 编码实现
首先定义ok()函数，接收待着色的第k号顶点编号，输出是否都能为该点着相应的颜色x［k］。True表示k号顶点能着x［k］号色； False表示k号顶点不能着x［k］号色。其代码如下： 





#牺牲下标为0的单元

def ok(k):

for j in range(1,k):

if ((a［k］［j］==1) and (x［j］==x［k］)):

return False

return True




定义一个深度优先搜索的backtrack()函数，搜索所有可能的着色方案，并统计着色方案数。其代码如下： 





def backtrack(t):

global colors,x,sum1,n,m,a

if (t>n):#搜索到叶子节点

sum1 += 1

colors.append(x［:］)

else:

for  i in range(1,m+1):#搜索中间节点的每一个分支，即尝试着任何一种颜色

x［t］=i

if (Ok(t)):

backtrack(t+1)




Python的入口——main()函数，在main()函数中，用邻接矩阵a存储无向图，牺牲0行0列位置的存储单元，下标从1开始有效。初始化相关辅助变量，调用backtrack()函数，求所有可能的着色方案，最后将结果打印输出到显示器上。输出结果中，0号存储单元数据无效，从下标1开始有效。其代码如下： 





if __name__ =="__main__":

a = ［［0,0,0,0,0,0］,［0,0,1,1,0,0］,［0,1,0,1,1,1］,［0,1,1,0,1,0］,［0,0,1,1,0,1］,［0,0,1,0,1,0］］

n = len(a) - 1

m = 3

sum1 = 0

colors = ［］

x = ［0 for i in range(n + 1)］

backtrack(1)

for i in range(len(colors)):

print(colors［i］)

print("共有："+str(sum1)+"种着色方案")




输出结果为
［0, 1, 2, 3, 1, 3］
［0, 1, 3, 2, 1, 2］
［0, 2, 1, 3, 2, 3］
［0, 2, 3, 1, 2, 1］
［0, 3, 1, 2, 3, 2］
［0, 3, 2, 1, 3, 1］
共有： 6种着色方案


视频讲解



5.8最小质量机器设计问题——满m叉树
设某一机器由n个部件组成，每一个部件可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的质量，cij是相应的价格。试设计一个算法，给出总价格不超过c的最小质量机器设计。
5.8.1问题分析——解空间及搜索条件
该问题实质上是为机器部件选供应商。机器由n个部件组成，每个部件有m个供应商可以选择，要求找出n个部件供应商的一个组合，使其满足n个部件总价格不超过c且总重量是最小的。显然，这个问题存在n个部件供应商的组合不满足总价格不超过c的条件，因此需要设置约束条件； 在n个部件供应商的组合满足总价格不超过c的前提下，哪个组合的总重量最小呢？问题要求找出总重量最小的组合，故需要设置限界条件。
1. 定义问题的解空间
该问题的解空间形式为(x1,x2,…,xn)，分量xi(i=1,2,…,n)表示第i个部件从第xi个供应商处购买。m个供应商的集合为S={1,2，…,m}，xi∈S，i=1,2,…,n。
2. 确定解空间的组织结构
问题解空间的组织结构是一棵满m叉树，树的深度为n。
3. 搜索解空间
(1) 设置约束条件。约束条件设置为∑ni=1cixi≤c。
(2) 设置限界条件。
假设当前扩展节点所在的层次为t，则下一步扩展就是要判断第t个零件从哪个供应商处购买。如果第1~t 个部件的重量之和大于或等于当前最优值，就没有继续深入搜索的必要。因为，再继续深入搜索也不会得到比当前最优解更优的一个解。令第1~t 个部件的重量之和用cw=∑ti=1wixi表示，价格之和用cc表示，二者初始值均为0。当前最优值用bestw表示，初始值为+∞，限界条件可描述为cw<bestw。
5.8.2算法设计
与图的m着色问题相同。
算法伪码描述如下： 





算法：backtrack(t)

输入：扩展节点所处从层次，根节点层次为1

输出：最小质量机器设计问题最优方案bestx及最优值bestw

if(t>n) then //搜索到解空间树的叶子节点

bestw ← cw

bestx ← x［:］

return

for j←1 to m do//循环m个供应商

x［t］←j //第t个部件从j供应商处购买

if(cc+c［t］［j］≤COST and  cw+w［t］［j］<bestw) then//判断约束条件和限界条件

cc←cc+c［t］［j］

cw←cw+w［t］［j］

backtrack(t+1)

cc←cc-c［t］［j］

cw←cw-w［t］［j］




5.8.3实例构造
考虑n=3，m=3，c=7的实例。部件的质量如表52所示、价格如表53所示。
最小质量机器设计问题的搜索过程如图550~图555所示(注： 图中节点旁括号内的数据为已选择部件的重量之和、价格之和)。




表52部件的质量表


供应商1供应商2供应商3


部件1123
部件2321
部件3232



表53部件的价格表


Cij 供应商1供应商2供应商3


部件1123
部件2542
部件3212


注： 行分别表示部件1、2和3； 列分别表示供应商1、2和3； 表中数据表示wij： 从供应商j处购得的部件i的质量; cij表示从供应商j处购得的部件i的价格。
从根节点A开始进行搜索，A是活节点且是当前的扩展节点，如图550(a)所示。扩展节点A沿x1=1分支扩展，cc=1≤c，满足约束条件； cw=1,bestw=∞，cw<bestw，满足限界条件。扩展生成的节点B成为活节点，并且成为当前的扩展节点，如图550(b)所示。扩展节点B沿x2=1分支扩展，cc=6≤c，满足约束条件； cw=4,bestw=∞,cw<bestw，满足限界条件。扩展生成的节点C成为活节点，并且成为当前的扩展节点，如图550(c)所示。扩展节点C沿x3=1分支扩展，cc=8>c，不满足约束条件，扩展生成的节点被剪掉。然后沿x3=2分支扩展，cc=7≤c，满足约束条件； cw=7,bestw=∞,cw<bestw，满足限界条件。扩展生成的节点D已经是叶子节点，找到了当前最优解，最优值为7，将bestw修改为7，如图550(d)所示。


图550最小质量机器设计问题的搜索过程（一）

从叶子节点D回溯到活节点C，活节点C再次成为当前的扩展节点。沿着它的x3=3分支扩展，不满足约束条件，扩展生成的节点被剪掉。继续回溯到活节点B，节点B成为当前的扩展节点，如图551(a)所示。扩展节点B沿x2=2分支扩展，cc=5≤c，满足约束条件； cw=3,bestw=7,cw<bestw，满足限界条件。扩展生成的节点E成为活节点，并且成为当前的扩展节点，如图551(b)所示。扩展节点E沿x3=1分支扩展，cc=7≤c，满足约束条件； cw=5,bestw=7,cw<bestw，满足限界条件。扩展生成的节点F 已经是叶子节点，找到了当前最优解，最优值为5，将bestw修改为5，如图551(c)所示。


图551最小质量机器设计问题的搜索过程（二）

从叶子节点F回溯到活节点E，沿着它的x3=2，3分支扩展，均不满足限界条件，扩展生成的节点被剪掉。继续回溯到活节点B，节点B成为当前的扩展节点，如图552(a)所示。扩展节点B沿x2=3分支扩展，cc=3≤c，满足约束条件； cw=2,bestw=5,cw<bestw，满足限界条件。扩展生成的节点G成为活节点，并且成为当前的扩展节点，如图552(b)所示。扩展节点G沿x3=1分支扩展，cc=5≤c，满足约束条件； cw=4,bestw=5,cw<bestw，满足限界条件。扩展生成的节点H已经是叶子节点，找到了当前最优解，其质量为4，bestw修改为4，如图552(c)所示。


图552最小质量机器设计问题的搜索过程（三）



从叶子节点H回溯到活节点G，沿着它的x3=2，3分支扩展，均不满足限界条件，扩展生成的节点被剪掉。继续回溯到活节点B，节点B的三个分支均搜索完毕，继续回溯到活节点A，节点A成为当前的扩展节点，如图553(a)所示。扩展节点A沿x1=2分支扩展，cc=2≤c，满足约束条件； cw=2,bestw=4,cw<bestw，满足限界条件。扩展生成的节点I成为活节点，并且成为当前的扩展节点，如图553(b)所示。


图553最小质量机器设计问题的搜索过程（四）


扩展节点I沿x2=1，2分支扩展，不满足限界条件，扩展生成的节点被剪掉。沿着x2=3分支扩展，cc=4≤c，满足约束条件； cw=3,bestw=4,cw<bestw，满足限界条件。扩展生成的节点J成为活节点，并且成为当前的扩展节点，如图554(a)所示。扩展节点J沿x3=1，2，3分支扩展，均不满足限界条件，扩展生成的节点被剪掉。开始回溯到活节点I。节点I的三个分支已搜索完毕，继续回溯到活节点A，节点A再次成为扩展节点，如图554(b)所示。


图554最小质量机器设计问题的搜索过程（五）

扩展节点A沿x1=3分支扩展，cc=3≤c，满足约束条件； cw=3,bestw=4,cw<bestw，满足限界条件。扩展生成的节点K成为活节点，并且成为当前的扩展节点，如图555(a)所示。扩展节点K沿x2=1，2，3分支扩展，均不满足限界条件，扩展生成的节点被剪掉。开始回溯到活节点A。此时，节点A的三个分支均搜索完毕，搜索结束。找到了问题的最优解为从根节点A到叶子节点H的路径(1,3,1)，最优值为4，如图555(b)所示。



图555最小质量机器设计问题的搜索过程（六）

5.8.4算法分析
计算约束函数和限界函数需要O(1)时间，需要判断约束函数和限界函数的节点在最坏情况下有1+m+m2+ m3+…+mn-1=(mn-1)/(m-1)个，故耗时O(mn-1)； 在叶子节点处记录当前最优方案需要耗时O(n)，在最坏情况下会搜索到每一个叶子节点，叶子节点有mn个，故耗时为O(nmn)。最小质量机器设计问题的回溯算法所需的计算时间为O(mn-1)+O(nmn)=O(nmn)。
5.8.5Python实战
定义一个深度优先搜索的backtrack()函数，搜索最小质量机器设计方案，记录最优值及所需费用。其代码如下： 





def Backtrack(t):

global bestw,cw,bestx,x,COST,cc,w,c,Total_cost

if(t>n):

Total_cost = cc

bestw = cw

bestx = x［:］

return

for j in range(1,m+1):

x［t］=j

if(cc+c［t］［j］<=COST and  cw+w［t］［j］<bestw):

cc+=c［t］［j］

cw+=w［t］［j］

Backtrack(t+1)

cc-=c［t］［j］

cw-=w［t］［j］




Python的入口——main()函数，在main()函数中，用二维列表c存储各供应商供应各部件的费用，二维列表w存储各供应商供应各部件的质量，牺牲0行0列位置的存储单元，下标从1开始有效。初始化相关辅助变量，调用backtrack()函数，求最小质量机器设计方案，最后将结果打印输出到显示器上。输出结果中，0号存储单元数据无效，从下标1开始有效。其代码如下： 





if __name__ =="__main__":

import sys

COST = 7

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

c = ［［0,0,0,0］,［0,1,2,3］,［0,5,4,2］,［0,3,1,2］］

n = 3

bestw = sys.maxsize

cw = 0

cc = 0

Total_cost = 0

m = 3

bestx = ［0 for i in range(n+1)］

x = ［0 for i in range(n+1)］

backtrack(1)

print("设计方案为：" ,bestx)

print("最优值为：" ,bestw)

print("所需费用为：" ,Total_cost)




输出结果为
设计方案为： ［0, 1, 3, 1］
最优值为： 4
所需费用为： 6