第5章
搜 索 算 法
学习目标
掌握回溯算法的算法框架
理解回溯算法及分支限界算法的基本思想
掌握回溯算法及分支限界算法的异同
能够建立子集树、排列树及满m叉树模型
通过实例学习，能够基于解空间模型，运用回溯算法及分支限界算法求解步骤解决实际问题
搜索算法是利用计算机的高性能有目的地枚举一个问题的部分或所有可能情况，从而找到解决问题的方法。该算法策略的适应性较强，只要问题有解，它肯定能将其解找出； 如果问题没有解，则它能给出问题无解的结论。因此，搜索算法可以称得上是万能的解决方法，但是其搜索效率有限。本章将着重介绍多种搜索算法。
视频讲解
5.1穷举搜索
假设问题的初始状态、目标状态和算符的定义都是确定的，那么问题的解空间就是确定的。对问题求解就是指如何有效地搜索这个确定的解空间，从中找出问题的真正解。搜索方法有很多，如穷举搜索、深度优先搜索、广度优先搜索等。
穷举搜索是一种最基本的搜索方法，其搜索思想是： 针对问题的可能解是有限种的情况，逐一检查所有可能的情况，从中找到问题真正的解。可以想象，当问题的可能解较多时，穷举搜索的效率会比较低，它是最耗时的一种解决方法。因此，这种搜索方法一般在问题求解没有更好的算法被选用时，才被使用。
图51有向带权图
【例51】给定一个有向带权图G=(V，E)，权非负，如图51所示。找出顶点1→5的最短路径及其长度。
问题分析： 该问题所有可能的路径只有三条，分别是1→2→4→5，1→3→4→5，1→4→5，采用穷举搜索的方法逐一检查这三条路径的长度，得出的最短路径为1→2→4→5，其长度为3。
【例52】给定一艘船和3个集装箱，船的载重量为10，3个集装箱的重量分别为5,8,3。在体积不受限制的前提下，如何将尽可能多的集装箱装上船？
问题分析： 每个集装箱只有两种状态，要么装上船，要么不装上船。用0表示不装上船，1表示装上船，则问题所有可能的解可以用8个3元的01向量表示，即（0,0,0）,（0,0,1），（0,1,0），（1,0,0），（1,1,0），（1,0,1），（0,1,1），（1,1,1）。这8种可能的解所代表的装上船的集装箱的总重量和箱子个数分别为（0,0），（3,1），（8,1），（5,1），（13,2），（8,2），（11,2），（16,3）。采用穷举搜索的方法逐一检查容易得出问题的解为(1,0,1)。
5.2深度优先搜索
1. 深度优先搜索的思想
给定图G=(V，E)。深度优先搜索的思想为： 初始时，所有顶点均未被访问过，任选一个顶点v作为源点。该方法先访问源点v，并将其标记为已访问过； 然后从v出发，选择v的下一个邻接点（子结点）w，如果w已访问过，则选择v的另外一个邻接点； 如果w未被访问过，则标记w为已访问过，并以w为新的出发点，继续进行深度优先搜索； 如果w及其子结点均已搜索完毕，则返回到v，再选择它的另外一个未曾访问过的邻接点继续搜索，直到图中所有和源点有路径相通的顶点均已访问过为止； 若此时图G中仍然存在未被访问过的顶点，则另选一个尚未访问过的顶点作为新的源点重复上述过程，直到图中所有顶点均被访问过为止。
【例53】给定一个有向图G=(V，E)，如图52所示。给出深度优先搜索该图的一个访问序列。
问题分析： 根据深度优先搜索的思想，初始时，所有顶点均未被访问过，因此可以任选一个顶点作为源点，搜索过程中需要判断源点的邻接点是否被访问过，然后根据判断结果做不同的处理，目标状态为全部顶点均被访问过。为此，用一个标识数组Visited［］标记图中的顶点是否被访问过，初始时Visited［］的值全部为0。若某顶点已被访问过，则将对应的数组Visited［］中的元素由0改为1。
搜索过程： 假定选择顶点1为源点，令 Visited［1］=1，输出顶点1。它有3个邻接点，分别为2、3、4，选择其中一个邻接点2（假定按照顶点编号由小到大的顺序选择邻接点）。由于顶点2未被访问过，令Visited［2］=1，输出顶点2。继续从顶点2出发进行深度优先搜索，选择顶点2的邻接点5，由于顶点5未被访问过，令Visited［5］=1，输出顶点5。继续从顶点5出发进行深度优先搜索，由于顶点5没有邻接点，故返回顶点2。由于顶点2的邻接点搜索完毕，则继续返回顶点1。选择顶点1的另外一个邻接点3，由于顶点3未被访问过，令Visited［3］=1，输出顶点3。继续从顶点3出发进行深度优先搜索，由于顶点3没有邻接点，故又返回顶点1。选择顶点1的最后一个邻接点4，由于顶点4未被访问过，令Visited［4］=1，输出顶点4。继续从顶点4出发进行深度优先搜索，此时，顶点4的所有邻接点2、3、5均已访问过，故返回顶点1。此时与顶点1相连通的顶点均已遍历完毕。但图52中还存在未被访问的顶点6和7。因此，再选择一个未被访问过的顶点6作为源点重复上述过程，依次将Visited［6］=1，输出顶点6，Visited［7］=1，输出顶点7，然后回溯到顶点6。此时图52的所有顶点均搜索完毕。输出一个深度优先搜索序列1,2,5,3,4,6,7。搜索顺序如图53所示，顶点旁边的序号为搜索顺序的序号。
图52有向图
图53搜索顺序
【例54】给定一个无向图G=(V，E)，如图54所示。给出深度优先搜索该图的一个搜索序列。
搜索过程： 假定选择顶点1作为源点，令Visited［1］=1，输出顶点1。它有3个邻接点，分别为2、3、4，选择其中一个邻接点2（假定按照顶点编号由小到大的顺序选择邻接点）。顶点2未被访问过，令Visited［2］=1，输出顶点2。继续从顶点2出发进行深度优先搜索，选择顶点2的邻接点1，由于顶点1已被访问过，故选择顶点2的另一个邻接点4。由于顶点4未被访问过，令Visited［4］=1，输出顶点4。继续从顶点4出发进行深度优先搜索，由于顶点4的邻接点1和2已访问过，因此选择它的第三个邻接点3。由于顶点3未被访问过，令Visited［3］=1，输出顶点3。继续从顶点3出发进行深度优先搜索，由于顶点3的两个邻接点1和4均已访问过，故返回顶点4。选择顶点4的最后一个邻接点5，由于顶点5未被访问过，令Visited［5］=1，输出顶点5。继续从顶点5出发进行深度优先搜索，由于顶点5的两个邻接点2和4均已访问过，故返回顶点4。由于顶点4的所有邻接点已被访问过，继续返回到顶点2。顶点2的最后一个邻接点已被访问过，故继续返回顶点1。此时，与顶点1相连通的顶点均已搜索完毕，但图54中还存在未被访问的顶点6和7。因此，再选择一个未访问的顶点6作为出发点重复上述过程，依次将Visited［6］=1，输出顶点6，Visited［7］=1，输出顶点7，再返回顶点6。此时图中所有顶点均已搜索完毕。输出图54的深度优先搜索序列1,2,4,3,5,6,7。搜索顺序如图55所示，顶点旁边的序号为搜索顺序的序号。
图54无向图
图55搜索顺序
2. 算法描述
//从顶点k出发进行深度优先搜索
void Dfsk(int k)
{
visited［k］=1； //标记顶点k已被访问过
for(int j=1;j<=n;j++)
if(c［k］［j］==1 && visited［j］==0)//c［］［］是图G对应的邻接矩阵
Dfsk(j);
}
//深度优先搜索整个图G
void Dfs()
{
for(int i=1;i<=n;i++)
if(visited［i］==0)
Dfsk(i);
}
3. C++实战
相关代码如下。
#include<iostream>
using namespace std;
//从顶点k出发进行深度优先搜索
template <class Type> void Dfsk(int n,int k,Type **c,bool *visited)
{
visited［k］=1; //标记顶点k已被访问过
for(int j=1;j<=n;j++)
if(c［k］［j］==1 && visited［j］==0)//c［］［］是图G对应的邻接矩阵
{
cout<<j<<" ";
Dfsk(n,j,c,visited);
}
}
//深度优先搜索整个图G
template <class Type> void Dfs(int n,Type **c,bool *visited)
{
for(int i=1;i<=n;i++)
if(visited［i］==0){
cout<<i<<" ";
Dfsk(n,i,c,visited);
}
}
int main(){
cout<<"请输入顶点个数n:";
int n;
cin>>n;
//标记图中顶点是否被访问过，顶点编号从1开始
bool *visited = new bool［n+1］;
int **c = new int*［n+1］;
for(int i=0;i<=n;i++)
c［i］ = new int［n+1］;
//输入图的邻接矩阵
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++)
cin>>c［i］［j］;
}
for(int i=1;i<=n;i++)
visited［i］=0; //用0表示顶点未被访问过
Dfs(n,c,visited);
delete ［］visited;
for(int i=0;i<=n;i++)
delete ［］c［i］;
delete ［］c;
}
5.3回溯算法
深度优先搜索是在明确给出了图中的各顶点及边（显式图）的情况下，按照深度优先搜索的思想对图中的每个顶点进行搜索，最终得出图的结构信息。回溯算法是在仅给出初始结点、目标结点及产生子结点的条件（一般由问题题意隐含给出）的情况下，构造一个图（隐式图），然后按照深度优先搜索的思想，在有关条件的约束下扩展到目标结点，从而找出问题的解。换言之，回溯算法从初始状态出发，在隐式图中以深度优先的方式搜索问题的解。当发现不满足求解条件时，就回溯，尝试其他路径。通俗地讲，回溯算法是一种“能进则进，进不了则换，换不了则退”的基本搜索方法。
视频讲解
5.3.1回溯算法的算法框架及思想
1. 回溯算法的算法框架及思想
回溯算法是一种搜索方法。用回溯算法解决问题时，首先应明确搜索范围，即问题所有可能解组成的范围。这个范围越小越好，且至少包含问题的一个(最优)解。为了定义搜索范围，需要明确以下几方面：
（1） 问题解的形式： 回溯算法希望问题的解能够表示成一个n元组(x1,x2,…,xn)的形式。
（2） 显约束： 对分量xi（i=1,2,…,n）的取值范围限定。
（3） 隐约束： 为满足问题的解而对不同分量之间施加的约束。
（4） 解空间： 对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间。
注意： 同一个问题的显约束可能有多种，不同显约束相应解空间的大小就会不同，通常情况下，解空间越小，算法的搜索效率越高。
【例55】n皇后问题。在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。换句话说，n皇后问题等价于在n×n格的棋盘上放置n个皇后，任意两个皇后不同行、不同列、不同斜线。
问题分析： 根据题意，先考虑显约束为不同行的解空间。
（1） 问题解的形式： n皇后问题的解表示成n元组(x1,x2,…,xn)的形式，其中xi（i=1,2,…,n）表示第i个皇后放置在第i行第xi列的位置。
（2） 显约束： n个皇后不同行。
（3） 隐约束： n个皇后不同列或不同斜线。
（4） 解空间： 根据显约束，第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元组组成。
显然，第二种表示方法使得问题的解空间明显变小，因此搜索效率更高。
其次，为了方便搜索，一般用树或图的形式将问题的解空间有效地组织起来。如例55的n皇后问题： 显约束为不同行的解空间树（n=4），如图56所示，显约束为不同行且不同列的解空间树(n=4)，如图57所示。树的结点代表状态，树根代表初始状态，树叶代表目标状态； 从树根到树叶的路径代表放置方案； 分支上的数据代表xi的取值，也可以说是将第i个皇后放置在第i行、第xi列的动作。
图56显约束为不同行的解空间树（n=4）
图57显约束为不同行且不同列的解空间树(n=4)
最后，搜索问题的解空间树。在搜索的过程中，需要了解几个名词：
（1） 扩展结点： 一个正在生成子树的结点称为扩展结点。
（2） 活结点： 一个自身已生成但其子树还没有全部生成的结点称为活结点。
（3） 死结点： 一个所有子树已经生成的结点称作死结点。
搜索思想： 从根开始，以深度优先搜索的方式进行搜索。根结点是活结点并且是当前的扩展结点。在搜索过程中，当前的扩展结点沿纵深方向移向一个新结点，判断该新结点是否满足隐约束，如果满足，则新结点成为活结点，并且成为当前的扩展结点，继续深一层的搜索； 如果不满足，则换到该新结点的兄弟结点（扩展结点的其他分支）继续搜索； 如果新结点没有兄弟结点，或其兄弟结点已全部搜索完毕，则扩展结点成为死结点，搜索回溯到其父结点处继续进行。搜索过程直到找到问题的解或根结点变成死结点为止。
从回溯算法的搜索思想可知，搜索开始之前必须确定问题的隐约束。隐约束一般是考察解空间结构中的结点是否有可能得到问题的可行解或最优解。如果不可能得到问题的可行解或最优解，就不用沿着该结点的分支继续搜索了，需要换到该结点的兄弟结点或回到上一层结点。也就是说，在深度优先搜索的过程中，不满足隐约束的分支被剪掉，只沿着满足隐约束的分支搜索问题的解，从而避免了无效搜索，加快了搜索速度。因此，隐约束又称为剪枝函数。隐约束（剪枝函数）一般有两种： 一是判断是否能够得到可行解的隐约束，称之为约束条件（约束函数）； 二是判断是否有可能得到最优解的隐约束，称为限界条件（限界函数）。可见，回溯算法是一种具有约束函数或限界函数的深度优先搜索方法。
总之，回溯算法的算法框架主要包括3部分：
（1） 针对所给问题，定义问题的解空间。
（2） 确定易于搜索的解空间组织结构。
（3） 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
2. 回溯算法的构造实例
【例56】用回溯算法解决4皇后问题。
问题分析： 按照回溯算法的搜索思想，首先确定根结点是活结点，并且是当前的扩展结点R。它扩展生成一个新结点C，如果C不满足隐约束，则舍弃； 如果满足，则C成为活结点并成为当前的扩展结点，搜索继续向纵深处进行（此时结点R不再是扩展结点）。在完成对子树C（以C为根的子树）的搜索之后，结点C变成了死结点。开始回溯到离死结点C最接近的活结点R，结点R再次成为扩展结点。如果扩展结点R还存在未搜索过的孩子结点，则继续沿R的下一个未搜索过的孩子结点进行搜索； 直到找到问题的解或者根结点变成死结点为止。
用回溯算法解决4皇后问题的求解过程设计如下：
步骤1： 定义问题的解空间。
设4皇后问题解的形式是4元组（x1,x2,x3,x4），其中xi(i=1,2,3,4)代表第i个皇后放置在第i行第xi列，xi的取值为1,2,3,4。
步骤2： 确定解空间的组织结构。
确定显约束： 第i个皇后和第j个皇后不同行，即： i≠j，对应的解空间的组织结构如图56所示。
步骤3： 搜索解空间。
步骤31： 确定约束条件。第i个皇后和第j个皇后不同列且不同斜线，即： xi≠xj并且|i-j|≠|xi-xj|。
步骤32： 确定限界条件。该问题不存在放置方案是否好坏的情况，所以不需要设置限界条件。
步骤33： 搜索过程。如图58~图513所示： 根结点A是活结点，也是当前的扩展结点，如图58（a)所示。扩展结点A沿着x1=1的分支生成孩子结点B，结点B满足隐约束，B成为活结点，并成为当前的扩展结点，如图58（b)所示。扩展结点B沿着x2=1，x2=2的分支生成的孩子结点不满足隐约束，舍弃； 沿着x2=3的分支生成的孩子结点C满足隐约束，C成为活结点，并成为当前的扩展结点，如图58（c)所示。扩展结点C沿着所有分支生成的孩子结点均不满足隐约束，全部舍弃，活结点C变成死结点。开始回溯到离它最近的活结点B，结点B再次成为扩展结点，如图58（d)所示。
图58搜索过程1
扩展结点B沿着x2=4的分支继续生成的孩子结点D满足隐约束，D成为活结点，并成为当前的扩展结点，如图59（a)所示。扩展结点D沿着x3=1的分支生成的孩子结点不满足隐约束，舍弃； 沿着x3=2的分支生成的孩子结点E满足隐约束，E成为活结点，并成为当前的扩展结点，如图59(b)所示。扩展结点E沿着所有分支生成的孩子结点均不满足隐约束，全部舍弃，活结点E变成死结点。开始回溯到最近的活结点D，D再次成为扩展结点，如图59(c)所示。扩展结点D沿着x3=3，x3=4的分支生成的孩子结点均不满足隐约束，舍弃，活结点D变成死结点。开始回溯到最近的活结点B，B再次成为扩展结点，如图59（d)所示。
图59搜索过程2
此时扩展结点B的孩子结点均搜索完毕，活结点B成为死结点。开始回溯到最近的活结点A，结点A再次成为扩展结点，如图510(a)所示。扩展结点A沿着x1=2的分支继续生成的孩子结点F满足隐约束，结点F成为活结点，并成为当前的扩展结点，如图510（b)所示。扩展结点F沿着x2=1,2,3的分支生成的孩子结点均不满足隐约束，全部舍弃； 继续沿着x2=4的分支生成的孩子结点G满足隐约束，结点G成为活结点，并成为当前的扩展结点，如图510（c)所示。
图510搜索过程3
扩展结点G沿着x3=1的分支生成的孩子结点H满足隐约束，结点H成为活结点，并成为当前的扩展结点，如图511（a)所示。扩展结点H沿着x4=1,2的分支生成的孩子结点均不满足隐约束，舍弃； 沿着x4=3的分支生成的孩子结点I满足隐约束。此时搜索过程搜索到了叶子结点，说明已经找到一种放置方案，即（2,4,1,3），如图511（b)所示。继续搜索其他放置方案，从叶子结点I回溯到最近的活结点H，H又成为当前扩展结点，如图511（c)所示。
图511搜索过程4
扩展结点H继续沿着x4=4的分支生成的孩子结点不满足隐约束，舍弃； 此时结点H的4个分支全部搜索完毕，H成为死结点，回溯到活结点G，如图512(a)所示。结点G又成为当前的扩展结点，沿着x3=2,3,4的分支生成的孩子结点均不满足隐约束，舍弃； 结点G成为死结点，回溯到活结点F，如图512(b)所示。结点F的4个分支均搜索完毕，继续回溯到活结点A，结点A再次成为当前的扩展结点，如图512(c)所示。
图512搜索过程5
图513搜索过程6
扩展结点A沿着x1=3,4分支的扩展过程与沿着x1=1,2分支的扩展过程类似，这里不再详述。最终形成的树如图513所示。
通常将搜索过程中形成的树型结构称为问题的搜索树。例56 4皇后问题对应的搜索树如图513所示。简单地讲，搜索树上的结点全部是解空间树中满足隐约束的结点，而不满足隐约束的结点被全部剪掉。
对显约束为不同行且不同列的4皇后问题的解空间树(图57)进行搜索的过程与上述搜索过程类似。二者最终形成的搜索树完全相同，只有搜索过程中检查的隐约束和分支数不同，留给读者练习。
3. 回溯算法的算法描述模式
回溯算法是一种带有约束函数或限界函数的深度优先搜索方法，搜索过程是在问题的解空间树中进行的。算法描述通常采用递归技术，也可以选用非递归技术。
（1） 递归算法描述模式。
void Backtrack(int t)
{
if (t>n) //搜索层次大于解空间树的深度，说明搜索到了叶子结点，找到了问题的一个解
output(x); //将找到的解记录或输出
else
for (int i=s(n,t);i<=e(n,t);i++)//检查扩展结点的每一个分支
{
x［t］=d(i);//将分支上的数据保存到记录当前解的数组x中
if (constraint(t)&&bound(t)) //判断沿该分支生成的孩子结点是否满足隐约束
Backtrack(t+1);//如果满足，则进入t+1层的孩子结点继续搜索，递归实现
}
}
这里，形参t代表当前扩展结点在解空间树中所处的层次。解空间树的根结点为第1层，根结点的孩子结点为第2层，以此类推，深度为n的解空间树的叶子结点为第n+1层。注意： 在解空间树中，结点所处的层次比该结点所在的深度大1。解空间树中结点的深度与层次之间的关系如图514所示。
图514解空间树中结点的深度与层次关系
变量n代表问题的规模，同时也是解空间树的深度。注意区分树的深度和树中结点的深度两个概念，树的深度指的是树中深度最大的结点深度。s(n,t)代表当前扩展结点处未搜索的子树的起始编号。e(n,t)代表当前扩展结点处未搜索的子树的终止编号。d(i)代表当前扩展结点处可选的分支上的数据。x是用来记录问题当前解的数组。constraint(t)代表当前扩展结点处的约束函数。bound(t)代表当前扩展结点处的限界函数。满足约束函数或限界函数则继续深一层次的搜索； 否则，剪掉相应的子树。Backtrack(t)代表从第t层开始搜索问题的解。由于搜索从解空间树的根结点开始，即从第1层开始搜索，因此函数调用为Backtrack(1)。
（2） 非递归算法描述模式。
voidNBacktrack()
{
int t=1;
while (t>0)
{
if (s(n,t)<=e(n,t))
for (int i=s(n,t);i<=e(n,t);i++)
{
x［t］=d(i);
if (constraint(t)&&bound(t))
if (t>n)
output(x);
else
t++;//更深一层搜索
}//end for
else
t--;//回溯到上一层的活结点
}//end while
}
这里出现的函数和变量均和递归算法描述模式中出现的含义相同。
视频讲解
5.3.2子集树
1. 概述
子集树是使用回溯算法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。此类问题解的形式为n元组（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i个元素是否在要找的子集中。xi的取值为0或1，xi=0表示第i个元素不在要找的子集中； xi=1表示第i个元素在要找的子集中。如图515所示是n=3时的子集树。
视频讲解
视频讲解
视频讲解
图515n=3时的子集树
子集树中所有非叶子结点均有左右两个分支，左分支为1，右分支为0，反之也可以。本书约定子集树的左分支为1，右分支为0。树中从根到叶子的路径描述了一个n元01向量，这个n元01向量表示集合S的一个子集，这个子集由对应分量为1的元素组成。如假定3个元素组成的集合S为{1,2,3}，从根结点A到叶结点I的路径描述的n元组为（1,1,0），它表示S的一个子集{1,2}。从根结点A到叶结点M的路径描述的n元组为（0,1,0），它表示S的另一个子集{2}。
在子集树中，树的根结点表示初始状态，中间结点表示某种情况下的中间状态，叶子结点表示结束状态。分支表示从一个状态过渡到另一个状态的行为。从根结点到叶子结点的路径表示一个可能的解。子集树的深度等于问题的规模。
解空间树为子集树的问题有很多，如：
01背包问题： 从n个物品组成的集合S中找出一个子集，这个子集内所有物品的总重量不超过背包的容量，并且这些物品的总价值在S的所有不超过背包容量的子集中是最大的。显然，这个问题的解空间树是一棵子集树。
子集和问题： 给定n个整数和一个整数C，要求找出n个数中哪些数相加的和等于C。这个问题实质上是要求从n个数组成的集合S中找出一个子集，这个子集中所有数的和等于给定的C。因此，子集和问题的解空间树也是一棵子集树。
装载问题： n个集装箱要装上两艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且∑ni=1wi≤c1+c2。装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这两艘轮船，如果有，找出一种装载方案。
这个问题如果有解，则采用下面的策略可得到最优装载方案。
（1） 首先将第一艘轮船尽可能装满。
（2） 将剩余的集装箱装上第二艘轮船。如果剩余的集装箱能够全部装上船，则找到一个合理的方案，如果不能全部装上船，则不存在装载方案。
将第一艘轮船尽可能装满等价于从n个集装箱组成的集合中选取一个子集，该子集中集装箱重量之和小于或等于第一艘船的载重量且最接近第一艘船的载重量。由此可知，装载问题的解空间树也是一棵子集树。
最大团问题： 给定一个无向图，找出它的最大团。这个问题等价于从给定无向图的n个顶点组成的集合中找出一个顶点子集，这个子集中的任意两个顶点之间有边相连且包含的顶点个数是所有该类子集中包含顶点个数最多的。因此这个问题也是从整体中取出一部分，这一部分构成整体的一个子集且满足一定的特性，它的解空间树是一棵子集树。
可见，对于要求从整体中取出一部分，这一部分需要满足一定的特性，整体与部分之间构成包含与被包含的关系，即子集关系的一类问题，均可采用子集树描述它们的解空间树。这类问题在解题时可采用统一的算法设计模式。
2. 子集树的算法描述模式
void Backtrack(int 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()为限界函数。
3. 子集树的构造实例
【例57】01背包问题。
（1） 问题描述： 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为W。一种物品要么全部装入背包，要么全部不装入背包，不允许部分装入。装入背包的物品的总重量不超过背包的容量。问应如何选择装入背包的物品，使得装入背包中的物品总价值最大?
（2） 问题分析： 根据问题描述可知，01背包问题要求找出n种物品集合{1,2,3,…,n}中的一部分物品，将这部分物品装入背包。装进去的物品总重量不超过背包的容量且价值之和最大。即： 找到n种物品集合{1,2,3,…,n}的一个子集，这个子集中的物品总重量不超过背包的容量，且总价值是集合{1,2,3,…,n}的所有不超过背包容量的子集中物品总价值最大的。
按照回溯算法的算法框架，首先需要定义问题的解空间，然后确定解空间的组织结构，最后进行搜索。搜索前要解决两个关键问题，一是确定问题是否需要约束条件（用于判断是否有可能产生可行解），如果需要，如何设置； 二是确定问题是否需要限界条件（用于判断是否有可能产生最优解），如果需要，如何设置。
（3） 解题步骤。
步骤1： 定义问题的解空间。
01背包问题是要将物品装入背包，且物品有且只有两种状态。第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。图516描述了n=4时的解空间树。
图516n=4时的解空间树
步骤3： 搜索解空间。
步骤31： 是否需要约束条件？如果需要，如何设置？
01背包问题的解空间包含2n个可能的解，是不是每一个可能的解描述的装入背包的物品的总重量都不超过背包的容量呢？显然不是，这个问题存在某种或某些物品无法装入背包的情况。因此，需要设置约束条件来判断所有可能的解描述的装入背包的物品总重量是否超出背包的容量，如果超出，为不可行解； 否则为可行解。搜索过程将不再搜索那些导致不可行解的结点及其孩子结点。约束条件的形式化描述为
∑ni=1wixi≤W（51）
步骤32： 是否需要限界条件？如果需要，如何设置？
01背包问题的可行解可能不止一个，问题的目标是找一个所描述的装入背包的物品总价值最大的可行解，即最优解。因此，需要设置限界条件来加速找出该最优解的速度。
如何设置限界条件呢？根据解空间的组织结构可知，任何一个中间结点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（52）
步骤33： 搜索过程。从根结点开始，以深度优先的方式进行搜索。根结点首先成为活结点，也是当前的扩展结点。由于子集树中约定左分支上的值为“1”，因此沿着扩展结点的左分支扩展，则代表装入物品，此时，需要判断是否能够装入该物品，即判断约束条件成立与否，如果成立，即进入左孩子结点，左孩子结点成为活结点，并且是当前的扩展结点，继续向纵深结点扩展； 如果不成立，则剪掉扩展结点的左分支，沿着其右分支扩展。右分支代表物品不装入背包，肯定有可能导致可行解。但是沿着右分支扩展有没有可能得到最优解呢？这一点需要由限界条件来判断。如果限界条件满足，说明有可能导致最优解，即进入右分支，右孩子结点成为活结点，并成为当前的扩展结点，继续向纵深结点扩展； 如果不满足限界条件，则剪掉扩展结点的右分支，开始向最近的活结点回溯。搜索过程直到所有活结点变成死结点结束。
（4） 01背包问题实例的搜索过程演示。
令n=4，W=7，w=(3,5,2,1)，v=(9,10,7,4)。搜索过程如图517~图521所示。（注： 图中结点旁括号内的数据表示背包的剩余容量和已装入背包的物品价值。）
首先，搜索从根结点开始，即根结点是活结点，也是当前的扩展结点。它代表初始状态，即背包是空的，如图517（a）所示。扩展结点1先沿着左分支扩展，此时需要判断式（51）约束条件。第一种物品的重量为3，3<7，满足约束条件，因此结点2成为活结点，并成为当前的扩展结点。它代表第1种物品已装入背包，背包剩余容量为4，背包内物品的总价值为9，如图517（b）所示。扩展结点2继续沿着左分支扩展，此时需要判断第2个物品能否装入背包。第2个物品的重量为5，背包的剩余容量为4。显然，该物品无法装入，故剪掉扩展结点2的左分支。此时，需要选择扩展结点2的右分支继续扩展，判断式（52）限界条件，cp=9，rp=11，bestp=0，cp+rp>bestp限界条件成立，则结点2沿右分支扩展的结点3成为活结点，并成为当前的扩展结点。扩展结点3代表背包剩余容量为4，背包内物品的总价值为9，如图517（c）所示。以此类推，扩展结点3沿着左分支扩展，第3种物品的重量是2，背包的剩余容量为4，满足约束条件，结点4成为活结点，并成为当前的扩展结点。结点4代表背包剩余容量为2，背包内物品总价值为16，如图517（d）所示。
图517搜索过程1
扩展结点4沿着左分支扩展，此时第4种物品的重量为1，背包的剩余容量为2，结点5满足约束条件。结点5已是叶子结点，故找到一个当前最优解，将其记录并修改bestp的值为当前最优解描述的装入背包的物品总价值20，如图518（a）所示。由于结点5已是叶子结点，不具备扩展能力，此时要回溯到离结点5最近的活结点4，结点4再次成为扩展结点，如图518（b）所示。扩展结点4沿着右分支继续扩展，此时要判断限界条件是否满足，cp=16，rp=0，bestp=20，cp+rp<bestp，限界条件不满足，故剪掉结点4的右分支。扩展结点4的左右两个分支均搜索完毕，回溯到最近的活结点3，结点3再次成为扩展结点，如图518（c）所示。扩展结点3沿着右分支继续扩展，此时要判断限界条件是否满足，cp=9，rp=4，bestp=20，cp+rp<bestp，限界条件不满足，故剪掉结点3的右分支。扩展结点3的左右两个分支均搜索完毕，回溯到最近的活结点2，结点2再次成为扩展结点。扩展结点2的两个分支均搜索完毕，故继续回溯到结点1，如图518（d）所示。
图518搜索过程2
扩展结点1沿着右分支继续扩展，判断限界条件是否满足，cp=0，rp=21，bestp=20，cp+rp>bestp，限界条件满足，则扩展的结点6成为活结点，并成为当前的扩展结点，如图519（a）所示。扩展结点6沿着左分支继续扩展，判断约束条件，当前背包剩余容量为7，第二种物品的重量为5，5<7，满足约束条件，扩展生成的结点7成为活结点，且是当前的扩展结点。此时背包的剩余容量为2，装进背包的物品总价值为10，如图519（b）所示。扩展结点7沿着左分支继续扩展，判断约束条件，当前背包剩余容量为2，第3种物品的重量为2，满足约束条件，扩展生成的结点8成为活结点，且是当前的扩展结点。此时背包的剩余容量为0，装入背包的物品总价值为17，如图519（c）所示。
图519搜索过程3
扩展结点8沿着左分支继续扩展，判断约束条件，当前背包剩余容量为0，第4种物品的重量为1，0<1，不满足约束条件，扩展生成的结点被剪掉。接下来沿着扩展结点8的右分支进行扩展，判断限界条件，cp=17，rp=0，bestp=20，cp+rp<bestp，不满足限界条件，沿右分支扩展生成的结点也被剪掉。扩展结点8的所有分支均搜索完毕，回溯到最近的活结点7，结点7又成为扩展结点，如图520（a）所示。扩展结点7沿着右分支继续扩展，判断限界条件，当前cp=10，rp=4，bestp=20，cp+rp<bestp，限界条件不满足，扩展生成的结点被剪掉。扩展结点7的所有分支均搜索完毕，回溯到活结点6，结点6又成为扩展结点，如图520（b）所示。扩展结点6沿着右分支继续扩展，判断限界条件，当前cp=0，rp=11，bestp=20，cp+rp<bestp，限界条件不满足，扩展生成的结点被剪掉。扩展结点6的所有分支均搜索完毕，回溯到活结点1，结点1又成为扩展结点，如图520（c）所示。
图520搜索过程4
图521搜索过程5
扩展结点1的两个分支均搜索完毕，它成为死结点，搜索过程结束，找到的问题的解为从根结点1到叶子结点5的路径（1,0,1,1），即将第1,3,4三种物品装入背包，装进去物品总价值为20，如图521所示。
（5） 限界条件式(52)的优化。
在上述限界条件中，rp表示第t+1种物品到第n种物品的总价值。事实上，背包的剩余容量不一定能够容纳从第t+1种物品到第n种物品的全部物品，那么剩余容量所能容纳的从第t+1种物品到第n种物品的最大价值（用brp表示）肯定小于或等于rp，用brp取代rp，则式(52)改写为
cp+brp>bestp(53)
01背包问题最终不一定能够将背包装满，因此，cp+brp同样是所有路径经过中间结点z的可行解的价值上界，且这个价值上界小于或等于cp+rp。因此，表达式cp+brp>bestp成立的可能性比cp+rp>bestp成立的可能性要小。用cp+brp>bestp作为限界条件，从中间结点z沿右分支继续向纵深搜索的可能性就小。也就是说，中间结点z的右分支剪枝的可能性就越大，搜索速度也会加快。
以式(53)作为限界条件的搜索过程与以式(52)作为限界条件的搜索过程只有在搜索右分支时进行的判断不同。在以式(53)作为限界条件的搜索过程中，需要求出brp的值，为方便起见，事先计算出所给物品单位重量的价值93,105,72,41。针对剩余的物品，单位重量价值大的物品优先装入背包，将背包剩余容量装满所得的价值即为brp的值。在图517(b)中，扩展结点2沿右分支扩展，判断限界条件，当前cp=9，剩余的不确定状态的物品为第3、第4种物品，背包剩余容量为4，将背包装满装入的最大价值为第3、第4种物品的价值之和，即brp=11，bestp=0，cp+brp>bestp，限界条件成立，扩展的结点3成为活结点，并成为当前的扩展结点，继续向纵深处扩展。式(53)限界条件的搜索与式(52)限界条件的搜索直到图518(b)（找到一个当前最优解后回溯到最近的活结点4）均相同，其后在式(53)限界条件下的搜索过程如图522所示。
扩展结点4沿右分支扩展，判断限界条件，cp=16，背包的剩余容量为2，没有剩余物品，故brp=0，bestp=20，cp+brp<bestp，限界条件不满足，扩展生成的结点被剪掉。此时，左右分支均检查完毕，开始回溯到活结点3，结点3又成为扩展结点，如图522(a)所示。扩展结点3沿右分支扩展，判断限界条件，cp=9，剩余容量为4，剩余物品为第4种物品，其重量为1，能够全部装入，故brp=4。bestp=20，cp+brp<bestp，限界条件不满足，扩展生成的结点被剪掉。此时，结点3的左右分支均搜索完毕，回溯到活结点2。结点2的两个分支已搜索完毕，继续回溯到活结点1，活结点1再次成为扩展结点，如图522(b)所示。扩展结点1继续沿右分支扩展，判断限界条件，cp=0，剩余容量为7，剩余物品为第2、3、4种物品，按照单位重量的价值大的物品优先的原则，将第3、4种物品全部装入背包。此时，背包剩余容量为4，第2种物品的重量为5，无法全部装入，只需装入第2种物品的4/5，那么装进去的价值为10×4/5=8，故brp=7+4+8=19，cp+brp=19<besp(20)，限界条件不满足，扩展生成的结点被剪掉。此时，左右分支均搜索完毕，搜索过程结束，找到的当前最优解为（1,0,1,1），最优值为20，如图522(c)所示。
图522搜索过程
（6） 算法描述。
以下算法描述针对式（53）的限界条件。形式参数t代表当前扩展结点在解空间树中所处的层次。首先定义一个Knap类：
class Knap
{
public:
friend int Knapsack(int p［］,int w［］,int c,int n);
void print()
{
for(int k=1;k<=n;k++)
cout<<bestx［k］<<" ";
cout<<endl;
}
private:
int Bound(int i);
void Backtrack(int t);
int c;//背包容量
int n; //物品数
int *w;//物品重量数组
int *p;//物品价值数组
int cw;//当前重量
int cp;//当前价值
int bestp;//当前最优值
int *bestx;//当前最优解
int *x;//当前解
};
类Knap的成员函数Bound()用于求将剩余的物品装满剩余的背包容量时装入背包物品的最大价值。用参数i表示剩余物品为第i~n种物品，成员函数Bound()基于物品按照单位重量的价值由大到小排好序的序列。成员函数Bound()的描述如下：
int Knap∷Bound(int i) //计算上界
{
int cleft=c-cw;//剩余容量
int b=cp;
//以物品单位重量价值递减序装入物品
while(i<=n && w［i］<=cleft)
{
cleft-=w［i］;
b+=p［i］;i++;}
//装满背包
if(i<=n)
b+=p［i］/w［i］*cleft;
return b;
}
类Knap的成员函数Backtrack()用于搜索解空间树，参数t表示当前扩展结点在解空间树中所处的层次。函数Backtrack()搜索解空间时，先判断是否达到叶子结点，如果到达叶子即t>n，说明找到了一个当前最优解，将其记录； 否则，如果没有到达叶子结点，则沿左子树扩展，此时判断是否满足约束条件，如果满足，即进行更深一层搜索（即递归更深一层）； 如果不满足，则沿着右子树扩展，此时判断是否满足限界条件，如果满足，即进行更深一层搜索，反之则回溯到最近的活结点。算法描述如下：
void Knap∷Backtrack(int t)
{
if(t>n)//到达叶子结点
{
for(int j=1;j<=n;j++)
bestx［j］=x［j］;
bestp=cp;
return;
}
if(cw+w［t］<=c) //搜索左子树
{
x［t］=1;
cw+=w［t］;
cp+=p［t］;
Backtrack(t+1);
cw-=w［t］;
cp-=p［t］;
}
if(Bound(t+1)>bestp)//搜索右子树
{ x［t］=0; Backtrack(t+1); }
}
用回溯算法求解01背包问题时，数组x用于记录当前解，其元素全部初始化为0。数组w用于存储物品的重量，数组p用于存储物品的价值，背包的容量用c表示。为了对物品按照单位重量的价值由大到小排序，定义了Object类，具体定义如下：
class Object
{ public:
friend int Knapsack(int p［］,int w［］,int c,int n);
int operator<=(Object a)const
{ return (d>=a.d); }
private:
int id;//物品编号
float d;//单位重量的价值
};
01背包问题的算法首先进行初始化工作，然后对物品类对象按照单位重量的价值由大到小排序，算法描述如下：
int Knapsack(int p［］,int w［］,intｃ,int n)
{ //初始化
int W=0;int P=0;int i=1;
Object *Q=new Object［n］;
for(i=1;i<=n;i++)
{
Q［i-1］.ID=i;
Q［i-1］.d=1.0*p［i］/w［i］;
P+=p［i］; W+=w［i］;
}
if(W<=c)return P;//装入所有物品
//依物品单位重量降序排序
Sort(Q,n); //将数组Q中的元素按照单位重量的价值由大到小排序
KnapK;
K.p=new int［n+1］;
K.w=new int［n+1］;
K.x=new int［n+1］;
K.bestx=new int［n+1］;
K.x［0］=0;
K.bestx［0］=0;
for(i=1;i<=n;i++)//按单位重量的价值降序排列物品重量和价值
{
K.p［i］=p［Q［i-1］.id］;
K.w［i］=w［Q［i-1］.id］;
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回溯搜索
K.Backtrack(1);//从根开始搜索解空间树
K.print(); //输出最优解
delete ［］ Q;delete ［］ K.w;delete ［］ K.p;
return K.bestp; //返回最优值
}
（7） 算法分析。
判断约束函数需O(1)，在最坏情况下有2n-1个左孩子，约束函数耗时最坏为O(2n)。计算上界限界函数需要O(n)时间，在最坏情况下有2n-1个右孩子需要计算上界，限界函数耗时最坏为O(n2n)。01背包问题的回溯算法所需的计算时间为O(2n)+O(n2n)=O(n2n)。
（8） C++实战。
相关代码如下。
#include<iostream>
#include<algorithm>
using namespace std;
class Knap
{
public:
friend int Knapsack(int p［］,int w［］,int c,int n);
void print()
{
for(int k=1;k<=n;k++)
cout<<bestx［k］<<" ";
cout<<endl;
}
private:
int Bound(int i);
void Backtrack(int t);
int c; //背包容量
int n; //物品数
int *w; //物品重量数组
int *p; //物品价值数组
int cw; //当前重量
int cp; //当前价值
int bestp; //当前最优值
int *bestx; //当前最优解
int *x; //当前解
};
int Knap::Bound(int i) //计算上界
{
int cleft=c-cw; //剩余容量
int b=cp;
//以物品单位重量价值递减序装入物品
while(i<=n && w［i］<=cleft)
{
cleft-=w［i］;
b+=p［i］;i++;
}
//装满背包
if(i<=n)
b+=p［i］/w［i］*cleft;
return b;
}
void Knap::Backtrack(int t)
{
if(t>n)//到达叶子结点
{
for(int j=1;j<=n;j++)
bestx［j］=x［j］;
bestp=cp;
return;
}
if(cw+w［t］<=c) //搜索左子树
{
x［t］=1;
cw+=w［t］;
cp+=p［t］;
Backtrack(t+1);
cw-=w［t］;
cp-=p［t］;
}
if(Bound(t+1)>bestp)//搜索右子树
{
x［t］=0;
Backtrack(t+1);
}
}
class Object
{
public:
friend int Knapsack(int p［］,int w［］,int c,int n);
int operator<(const Object &a)
{ return (this->d > a.d); }
private:
int id; //物品编号
float d; //单位重量的价值
};
int Knapsack(int p［］,int w［］,int c,int n)
{ //初始化
int W=0;int P=0;int i=1;
Object *Q=new Object［n］;
for(i=1;i<=n;i++)
{
Q［i-1］.id=i;
Q［i-1］.d=1.0*p［i］/w［i］;
P+=p［i］;
W+=w［i］;
}
if(W<=c) return P; //装入所有物品
for(int i=0;i<=n;i++)
cout<<Q［i］.d<<" ";
cout<<endl;
//依物品单位重量降序排序
sort(Q,Q+n); //将数组Q中的元素按照单位重量的价值由大到小排序
for(int i=0;i<=n;i++)
cout<<Q［i］.d<<" ";
cout<<endl;
Knap K;
K.p=new int［n+1］;
K.w=new int［n+1］;
K.x=new int［n+1］;
K.bestx=new int［n+1］;
int *bestx = new int［n+1］;
K.x［0］=0;
K.bestx［0］=0;
for(i=1;i<=n;i++)//按单位重量的价值降序排列物品重量和价值
{
K.p［i］=p［Q［i-1］.id］;
K.w［i］=w［Q［i-1］.id］;
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回溯搜索
K.Backtrack(1); //从根开始搜索解空间树
K.print(); //输出最优解
cout<<"装入的物品编号为：";
for(int i=1;i<=n;i++)
if(K.bestx［i］)
cout<<Q［i-1］.id<<" ";
cout<<endl;
delete ［］ Q;
delete ［］ K.w;
delete ［］ K.p;
delete ［］ K.x;
delete ［］ K.bestx;
delete ［］ bestx;
return K.bestp; //返回最优值
}
int main(){
int p［］={0,9,10,7,4};
int w［］={1,3,5,2,1};
int c = 7;
int n = 4;
int bestp = Knapsack(p,w,c,n);
cout<<"最大价值为："<<bestp<<endl;
return 0;
}
【例58】最大团问题。
（1） 问题描述。
给定无向图G=(V，E)。如果UV，且对任意u，v∈U，有(u，v)∈E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。最大团问题就是要求找出无向图G的包含顶点个数最多的团。
（2） 问题分析。
根据问题描述可知，最大团问题就是要求找出无向图G=(V，E)的n个顶点集合{1,2,3,…,n}的一部分顶点V′，即n个顶点集合{1,2,3,…,n}的一个子集，这个子集中的任意两个顶点在无向图Ｇ中都有边相连，且包含顶点个数是n个顶点集合{1,2,3,…,n}所有同类子集中包含顶点个数最多的。显然，问题的解空间是一棵子集树，解决方法与解决01背包问题类似。
（3） 解题步骤。
步骤1： 定义问题的解空间。
问题解的形式为n元组，每一个分量的取值为0或1，即问题的解是一个n元01向量。具体形式为： （x1,x2,…,xn），其中xi=0或1，i=1,2,…,n。xi=1表示图G中第i个顶点在团里，xi=0表示图G中第i个顶点不在团里。
步骤2： 确定解空间的组织结构。
解空间是一棵子集树，树的深度为n。
步骤3： 搜索解空间。
步骤31： 确定是否需要约束条件，如果需要，如何设置？
最大团问题的解空间包含2n个子集，这些子集中存在集合中的某两个顶点没边相连的情况。显然，这种情况下的可能解不是问题的可行解。故需要设置约束条件来判断是否有可能导致问题的可行解。
假设当前扩展结点处于解空间树的第t层，那么从第1个顶点到第t-1个顶点的状态（有没有在团里）已经确定。接下来沿着扩展结点的左分支进行扩展，此时需要判断是否将第t个顶点放入团里。只要第t个顶点与前t-1个顶点中在团里的那些顶点有边相连，则能放入团中，否则，就不能放入团中。因此，约束函数描述如下：
Bool Place（int t）
{
Bool OK=true;
for (int j=1; j<t; j++)
if (x［j］ && a［t］［j］==0) //顶点t与顶点j不相连
{
OK=false;
break;
}
return OK;
}
其中，形式参数t表示第t个顶点，Place(t)用来判断第t个顶点能否放入团。二维数组a［］［］是图G的邻接矩阵。一维数组x［］记录当前解。搜索到第t层时，从第1个顶点到第t-1个顶点的状态存放在x［1:t-1］中。
步骤32： 确定是否需要限界条件？如果需要，如何设置？
最大团问题的可行解可能不止一个，问题的目标是找一个包含的顶点个数最多的可行解，即最优解。因此，需要设置限界条件来加速寻找该最优解的速度。
如何设置限界条件呢？与01背包问题类似。假设当前的扩展结点为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。
图523无向图
步骤33： 搜索过程。最大团问题的搜索和01背包问题的搜索相似，只是进行判断的约束条件和限界条件不同而已。以图523给定的无向图为例，按照01背包问题的搜索过程形成的搜索树如图524所示。找到问题的解是从根结点A到叶子结点N的路径（0,1,1,1,1）已在图524中用粗线画出，求得的最大团如图525所示。
图524搜索树
图525最大团
（4） 算法描述。
令一维数组x记录当前解，一维数组bestx记录当前最优解，变量cn、bestn分别记录当前已包含在团里的顶点个数和当前最优解包含的在团里的顶点个数，初始时均为0。找出最大团的算法中关键是判断当前顶点是否能够放入团里的约束条件，如果能放入团，就进行更深一层搜索； 否则判断限界函数是否满足，如果满足则更深一层搜索，反之，回溯到最近的活结点。回溯搜索的算法描述如下：
void Backtrack(int t)
{
if (t > n) //到达叶结点
{
for(int i=1;i<=n;i++)
bestx［i］=x［i］;
bestn=cn;
return;
}
if (Place(t)) //进入左子树
{
x［t］=1;
cn++;
Backtrack(t+1);
cn--;
}
if (cn+n-t>bestn) //进入右子树
{
x［t］=0;
Backtrack(t+1);
}
}//end Backtrack
搜索解空间树时要从根结点开始，以深度优先的方式进行。故初始化工作完成后，只需要调用Backtrack(1)便可求得最大团。
（5） 算法分析。
判断约束函数需耗时O(n)，在最坏情况下有2n-1个左子树，耗时最坏为O(n2n)。判断限界函数需要O(1)时间，在最坏情况下有2n-1个右孩子结点需要判断限界函数，耗时最坏为O(2n)。因此，最大团问题的回溯算法所需的计算时间为O(2n)+O(n2n)=O(n2n)。
（6） C++实战。
相关代码如下。
#include<iostream>
using namespace std;
class Max_Clique{
public:
Max_Clique(int n,int cn,int bestn)
{
this->n = n;
this->cn = cn;
this->bestn = bestn;
}
void Backtrack(int t);
void print()
{
cout<<"最优解为：";
for(int i=1;i<=n;i++)
cout<<bestx［i］<<" ";
cout<<endl;
}
bool place(int t);
int *x;
int **a;
int *bestx;
int n;
int cn;
int bestn;
};
bool Max_Clique::place(int t)
{
bool OK=true;
for (int j=1; j<t; j++)
if (x［j］ && a［t］［j］==0)// 顶点t与顶点j不相连
{
OK=false;
break;
}
return OK;
}
void Max_Clique::Backtrack(int t)
{
if (t > n) // 到达叶结点
{
for(int i=1;i<=n;i++)
bestx［i］=x［i］;
bestn=cn;
return;
}
if (place(t)) // 进入左子树
{
x［t］=1;
cn++;
Backtrack(t+1);
cn--;
}
if (cn+n-t>bestn) // 进入右子树
{
x［t］=0;
Backtrack(t+1);
}
}//end Backtrack
int main(){
cout<<"请输入图的顶点数n:";
int n;
cin>>n;
Max_Clique clique(n,0,0);
clique.bestx = new int［n+1］;
clique.x = new int［n+1］;
clique.a = new int*［n+1］;
for(int i=0;i<=n;i++)
{
clique.a［i］ = new int ［n+1］;
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++)
cin>>clique.a［i］［j］;
}
clique.Backtrack(1);
clique.print();
cout<<"最大团顶点个数为："<<clique.bestn<<endl;
delete ［］clique.bestx;
delete ［］clique.x;
delete ［］ clique.a;
}
视频讲解
视频讲解
视频讲解
5.3.3排列树
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。
图526n=3的排列树
n=3时的排列树如图526所示。
在排列树中从根到叶子的路径描述了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）。
在排列树中，树的根结点表示初始状态（所有位置全部没有放置元素）； 中间结点表示某种情况下的中间状态（中间结点之前的位置上已经确定了元素，中间结点之后的位置上还没有确定元素）； 叶子结点表示结束状态（所有位置上的元素全部确定）； 分支表示从一个状态过渡到另一个状态的行为（在特定位置上放置元素）； 从根结点到叶子结点的路径表示一个可能的解（所有元素的一个排列）。排列树的深度等于问题的规模。
解空间树为排列树的问题有很多，如：
n皇后问题： 满足显约束为不同行、不同列的解空间树。约定不同行的前提下，n个皇后的列位置是n个列的一个排列，这个排列必须满足n个皇后的位置不在一条斜线上。
旅行商问题： 找出n个城市的一个排列，沿着这个排列的顺序遍历n个城市，最后回到出发城市，求长度最短的旅行路径。
批处理作业调度问题： 给定n个作业的集合{J1,J2,…,Jn}，要求找出n个作业的一个排列，按照这个排列进行调度，使得完成时间和达到最小。
圆排列问题： 给定n个大小不等的圆c1,c2,…,cn，现要将这n个圆放入一个矩形框，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出具有最小长度的圆排列。
电路板排列问题： 将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. 排列树的算法描述模式
void Backtrack(int t)
{
if (t>n) output(x);
else
for (int i=t;i<=n;i++)
{
swap(x［t］, x［i］);
if (constraint(t)&&bound(t))
Backtrack(t+1);
swap(x［t］, x［i］);
}
}
这里，形式参数t表示扩展结点在解空间树中所处的层次，n表示问题的规模，即解空间树的深度，x［］是用来存储当前解的数组，初始化x［i］=i(i=1,2,…,n)，constraint()为约束函数，bound()为限界函数，swap()函数实现两个元素位置的交换。
3. 排列树的构造实例
【例59】批处理作业调度问题。
（1） 问题描述。
给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，再由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业Ji在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作业，制定出最佳作业调度方案，使其完成时间和达到最小。
（2） 问题分析。
根据问题描述可知，批处理作业调度问题要求找出n个作业{J1,J2,…,Jn}的一个排列，按照这个排列的顺序进行调度，使得完成n个作业的完成时间和最小。按照回溯算法的算法框架，首先需要定义问题的解空间，然后确定解空间的组织结构，最后进行搜索。搜索前要解决两个关键问题，一是确定问题是否需要约束条件（判断是否有可能产生可行解的条件），如果需要，如何设置。由于作业的任何一种调度次序不存在无法调度的情况，均是合法的。因此，任何一个排列都表示问题的一个可行解。故不需要约束条件； 二是确定问题是否需要限界条件，如果需要，如何设置。在n个作业的n!种调度方案（排列）中，存在完成时间和多与少的情况，该问题要求找出完成时间和最少的调度方案。因此，需要设置限界条件。
（3） 解题步骤。
步骤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： 搜索解空间。
步骤31： 由于不需要约束条件，故无须设置。
步骤32： 设置限界条件。
用cf表示当前已完成调度的作业所用的时间和，用bestf表示当前找到的最优调度方案的完成时间和。显然，继续向纵深处搜索时，cf不会减少，只会增加。因此当cf≥bestf时，没有继续向纵深处搜索的必要。限界条件可描述为： cf<bestf，cf的初始值为0，bestf的初始值为＋∞。
步骤33： 搜索过程。扩展结点沿着某个分支扩展时需要判断限界条件，如果满足，则进入深一层继续搜索； 如果不满足，则将扩展生成的结点剪掉。搜索到叶子结点时，即找到当前最优解。搜索过程直到全部活结点变成死结点为止。
（4） 批处理作业调度问题的构造实例。
注： 行分别表示作业J1,J2和J3； 列分别表示机器1和机器2。表中数据表示tji，即作业Ji需要机器j的处理时间。
考虑n=3的实例，每个作业在两台机器上的处理时间如表51所示。
表51作业的处理时间
作业
机器1
机器2
J1
2
1
J2
3
1
J3
2
3
搜索过程如图527~图533所示：从根结点A开始，结点A成为活结点，并且是当前的扩展结点，如图527（a）所示。扩展结点A沿着x1=1的分支扩展，F11=2，F21=3，故cf=3，bestf=+∞，cf<bestf，限界条件满足，扩展生成的结点B成为活结点，并且成为当前的扩展结点，如图527（b)所示。扩展结点B沿着x2=2的分支扩展，F12=5，F22=6，故cf=F21+F22=9，bestf=+∞，cf<bestf，限界条件满足，扩展生成的结点E成为活结点，并且成为当前的扩展结点，如图527（c)所示。扩展结点E沿着x3=3的分支扩展，F13=7，F23=10，故cf=F21+F22+F23=19,bestf=+∞,cf<bestf，限界条件满足，扩展生成的结点K是叶子结点。此时，找到当前最优的一种调度方案（1,2,3），同时修改bestf=19，如图527（d)所示。
图527搜索过程1
叶子结点K不具备扩展能力，开始回溯到活结点E。结点E只有一个分支，且已搜索完毕，因此结点E成为死结点，继续回溯到活结点B，结点B再次成为扩展结点，如图528（a)所示。扩展结点B沿着x2=3的分支扩展，cf=10，bestf=19，cf<bestf，限界条件满足，扩展生成的结点F成为活结点，并且成为当前的扩展结点，如图528（b)所示。扩展结点F沿着x3=2的分支扩展，cf=18，bestf=19，cf<bestf，限界条件满足，扩展生成的结点L是叶子结点。此时，找到比先前更优的一种调度方案（1,3,2），修改bestf=18，如图528（c)所示。从叶子结点L开始回溯到活结点F。结点F的一个分支已搜索完毕，结点F成为死结点，回溯到活结点B。结点B的两个分支已搜索完毕，回溯到活结点A，结点A再次成为扩展结点，如图528（d)所示。
图528搜索过程2
扩展结点A沿着x1=2的分支扩展，cf=4，bestf=18，cf<bestf，限界条件满足，扩展生成的结点C成为活结点，并成为当前的扩展结点，如图529（a)所示。扩展结点C沿着x2=1的分支扩展，cf=10，bestf=18，cf<bestf，限界条件满足，扩展生成的结点G成为活结点，并成为当前的扩展结点，如图529（b)所示。扩展结点G沿着x3=3的分支扩展，cf=20，bestf=18，cf>bestf，限界条件不满足，扩展生成的结点被剪掉，如图529（c)所示。
图529搜索过程3
结点G的一个分支搜索完毕，结点G成为死结点，继续回溯到活结点C，如图530（a）所示。扩展结点C沿着x2=3的分支扩展，cf=12，bestf=18，cf<bestf，限界条件满足，扩展生成的结点H成为活结点，并成为当前的扩展结点，如图530（b）所示。扩展结点H沿着x3=1的分支扩展，cf=21，bestf=18，cf>bestf，限界条件不满足，扩展生成的结点被剪掉。结点H的一个分支搜索完毕，开始回溯到活结点C。此时，结点C的两个分支已搜索完毕，继续回溯到活结点A，结点A再次成为当前的扩展结点，如图530（c)所示。
图530搜索过程4
扩展结点A沿着x1=3的分支扩展，cf=5，bestf=18，cf<bestf，限界条件满足，扩展生成的结点D成为活结点，并成为当前的扩展结点，如图531（a)所示。扩展结点D沿着x2=1的分支扩展，cf=11，bestf=18，cf<bestf，限界条件满足，扩展生成的结点I成为活结点，并成为当前的扩展结点，如图531（b)所示。
图531搜索过程5
扩展结点I沿着x3=2的分支扩展，cf=19，bestf=18，cf>bestf，限界条件不满足，扩展生成的结点被剪掉，回溯到活结点D，结点D再次成为当前的扩展结点，如图532（a）所示。扩展结点D沿着x2=2的分支扩展，cf=11，bestf=18，cf<bestf，限界条件满足，扩展生成的结点J成为活结点，并成为当前的扩展结点，如图532（b）所示。
图532搜索过程6
扩展结点J沿着x3=1的分支扩展，cf=19，bestf=18，cf>bestf，限界条件不满足，扩展生成的结点被剪掉，回溯到活结点D，结点D的两个分支搜索完毕，继续回溯到活结点A，如图533（a）所示。活结点A的3个分支也已搜索完毕，结点A变成死结点，搜索结束。至此，找到的最优的调度方案为从根结点A到叶子结点L的路径（1, 3, 2），如图533（b）所示。
图533搜索过程7
（5） 算法描述。
为了对解决该问题的方法进行描述，设置了数组x、bestx和m，变量f1、f2、cf和bestf，其中数组x用来记录当前调度，bestx用来记录当前最优调度，初始时，x［i］=i，bestx［i］=0，i=1,2,…,n。二维数组m记录各作业分别在两台机器上的处理时间； f1记录作业在第一台机器上的完成时间和，f2记录作业在第二台机器上的完成时间和，cf记录当前在第二台机器上的完成时间和，bestf记录当前最优调度的完成时间和。求解该问题的算法描述如下：
void Backtrack(int t)
{
int tempf,j;
if(t>n)//到达叶子结点
{for(int i=1;i<=n;i++)
bestx［i］=x［i］;
bestf=cf;
return;
}//end if
for(j=t; j <=n; j++)//非叶子结点
{f1+=m［x［j］］［1］;tempf=f2; //保存上一个作业在机器2的完成时间
f2=(f1>f2?f1:f2)+m［x［j］］［2］; //当前作业在机器2的完成时间
cf+=f2; //以确定的调度作业在机器2上的完成时间和
if(cf<bestf)
{swap(x［t］, x［j］); //交换两个元素的值
Backtrack(t+1);
swap(x［t］, x［j］);
}
f1-=m［x［j］］［1］;
cf-=f2;
f2=tempf;
}//end for
}
求解问题时，先将相关量初始化，然后从根结点开始搜索，即Backtrack(1)就可以求得问题的最优解。
（6） 算法分析。
计算限界函数需要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!)=O((n+1)!)。
(7) C++实战。
相关代码如下。
#include<iostream>
#include<cfloat>
#define INF DBL_MAX
using namespace std;
class Jobs_Schedule{
public:
Jobs_Schedule(int n,double cf,double bestf,double f1,double f2)
{
this->n = n;
this->cf = cf;
this->bestf = bestf;
this->f1 = f1;
this->f2 = f2;
}
void Backtrack(int t);
void print()
{
cout<<"最优解为：";
for(int i=1;i<=n;i++)
cout<<bestx［i］<<" ";
cout<<endl;
}
int *x;
double **m; //存储作业编号及作业在机器上的处理实践
double f1,f2; //f1为第一台机器的完成时间和，f2为第二台机
//器上的完成时间和
int *bestx; //最优解
int n; //作业个数
double cf; //当前第二台机器上的完成时间和
double bestf; //第二台机器的当前最小的完成时间和
};
void Jobs_Schedule::Backtrack(int t)
{
int tempf,j,temp;
if(t>n)//到达叶子结点
{
for(int i=1;i<=n;i++)
bestx［i］=x［i］;
bestf=cf;
return;
}//end if
for(j=t; j <=n; j++)//非叶子结点
{
f1+=m［x［j］］［1］;
tempf=f2; //保存上一个作业在机器2的完成时间
f2=(f1>f2?f1:f2)+m［x［j］］［2］; //当前作业在机器2的完成时间
cf+=f2; //以确定的调度作业在机器2上的完成时间和
if(cf<bestf)
{swap(x［t］, x［j］); //交换两个元素的值
Backtrack(t+1);
swap(x［t］, x［j］);
}
f1-=m［x［j］］［1］;
cf-=f2;
f2=tempf;
}//end for
}//end Backtrack
int main(){
cout<<"请输入图作业数n:";
int n;
cin>>n;
Jobs_Schedule schedule(n,0,INF,0,0);
schedule.bestx = new int［n+1］;
schedule.x = new int［n+1］;
schedule.m = new double*［n+1］;
for(int i=0;i<=n;i++)
{
schedule.m［i］ = new double［3］;
schedule.x［i］ = i;
}
//m的第0行舍弃，从第一行是第一个作业在第一台和第二台机器上的处理时间
//m中存储的元素为(编号，第一台机器的处理时间，第二台机器的处理时间)
for(int i=0;i<=n;i++){
for(int j=1;j<3;j++)
cin>>schedule.m［i］［j］;
schedule.m［i］［0］=i;
}
schedule.Backtrack(1);
schedule.print();
cout<<"最小完成时间和为："<<schedule.bestf<<endl;
delete ［］schedule.bestx;
delete ［］schedule.x;
for(int i=0;i<=n;i++)
delete ［］ schedule.m［i］;
delete ［］ schedule.m;
}
【例510】旅行商问题。
（1） 问题描述。
设有n个城市组成的交通图，一个售货员从住地城市出发，到其他城市各一次去推销货物，最后回到住地城市。假定任意两个城市i，j之间的距离dij(dij=dji)是已知的，问应该怎样选择一条最短的路线？
（2） 问题分析。
旅行商问题给定n个城市组成的无向带权图G=(V，E)，顶点代表城市，权值代表城市之间的路径长度。要求找出以住地城市开始的一个排列，按照这个排列的顺序推销货物，所经路径长度是最短的。问题的解空间是一棵排列树。显然，对于任意给定的一个无向带权图，存在某两个城市（顶点）之间没有直接路径（边）的情况。也就是说，并不是任何一个以住地城市开始的排列都是一条可行路径（问题的可行解），因此需要设置约束条件，判断排列中相邻两个城市之间是否有边相连，有边相连则能走通； 反之，不是可行路径。另外，在所有可行路径中，要找一条最短的路线，因此需要设置限界条件。
（3） 解题步骤。
步骤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的旅行商问题的解空间树如图534所示。
步骤3： 搜索解空间。
步骤31： 设置约束条件。
用二维数组g［］［］存储无向带权图的邻接矩阵，如果g［i］［j］≠∞表示城市i和城市j有边相连，能走通。
步骤32： 设置限界条件。
用cl表示当前已走过的城市所用的路径长度，用bestl表示当前找到的最短路径的路径长度。显然，继续向纵深处搜索时，cl不会减少，只会增加。因此当cl≥bestl时，没有继续向纵深处搜索的必要。限界条件可描述为： cl<bestl，cl的初始值为0，bestf的初始值为＋∞。
步骤33： 搜索过程。扩展结点沿着某个分支扩展时需要判断约束条件和限界条件，如果两者都满足，则进入深一层继续搜索。反之，剪掉扩展生成的结点。搜索到叶子结点时，找到当前最优解。搜索过程直到全部活结点变成死结点。
（4） 旅行商问题的构造实例。
考虑n=5的无向带权图，如图535所示。
图534n=4的解空间树
图535无向带权图
搜索过程如图536~图540所示： 由于排列的第一个元素已经确定，即推销员的住地城市1，搜索从根结点A0的孩子结点A开始，结点A是活结点，并且成为当前的扩展结点，如图536(a)所示。扩展结点A沿着x2=2的分支扩展，城市1和城市2有边相连，约束条件满足； cl=10，bestl=∞，cl<bestl，限界条件满足，扩展生成的结点B成为活结点，并且成为当前的扩展结点，如图536(b)所示。扩展结点B沿着x3=3的分支扩展，城市2和城市3有边相连，约束条件满足； cl=25，bestl=∞，cl<bestl，限界条件满足，扩展生成的结点C成为活结点，并且成为当前的扩展结点，如图536(c)所示。扩展结点C沿着x4=4的分支扩展，城市3和城市4有边相连，约束条件满足； cl=32，bestl=∞，cl<bestl，限界条件满足，扩展生成的结点D成为活结点，并且成为当前的扩展结点，如图536(d)所示。
图536搜索过程1
扩展结点D沿着x5=5的分支扩展，城市4和城市5有边相连，约束条件满足； cl=38，bestl=∞，cl<bestl，限界条件满足，扩展生成的结点E是叶子结点。由于城市5与住地城市1有边相连，故找到一条当前最优路径（1,2,3,4,5），其长度为50，修改bestl=50，如图537(a)所示。接下来开始回溯到结点D，再回溯到结点C，C成为当前的扩展结点，如图537(b)所示。
图537搜索过程2
以此类推，第一次回溯到第二层的结点A时的搜索树如图538所示。结点旁边的“×”表示不能从推销货物的最后一个城市回到住地城市。
图538搜索过程3
第二层的结点A再次成为扩展结点，开始沿着x2=3的分支扩展，城市1和城市3之间没有边相连，不满足约束条件，扩展生成的结点被剪掉。沿着x2=4的分支扩展，满足约束条件和限界条件，进入其扩展的孩子结点继续搜索。搜索过程略。此时，找到当前最优解（1，4，3，2，5），路径长度为43。直到第二次回溯到第二层的结点A时所形成的搜索树如图539所示。
图539搜索过程4
结点A沿着x2=5的分支扩展，满足约束条件和限界条件，进入其扩展的孩子结点继续搜索，搜索过程略。直到第三次回溯到第二层的结点A时所形成的搜索树如图540所示。此时，搜索过程结束，找到的最优解为图540中粗线条描述的路径（1,4,3,2,5），路径长度为43。
图540搜索过程5
（5） 算法描述。
该问题的算法描述中，二维数组g表示图的邻接矩阵，数组x、bestx分别记录当前路径和当前最优路径。注意，初始时，x数组中各元素的值和其所在的位置下标相等，bestx中的元素全部为0，即x［i］=i，bestx［i］=0,i=1,2,…,n。变量cl和bestl分别表示当前路径长度和当前最短路径的路径长度。cl=0,bestl=∞。求解该问题的算法描述如下：
void Traveling(int t)
{
if(t>n)//到达叶子结点
{
//推销货物的最后一个城市与住地城市有边相连并且路径长度比当前最优值小，说明找到了一条
//更好的路径，记录相关信息
if(g［x［n］］［1］ !=∞&& (cl+g［x［n］］［1］< bestl))
{
for(j=1;j<=n;j++)
bestx［j］=x［j］;
bestl=cl+g［x［n］］［1］;
}
}
else//没有到达叶子结点
for(j=t;j<=n;j++)//搜索扩展结点的所有分支
//如果第t-1个城市与第t个城市有边相连并且有可能得到更短的路线
if(g［x［t-1］］［x［j］］ !=∞ && (cl+g［x［t-1］］［x［j］］< bestl))
{//保存第t个要去的城市编号到x［t］中，进入第t+1层
swap(x［t］,x［j］); //交换两个元素的值
cl+=g［x［t-1］］［x［t］］;
Traveling(t+1); //从第t+1层的扩展结点继续搜索
//第t+1层搜索完毕，回溯到第t层
cl-=g［x［t-1］］［x［t］］;
swap(x［t］,x［j］);
}
}
由于旅行商从住地出发，首先推销商品的城市是住地城市，因此，求旅行商最短路径的时候，只需要从解空间树的第二层结点开始搜索就行，即Traveling(2)。
（6） 算法分析。
判断限界函数需要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!)。
(7) C++实战。
相关代码如下。
#include<iostream>
#include<cfloat>
#define INF DBL_MAX
using namespace std;
class Traving_salesman_problem{
public:
Traving_salesman_problem(int n,double cl,double bestl)
{
this->n = n;
this->cl = cl;
this->bestl = bestl;
}
void Traveling(int t)
{
if(t>n)//到达叶子结点
{
//推销货物的最后一个城市与住地城市有边相连并且路径长度比当前最优值小，说
//明找到了一条更好的路径，记录相关信息
if(g［x［n］］［1］ != INF && (cl+g［x［n］］［1］< bestl))
{
for(int j=1;j<=n;j++)
bestx［j］=x［j］;
bestl=cl+g［x［n］］［1］;
}
}
else //没有到达叶子结点
for(int j=t;j<=n;j++)//搜索扩展结点的所有分支
//如果第t-1个城市与第t个城市有边相连并且有可能得到更短的路线
{
if(g［x［t-1］］［x［j］］ != INF && (cl+g［x［t-1］］［x［j］］< bestl))
{//保存第t个要去的城市编号到x［t］中，进入第t+1层
swap(x［t］,x［j］); //交换两个元素的值
cl+=g［x［t-1］］［x［t］］;
Traveling(t+1); //从第t+1层的扩展结点继续搜索
//第t+1层搜索完毕，回溯到第t层
cl-=g［x［t-1］］［x［t］］;
swap(x［t］,x［j］);
}
}
}
void print()
{
cout<<"最优解为：";
for(int i=1;i<=n;i++)
cout<<bestx［i］<<" ";
cout<<endl;
}
int *x;
double **g; //存储作业编号及作业在机器上的处理实践
int *bestx; //最优解
int n; //作业个数
double cl; //当前第二台机器上的完成时间和
double bestl; //第二台机器的当前最小的完成时间和
};
int main(){
cout<<"请输入图作业数n:";
int n;
cin>>n;
Traving_salesman_problem tsp(n,0,INF);
tsp.bestx = new int［n+1］;
tsp.x = new int［n+1］;
tsp.g = new double*［n+1］;
for(int i=0;i<=n;i++)
{
tsp.g［i］=new double［n+1］;
tsp.x［i］=i; //解向量初始化，必须是下标与顶点编号一致， 按照
//顶点编号的顺序初始化x
}
//g为图的邻接矩阵，其第0行、0列舍弃，从第一行是1号顶点和其他顶点的连接边及边权情况
for(int i=0;i<=n;i++){
for(int j=1;j<=n;j++)
cin>>tsp.g［i］［j］;
tsp.g［i］［0］=0;
}
tsp.Traveling(2);
tsp.print();
cout<<"最短路径长度为："<<tsp.bestl<<endl;
delete ［］tsp.bestx;
delete ［］tsp.x;
for(int i=0;i<=n;i++)
delete ［］ tsp.g［i］;
delete ［］ tsp.g;
}
视频讲解
视频讲解
5.3.4满m叉树
1. 概述
满m叉树是用回溯算法解题时经常遇到的第三种典型的解空间树，也可以称为组合树。当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合。这类问题的解空间树称为满m叉树。此类问题解的形式为n元组（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i个元素的选择为xi。n=3时的满m=3叉树如图541所示。
图541满3叉树
在满m叉树中从根到叶子的路径描述了n个元素的一种选择。树的根结点表示初始状态（任何一个元素都没有确定），中间结点表示某种情况下的中间状态（一些元素的选择已经确定，另一些元素的选择没有确定），叶子结点表示结束状态（所有元素的选择均已确定），分支表示从一个状态过渡到另一个状态的行为（特定元素做何种选择），从根结点到叶子结点的路径表示一个可能的解（所有元素的一个排列）。满m叉树的深度等于问题的规模n。
解空间树为满m叉树的问题有很多，如：
n皇后问题： 显约束为不同行的解空间树，在不同行的前提下，任何一个皇后的列位置都有n种选择。n个列位置的一个组合必须满足n个皇后的位置不在同一列或不在同一条斜线上的性质。这个问题的解空间便是一棵满m（m=n）叉树。
图的m着色问题： 给定无向连通图G 和m 种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G 中有边相连的两个顶点着不同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图G和m 种颜色，找出所有不同的着色法。这个问题实质上是用给定的m种颜色给无向连通图G的顶点着色。每一个顶点所着的颜色有m种选择，找出n个顶点着色的一个组合，使其满足有边相连的两个顶点之间所着颜色不相同。很明显，这是一棵满m叉树。
最小重量机器设计问题可以看作给机器的n个部件找供应商，也可以看作m个供应商供应机器的哪个部件。如果看作给机器的n个部件找供应商，则问题实质为： n个部件中的每一个部件均有m种选择，找出n个部件供应商的一个组合，使其满足n个部件的总价格不超过c且总重量是最小的。问题的解空间是一棵满m叉树。如果看作m个供应商供应机器的哪个部件，则问题的解空间是一棵排列树，读者可以自己思考一下原因。
可见，对于要求找出n个元素的一个组合，该组合需要满足一定特性这类问题，均可采用满m叉树描述它们的解空间结构。这类问题在解题时可采用统一的算法设计模式。
2. 满m叉树的算法描述模式
void Backtrack(int t)
{
if (t>n) output(x);
else
for (int i=1;i<=m;i++)
if (constraint(t)&&bound(t))
{
x［t］=i;
做其他相关标识；
Backtrack(t+1);
做其他相关标识的反操作； //退回相关标识
}
}
这里，形式参数t表示扩展结点在解空间树中所处的层次，n表示问题的规模，即解空间树的深度，m表示每一个元素可选择的种数。x是用来存放解的一维数组，初始化为x［i］=0(i=1,2,…,n)，constraint()为约束函数，bound()为限界函数。
3. 满m叉树的构造实例
【例511】图的m着色问题。
（1） 问题描述。
给定无向连通图G=(V，E) 和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中有边相连的两个顶点着不同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图G和m 种颜色，找出所有不同的着色方法。
（2） 问题分析。
该问题中每个顶点所着的颜色均有m种选择，n个顶点所着颜色的一个组合是一个可能的解。根据回溯算法的算法框架，定义问题的解空间及其组织结构是很容易的。需要不需要设置约束条件和限界条件呢？从给定的已知条件来看，无向连通图G中假设有n个顶点，它肯定至少有n-1条边，有边相连的两个顶点所着颜色不相同，n个顶点所着颜色的所有组合中必然存在不是问题着色方案的组合，因此需要设置约束条件； 而针对所有可行解（组合），不存在可行解优劣的问题。所以，不需要设置限界条件。
（3） 解题步骤。
步骤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： 搜索解空间。
步骤31： 设置约束条件。
当前顶点要和前面已确定颜色且有边相连的顶点所着颜色不相同。假设当前扩展结点所在的层次为t，则下一步扩展就是要判断第t个顶点着什么颜色，第t个顶点所着的颜色要与已经确定所着颜色的第1~(t-1)个顶点中与其有边相连的颜色不相同。
约束函数可描述为：
bool OK(int t)
{for(int j=1;j<t;j++)
if(a［t］［j］)//a表示邻接矩阵
if(x［j］==x［t］) //x记录当前解
return false;
return true;
}
步骤32： 无须设置限界条件。
步骤33： 搜索过程。扩展结点沿着某个分支扩展时需要判断约束条件，如果满足，则进入深一层继续搜索； 如果不满足，则扩展生成的结点被剪掉。搜索到叶子结点时，找到一种着色方案。搜索过程直到全部活结点变成死结点为止。
（4） 图的m着色问题构造实例。
图542无向连通图
给定如图542所示的无向连通图和m=3。
搜索过程如图543~图548所示： 从根结点A开始，结点A是当前的活结点，也是当前的扩展结点，它代表的状态是给定无向连通图中任何一个顶点还没有着色，如图543(a)所示。沿着x1=1分支扩展，满足约束条件，生成的结点B成为活结点，并成为当前的扩展结点，如图543(b)所示。扩展结点B沿着x2=1分支扩展，不满足约束条件，生成的结点被剪掉。然后沿着x2=2分支扩展，满足约束条件，生成的结点C成为活结点，并成为当前的扩展结点，如图543(c)所示。扩展结点C沿着x3=1和x3=2分支扩展，均不满足约束条件，生成的结点被剪掉。然后沿着x3=3分支扩展，满足约束条件，生成的结点D成为活结点，并成为当前的扩展结点，如图543(d)所示。
图543搜索过程1
扩展结点D沿着x4=1分支扩展，满足约束条件，生成的结点E成为活结点，并成为当前的扩展结点，如图544(a)所示。扩展结点E沿着x5=1和x5=2分支扩展，均不满足约束条件，生成的结点被剪掉。然后沿着x5=3分支扩展，满足约束条件，生成的结点F是叶子结点。此时，找到了一种着色方案，如图544(b)所示。从叶子结点F回溯到活结点E，结点E的所有孩子结点已搜索完毕，因此它成为死结点。继续回溯到活结点D，结点D再次成为扩展结点，如图544(c)所示。
图544搜索过程2
扩展结点D沿着x4=2和x4=3分支扩展，均不满足约束条件，生成的结点被剪掉。再回溯到活结点C。结点C的所有孩子结点搜索完毕，它成为死结点，继续回溯到活结点B，结点B再次成为扩展结点，如图545(a)所示。扩展结点B沿着x2=3分支继续扩展，满足约束条件，生成的结点G成为活结点，并成为当前的扩展结点，如图545(b)所示。扩展结点G沿着x3=1分支扩展，不满足约束条件，生成的结点被剪掉； 然后沿着x3=2分支扩展，满足约束条件，生成的结点H成为活结点，并成为当前的扩展结点，如图545(c)所示。
图545搜索过程3
扩展结点H沿着x4=1分支扩展，满足约束条件，生成的结点I成为活结点，并且成为当前的扩展结点，如图546(a)所示。扩展结点I沿着x5=1分支扩展，不满足约束条件，生成的结点被剪掉； 然后沿着x5=2分支扩展，满足约束条件，J已经是叶子结点，找到第2种着色方案，如图546(b)所示。从叶子结点J回溯到活结点I，结点I再次成为扩展结点，如图546(c)所示。
图546搜索过程4
沿着结点I的 x5=3分支扩展的结点不满足约束条件，被剪掉。此时结点I成为死结点。继续回溯到活结点H，结点H再次成为扩展结点，如图547(a)所示。沿着结点H的x4=2和x4=3分支扩展的结点不满足约束条件，被剪掉。此时结点H成为死结点。继续回溯到活结点G，结点G再次成为扩展结点，如图547(b)所示。沿着结点G的x3=3分支扩展的结点不满足约束条件，被剪掉。此时结点G成为死结点。继续回溯到活结点B，结点B的孩子结点已搜索完毕，继续回溯到结点A，如图547(c)所示。
图547搜索过程5
以此类推，扩展结点A沿着x1=2和x1=3分支扩展的情况如图548所示。
图548搜索过程6
最终找到6种着色方案，分别为根结点A到如图548(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） 算法描述。
在算法描述中，数组x记录着色方案； 变量sum记录着色方案的种数，初始为0； m为给定的颜色数； n为图的顶点个数。该算法的关键是判断当前顶点可以着哪种颜色。图的着色问题的算法描述如下：
void Backtrack(int t)//搜索函数
{
if(t>n)
{
sum++;
printf("第%d种方案： ＼n",sum);
for(int i=1;i<=n;i++)
cout<<x［i］<<"";
cout<<endl;
}
else
for(int i=1;i<=m;i++)
{
x［t］=i;
if(OK(t))
Backtrack(t+1);
}
}
从根结点开始搜索着色方案，即Backtrack(1)。
（6） 算法分析。
计算限界函数需要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)。
（7） C++实战。
相关代码如下。
#include<iostream>
#include<cfloat>
#define INF DBL_MAX
using namespace std;
class Graphic_m_colors{
public:
Graphic_m_colors(int n,int m,int sum){
this->n = n;
this->m = m;
this->sum = sum;
}
bool OK(int t){
for(int j=1;j<t;j++)
if(a［t］［j］)
if(x［j］==x［t］)
return false;
return true;
}
void Backtrack(int t)//搜索函数
{
if(t>n)
{
sum++;
cout<<"第"<<sum<<"种方案为："<<endl;
for(int i=1;i<=n;i++)
cout<<x［i］<<" ";
cout<<endl;
}
else
for(int i=1;i<=m;i++)
{
x［t］=i;
if(OK(t))
Backtrack(t+1);
}
}
int *x; //记录一种着色方案
int **a; //图的邻接矩阵
int n; //图的顶点个数
int m; //颜色数
int sum; //方案数
};
int main(){
cout<<"请输入图的顶点数n和颜色数m:";
int n,m;
cin>>n>>m;
Graphic_m_colors gmc(5,3,0);
gmc.x = new int［n+1］;
gmc.a = new int*［n+1］;
for(int i=0;i<=n;i++)
gmc.a［i］ = new int ［n+1］;
//g为图的邻接矩阵，其第0行、0列舍弃，从第一行是1号顶点和其他顶点的连接边及边权情况
for(int i=0;i<=n;i++){
for(int j=1;j<=n;j++)
cin>>gmc.a［i］［j］;
gmc.a［i］［0］=0;
}
gmc.Backtrack(1);
cout<<"共："<<gmc.sum<<"种着色方案。"<<endl;
delete ［］gmc.x;
for(int i=0;i<=n;i++)
delete ［］ gmc.a［i］;
delete ［］ gmc.a;
}
【例512】最小重量机器设计问题。
（1） 问题描述。
设某一机器由n个部件组成，每一个部件可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计。
（2） 问题分析。
该问题实质上是为机器部件选供应商。机器由n个部件组成，每个部件有m个供应商可以选择，要求找出n个部件供应商的一个组合，使其满足n个部件总价格不超过c且总重量是最小的。显然，这个问题存在n个部件供应商的组合不满足总价格不超过c的条件，因此需要设置约束条件； 在n个部件供应商的组合满足总价格不超过c的前提下，哪个组合的总重量最小呢？要求找出总重量最小的组合，故需要设置限界条件。
（3） 解题步骤。
步骤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： 搜索解空间。
步骤31： 设置约束条件。约束条件设置为∑ni=1cixi≤c。
步骤32： 设置限界条件。
假设当前扩展结点所在的层次为t，则下一步扩展就是要判断第t个零件从哪个供应商处购买。如果第1~t 个部件的重量之和大于或等于当前最优重量，则没有继续深入搜索的必要。因为，再继续深入搜索也不会得到比当前最优解更优的一个解。令第1~t 个部件的重量之和用cw=∑ti=1wixi表示，价格之和用cc表示，二者初始值均为0。当前最优重量用bestw表示，初始值为+∞，限界条件可描述为： cw<bestw。
步骤33： 搜索过程。与图的m着色问题相同。
（4） 最小重量机器设计问题的构造实例。
注： 行分别表示部件1、2和3； 列分别表示供应商1、2和3； 表中数据表示wij： 从供应商j处购得的部件i的重量; cij表示从供应商j处购得的部件i的价格。
考虑n=3，m=3，c=7的实例。部件的重量如表52所示、价格如表53所示。
表52部件的重量表
供应商1供应商2供应商3
部件1123
部件2321
部件3232
表53部件的价格表
供应商1供应商2供应商3
部件1123
部件2542
部件3212
搜索过程如图549~图554所示。（注： 图中结点旁括号内的数据为已选择部件的重量之和、价格之和。）
从根结点A开始进行搜索，A是活结点且是当前的扩展结点，如图549(a)所示。扩展结点A沿x1=1分支扩展，cc=1≤c，满足约束条件； cw=1,bestw=∞，cw<bestw，满足限界条件。扩展生成的结点B成为活结点，并成为当前的扩展结点，如图549（b)所示。扩展结点B沿x2=1分支扩展，cc=6≤c，满足约束条件； cw=4,bestw=∞,cw<bestw，满足限界条件。扩展生成的结点C成为活结点，并成为当前的扩展结点，如图549（c)所示。扩展结点C沿x3=1分支扩展，cc=8>c，不满足约束条件，扩展生成的结点被剪掉。然后沿x3=2分支扩展，cc=7≤c，满足约束条件； cw=7,bestw=∞,cw<bestw，满足限界条件。扩展生成的结点D已经是叶子结点，找到了当前最优解，最优重量为7，将bestw修改为7，如图549（d)所示。
图549搜索过程1
从叶子结点D回溯到活结点C，活结点C再次成为当前的扩展结点。沿着它的x3=3分支扩展，不满足约束条件，扩展生成的结点被剪掉。继续回溯到活结点B，结点B成为当前的扩展结点，如图550(a)所示。扩展结点B沿x2=2分支扩展，cc=5≤c，满足约束条件； cw=3,bestw=7,cw<bestw，满足限界条件。扩展生成的结点E成为活结点，并成为当前的扩展结点，如图550(b)所示。扩展结点E沿x3=1分支扩展，cc=7≤c，满足约束条件； cw=5,bestw=7,cw<bestw，满足限界条件。扩展生成的结点F 已经是叶子结点，找到了当前最优解，最优重量为5，将bestw修改为5，如图550(c)所示。
图550搜索过程2
从叶子结点F回溯到活结点E，沿着它的x3=2和x3=3分支扩展，均不满足限界条件，扩展生成的结点被剪掉。继续回溯到活结点B，结点B成为当前的扩展结点，如图551(a)所示。扩展结点B沿x2=3分支扩展，cc=3≤c，满足约束条件； cw=2,bestw=5,cw<bestw，满足限界条件。扩展生成的结点G成为活结点，并成为当前的扩展结点，如图551(b)所示。扩展结点G沿x3=1分支扩展，cc=5≤c，满足约束条件； cw=4,bestw=5,cw<bestw，满足限界条件。扩展生成的结点H已经是叶子结点，找到了当前最优解，其重量为4，bestw修改为4，如图551(c)所示。
图551搜索过程3
从叶子结点H回溯到活结点G，沿着它的x3=2和x3=3分支扩展，均不满足限界条件，扩展生成的结点被剪掉。继续回溯到活结点B，结点B的3个分支均搜索完毕，继续回溯到活结点A，结点A成为当前的扩展结点，如图552(a)所示。扩展结点A沿x1=2分支扩展，cc=2≤c，满足约束条件； cw=2,bestw=4,cw<bestw，满足限界条件。扩展生成的结点I成为活结点，并成为当前的扩展结点，如图552(b)所示。
图552搜索过程4
扩展结点I沿x2=1和x2=2分支扩展，不满足限界条件，扩展生成的结点被剪掉。沿着x2=3分支扩展，cc=4≤c，满足约束条件； cw=3,bestw=4,cw<bestw，满足限界条件。扩展生成的结点J成为活结点，并成为当前的扩展结点，如图553(a)所示。扩展结点J沿x3=1、x3=2和x3=3分支扩展，均不满足限界条件，扩展生成的结点被剪掉。开始回溯到活结点I。结点I的3个分支已搜索完毕，继续回溯到活结点A，结点A再次成为扩展结点，如图553(b)所示。
图553搜索过程5
扩展结点A沿x1=3分支扩展，cc=3≤c，满足约束条件； cw=3,bestw=4,cw<bestw，满足限界条件。扩展生成的结点K成为活结点，并成为当前的扩展结点，如图554(a)所示。扩展结点K沿x2=1、x2=2和x2=3分支扩展，均不满足限界条件，扩展生成的结点被剪掉。开始回溯到活结点A。此时，结点A的3个分支均搜索完毕，搜索结束。找到了问题的最优解为从根结点A到叶子结点H的路径（1,3,1），最优重量为4，如图554(b)所示。
图554搜索过程6
（5） 算法描述。
最小重量机器设计问题涉及部件个数、部件重量、价格、供应商信息，用数组w，c分别存储部件的重量和价格，数组x、bestx分别记录当前解和当前最优解，变量cw、cc、bestw分别记录当前重量、当前花费、当前最优重量。将算法中用到的数据及对数据的操作定义为一个类，具体如下：
class MinMachine
{
int n; //部件个数
int m; //供应商个数
double COST; //题目中的C
double cw; //当前的重量
double cc; //当前花费
double bestw; //当前最小重量
int * bestx; int *x;
double ** w;
double ** c;
public:
MinMachine();//构造函数
void Backtrack(int i);//回溯搜索
void print();//输出最优解和最优重量最优价格
~MinMachine();//析构函数，释放new动态开辟的空间
};
类MinMachine的构造函数用于对数据成员的初始化，其描述如下：
MinMachine∷MinMachine()
{
cw=0; //当前的重量
cc=0; //当前花费
bestw=+∞; //当前最小重量
cout<<"请输入部件个数： "; cin>>n;
cout<<"请输入供应商个数： "; cin>>m;
cout<<"请输入总价格不超过： "; cin>>COST;
w=new double*［n+1］;
c=new double*［n+1］;
for(int i=0;i<=n;i++)
{
w［i］=new double［m+1］;
c［i］=new double［m+1］;
bestx=new int［n+1］;
x=new int［n+1］;
}
for(int j=1;j<=m;j++)
for(i=1;i<=n;i++)
{
cout<<"请输入第 "<<j<<" 个供应商的第 "<<i<<" 个部件的重量： ";
cin>>w［i］［j］;
cout<<"请输入第 "<<j<<" 个供应商的第 "<<i<<" 个部件的价格： ";
cin>>c［i］［j］;
if(w［i］［j］<0 || c［i］［j］<0)
{cout<<"重量或价钱不能为负数！＼n";i=i-1;}
}
}
类MinMachine的成员函数Backtrack()用于搜索解空间树。搜索问题的解时，从根结点开始，给形式参数t传递1。搜索过程中，沿其中一个分支扩展，判断约束条件和限界条件是否满足，如果满足，则更深一层搜索； 如果不满足，则换其他分支继续搜索； 如果没有其他分支，则回溯到最近的活结点继续搜索。
void MinMachine∷Backtrack(int t)
{
if(t>n) //到达叶子结点
{ bestw=cw;
for(int j=1;j<=n; j++) //保存当前最优解
bestx［j］= x［j］;
return;
}
for(int j=1; j<=m; j++) //非叶子结点，依次搜索每一个供应商
{ x［t］=j;
if(cc+c［t］［j］<=COST && cw+w［t］［j］<bestw)//判断约束条件和限界条件
{
cc+=c［t］［j］;cw+=w［t］［j］;
Backtrack(t+1); cc-=c［t］［j］;cw-=w［t］［j］;
}
}
}
类MinMachine的成员函数print()用于求解满足条件的问题的最优解并输出问题，即输出最优解及其对应的最小重量和所花费的钱数。
void MinMachine∷print()
{
double Totalc=0;//用于记录最优解所花费的钱数
Backtrack(1);//从根结点开始搜索解空间树，找出满足条件的解
cout<<"＼n最小重量机器的重量是: "<<bestw<<endl;
for(int k=1; k<=n; k++)
{
cout<<" 第 "<<k<<" 部件来自供应商 "<<bestx［k］<<"＼n";
Totalc+=c［k］［bestx［k］］;
}
cout<<"＼n该机器的总价钱是: "<<Totalc<<endl;
}
类MinMachine的析构函数~MinMachine（）用于释放new动态开辟的空间。
MinMachine∷~MinMachine（）
{
for(int i=0;i<=n;i++)
{
delete［］w［i］;
delete［］c［i］;
}
delete ［］w;
delete ［］c;
delete ［］bestx;
delete ［］x;
}
（6） 算法分析。
计算约束函数和限界函数需要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)。
(7) C++实战。
相关代码如下。
#include<iostream>
#include<cfloat>
#define INF DBL_MAX
using namespace std;
class MinMachine
{
public:
int n; //部件个数
int m; //供应商个数
double COST; //题目中的C
double cw; //当前的重量
double cc; //当前花费
double bestw; //当前最小重
int * bestx;
int *x;
double **w;
double **c;
public:
MinMachine(); //构造函数
void Backtrack(int i); //回溯搜索
void print(); //输出最优解和最优重量最优价格
~MinMachine(); //析构函数,释放new动态开辟的空间
};
MinMachine::MinMachine()
{
cw=0; //当前的重量
cc=0; //当前花费
bestw=INF; //当前最小重量
cout<<"请输入部件个数："; cin>>n;
cout<<"请输入供应商个数："; cin>>m;
cout<<"请输入总价格不超过："; cin>>COST;
w = new double *［n+1］;
c = new double *［n+1］;
for (int i=0;i<=n;i++)
{
w［i］ = new double［m+1］;
c［i］ = new double［m+1］;
bestx = new int［n+1］;
x = new int［n+1］;
}
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++)
{
cout<<"请输入第 "<<j<<" 个供应商的第 "<<i<<" 个部件的重量：";
cin>>w［i］［j］;
cout<<"请输入第 "<<j<<" 个供应商的第 "<<i<<" 个部件的价格：";
cin>>c［i］［j］;
if(w［i］［j］<0 || c［i］［j］<0)
{
cout<<"重量或价钱不能为负数!＼n";
i=i-1;
}
}
}
void MinMachine::Backtrack(int t)
{
if(t>n) //到达叶子结点
{
bestw = cw;
for(int j=1;j<=n; j++) //保存当前最优解
bestx［j］= x［j］;
return;
}
for(int j=1; j<=m; j++) //非叶子结点，依次搜索每一个供应商
{
x［t］=j;
if(cc+c［t］［j］<=COST && cw+w［t］［j］<bestw)//判断约束条件和限界条件
{
cc+=c［t］［j］;cw+=w［t］［j］;
Backtrack(t+1);
cc-=c［t］［j］;
cw-=w［t］［j］;
}
}
}
void MinMachine::print()
{
double Totalc=0; //用于记录最优解所花费的钱数
Backtrack(1); //从根结点开始搜索解空间树，找出满足条件的解
cout<<"＼n最小重量机器的重量是: "<<bestw<<endl;
for(int k=1; k<=n; k++)
cout<<" 第 "<<k<<" 部件来自供应商 "<<bestx［k］<<"＼n";
cout<<"＼n该机器的总价钱是: "<<Totalc<<endl;
}
MinMachine::~MinMachine()
{
for (int i=0;i<=n;i++)
{
delete ［］w［i］;
delete ［］c［i］;
}
delete ［］w;
delete ［］c;
delete ［］bestx;
delete ［］x;
}
int main(){
MinMachine min_machine;
min_machine.print(); //从根结点开始搜索解空间树，找出满足条件的解
}
视频讲解
5.4宽度优先搜索
1. 宽度优先搜索的思想
给定图G=(V，E)，它的初始状态是所有顶点均未被访问过，在图G中任选一个顶点v作为源点，则宽度优先搜索的思想为： 先访问顶点v，并将其标记为已访问过； 然后从v出发，依次访问v的邻接点（孩子结点）w1,w2,…,wt, 如果wi(i=1,2,…,t)未访问过，则标记wi为已访问过，将其插入队列； 然后再依次从队列中取出w1,w2,…,wt，访问它们的邻接点。以此类推，直到图中所有和源点v有路径相通的顶点均已访问过为止； 若此时图G中仍然存在未被访问过的顶点，则另选一个尚未访问过的顶点作为新的源点。重复上述过程，直到图中所有顶点均已访问过为止。
【例513】给定一个有向图，如图555所示，给出宽度优先搜索的一个序列。
（1） 问题分析。
根据宽度优先搜索的思想，初始状态是所有顶点均未被访问过，需要任选一个顶点作为源点，搜索过程中需要判断源点的邻接点是否被访问过，然后根据判断结果做不同的处理，目标状态为全部顶点已被访问过。为此，用一个标识数组Visited［］标记图中的顶点是否被访问过，初始Visited［］的值全部为0。若某顶点已访问过，则将数组Visited［］中的对应元素由0改为1。
（2） 搜索过程。
假定选择顶点1为源点，Visited［1］=1，输出顶点1，依次访问它的3个邻接点2、3、4，它们均未被访问过，将其输出，标记Visited［2~4］=1，并插入队列； 从队列中取出顶点2，它的邻接点5未被访问过，将其输出，标记Visited［5］=1，并将顶点5插入队列； 依次取出队列中的顶点，顶点3没有邻接点，顶点4的两个邻接点已访问过，顶点5没有邻接点。此时队列为空，图555中与顶点1相连通的顶点已访问完毕。再选择顶点7为源点，重复上述过程。搜索顺序如图556所示，图中虚线上的数据表示访问的次序。
图555有向图
图556搜索顺序
【例514】给定一个无向图，如图557所示，给出宽度优先搜索的一个序列。
搜索过程如下： 假定选择顶点1为源点，Visited［1］=1，输出顶点1，依次访问它的两个邻接点2、4，它们均未被访问过，将其输出，标记Visited［2］=1, Visited［4］=1，并插入队列； 从队列中取出顶点2，它的邻接点5未被访问过，将其输出，标记Visited［5］=1，并将5插入队列； 从队列中取出顶点4，它的邻接点3和7未被访问过，将其输出，标记Visited［3］=1，Visited［7］=1，并将顶点3和7插入队列； 依次取出队列中的顶点5和顶点3，顶点5的邻接点已访问过，顶点7的邻接点6未被访问过，标记Visited［6］=1，并将顶点6插入队列。取出队列中的顶点6，它的邻接点已访问过，此时，队列为空，搜索结束。搜索顺序如图558所示（注： 图中虚线上的数据表示访问的次序）。
图557无向图
图558搜索顺序
2. 宽度优先搜索算法描述
voidBFSV0(int v0)//从v0开始广度优先搜索所在的连通子图
{ int w；
visit(v0); visited［v0］=1;visit(v0)访问v0
InitQueue(&Q);//初始化空队
InsertQueue(&Q,v0)； // v0进队
while (!Empty(Q))
{
DeleteQueue(&Q, &v);//队头元素出队
for(int i=1;i<=n;i++)//依次访问v的邻接点
{
if(g［v］［i］!=0)w=i;//g表示图的邻接矩阵
if (!visited(w))
{ visit(w);visited［w］=1;InsertQueue(&Q, w);}//visit(w)访问w
}
}
}
BFS()//宽度优先搜索整个图G
{
for(int i=1;i<=n;i++)
if(visited［i］==0)
BFSV0(i);
}
3. C++实战
相关代码如下。
#include<iostream>
#include<queue>
using namespace std;
void BFSV0(int v0,int n,int **g,bool visited［］)//从v0开始广度优先搜索所在的连通子图
{
queue<int>Q;
cout<<v0<<" ";
visited［v0］=1;
Q.push(v0);
while (!Q.empty())
{
int v = Q.front(); //队头元素出队
Q.pop();
for(int i=1;i<=n;i++)//依次访问v的邻接点
{
if(g［v］［i］!=0){
int w=i;
if (!visited［w］)
{
cout<<w<<" ";
visited［w］=1;
Q.push(w);
}
}
}
}
}
BFS(int n,int **g,bool visited［］)//宽度优先搜索整个图G
{
for(int i=1;i<=n;i++)
if(visited［i］==0)
BFSV0(i,n,g,visited);
}
int main(){
cout<<"请输入顶点个数n:";
int n;
cin>>n;
//标记图中顶点是否被访问过，顶点编号从1开始
bool *visited = new bool［n+1］;
int **c = new int*［n+1］;
for(int i=0;i<=n;i++)
c［i］ = new int［n+1］;
//输入图的邻接矩阵
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cin>>c［i］［j］;
}
for(int i=1;i<=n;i++)
visited［i］=0; //用0表示顶点未被访问过
BFS(n,c,visited);
delete ［］visited;
for(int i=0;i<=n;i++)
delete ［］c［i］;
delete ［］c;
}
视频讲解
5.5分支限界算法
5.5.1分支限界算法的基本思想
分支限界算法类似于回溯算法，也是一种在问题的解空间树中搜索问题解的算法，它常以宽度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。分支限界算法首先将根结点加入活结点表（用于存放活结点的数据结构），接着从活结点表中取出根结点，使其成为当前扩展结点，一次性生成其所有孩子结点，判断孩子结点是舍弃还是保留，舍弃那些导致不可行解或导致非最优解的孩子结点，其余的被保留在活结点表中。再从活结点表中取出一个活结点作为当前扩展结点，重复上述扩展过程，一直持续到找到所需的解或活结点表为空时为止。由此可见，每一个活结点最多只有一次机会成为扩展结点。
可见，分支限界算法搜索过程的关键在于判断孩子结点是舍弃还是保留。因此，在搜索之前要设定孩子结点是舍弃还是保留的判断标准，这个判断标准与回溯算法搜索过程中用到的约束条件和限界条件含义相同。活结点表的实现通常有两种方法： 一是先进先出队列，二是优先级队列，它们对应的分支限界算法分别称为队列式(FIFO)分支限界算法和优先队列式分支限界算法。
队列式分支限界算法按照队列先进先出（FIFO）的原则选取下一个结点作为当前扩展结点。优先队列式分支限界算法按照规定的优先级选取队列中优先级最高的结点作为当前扩展结点。优先队列一般用二叉堆来实现： 最大堆实现最大优先队列，体现最大效益优先； 最小堆实现最小优先队列，体现最小费用优先。
分支限界算法的一般解题步骤为：
（1） 定义问题的解空间。
（2） 确定问题的解空间组织结构（树或图）。
（3） 搜索解空间。搜索前要定义判断标准（约束函数或限界函数），如果选用优先队列式分支限界算法，则必须确定优先级。
5.5.201背包问题
分别用队列式分支限界算法和优先队列式分支限界算法解01背包问题： n=4，w=［3,5,2,1］，v=［9,10,7,4］，C=7。
1. 求解步骤
步骤1： 定义问题的解空间。
该实例的解空间为（x1,x2,x3,x4），xi=0或1(i=1,2,3,4)。
步骤2： 确定问题的解空间组织结构。
该实例的解空间是一棵子集树，深度为4。
步骤3： 搜索解空间。
根据采用的搜索方法不同定义合适的约束条件和限界条件，然后开始搜索。初始时将根结点放入活结点表中。从活结点表中取出一个活结点作为当前的扩展结点，一次性生成扩展结点的所有孩子结点，判断是否满足约束条件和限界条件，如果满足，则将其插入活结点表； 反之则舍弃。搜索过程直到找到问题的解或活结点表为空为止。
2. 01背包问题实例的搜索过程演示
（1） 队列式分支限界算法。
定义约束条件为∑ni=1wixi≤C，限界条件为cp+rp>bestp。其中，cp表示当前已装入背包的物品总价值，初始值为0； rp表示剩余物品的总价值，初始值为所有物品的价值之和； bestp表示当前最优解，初始值为0，当cp>bestp时，更新bestp为cp。
采用队列式分支限界算法对该实例的搜索过程如图559~图562所示。 (注： 图中深色结点表示死结点，已不在活结点表中； 结点旁括号内的数据表示背包的剩余容量、已装入背包的物品价值。)
初始时，将根结点A插入活结点表中，结点A是唯一的活结点，如图559(a)所示。从活结点表中取出A，结点A是当前的扩展结点，一次性生成它的两个孩子结点B和C，结点B满足约束条件，将bestp改写为结点B的cp，即bestp=9； 对于结点C，由于cp=0，rp=21，bestp=9，满足限界条件，依次将B和C插入活结点表，如图559(b)所示。再从活结点表中取出一个活结点B作为当前的扩展结点，一次性生成B的两个孩子结点，左孩子结点不满足约束条件，舍弃； 对于右孩子结点D，由于cp=9，rp=11,bestp=9，满足限界条件，将结点D保存到活结点表中，如图559(c)所示。
图559搜索过程1
重复上述过程，从活结点表中取出C，结点C是当前的扩展结点，一次性生成它的两个孩子结点E和F，结点E满足约束条件，将bestp改写为结点E的cp，bestp=10。由于cp=0，rp=11，bestp=10，结点F满足限界条件。依次将E和F插入到活结点表中，如图560(a)所示。从活结点表中取出D，结点D是当前的扩展结点，一次性生成它的两个孩子结点G和H，结点G满足约束条件，将G插入活结点表，bestp改写为结点G的cp，bestp=16。由于cp=9，rp=4，bestp=16，结点H不满足限界条件，舍弃，如图560(b)所示。
图560搜索过程2
从活结点表中取出E，结点E是当前的扩展结点，一次性生成它的两个孩子结点I和J，结点I满足约束条件。将其插入活结点表，修改bestp=17。对于结点J，由于cp=10，rp=4，bestp=17，不满足限界条件，舍弃，如图561(a)所示。从活结点表中取出F，结点F是当前的扩展结点，一次性生成它的两个孩子结点K和L，结点K满足约束条件，插入活结点表。由于cp=0，rp=4，bestp=17，结点L不满足限界条件，舍弃，如图561(b)所示。
图561搜索过程3
从活结点表中取出G，结点G是当前的扩展结点，一次性生成它的两个孩子结点M和N，左孩子结点M满足约束条件且已经是叶子结点，此时找到了当前最优解，将M暂存临时变量bestJ中，修改bestp=20，右孩子结点N不满足限界条件，舍弃。如图562（a)所示。从活结点表中取出活结点I，它扩展生成的孩子结点不满足约束条件或限界条件，舍弃。再取一个活结点K，它扩展生成的左孩子结点O满足约束条件且已是叶子结点，又找到了一个解，由于该解对应的cp<bestp，故不保存； K扩展生成的右孩子不满足限界条件，舍弃。此时活结点表为空，算法结束，找到了问题的最优解，即从根结点A到叶子结点M的路径（粗线条表示的路径）（1,0,1,1,），最优值为20，如图562(b)所示。
图562搜索过程4
（2） 优先队列式分支限界算法。
优先级定义为： 活结点代表的部分解所描述的装入背包的物品价值上界，该价值上界越大，优先级越高。活结点的价值上界up=活结点的cp+剩余物品装满背包剩余容量的最大价值r′p。
约束条件： 同（1）中队列式分支限界算法相同。限界条件： up=cp+r′p>bestp。
采用优先队列式分支限界算法对上述实例的搜索过程如图563、图564所示。
初始时，将根结点A插入活结点表，结点A是唯一的活结点，如图563(a)所示。从活结点表中取出A，结点A是当前的扩展结点，一次性生成它的两个孩子结点B和C，结点B满足约束条件，将结点B插入活结点表，其up=9+4+7+15×10=22，bestp=cp=9； 结点C的up=0+4+7+45×10=19，满足限界条件，将C插入活结点表，如图563（b)所示。从活结点表中取出一个优先级最高的活结点B作为当前的扩展结点，一次性生成B的两个孩子结点，左孩子结点不满足约束条件，舍弃； 右孩子结点D的up=9+4+7=20，满足限界条件，将结点D保存到活结点表中，如图563(c)所示。从活结点表中取出优先级最高的活结点D，结点D是当前的扩展结点，一次性生成它的两个孩子结点E和F，结点E满足约束条件，其bestp=16，up=16+4=20，将E插入活结点表； 结点F的up=9+4=11，不满足限界条件，舍弃，如图563(d)所示。
图563搜索过程1
从活结点表中取出优先级最高的活结点E，结点E是当前的扩展结点，一次性生成它的两个孩子结点，左孩子结点G满足约束条件且是叶子结点，其bestp=20，up=20，将G插入活结点表； 右孩子结点的up=16，不满足限界条件，舍弃，如图564（a)所示。从活结点表取出优先级最高的活结点G，由于G已经是叶子结点，搜索结束，找到了问题的最优解，即从根结点到叶结点的路径（1,0,1,1），bestp=20。如图564(b)中粗线条所示。
图564搜索过程2
思考： 如果将队列式分支限界算法中的限界条件改为cp+r′p>bestp，搜索树有何变化？同样，如果将优先队列式分支限界算法中的限界条件改为cp+rp>bestp，搜索树又有何变化？如果选用活结点的cp作为优先级呢？这些情况下的搜索树留给读者练习。
3. 算法描述
注： 针对上述优先队列式分支限界算法进行算法描述。
采用最大堆来实现活结点优先队列，堆中元素N的优先级由uprofit给出。算法采用的数据结构包括子集树结点类型，最大堆结点类型和最大堆结构体类型，具体描述如下：
（1） 子集树结点类。
class bbnode
{
public:
friend class Knap;
friend int Knapsack(int p［］, int w［］, int c, int n);
private:
bbnode*parent; //指向父结点的指针，构造最优解使用
boolLChild; //左孩子结点标志，“1”表示左孩子，“0”表示不是左孩子
};
（2） 最大堆结点类。
class HeapNode
{
public:
friend class Knap;
operator int() const {return uprofit;}
int uprofit, //结点的价值上界
int profit; //结点所对应的价值
int weight; //结点所对应的重量
int level; //活结点在子集树中所处的层序号
bbnode *ptr; //指向活结点在子集树中相应结点的指针
};
（3） 堆类型的结构体。
typedef struct
{
int capacity;
int size;
HeapNode *Elem;
}Heap, *MaxHeap;
定义了堆类型的结构体以后，要对堆进行初始化，即确定堆中最多允许存放的元素个数并开辟足够的空间，当前无任何元素。堆结构体的初始化如下：
MaxHeap initH(int maxElem)
{
MaxHeap H;
H=new Heap;
H->capacity=maxElem; //堆中最多允许存放的元素个数
H->Elem=new HeapNode［maxElem］;//开辟足够的空间
H->size=0; //堆中实际存放的元素个数
return H;
}
对堆结构的操作，主要是将一个元素插入堆或从堆中删除并调整成新堆，堆的插入和删除操作描述如下：
（1） 插入堆结点的描述。
void InsertH(HeapNode x, MaxHeap H)
{
if(H->size>=H->capacity){
cout<<"堆已满，插入失败"<<endl;
return;
}
H->Elem［++H->size］=x;
int sindex=H->size/2;
while(sindex>=1){
if(H->Elem［H->size］.uprofit>H->Elem［sindex］.uprofit)
swap(H->Elem［H->size］,H->Elem［sindex］);
else
break;
sindex = sindex/2;
}
}
（2） 删除堆结点的算法描述。
HeapNodeDeleteMaxH(MaxHeap H)
{ HeapNode HeapTop;
HeapTop=H->Elem［1］;
H->Elem［1］=H->Elem［H->size--］;
int m=0; int i=1,i1,i2;
do{
m=i,i1=2*m,i2=2*m+1;
if((i1<=H->size)&&(H->Elem［i1］.uprofit>H->Elem［i］).uprofit)i=i1;
if((i2<=H->size)&&(H->Elem［i2］.uprofit>H->Elem［i］).uprofit)i=i2;
if(i!=m)
swap(H->Elem［i］,H->Elem［m］);
}while(i!=m)
return HeapTop;
}
算法中用到的类Knap与用回溯算法解该问题时用到的类Knap很相似，它们的主要区别在于本节的类Knap中没有成员函数Backtrack，而增加了新的成员函数AddLiveNode，用于将活结点插入最大堆； 成员函数MaxKnapsack用于求问题的最大价值和最优解。
class Knap
{
public:
friend int Knapsack(int p［］, int w［］, int c, int n, int bestx［］);
int MaxKnapsack();
private:
MaxHeap H; int Bound(int i);
void AddLiveNode(int up, int cp, int cw, bool ch, int level);
bbnode *E; //指向扩展结点的指针
int c; //背包容量
int n; //物品数
int *w; //物品重量数组
int *p; //物品价值数组
int cw; //当前装包重量
int cp; //当前装包价值
int bestp;//最大价值
int *bestx; //最优解
};
类Knap的成员函数Bound与回溯算法解决该问题时的相同，具体描述参见5.3.2节的详细描述。
成员函数AddLiveNode主要负责将活结点插入活结点表，调用插入堆结点的操作完成。具体描述如下：
void Knap∷AddLiveNode(int up, int cp, int cw, bool ch, int lev)
{
//将一个新的活结点插入子集树和最大堆H
bbnode *b=new bbnode;
b->parent=E;
b->LChild=ch;
HeapNode N;
N.uprofit=up;
N.profit=cp;
N.weight=cw;
N.level=lev;
N.ptr=b;
InsertH(N, H);
}
类Knap的成员函数MaxKnapsack根据分支限界法的搜索思想搜索解空间树，找出问题的最优解和最优值（最大价值）。具体描述如下：
int Knap∷MaxKnapsack()
{
//定义最大堆的容量为1000
H=initH(1000); bestx=new int［n+1］;
int i=1; E=0; cw=cp=0; int bestp=0;//当前最优值
int up=Bound(1); //价值上界
while(i!=n+1) //搜索子集空间树
{//检查当前扩展结点的左孩子结点
if(cw+w［i］<=c) //左孩子结点为可行结点
{
if(cp+p［i］>bestp)bestp=cp+p［i］;
AddLiveNode(up, cp+p［i］, cw+w［i］, true, i+1);
}
up=Bound(i+1);
if(up>=bestp)AddLiveNode(up, cp, cw, false, i+1); //检查当前扩展结点的右孩子结点
//取下一扩展结点
HeapNode N;
N=DeleteMaxH(H);
E=N.ptr; cw=N.weight; cp=N.profit; up=N.uprofit;
i=N.level;
}//end while
for(i=n;i >0;i--)//构造当前最优解
{ bestx［i］=E->LChild; E=E->parent; }
return cp;
}
类的友元函数Knapsack完成对输入数据的预处理。其主要任务是对相关变量的初始化、将各物品按照单位重量的价值由大到小排序，然后调用MaxKnapsack完成对解空间树的优先队列式分支限界搜索。具体实现与5.5.2节中的Knapsack类似，请读者参阅5.5.2节的Knapsack函数的描述自行设计。
4. C++实战
相关代码如下。
#include<iostream>
#include<algorithm>
using namespace std;
//子集树结点类
class bbnode
{
public:
friend class Knap;
friend int Knapsack(int p［］, int w［］, int c, int n);
private:
bbnode *parent;//指向父结点的指针，构造最优解使用
bool LChild; //左孩子结点标志，1表示左孩子，0表示不是左孩子
};
//最大堆结点类
class HeapNode
{
public:
friend class Knap;
operator int() const {return uprofit;}
int uprofit; //结点的价值上界
int profit; //结点所对应的价值
int weight; //结点所对应的重量
int level; //活结点在子集树中所处的层序号
bbnode *ptr; //指向活结点在子集树中相应结点的指针
};
//堆类型的结构体
typedef struct
{
int capacity;
int size;
HeapNode *Elem;
}Heap, *MaxHeap;
//堆结构的初始化函数
MaxHeap initH(int maxElem)
{
MaxHeap H;
H=new Heap;
H->capacity=maxElem; //堆中最多允许存放的元素个数
H->Elem=new HeapNode［maxElem］; //开辟足够的空间
H->size=0; //堆中实际存放的元素个数
return H;
}
//堆插入操作
void InsertH(HeapNode x, MaxHeap H)
{
if(H->size>=H->capacity){
cout<<"堆已满，插入失败"<<endl;
return;
}
H->Elem［++H->size］=x;
int sindex=H->size/2;
while(sindex>=1){
if(H->Elem［H->size］.uprofit>H->Elem［sindex］.uprofit)
swap(H->Elem［H->size］,H->Elem［sindex］);
else
break;
sindex = sindex/2;
}
}
//堆删除操作
HeapNode DeleteMaxH(MaxHeap H)
{
HeapNode HeapTop;
HeapTop=H->Elem［1］;
H->Elem［1］=H->Elem［H->size--］;
int m=0;
int i=1,i1,i2;
do{
m=i,i1=2*m,i2=2*m+1;
if((i1<=H->size)&&(H->Elem［i1］.uprofit>H->Elem［i］.uprofit))
i=i1;
if((i2<=H->size)&&(H->Elem［i2］.uprofit>H->Elem［i］.uprofit))
i=i2;
if(i!=m)
swap(H->Elem［i］,H->Elem［m］);
}while(i!=m);
return HeapTop;
}
class Knap
{
public:
friend int Knapsack(int p［］, int w［］, int c, int n);
int MaxKnapsack();
void print()
{
cout<<"按照单位重量的价值降序排列的最优解为：";
for(int k=1;k<=n;k++)
cout<<bestx［k］<<" ";
cout<<endl;
}
private:
MaxHeap H;
int Bound(int i);
void AddLiveNode(int up, int cp, int cw, bool ch, int level);
bbnode *E; //指向扩展结点的指针
int c; //背包容量
int n; //物品数
int *w; //物品重量数组
int *p; //物品价值数组
int cw; //当前装包重量
int cp; //当前装包价值
int bestp; //最大价值
int *bestx; //最优解
};
int Knap::Bound(int i) //计算上界
{
int cleft=c-cw; //剩余容量
int b=cp;
//以物品单位重量价值递减序装入物品
while(i<=n && w［i］<=cleft)
{
cleft-=w［i］;
b+=p［i］;i++;
}
//装满背包
if(i<=n)
b+=p［i］/w［i］*cleft;
return b;
}
void Knap::AddLiveNode(int up, int cp, int cw, bool ch, int lev)
{
//将一个新的活结点插入到子集树和最大堆H中
bbnode *b=new bbnode;
b->parent=E;
b->LChild=ch;
HeapNode N;
N.uprofit=up;
N.profit=cp;
N.weight=cw;
N.level=lev;
N.ptr=b;
InsertH(N, H);
}
int Knap::MaxKnapsack()
{
//定义最大堆的容量为1000
H=initH(1000);
bestx=new int［n+1］;
int i=1;
E=0;
cw=cp=0;
bestp=0; //当前最优值
int up=Bound(1); //价值上界
while(i!=n+1) //搜索子集空间树
{ //检查当前扩展结点的左孩子结点
if(cw+w［i］<=c) //左孩子结点为可行结点
{
if(cp+p［i］>bestp)
bestp=cp+p［i］;
AddLiveNode(up, cp+p［i］, cw+w［i］, true, i+1);
}
up=Bound(i+1);
if(up>=bestp)
AddLiveNode(up, cp, cw, false, i+1); //检查当前扩展结点的右孩子结点
//取下一扩展结点
HeapNode N;
N=DeleteMaxH(H);
E=N.ptr;
cw=N.weight;
cp=N.profit;
up=N.uprofit;
i=N.level;
}//end while
for(i=n;i >0;i--) //构造当前最优解
{
bestx［i］=E->LChild;
E=E->parent;
}
return cp;
}
class Object
{
public:
friend int Knapsack(int p［］,int w［］,int c,int n);
int operator<(const Object &a)
{ return(this->d > a.d); }
private:
int id; //物品编号
float d; //单位重量的价值
};
int Knapsack(int p［］,int w［］,int c,int n)
{ //初始化
int W=0;int P=0;int i=1;
Object *Q=new Object［n］;
for(i=1;i<=n;i++)
{
Q［i-1］.id=i;
Q［i-1］.d=1.0*p［i］/w［i］;
P+=p［i］;
W+=w［i］;
}
if(W<=c) return P; //装入所有物品
//依物品单位重量降序排序
sort(Q,Q+n); //将数组Q中的元素按照单位重量的价值由大到小排
Knap K;
K.p=new int［n+1］;
K.w=new int［n+1］;
K.bestx=new int［n+1］;
int *bestx = new int［n+1］;
K.bestx［0］=0;
for(i=1;i<=n;i++)//按单位重量的价值降序排列物品重量和价值
{
K.p［i］=p［Q［i-1］.id］;
K.w［i］=w［Q［i-1］.id］;
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//分支限界算法搜索
K.bestp = K.MaxKnapsack();
K.print(); //输出最优解
cout<<"装入的重量为："<<K.cw<<endl;
cout<<"装入的物品编号为：";
for(int i=1;i<=n;i++)
if(K.bestx［i］)
cout<<Q［i-1］.id<<" ";
cout<<endl;
delete ［］ Q;
delete ［］ K.w;
delete ［］ K.p;
delete ［］ K.bestx;
delete ［］ bestx;
return K.bestp; //返回最优值
}
int main(){
int p［］={0,9,10,7,4};
int w［］={1,3,5,2,1};
int c = 7;
int n = 4;
int bestp = Knapsack(p,w,c,n);
cout<<"最大价值为："<<bestp<<endl;
return 0;
}
视频讲解
5.5.3旅行商问题
旅行商问题的解空间和解空间组织结构已在5.3节的例510中详细分析过。在此基础上，讨论如何用分支限界算法进行搜索。
图565无向连通图
考虑n=4的实例，如图565所示，城市1为售货员所在的住地城市。
对于该实例，简单做如下分析：
(1) 问题的解空间（x1,x2,x3,x4），其中令S={1,2,3,4}，x1=1，x2∈S-{x1}，x3∈S-{x1,x2}，x4∈S-{x1,x2,x3}。
(2) 解空间的组织结构是一棵深度为4的排列树。
(3) 搜索： 设置约束条件g［i］［j］!=∞，其中1≤i≤4，1≤j≤4，g是该图的邻接矩阵； 设置限界条件： cl<bestl，其中cl表示当前已经走的路径长度，初始值为0； bestl表示当前最短路径长度，初始值为∞。
搜索过程：
① 队列式分支限界算法对该实例的搜索过程如图566~图568所示（注： 图中结点旁的数据为cl的值）。
由于x1的取值是确定的，所以从根结点A0的孩子结点A开始搜索即可。将结点A插入活结点表，结点A是活结点并且是当前的扩展结点，如图566(a)所示。从活结点表中取出活结点A作为当前的扩展结点，一次性生成它的3个孩子结点B、C、D，均满足约束条件和限界条件，依次插入活结点表，结点A变成死结点，如图566(b)所示。从活结点表中取出活结点B作为当前的扩展结点，一次性生成它的两个孩子结点E、F，均满足约束条件和限界条件，依次插入活结点表，结点B变成死结点，如图566(c)所示。
图566搜索过程1
从活结点表中取出活结点C作为当前的扩展结点，一次性生成它的两个孩子结点G、H，均满足约束条件和限界条件，依次插入活结点表，结点C变成死结点，如图567(a)所示。从活结点表中取出活结点D作为当前的扩展结点，一次性生成它的两个孩子结点I、J，均满足约束条件和限界条件，依次插入活结点表，结点D变成死结点，如图567(b)所示。
图567搜索过程2
从活结点表中取出活结点E作为当前的扩展结点，一次性生成它的一个孩子结点K，满足约束条件和限界条件，结点K已经是叶子结点，且顶点4与住地城市1有边相连，说明已找到一个当前最优解，记录该结点，最短路径长度为42，修改bestl=42，如图568(a)所示。从活结点表中依次取出活结点F、G、H、I、J，一次性生成它们的孩子结点，均不满足限界条件，舍弃，这些结点变成死结点。此时，活结点表为空，算法结束，找到的最优解是从根结点到叶子结点K的路径（1,2,3,4），路径长度为42，如图568(b)所示。
图568搜索过程3
② 优先队列式分支限界算法对该实例的搜索过程如图569~图571所示(注： 结点旁的数据为cl的值)。
优先级定义为： 活结点所对应的已经走过的路径长度cl，长度越短，优先级越高。
从结点A开始，结点A插入活结点表，结点A是活结点并且是当前的扩展结点，如图569(a)所示。从活结点表中取出活结点A作为当前的扩展结点，一次性生成它的3个孩子结点B、C、D，均满足约束条件和限界条件，依次插入活结点表，结点A变成死结点，如图569(b)所示。从活结点表中取出优先级最高的活结点D作为当前的扩展结点，一次性生成它的两个孩子结点E、F，均满足约束条件和限界条件，依次插入活结点表，结点D变成死结点，如图569(c)所示。
图569搜索过程1
从活结点表中取出优先级最高的活结点F作为当前的扩展结点，一次性生成它的一个孩子结点G，满足约束条件和限界条件将G插入活结点表。由于结点G已经是叶子结点，此时找到了当前最优解，最短路径长度为42，修改bestl=42，如图570（a)所示。从活结点表中取出优先级最高的活结点E作为当前的扩展结点，一次性生成它的一个孩子结点，不满足限界条件，舍弃，结点E变成死结点，如图570(b)所示。
图570搜索过程2
从活结点表中取出优先级最高的活结点B作为当前的扩展结点，一次性生成它的两个孩子结点H、I，结点H满足约束条件和限界条件，将其插入活结点表； 结点I不满足限界条件，舍弃。结点B变成死结点，如图571(a)所示。从活结点表中取出优先级最高的活结点H作为当前的扩展结点，生成的孩子结点不满足限界条件，舍弃，结点H变成死结点。再从活结点表中取出优先级最高的活结点G作为当前的扩展结点，G已经是叶子结点，此时找到问题的最优解，算法结束，找到问题的最优解是从根结点A0到叶子结点G的最短路径（1,4,3,2），最短路径长度为42，如图571(b)中粗线条所示。
图571搜索过程3
图572优化条件下的搜索树
(4) 算法优化。
根据题意，每个城市各去一次销售商品。因此，可以估计路径长度的下界（用zl表示），初始时，zl等于图中每个顶点权最小的出边权之和。随着搜索的深入，可以估计剩余路径长度的下界（用rl表示）。故可以考虑用zl(zl=当前路径长度cl+剩余路径长度的下界rl)作为活结点的优先级，同时将限界条件优化为zl=cl+rl>bestl，cl的初始值为0，rl初始值为每个顶点权最小的出边权之和。那么，按照该限界条件，上述搜索过程形成的搜索树如图572所示。
(5) 算法描述。
根据上述讨论，优先队列式分支限界算法搜索解空间树时，需要设置优先级和判断孩子结点是舍弃还是保留的判断标准。在具体实现时，用邻接矩阵表示所给的图G，在类Traveling中用二维数组a存储图G的邻接矩阵，cl和bestl分别表示当前已走的路径长度和当前最短路径长度。类Traveling的定义如下：
class Traveling
{
public:
Traveling(int n,double**a,double cl,double bestl)
{
this->n=n;
this->a=a;
this->cl=cl;
this->bestl=bestl;
}
doubleTSP();
double ShortestEdge(double*Minout,double & MinSum);
void print(){
for(int i=1;i<=n;i++)
cout<<bestx［i］<<"";
cout<<end;
}
private:
int n*bestx; //图G的顶点数
double **a,cl,bestl;
//a表示邻接矩阵，cl表示当前路径长度，bestl表示当前最小路径长度
};
根据旅行商问题的特点，每个城市去且仅去一次，可设置该问题的优先级为子树的最短路径长度，其长度越短，优先级越高，故优先队列采用最小堆来实现。最小堆结点结构的定义如下：
class MinHeapNode
{
friend class Traveling;
public:
double zl,cl, rl; //zl表示子树路径长度的下界，cl表示当前路径长度，rl表示
//x［s+1:n］中顶点最小出边路径长度和
int s, *x, n; //s表示根结点到当前结点的路径为x［1:s-1］，x表示需要进一步搜索
//的结点为x［s:n］ ，n表示总共结点数
};
//定义按照zl构建小顶堆
struct Cmp{
bool operator()(MinHeapNode a,MinHeapNode b){
return a.zl>b.zl;
}
}
类Traveling的成员函数TSP中，首先创建一个最小堆，找出所有顶点出边最短路径长度并用Minout记录，其中Minout［i］记录了第i个顶点的最短出边权； 然后计算并用变量MinSum记录所有最短出边的路径长度和。数组x记录最短路径，初始化为x［i］=i，i=1,2,…,n。由于x1的取值必为住地城市，故搜索最短路径时只需要从解空间树的第二层开始搜索，即s初始化为2。
① 计算每个顶点的最短出边及它们的长度之和。
double Traveling∷ShortestEdge(double * Minout,double & MinSum)
{
for(int i=1;i<=n;i++) //计算最小出边及其路径长度和
{double Min=∞;
for(int j=1;j<=n;j++)
if(a［i］［j］!=∞&& (a［i］［j］<Min))Min=a［i］［j］;
if(Min==∞) returnMin; //无回路
Minout［i］=Min;MinSum+=Min;
}
}
return 1;
② TSP算法描述。
double Traveling∷TSP(int v［］)//解旅行售货员的优先队列分支定界法
{
priority-queue<MinHeapNode,vector<MinHeapNode >,Cmp>H;
double MinSum,Minout［n+1］;
bestx=new int［n+1］;
if(ShortestEdge(Minout,MinSum,n)==∞)return -1;
else
{ MinHeapNode E;E.x=new int［n+1］;
for(i=1;i<=n;i++)E.x［i］= i;
E.s=2;E.n=n; //需记录总共的结点数，方可分配空间
E.cl=0;E.rl=MinSum;double bestl=∞;
H.push(E);
//搜索排列树
while(E.s<=n&&!H.empty()) //非叶结点
{
E=H.top();//取下一活结点扩展H.pop();
if(E.s==n) //当前扩展结点是叶结点的父结点
{if(a［E.x［n-1］］［E.x［n］］!=∞&& a［E.x［n］］［1］!=∞&&
(E.cl+a［E.x［n-1］］［E.x［n］］+a［E.x［n］］［1］<bestl))
{//再加两条边构成回路，判断回路是否优于当前最优解
cl=E.cl+a［E.x［n-1］］［E.x［n］］+a［E.x［n］］［1］;
if(E.cl<best){
bestl=E.cl;
for(int i=1;i<=n;i++)
bestx［i］=E.x［i］;}
}}
else{ //非叶结点的父结点时，产生当前扩展结点的所有子结点
for(i=E.s;i<=n;i++)
if(a［E.x［E.s-1］］［E.x［i］］!=∞) //可行子结点
{ double cl=E.cl+a［E.x［E.s-1］］［E.x［i］］;double rl=E.rl-MinOut［E.x［E.s-1］］;
Type b=cl+rl; //子结点的下界
if(b<bestl)//子树可能含有最优解，结点插入最小堆
{MinHeapNodeN;N.x=new int［n+1］;
for(j=1;j<=n;j++) N.x［j］=E.x［j］;
N.x［E.s］=E.x［i］;N.x［i］=E.x［E.s］;N.cl=cl;N.s=E.s+1;
N.n=n; N.zl =b;N.key=N.zl; N.rl=rl;H.push(N);
}
}
}//end else
}//end while(E.s <=n)
if(bestl==∞)return -1; //无回路
return bestl;
}//end else
}
(6) C++实战。
相关代码如下。
#include<iostream>
#include<cfloat>
#include<algorithm>
#include<queue>
#define INF DBL_MAX
using namespace std;
class Traveling
{
public:
Traveling(int n,double **a,double cl,double bestl)
{
this->n = n;
this->a = a;
this->cl = cl;
this->bestl = bestl;
}
double TSP();
double ShortestEdge(double * Minout,double & MinSum);
void print(){
for(int i=1;i<=n;i++)
cout<<bestx［i］<<" ";
cout<<endl;
}
private:
int n;//图G的顶点数
double **a,cl,bestl; //a表示邻接矩阵，cl表示当前路径长度，bestl表示当
//前最小路径长度
int *bestx;
};
//最小堆结构的类
class MinHeapNode
{
friend class Traveling;
public:
double zl,cl,rl; //zl表示子树路径长度的下界，cl表示当前路径长度，
//rl表示?x［s+1:n］中顶点最小出边路径长度和
int s, *x, n; //s表示根结点到当前结点的路径为x［1:s-1］，x表示
//需要进一步搜索的结点为x［s:n］，n表示总共结点数
};
//定义按照zl构建小顶堆
struct Cmp{
bool operator()(MinHeapNode a,MinHeapNode b){
return a.zl > b.zl;
}
};
//计算每个顶点的最短出边及它们的长度之和
double Traveling::ShortestEdge(double *MinOut,double &MinSum)
{
for(int i=1;i<=n;i++) //计算最小出边及其路径长度和
{
double Min=INF;
for(int j=1;j<=n;j++)
if(a［i］［j］!=INF && (a［i］［j］<Min))
Min=a［i］［j］;
if(Min == INF)
return Min; //无回路
MinOut［i］=Min;
MinSum+=Min;
}
return 1;
}
//解旅行售货员的优先队列分支限界算法
double Traveling::TSP()
{
priority_queue<MinHeapNode,vector<MinHeapNode>,Cmp>H;
double MinSum,MinOut［n+1］;
bestx = new int ［n+1］;
if(ShortestEdge(MinOut,MinSum)==INF)
return -1;
else
{
MinHeapNode E;
E.x=new int［n+1］;
for(int i=1;i<=n;i++)
E.x［i］= i;
E.s=2;
E.n=n; //需记录总共的结点数，方可分配空间
E.cl=0;
E.rl=MinSum;
double bestl=INF;
H.push(E);
//搜索排列树
while(E.s<=n && !H.empty()) //非叶结点
{
E = H.top(); //取下一活结点扩展
H.pop();
if(E.s==n) //当前扩展结点是叶结点的父结点
{
if(a［E.x［n-1］］［E.x［n］］!=INF && a［E.x［n］］［1］!=INF && (E.cl+a［E.x［n-1］］［E.x［n］］+a［E.x［n］］［1］<bestl))
{
//再加2条边构成回路，判断回路是否优于当前最优解
E.cl=E.cl+a［E.x［n-1］］［E.x［n］］+a［E.x［n］］［1］;
if(E.cl<bestl)
{
bestl = E.cl;
for(int i=1;i<=n;i++)
bestx［i］ = E.x［i］;
}
}
}
else
{ //非叶结点的父结点时，产生当前扩展结点的所有子结点
for(int i=E.s;i<=n;i++)
if(a［E.x［E.s-1］］［E.x［i］］!=INF)//可行子结点
{
double cl=E.cl+a［E.x［E.s-1］］［E.x［i］］;
double rl=E.rl-MinOut［E.x［i］］;
double b=cl+rl; //子结点的下界
if(b<bestl) //子树可能含有最优解，结点插入最小堆
{
MinHeapNode N;
N.x=new int［n+1］;
for(int j=1;j<=n;j++)
N.x［j］=E.x［j］;
N.x［E.s］=E.x［i］;
N.x［i］=E.x［E.s］;
N.cl=cl;
N.s=E.s +1;
N.n=n;
N.zl=b;
N.rl=rl;
H.push(N);
}
}
}//end else
}//end while(E.s <=n)
if(bestl==INF)
return -1; //无回路
return bestl;
}//end else
}
int main(){
cout<<"请输入城市个数n：";
int n;
cin>>n;
double **a = new double*［n+1］;
for(int i=0;i<=n;i++)
a［i］= new double［n+1］;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a［i］［j］;
Traveling traveling(n,a,0,INF);
double bestl = traveling.TSP();
cout<<"最短路径为："<<bestl<<endl;
cout<<"最优解为："<<endl;
traveling.print();
return 0;
}
视频讲解
5.5.4布线问题
1. 问题描述
布线问题就是在N×M的方格阵列中，指定一个方格的中点为a，另一个方格的中点为b，如图573所示，
图573 9×7阵列
问题要求找出a到b的最短布线方案（即最短路径）。布线时只能沿直线或直角，不能走斜线。黑色的单元格代表不可以通过的封锁方格。
2. 问题分析
将方格抽象为顶点，中心方格和相邻4个方向（上、下、左、右）能通过的方格用一条边连起来。这样，可以把问题的解空间定义为一个图。
该问题是特殊的最短路径问题，特殊之处在于用布线走过的方格数代表布线的长度，也就是说，布线时每布一个方格，布线长度累加1。由问题描述可知，从a点开始布线，只能朝上、下、左、右4个方向进行布线，并且遇到以下几种情况均不能布线： 封锁方格、超出方格阵列的边界、已布过线的方格，把能布线的方格插入活结点表，然后从活结点表中取出一个活结点作为当前扩展结点继续扩展，搜索过程直到找到问题的目标点或活结点表为空为止。采用队列式分支限界算法。
3. 解题步骤
搜索从起始点a开始，到目标点b结束。约束条件为有边相连且未曾布线。
搜索过程： 从a开始将其作为第一个扩展结点，沿a的上、下、左、右4个方向的相邻结点扩展。判断约束条件是否成立，如果成立，则放入活结点表，并将这些方格标记为1。接着从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格记为2。以此类推，直到算法搜索到目标方格或活结点表为空为止。目标方格里的数据表示布线长度。
构造最优解过程。从目标点开始，沿着上、下、左、右4个方向。判断如果某个方向方格里的数据比扩展结点方格里的数据小1，则进入该方向方格，使其成为当前的扩展结点。以此类推，搜索过程一直持续到起始点。如图573所示实例的搜索过程为： 结点a的扩展情况如图574(a)所示，方格为1的结点扩展情况如图574(b)所示，依次类推，搜索到目标点时的情况如图574(c)所示，构造最优解的过程（上、下、左、右）如图574(d)所示。
图574构造最优解
4. 算法描述
在实现布线问题的算法时，需要存储方格阵列、封锁标记、布线的起点和终点位置、4个方向的相对位置、边界标识等。算法描述中，用二维数组grid表示给定方阵阵列，grid［i］［j］等于-1，表示第i行、第j列的方格未曾布线； grid［i］［j］大于或等于0，表示第i行、第j列的方格已布线； grid［i］［j］=-2，表示第i行、第j列的方格已被封锁。为了便于判断是否到达阵列边界，在方格阵列的外围加了一堵 “围墙”，其值也为-2，即布线不能通过。
typedef struct
{ int row;int col;}Position;
bool findpath(Position start, Position finish, int&PathLen,Position *&path)
{if ((start.row==finish.row)&&(start.col==finish.col)) //起点与终点相同，不用布线
{ pathLen=0;return true;}
for(int i=0;i<=m+1;i++) //方格阵列的上下“围墙”
grid［0］［i］=grid［n+1］［i］=-2;
for(int i=0；i<=n+1;i++)//方格阵列的左右“围墙”
grid［i］［0］=grid［i］［n+1］=-2;
//初始化四个扩展方向相对位置
Position offset［4］;
offset［0］.row=0;offset［0］.col=1;offset［1］.row=1;offset［1］.col=0;
offset［2］.row=0;offset［2］.col=-1;offset［3］.row=-1;offset［3］.col=0;
int NumofNbrs=4//4个方向
Position here, nbr;//here记录当前扩展方格，nbr记录扩展方向的方格
here.row=start.row;here.col=start.col;grid［start.row］［start.col］=0
LinkedQueue <Position> Q;
do {
for(int i=0; i<Numofnbrs;i++)//沿着扩展结点的右、下、左、上4个方向扩展
{
nbr.row=here.row+offset［i］.row;nbr.col=here.col+offset［i］.col;
if(grid［nbr.row］［nbr.col］==-1) //如果这个方格还没有扩展
grid［nbr.row］［nbr.col］=grid［here.row］［here.col］+1;
if((nbr.row==finish.row)&&(nbr.col==finish.col))break;
//如果到达终点结束
Q.Add(nbr); //此邻结点放入队列
}
if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//完成布线
if(Q.Isempty()) return;//如果扩展结点都用完了，还到不了终点，则无解
Q.Delete(here);//从队列中取下一个扩展结点
} while(true)
//逆向构造最短布线方案
PathLen=grid［finish.row］［finish.col］;path=new Position［Pathlen］;
here=finish;
for(int j=PathLen-1;j>=0;j--)
{
path［j］=here;
for(int i=0;i<Numofnbrs;i++)
{ nbr.row=here.row+offset［i］.row;nbr.col=here.col+offset［i］.col;
if (grid［nbr.row］［nbr.col］==j) break;
}
here=nbr;//往回推进
}
return true;
}
5. C++实战
相关代码如下。
#include<iostream>
#include<queue>
using namespace std;
typedef struct{
int row;
int col;
}Position;
bool findpath(int n,int m,int **grid,Position start, Position finish, int&PathLen,Position *&path)
{
if ((start.row==finish.row)&&(start.col==finish.col))//起点与终点相同，不用布线
{
PathLen=0;
return true;
}
for(int i=0;i<=m+1;i++)//方格阵列的上下"围墙"
grid［0］［i］=grid［n+1］［i］=-2;
for(int i=0;i<=n+1;i++)//方格阵列的左右"围墙"
grid［i］［0］=grid［i］［m+1］=-2;
//初始化4个扩展方向相对位置
Position offset［4］;
offset［0］.row=0;
offset［0］.col=1;
offset［1］.row=1;
offset［1］.col=0;
offset［2］.row=0;
offset［2］.col=-1;
offset［3］.row=-1;
offset［3］.col=0;
int Numofnbrs=4; //4个方向
Position here, nbr; //here记录当前扩展方格，nbr记录扩展方向的方格
here.row=start.row;
here.col=start.col;
grid［start.row］［start.col］=0;
queue <Position>Q;
do
{
for(int i=0; i<Numofnbrs;i++)//沿着扩展结点的右、下、左、上4个方向扩展
{
nbr.row=here.row+offset［i］.row;
nbr.col=here.col+offset［i］.col;
if(grid［nbr.row］［nbr.col］==-1) //如果这个方格还没有扩展
{
grid［nbr.row］［nbr.col］=grid［here.row］［here.col］+1;
Q.push(nbr); //此邻结点放入队列
}
if((nbr.row==finish.row)&&(nbr.col==finish.col))
break; //如果到达终点结束
}
if((nbr.row==finish.row)&&(nbr.col==finish.col))
break; //完成布线
if(Q.empty())
return 0; //如果扩展结点用完，还到不了终点，则无解
here = Q.front(); //从队列中取下一个扩展结点
Q.pop();
} while(true);
//逆向构造最短布线方案
PathLen=grid［finish.row］［finish.col］;
path=new Position［PathLen］;
here=finish;
for(int j=PathLen-1;j>=0;j--)
{
path［j］=here;
for(int i=0;i<Numofnbrs;i++)
{
nbr.row=here.row+offset［i］.row;
nbr.col=here.col+offset［i］.col;
if (grid［nbr.row］［nbr.col］==j)
break;
}
here=nbr; //往回推进
}
return true;
}
int main(){
cout<<"请输入棋盘的行列数n,m:";
int n,m;
cin>>n>>m;
int **grid = new int *［n+2］;
for(int i=0;i<=n+1;i++)
grid［i］= new int［m+2］;
//初始化为-1，标识未访问过的方格
for(int i=0;i<=n+1;i++)
for(int j=0;j<=m+1;j++)
grid［i］［j］=-1;
//设置障碍物
grid［0］［5］=grid［1］［3］=grid［2］［3］=grid［2］［5］=grid［2］［6］=-2;
grid［3］［3］=grid［4］［6］=grid［5］［4］=grid［5］［5］=grid［5］［6］=-2;
grid［6］［6］=grid［8］［3］=grid［8］［5］=-2;
Position start,finish;
cout<<"请输入起点：";
cin>>start.row>>start.col;
cout<<"请输入终点：";
cin>>finish.row>>finish.col;
int PathLen = 0;
Position *path;
bool res = findpath(n,m,grid,start,finish,PathLen,path);
if(res)
{
cout<<"最短路径长度为："<<PathLen<<endl;
cout<<"最短路径为："<<endl;
cout<<start.row<<" "<<start.col<<endl;
for(int i=0;i<PathLen;i++)
cout<<path［i］.row<<" "<<path［i］.col<<endl;
}
else
cout<<"start到finish走不通!"<<endl;
return 0;
}
5.5.5分支限界算法与回溯算法的比较
通过以上几小节的学习，容易得知分支限界算法与回溯算法类似。
1. 相同点
（1） 均需要先定义问题的解空间，确定的解空间组织结构一般都是树或图。
（2） 在问题的解空间树上搜索问题解。
（3） 搜索前均需确定判断条件，该判断条件用于判断扩展生成的结点是否为可行结点。
（4） 搜索过程中必须判断扩展生成的结点是否满足判断条件，如果满足，则保留该扩展生成的结点，否则舍弃。
2. 不同点
（1） 在一般情况下，分支限界算法与回溯算法的求解目标不同。回溯算法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界算法的求解目标则是找出满足约束条件的一个解。换言之，分支限界算法是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
（2） 由于求解目标不同，导致分支限界算法与回溯算法在解空间树上的搜索方式也不相同。回溯算法以深度优先的方式搜索解空间树，而分支限界算法则以宽度优先或以最小耗费（最大效益）优先的方式搜索解空间树。
（3） 由于搜索方式不同，直接导致当前扩展结点的扩展方式也不相同。在分支限界算法中，当前扩展结点一次性生成所有的孩子结点，舍弃那些导致不可行解或导致非最优解的孩子结点，其余孩子结点被加入活结点表，而后自己变成死结点。因此，每一个活结点最多只有一次机会成为扩展结点。在回溯算法中，当前扩展结点选择其中某一个孩子结点进行扩展，如果扩展的孩子结点是可行结点，则进入该孩子结点继续搜索，等到以该孩子结点为根的子树搜索完毕，则回溯到最近的活结点继续搜索。因此，每一个活结点有可能多次成为扩展结点。
在解决实际问题时，有些问题用回溯算法或分支限界算法解决效率都比较高，但是有些用分支限界算法解决比较好，而有些用回溯算法解决比较好。如：
（1） 一个比较适合采用回溯算法解决的问题——n皇后问题。
n皇后问题的解空间可以组织成一棵排列树，问题的解与解之间不存在优劣差异。直到搜索到叶结点时才能确定出一组解。如果用回溯算法可以系统地搜索n皇后问题的全部解，而且由于解空间树是排列树的特性，代码的编写十分容易。在最坏的情况下，堆栈的深度不会超过n。如果采取分支限界算法，在解空间树的第一层就会产生n个活结点，如果不考虑剪枝，将在第二层产生n×(n-1)个活结点，如此下去对队列空间的要求太高。
另外，n皇后问题不适合使用分支限界算法处理的根源在于n皇后问题需要找出所有解的组合，而不是某种最优解（事实上也没有最优解可言）。
（2） 一个既可以采用回溯算法也可以采用分支限界算法解决的问题——01背包问题。
01背包问题的解空间树是一棵子集树，问题的解要求具有最优性质。如果采用回溯算法解决这个问题，可采用如下的搜索策略： 只要一个结点的左孩子结点是一个可行结点就搜索其左子树； 而对于右子树，用贪心算法构造一个上界函数，这个函数表明这个结点的子树所能达到的最大价值，只有在这个上界函数的值超过当前最优解时才进行搜索。随着搜索进程的推进，最优解不断得到加强，对搜索的限制就越来越严格。如果采用优先队列式分支限界算法解决这个问题，同样需要用到贪心算法构造的上界函数。不同的是，这个上界函数的作用不仅仅在于判断是否进入一个结点的子树继续搜索，还用作一个活结点的优先队列的优先级，这样一旦有一个叶结点成为扩展结点，就表明已经找到了最优解。
可以看出，用两种方法处理01背包问题都有一定的可行性，相比之下回溯算法的思路容易理解一些。但是这是一个寻找最优解的问题，由于采用了优先队列处理，不同的结点没有相互之间的牵制和联系，用分支限界算法处理效果一样很好。
（3） 一个比较适合采用分支限界算法解决的问题——布线问题。
布线问题的解空间是一个图，适合采用队列式分支限界算法来解决。从起始位置a开始将它作为第一个扩展结点。与该结点相邻并且可达的方格被加入活结点表，并将这些方格标记为1，表示它们到a的距离为1。接着从活结点队列中取出队首元素作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并加入活结点表。这个过程一直继续到算法搜索到目标方格b或活结点表为空时为止（表示没有通路）。如果采用回溯算法，这个解空间需要搜索完毕才确定最短布线方案，效率很低。
请读者考虑一下，最大团问题、单源最短路径问题、符号三角形问题、图的m着色问题等适合采用回溯算法还是分支限界算法来求解。
拓展知识： 蚁群算法
群体智能（Swarm Intelligence，SI）是一种人工智能技术，主要探讨由多个简单个体构成的群体的集体行为，这些个体之间相互作用，个体与环境之间也相互影响。尽管没有集中控制机制来指导个体的行为，个体之间的局部交互也能够导致某一社会模式的出现。自然界中诸如此类的现象很多，如蚁群、鸟群、兽群、蜂群等，由这种自然现象引发的“群类算法”，如蚁群算法、粒子群算法能够成功地解决现实中的优化问题。SI与其他进化算法有共同之处，都是基于种群的，系统从一个由多个个体（潜在解）组成的种群开始，这些个体模仿昆虫或动物的社会行为来代代繁殖，以寻求最优。不同于其他进化算法的是，群体智能模式不使用交叉、变异这些进化算子，个体只是根据自身与群体中其他个体、与周围环境的关系来不断更新，以求得最优。
蚁群算法是模拟自然界蚂蚁觅食过程的一种分布式、启发式群体智能算法，最早于1991年由学者Colorni、Dorigo和Maniezzo提出，用于求解复杂的组合优化问题，如旅行商问题(TSP)、加工调度问题(JSSP)、图着色问题(GCP)等。
像蚂蚁这类群居昆虫，虽然单个个体的行为极为简单，但由这样的个体组成的蚁群却表现出极其复杂的行为，能够完成复杂的任务，不仅如此，蚂蚁还能适应环境的变化，如在运动的路线上遇到障碍物时，蚂蚁能够很快重新找到最优路线。那么蚁群是如何寻找最优路径的呢？
1. 蚂蚁觅食过程中的最短路径搜索策略
Colorni、Dorigo和Maniezzo三位学者在对大自然中真实蚁群的集体行为进行研究的过程中发现： 蚂蚁这类群居昆虫虽然没有视觉，却能找到由蚁巢到食物源的最短路径。再经过进一步的大量细致观察研究发现，蚂蚁个体之间通过一种称为信息素（pheromone）的物质进行信息传递，信息素中记录了食物源的远近与食物量的多少，蚂蚁在运动过程中，能够在它所经过的路径上留下该物质，而其他蚂蚁通过触角能够检测识别到这种信息素，并能够感知这种物质的强度，以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象： 某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法模拟真实蚁群的协作过程，算法由许多蚂蚁共同完成，每只蚂蚁在候选解的空间中独立地搜索解，并在所寻得的解上留下一定的信息量，解的性能越好蚂蚁留在其上的信息量越大，信息量越大的解被选择的可能性就越大。在算法的初级阶段所有解上的信息量是相同的，随着算法的推进，较优解上的信息量增加，算法渐渐收敛，即最终找到一条最短的路线，此后所有的蚂蚁都将走这条最短路径到达食物源。
如图575(a)所示，假设从蚁穴到食物源有两条等长路线NAF和NBF（NAF=NBF）。开始时，两条路线上都没有信息素，各个蚂蚁将随机选择其中一条路线，并沿途散播信息素； 随时间的推移，各路线会挥发掉部分信息素，也不断地增加新的蚂蚁带来的信息素，这是一个正反馈的过程； 后来的蚂蚁再选择路线时，浓度较高的路线被选择的概率较大； 一段时间后，越来越多的蚂蚁会选择同一条路线，而另一条路线上的蚂蚁数量越来越少，且其上的信息素逐渐挥发殆尽。
如图575(b)所示，对于两条不等长的路线NAF和NBF（NAF>NBF）来说，开始时，两条路线上都没有信息素，各蚂蚁是随机选择其中一条路线，即有的走NAF路线，另一些走NBF路线，并沿途散播信息素，两条路线上的蚂蚁数大致相等； 假设蚂蚁的行走速度相同，则选择走NBF路线（较短路线）的蚂蚁比选择走NAF路线（较长路线）的蚂蚁先到达食物源F； 当走NBF路线的蚂蚁返回到蚁穴时，走NAF路线的蚂蚁仍在途中C点处，即2NBF=NAF+FAC，可以看出，线段NC上的信息素要少于别处； 下次蚂蚁再选择路线时，会以较高概率走较短路径，这使得较长路线上的信息素浓度越来越低，较短路线上的信息素浓度越来越高； 一段时间后，所有的蚂蚁都将选择较短的路线。
图575蚂蚁觅食时最短路径选择
蚁群算法就是从蚂蚁觅食时寻找最短路径的现象中得到启示而设计的，由计算机编程实现的分布式并行搜索策略。蚂蚁通过别的蚂蚁留下来的信息素的强弱作为自己选择路径的参数，信息素越强的路径被选择的可能性越大。信息素的更新策略是越好的路径上获得的信息素越多，通过这个正反馈来寻找更好的路径，这是蚁群算法工作的基本原理。单个蚂蚁的规则相当简单，但是通过蚂蚁群体的协同工作，产生对复杂环境的认知，以实现对解空间进行有效的搜索。
2. 蚁群算法的基本步骤
上述介绍的只是有关蚁群算法的简单原理，当然要设计出切实可行的算法并建立模型需要将模型进一步精确，如要计算信息素的挥发（即信息素的浓度将随时间而逐步降低）等。
据蚁群算法的基本原理，人们设计了一个寻找最优路径的蚁群算法：
（1） 一群蚂蚁随机从出发点出发，遇到食物，衔住食物，沿原路返回。
（2） 蚂蚁在往返途中，在路上留下信息素标志。
（3） 信息素随时间逐渐蒸发（一般可用负指数函数来表示）。
（4） 由蚁穴出发的蚂蚁，其选择路径的概率与各路径上的信息素浓度成正比。
利用同样原理可以描述蚁群进行多食物源的寻食情况。
3. 基本蚁群算法模型
因为蚂蚁觅食的过程与旅行商问题非常相似，下面通过求解n个城市的TSP问题为例来说明基本的蚁群算法模型，其他问题可以对此模型稍做修改便可应用。
首先设TSP中城市i与城市j之间的距离为dij，m为蚁群中蚂蚁的数量，bi(t)表示t时刻位于城市i的蚂蚁数量，则有m=∑ni=1bi(t)。τij(t)表示t时刻弧(i，j)上的信息素量。初始时刻各弧上的信息素量相等，τij(0)=C，C为常数。蚂蚁k在运动过程中，根据各弧上的信息素量来决定移动的方向，pkij(t)表示在t时刻蚂蚁k由点i向j移动的概率，则有
pkij(t)=ταij(t)ηβij(t)∑S∈Jk(i)ταis(t)ηβis(t)，若j∈Jk(i)
0，否则(54)
其中，Jk(i)表示城市i上的蚂蚁k下一步允许选择的城市集合。α,β分别表示蚂蚁在移动过程中所积累的信息素τij(t)及启发式因子ηij(t)在蚂蚁择路时的重要程度。ηij表示由城市i到城市j的期望值，可模拟某种启发式算法具体确定。另外，蚁群算法还具有记忆功能，用tab uk(k=1,2,…,m)记录蚂蚁k当前所走过的城市，集合tab uk随进化过程做动态调整。随时间的推移，以前留下的信息素逐渐挥发，用参数1-ρ表示信息素挥发程度，经过l个时刻，蚂蚁完成一次循环，各弧上的信息素量做以下调整
τij(t+l)=ρ·τij(t)+Δτij(55)
Δτij=∑mk=1Δτkij(56)
Δτkij表示第k只蚂蚁在本次循环中留在弧<i,j>上的信息素量，Δτij表示本次循环中弧<i,j>上的信息素的总增量，则有
Δτkij=QLk，若第k只蚂蚁在本次循环中经过弧<i,j>
0，否则(57)
其中，Q是常数，Lk表示第k只蚂蚁在本次循环中所走路径的总长度。
此模型中，参数Q,C,α,β,ρ通常由实验确定其最佳值。
蚁群算法解TSP的主要步骤描述如下：
步骤1： 迭代次数nc=0； 各τij和Δτij的初始化； 将m个蚂蚁置于n个顶点上。
步骤2： 将各蚂蚁的初始出发点置于当前解路线集中； 对每个蚂蚁k（k=1,2,…,m），按式(1)的概率pkij移至下一顶点j； 将顶点j置于当前解路线集中。
步骤3： 计算各蚂蚁的目标函数值Zk； 记录当前最好解。
步骤4： 按更新方程式(2)修改轨迹强度。
步骤5： 对各弧(i,j)，置Δτij=0,nc=nc+1。
步骤6： 若nc<预定迭代次数且无退化行为（即找到的都是相同解），则转步骤2； 否则，算法结束。
算法的时间复杂度为O(nc·m·n2)。就TSP而言，经验结果是，当m约等于n时，效果最佳，此时的时间复杂度为O(nc·n3)。
4. 蚁群算法的特点
蚁群算法是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等搜索算法以后的又一种应用于组合优化问题的随机搜索算法。众多的研究结果已经证明，蚁群算法具有较强的发现较好解的能力，这是因为该算法不仅利用了正反馈原理（在一定程度上可以加快进化过程），而且它本质上是一种并行算法，不同个体之间不断地进行信息的交流和传递，从而能够相互协作，有利于发现较好的解。该算法可以解释为一种特殊的强化学习（Reinforcement Learning）算法。
从查新情况分析，研究和应用蚁群算法主要集中在比利时、意大利、英国等欧洲国家，日本和美国也是近些年开始启动研究的。国内则于1998年末到1999年初才开始有少量的公开报道和研究成果，多局限于TSP问题。
该算法具有如下的优点：
（1） 自组织性。算法初期，单个的蚂蚁无序地寻找解，经过一段时间的演化，蚂蚁间通过信息素的作用，自发地越来越趋向于寻找到接近最优解的一些解，是个从无序到有序的过程。
（2） 较强的鲁棒性。对蚁群算法模型稍加修改，便可以应用于其他问题。
（3） 本质上并行。蚁群在问题空间的多点同时开始进行独立的解搜索，增强了算法的全局搜索能力。
（4） 正反馈。蚁群能够最终找到最短路径，直接依赖于最短路径上信息素的堆积，而信息素的堆积却是一个正反馈的过程。
（5） 易于与其他方法结合。蚁群算法很容易与多种启发式算法结合，以改善算法的性能。
蚁群算法也存在一些缺陷：
（1） 需要较长的搜索时间。当群体规模较大时，很难在较短的时间内从大量杂乱无章的路径中找出一条较好的路径。
（2） 容易出现停滞现象（Stagnation Behavior）。即在搜索进行到一定程度后，所有个体所发现的解完全一样，以致不能对解空间进一步进行搜索，不利于发现更好的解。
许多研究者已经注意到上述两个问题，并提出了一些改善措施，如M.Dorigo提出蚁量算法（AntQuantity System），Thomas等人提出最大最小蚁群算法（MaxMin Ant System，MMAS）,郝晋等人提出具有扰动特性的蚁群算法（Stochastic Distributed Ant System，SDAS）,陈烨提出带杂交算子的蚁群算法,等等。
5. 蚁群算法的应用情况
由于蚁群算法不依赖于问题的具体领域，所以在很多学科有广泛的应用。例如：
（1） 函数优化。蚁群算法应用的领域之一，也是评价蚁群算法性能的主要方法。
（2） 组合优化。用于二次分配问题、背包问题、TSP问题、加工车间（jobshop）问题等。
（3） 人工生命。蚁群算法在人工生命及复杂系统的模拟设计等方面应用前景广阔。
（4） 机器学习。基于蚁群算法的机器学习在许多领域得到了应用。例如利用蚁群算法进行神经网络训练、神经网络的优化设计等。
此外，蚁群算法在集成电路布线、数据挖掘、生产调度等方面也有广泛应用。
特别需要指出的是： 由于蚁群算法在求解复杂组合优化问题方面具有并行化、正反馈、鲁棒性强等先天优越性，所以在解决一些组合优化问题时所取得的结果无论是在解的质量上，还是在收敛速度上都优于或至少等效于模拟退火及其他启发式算法。
本章习题
51叙述穷举搜索、深度优先搜索、回溯算法、宽度优先搜索及分支限界算法的思想。
52试说明回溯算法与分支限界算法的异同点。
53部落卫队问题。原始部落中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都有仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何两个人都不是仇敌。给定部落中居民间的仇敌关系，编程计算组成部落卫队的最佳方案。
54子集和问题。该问题的一个实例为<s，t>，其中s={x1,x2,…,xn}是一个正整数的集合，t是一个正整数，判定是否存在s的一个子集s1，使得s1的元素和等于t。
55有一批共n个集装箱要装上两艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且∑ni=1wi≤c1+c2。要求确定是否可以将这个集装箱装上这两艘轮船。如果有，找出一种合理的装载方案。
图576题56
56给定n个大小不等的圆c1,c2,…,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且给定的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图576所示。其最小长度为2+42。
57运动员最佳匹配问题。羽毛球队有男女运动员各n人。给定两个n×n矩阵P和Q。P［i］［j］是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势； Q［i］［j］是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响，P［i］［j］不一定等于Q［j］［i］。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P［i］［j］×Q［j］［i］。设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。
58最小长度电路板排列问题。最小长度电路板排列问题是大规模电子系统设计中提出的实际问题。该问题的提法是，将n块电路板以最佳排列方案插入带有n个插槽的机箱。n块电路板的不同的排列方式对应不同的电路板插入方案。设B={1,2,…,n }是n块电路板的集合。集合L={N1,N2,…，Nm }是n块电路板的m个连接块。其中每个连接块Ni是B的一个子集，且Ni中的电路板用同一根导线连接在一起。
59设有n个顾客同时等待一项服务。顾客i需要的服务时间为Ti，其中1≤i≤n。共有s 处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n个顾客等待服务时间的总和除以n。
510整数变换问题。关于整数i 的变换f和g定义如下： f(i)=3i，g(i)=i/2。试设计一个算法，对于给定的两个整数n和m，用最少的f和g变换次数将n变换为m。例如， 可以用4次变换将整数15变换为整数4∶4=gfgg(15)。当整数n不可能变换为整数m时，算法应如何处理?
511推箱子问题。码头仓库是划分为n×m个格子的矩形阵列。有公共边的格子是相邻格子。当前仓库中有的格子是空闲的，有的格子则已经堆放了沉重的货物。由于堆放的货物很重，单凭仓库管理员的力量是无法移动的。仓库管理员有一项任务，要将一个小箱子推到指定的格子上。管理员可以在仓库中移动，但不能跨过已经堆放了货物的格子。管理员站在与箱子相对的空闲格子上时，可以做一次推动，把箱子推到相邻的空闲格子。只能向管理员的对面方向推箱子。由于要推动的箱子很重，仓库管理员希望尽量减少推箱子的次数。请设计一算法，使仓库管理员推箱子的次数最少。
512喷漆机器人。F大学开发出一种喷漆机器人Rob，能用指定颜色给一块矩形材料喷漆。Rob每次拿起一种颜色的喷枪，为指定颜色的小矩形区域喷漆。喷漆工艺要求，一个小矩形区域只能在所有紧靠它上方的矩形区域都喷过漆后，才能开始喷漆，且小矩形区域开始喷漆后必须一次性喷完，不能只喷一部分。为Rob编写一个自动喷漆程序，使Rob拿起喷枪的次数最少。