第 4 章回溯
寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大的问题。
本章集中阐述回溯方法，这种方法被用来设计货箱装船、背包、最大完备子图、旅行商和电路板排列问题的求解算法。
4.1 算法思想
回溯（b a c k t r a c k i n g）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（ solution space），这个空间必须至少包含问题的一个解（可能是最优的）。在迷宫老鼠问题中，我们可以定义一个包含从入口到出口的所有路径的解空间；在具有n 个对象的0 / 1背包问题中（见1 . 4节和2 . 2节），解空间的一个合理选择是2n 个长度为n 的0 / 1向量的集合，这个集合表示了将0或1分配给x的所有可能方法。当n= 3时，解空间为{ ( 0 , 0 , 0 )，( 0 , 1 , 0 )，( 0 , 0 , 1 )，( 1 , 0 , 0 )，( 0 , 1 , 1 )，( 1 , 0 , 1 )，( 1 , 1 , 0 )，( 1 , 1 , 1 ) }。
下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。图1 6 - 1用图的形式给出了一个3×3迷宫的解空间。从( 1 , 1 )点到( 3 , 3 )点的每一条路径都定义了3×3迷宫解空间中的一个元素，但由于障碍的设置，有些路径是不可行的。
图1 6 - 2用树形结构给出了含三个对象的0 / 1背包问题的解空间。从i 层节点到i+ 1层节点的一条边上的数字给出了向量x 中第i个分量的值x i ，从根节点到叶节点的每一条路径定义了解空间中的一个元素。从根节点A到叶节点H的路径定义了解x= [ 1 , 1 , 1 ]。根据w 和c 的值，从根到叶的路径中的一些解或全部解可能是不可行的。
一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。在迷宫老鼠问题中，开始节点为入口节点( 1 , 1 )；在0 / 1背包问题中，开始节点为根节点A。开始节点既是一个活节点又是一个E-节点（expansion node）。从E-节点可移动到一个新节点。如果能从当前的E-节点移动到一个新节点，那么这个新节点将变成一个活节点和新的E-节点，旧的E-节点仍是一个活节点。如果不能移到一个新节点，当前的E-节点就“死”了（即不再是一个活节点），那么便只能返回到最近被考察的活节点（回溯），这个活节点变成了新的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时，搜索过程结束。
例4-1 [迷宫老鼠] 考察图16-3a 的矩阵中给出的3×3的“迷宫老鼠”问题。我们将利用图1 6 -1给出的解空间图来搜索迷宫。
从迷宫的入口到出口的每一条路径都与图1 6 - 1中从( 1 , 1 )到( 3 , 3 )的一条路径相对应。然而，图1 6 - 1中有些从( 1 , 1 )到( 3 , 3 )的路径却不是迷宫中从入口到出口的路径。搜索从点( 1 , 1 )开始，该点是目前唯一的活节点，它也是一个E-节点。为避免再次走过
这个位置，置m a z e( 1 , 1 )为1。从这个位置，能移动到( 1 , 2 )或( 2 , 1 )两个位置。对于本例，两种移动都是可行的，因为在每一个位置都有一个值0。假定选择移动到( 1 , 2 )，m a z e( 1 , 2 )被置为1以避免再次经过该点。迷宫当前状态如图16-3b 所示。这时有两个活节点(1,1) (1,2)。( 1 , 2 )成为E-节点。
在图1 6 - 1中从当前E-节点开始有3个可能的移动，其中两个是不可行的，因为迷宫在这些位置上的值为1。唯一可行的移动是( 1 , 3 )。移动到这个位置，并置m a z e( 1 , 3 )为1以避免再次经过该点，此时迷宫状态为1 6 - 3 c。图1 6 - 1中，从( 1 , 3 )出发有两个可能的移动，但没有一个是可行的。所以E-节点( 1 , 3 )死亡，回溯到最近被检查的活节点( 1 , 2 )。在这个位置也没有可行的移动，故这个节点也死亡了。唯一留下的活节点是( 1 , 1 )。这个节点再次变为E-节点，它可移动到( 2 , 1 )。现在活节点为( 1 , 1 )，( 2 , 1 )。继续下去，能到达点( 3 , 3 )。此时，活节点表为( 1 , 1 )，( 2 , 1 )，( 3 , 1 )，( 3 , 2 )，( 3 , 3 )，这即是到达出口的路径。
程序5 - 1 3是一个在迷宫中寻找路径的回溯算法。
例4-2 [0/1背包问题] 考察如下背包问题：n= 3，w= [ 2 0 , 1 5 , 1 5 ]，p= [ 4 0 , 2 5 , 2 5 ]且c= 3 0。从根节点开始搜索图1 6 - 2中的树。根节点是当前唯一的活节点，也是E-节点，从这里能够移动到B或C点。假设移动到B，则活节点为A和B。B是当前E-节点。在节点B，剩下的容量r 为1 0，而收益c p 为4 0。从B点，能移动到D或E。移到D是不可行的，因为移到D所需的容量w2 为1 5。到E的移动是可行的，因为在这个移动中没有占用任何容量。E变成新的E-节点。这时活节点为A , B , E。在节点E，r= 1 0，c p= 4 0。从E，有两种可能移动（到J 和K），到J 的移动是不可行的，而到K的移动是可行的。节点K变成了新的E-节点。因为K是一个叶子，所以得到一个可行的解。这个解的收益为c p= 4 0。x 的值由从根到K的路径来决定。这个路径（ A , B , E , K）也是此时的活节点序列。既然不能进一步扩充K，K节点死亡，回溯到E，而E也不能进一步扩充，它也死亡了。接着，回溯到B，它也死亡了，A再次变为E-节点。它可被进一步扩充，到达节点C。此时r= 3 0，c p= 0。从C点能够移动到F或G。假定移动到F。F变为新的E-节点并且活节点为A, C,F。在F，r= 1 5，c p= 2 5。从F点，能移动到L或M。假定移动到L。此时r= 0，c p= 5 0。既然L是一个叶节点，它表示了一个比目前找到的最优解（即节点K）更好的可行解，我们把这个解作为最优解。节点L 死亡，回溯到节点F。继续下去，搜索整棵树。在搜索期间发现的最优解即为最后的解。
例4-3 [旅行商问题] 在这个问题中，给出一个n 顶点网络（有向或无向），要求找出一个包含所有n 个顶点的具有最小耗费的环路。任何一个包含网络中所有n 个顶点的环路被称作一个旅行（t o u r）。在旅行商问题中，要设法找到一条最小耗费的旅行。
图1 6 - 4给出了一个四顶点网络。在这个网络中，一些旅行如下： 1 , 2 , 4 , 3 , 1；
1 , 3 ,
2 , 4 , 1和1 , 4 ,
3 , 2 , 1。旅行2 ,
4 , 3 , 1 , 2；4 , 3 , 1 , 2 , 4和3 , 1 , 2 , 4 , 3和旅行1 , 2 , 4 , 3 , 1一样。而旅行1 , 3 , 4 , 2 , 1是旅行1 , 2 , 4 , 3 , 1的“逆”。旅行1 , 2 , 4 , 3 , 1的耗费为6 6；而1 , 3 , 2 , 4 , 1的耗费为2 5；
1 , 4 , 3 ,
2 , 1为5 9。故1 ,
3 , 2 ,
4 , 1是该网络中最小耗费的旅行。
顾名思义，旅行商问题可被用来模拟现实生活中旅行商所要旅行的地区问题。顶点表示旅行
商所要旅行的城市（包括起点）。边的耗费给出了在两个城市旅行所需的时间（或花费）。旅行表示当旅行商游览了所有城市再回到出发点时所走的路线。
旅行商问题还可用来模拟其他问题。假定要在一个金属薄片或印刷电路板上钻许多孔。孔的位置已知。这些孔由一个机器钻头来钻，它从起始位置开始，移动到每一个钻孔位置钻孔，然后回到起始位置。总共花的时间是钻所有孔的时间与钻头移动的时间。钻所有孔所需的时间独立于钻孔顺序。然而，钻头移动时间是钻头移动距离的函数。因此，希望找到最短的移动路径。
另有一个例子，考察一个批量生产的环境，其中有一个特殊的机器可用来生产n 个不同的
产品。利用一个生产循环不断地生产这些产品。在一个循环中，所有n 个产品被顺序生产出来，然后再开始下一个循环。在下一个循环中，又采用了同样的生产顺序。例如，如果这台机器被用来顺序为小汽车喷红、白、蓝漆，那么在为蓝色小汽车喷漆之后，我们又开始了新一轮循环，为红色小汽车喷漆，然后是白色小汽车、蓝色小汽车、红色小汽车，..，如此下去。一个循环的花费包括生产一个循环中的产品所需的花费以及循环中从一个产品转变到另一个产品的花费。虽然生产产品的花费独立于产品生产顺序，但循环中从生产一个产品转变到生产另一个产品的花费却与顺序有关。为了使耗费最小化，可以定义一个有向图，图中的顶点表示产品，边＜(i , j)＞上的耗费值为生产过程中从产品i 转变到产品j 所需的耗费。一个最小耗费的旅行定义了一个最小耗费的生产循环。
既然旅行是包含所有顶点的一个循环，故可以把任意一个点作为起点（因此也是终点）。针对图1 6 - 4，任意选取点1作为起点和终点，则每一个旅行可用顶点序列1, v2 ,., v n , 1来描述，
v2 , ., v n 是(2, 3, ., n) 的一个排列。可能的旅行可用一个树来描述，其中每一个从根到叶的路
径定义了一个旅行。图1 6 - 5给出了一棵表示四顶点网络的树。从根到叶的路径中各边的标号定义了一个旅行（还要附加1作为终点）。例如，到节点L的路径表示了旅行1 , 2 , 3 , 4 , 1，而到节点O的路径表示了旅行1 , 3 , 4 , 2 , 1。网络中的每一个旅行都由树中的一条从根到叶的确定路径来表示。因此，树中叶的数目为(n- 1 )！。
回溯算法将用深度优先方式从根节点开始，通过搜索解空间树发现一个最小耗费的旅行。对图1 6 - 4的网络，利用图1 6 - 5的解空间树，一个可能的搜索为A B C F L。在L点，旅行1 , 2 , 3 , 4 , 1作为当前最好的旅行被记录下来。它的耗费是5 9。从L点回溯到活节点F。由于F没有未被检查的孩子，所以它成为死节点，回溯到C点。C变为E-节点，向前移动到G，然后是M。这样构造出了旅行1 , 2 , 4 , 3 , 1，它的耗费是6 6。既然它不比当前的最佳旅行好，抛弃它并回溯到G，然后是C , B。从B点，搜索向前移动到D，然后是H , N。这个旅行1 , 3 , 2 , 4 , 1的耗费是2 5，比当前的最佳旅行好，把它作为当前的最好旅行。从N点，搜索回溯到H，然后是D。在D点，再次向前移动，到达O点。如此继续下去，可搜索完整个树，得出1 , 3 , 2 , 4 , 1是最少耗费的旅行。
当要求解的问题需要根据n 个元素的一个子集来优化某些函数时，解空间树被称作子集树（subset tree）。所以对有n 个对象的0 / 1背包问题来说，它的解空间树就是一个子集树。这样一棵树有2n 个叶节点，全部节点有2n+ 1－1个。因此，每一个对树中所有节点进行遍历的算法都必须耗时 ( 2n )。当要求解的问题需要根据一个n 元素的排列来优化某些函数时，解空间树被称作排列树（permutation tree）。这样的树有n! 个叶节点，所以每一个遍历树中所有节点的算法都必须耗时 (n! )。图1 6 - 5中的树是顶点{ 2 , 3 , 4 }的最佳排列的解空间树，顶点1是旅行的起点和终点。
通过确定一个新近到达的节点能否导致一个比当前最优解还要好的解，可加速对最优解的搜索。如果不能，则移动到该节点的任何一个子树都是无意义的，这个节点可被立即杀死，用来杀死活节点的策略称为限界函数（ bounding function）。在例1 6 - 2中，可使用如下限界函数：杀死代表不可行解决方案的节点；对于旅行商问题，可使用如下限界函数：如果目前建立的部分旅行的耗费不少于当前最佳路径的耗费，则杀死当前节点。如果在图1 6 - 4的例子中使用该限界函数，那么当到达节点I时，已经找到了具有耗费2 5的1 , 3 , 2 , 4 , 1的旅行。在节点I，部分旅行1 , 3 , 4的耗费为2 6，若旅行通过该节点，那么不能找到一个耗费小于2 5的旅行，故搜索以I为根节点的子树毫无意义。
小结
回溯方法的步骤如下：
1) 定义一个解空间，它包含问题的解。
2) 用适于搜索的方式组织该空间。
3) 用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。
回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前E-节点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话，再多的空间也不够用。
练习
1. 考察如下0 / 1背包问题：n= 4，w= [ 2 0 , 2 5 , 1 5 , 3 5 ]，p= [ 4 0 , 4 9 , 2 5 , 6 0 ]，c= 6 2。
1) 画出该0 / 1背包问题的解空间树。
2) 对该树运用回溯算法（利用给出的p s , w s , c值），依回溯算法遍历节点的顺序标记节点。确定回溯算法未遍历的节点。
2. 1) 当n= 5时，画出旅行商问题的解空间树。
2) 在该树上，运用回溯算法（使用图1 6 - 6的例子）。依回溯算法遍历节点的顺序标记节点。确定未被遍历的节点。
3. 每周六， Mary 和Joe 都在一起打乒乓球。她们每人都有一个装有1 2 0个球的篮子。
这样一直打下去，直到两个篮子为空。然后她们需要从球桌周围拾起2 4 0个球，放入各自
的篮子。Mary 只拾她这边的球，而Joe 拾剩下的球。描述如何用旅行商问题帮助Mary 和
Joe 决定她们拾球的顺序以便她们能走最少的路径。
4.2 应用
4.2.1 货箱装船
1. 问题
在1 . 3节中，考察了用最大数量的货箱装船的问题。现在对该问题做一些改动。在新问题中，有两艘船，n 个货箱。第一艘船的载重量是c1，第二艘船的载重量是c2，w i 是货箱i 的重量且n i = 1w i≤c1+c2。我们希望确定是否有一种可将所有n 个货箱全部装船的方法。若有的话，找出该方法。
例4-4 当n= 3，c1 =c2 = 5 0，w=[10,40,40] 时，可将货箱1 , 2装到第一艘船上，货箱3装到第二艘船上。如果w= [ 2 0 , 4 0 , 4 0 ]，则无法将货箱全部装船。当n i = 1w i＝c1+c2 时，两艘船的装载问题等价于子集之和（ s u m - o f - s u b s e t）问题，即有n 个数字，要求找到一个子集（如果存在的话）使它的和为c1。当c1=c2 且n i = 1w i＝2c1 时，两艘船的装载问题等价于分割问题（ partition problem），即有n个数字a i , ( 1≤i≤n)，要求找到一个子集（若存在的话），使得子集之和为( n i = 1a i)/ 2。分割问题和子集之和问题都是N P-复杂问题。而且即使问题被限制为整型数字，它们仍是N P-复杂问题。所以不能期望在多项式时间内解决两艘船的装载问题。当存在一种方法能够装载所有n 个货箱时，可以验证以下的装船策略可以获得成功： 1) 尽可能地将第一艘船装至它的重量极限； 2) 将剩余货箱装到第二艘船。为了尽可能地将第一艘船装满，需要选择一个货箱的子集，它们的总重量尽可能接近c1。这个选择可通过求解0 / 1背包问题来实现，即寻找m ax (n i = 1w i x i )，其中n i = 1w i x i≤c1，x i
，1≤i≤n。当重量是整数时，可用1 5 . 2节的动态规划方法确定第一艘船的最佳装载。用元组方法所需时间为O ( m i n {c1 , 2 n }）。可以使用回溯方法设计一个复杂性为O ( 2n ) 的算法，在有些实例中，该方法比动态规划算法要好。
2. 第一种回溯算法
既然想要找到一个重量的子集，使子集之和尽量接近c1，那么可以使用一个子集空间，并将其组织成如图1 6 - 2那样的二叉树。可用深度优先的方法搜索该解空间以求得最优解。使用限界函数去阻止不可能获得解答的节点的扩张。如果Z是树的j+ 1层的一个节点，那么从根到O 的路径定义了x i（1≤i≤j）的值。使用这些值，定义c w（当前重量）为n i = 1w i x i 。若c w>c1，则以O为根的子树不能产生一个可行的解答。可将这个测试作为限界函数。当且仅当一个节点的c w值大于c1 时，定义它是不可行的。
例4-5 假定n= 4，w= [ 8 , 6 , 2 , 3 ]，c1 = 1 2。解空间树为图1 6 - 2的树再加上一层节点。搜索从根A开始且c w= 0。若移动到左孩子B则c w= 8，c w≤c1 = 1 2。以B为根的子树包含一个可行的节点，故移动到节点B。从节点B不能移动到节点D，因为c w+w2 >c1。移动到节点E，这个移动未改变c w。下一步为节点J，c w= 1 0。J的左孩子的c w值为1 3，超出了c1，故搜索不能移动到J的左孩子。
可移动到J的右孩子，它是一个叶节点。至此，已找到了一个子集，它的c w= 1 0。x i 的值由从A到J的右孩子的路径获得，其值为[ 1 , 0 , 1 , 0 ]。
回溯算法接着回溯到J，然后是E。从E，再次沿着树向下移动到节点K，此时c w= 8。移动到它的左子树，有c w= 11。既然已到达了一个叶节点，就看是否c w的值大于当前的最优c w 值。结果确实大于最优值，所以这个叶节点表示了一个比[ 1 , 0 , 1 , 0 ]更好的解决方案。到该节点的路径决定了x 的值[ 1 , 0 , 0 , 1 ]。从该叶节点，回溯到节点K，现在移动到K 的右孩子，一个具有c w= 8的叶节点。这个叶节点中没有比当前最优cw 值还好的cw 值，所以回溯到K , E , B直到A。从根节点开始，沿树继续向下移动。算法将移动到C并搜索它的子树。
当使用前述的限界函数时，便产生了程序1 6 - 1所示的回溯算法。函数M a x L o a d i n g返回≤c的最大子集之和，但它不能找到产生该和的子集。后面将改进代码以便找到这个子集。
M a x L o a d i n g调用了一个递归函数m a x L o a d i n g，它是类L o a d i n g的一个成员，定义L o a d i n g类是为了减少M a x L o a d i n g中的参数个数。maxLoading(1) 实际执行解空间的搜索。MaxLoading(i) 搜索以i层节点（该节点已被隐式确定）为根的子树。从根到该节点的路径定义的子解答有一个重量值c w，目前最优解答的重量为b e s t w，这些变量以及与类L o a d i n g的一个成员相关联的其他变量，均由M a x L o a d i n g初始化。程序16-1 第一种回溯算法
template
class Loading {
friend MaxLoading(T [], T, int);
p r i v a t e :
void maxLoading(int i);
int n; // 货箱数目
T *w, // 货箱重量数组
c, // 第一艘船的容量
c w, // 当前装载的重量
bestw; // 目前最优装载的重量
} ;
template
void Loading
{// 从第i 层节点搜索
if (i > n) {// 位于叶节点
if (cw > bestw) bestw = cw;
r e t u r n ; }
// 检查子树
if (cw + w[i] <= c) {// 尝试x[i] = 1
cw += w[i];
m a x L o a d i n g ( i + 1 ) ;
cw -= w[i];}
maxLoading(i+1);// 尝试x[i] = 0
}
template
T MaxLoading(T w[], T c, int n)
{// 返回最优装载的重量
Loading
// 初始化X
X.w = w;
X.c = c;
X.n = n;
X.bestw = 0;
X.cw = 0;
// 计算最优装载的重量
X . m a x L o a d i n g ( 1 ) ;
return X.bestw;
}
如果i＞n，则到达了叶节点。被叶节点定义的解答有重量c w，它一定≤c，因为搜索不会移动到不可行的节点。若c w > b e s t w，则目前最优解答的值被更新。当i≤n 时，我们处在有两个孩子的节点Z上。左孩子表示x [ i ] = 1的情况，只有c w + w [ i ]≤c 时，才能移到这里。当移动到左孩子时， cw 被置为c w + w [ i ]，且到达一个i + 1层的节点。以该节点为根的子树被递归搜索。当搜索完成时，回到节点Z。为了得到Z的cw 值，需用当前的cw 值减去w [ i ]，Z的右子树还未搜索。既然这个子树表示x [ i ] = 0的情况，所以无需进行可行性检查就可移动到该子树，因为一个可行节点的右孩子总是可行的。
注意：解空间树未被m a x L o a d i n g显示构造。函数m a x L o a d i n g在它到达的每一个节点上花费( 1 )时间。到达的节点数量为O ( 2n )，所以复杂性为O ( 2n )。这个函数使用的递归栈空间为(n)。
3. 第二种回溯方法
通过不移动到不可能包含比当前最优解还要好的解的右子树，能提高函数m a x L o a d i n g的性能。令b e s t w为目前最优解的重量， Z为解空间树的第i 层的一个节点， c w的定义如前。以Z为根的子树中没有叶节点的重量会超过c w + r，其中r=n j = i + 1w[ j ] 为剩余货箱的重量。因此，当c w + r≤b e s t w时，没有必要去搜索Z的右子树。
例4-6 令n, w, c1 的值与例4 - 5中相同。用新的限界函数，搜索将像原来那样向前进行直至到达第一个叶节点J（它是J的右孩子）。bestw 被置为1 0。回溯到E，然后向下移动到K 的左孩子，此时b e s t w被更新为11。我们没有移动到K的右孩子，因为在右孩子节点c w = 8，r = 0，c w + r≤b e s t w。回溯到节点A。同样，不必移动到右孩子C，因为在C点c w = 0，r = 11且c w + r≤b e s t w。加强了条件的限界函数避免了对A的右子树及K的右子树的搜索。
当使用加强了条件的限界函数时，可得到程序1 6 - 2的代码。这个代码将类型为T的私有变量r 加到了类L o a d i n g的定义中。新的代码不必检查是否一个到达的叶节点有比当前最优解还优的重量值。这样的检查是不必要的，因为加强的限界函数不允许移动到不能产生较好解的节点。因此，每到达一个新的叶节点就意味着找到了比当前最优解还优的解。虽然新代码的复杂性仍是O ( 2n )，但它可比程序1 6 - 1少搜索一些节点。
程序16-2 程序1 6 - 1的优化
template
void Loading
{// // 从第i 层节点搜索
if (i > n) {// 在叶节点上
bestw = cw;
r e t u r n ; }
// 检查子树
r -= w[i];
if (cw + w[i] <= c) {//尝试x[i] = 1
cw += w[i];
m a x L o a d i n g ( i + 1 ) ;
cw -= w[i];}
if (cw + r > bestw) //尝试x[i] = 0
m a x L o a d i n g ( i + 1 ) ;
r += w[i];
}
template
T MaxLoading(T w[], T c, int n)
{// 返回最优装载的重量
Loading
// 初始化X
X.w = w;
X.c = c;
X.n = n;
X.bestw = 0;
X.cw = 0;
// r的初始值为所有重量之和
X.r = 0;
for (int i = 1; i <= n; i++)
X.r += w[i];
// 计算最优装载的重量
X . m a x L o a d i n g ( 1 ) ;
return X.bestw;
}
4. 寻找最优子集
为了确定具有最接近c 的重量的货箱子集，有必要增加一些代码来记录当前找到的最优子集。为了记录这个子集，将参数bestx 添加到Maxloading 中。bestx 是一个整数数组，其中元素可为0或1，当且仅当b e s t x [ i ] = 1时，货箱i 在最优子集中。新的代码见程序1 6 - 3。
程序16-3 给出最优装载的代码
template
void Loading
{ / /从第i 层节点搜索
if (i > n) {// 在叶节点上
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestw = cw; return;}
// 检查子树
r -= w[i];
if (cw + w[i] <= c) {//尝试x[i] = 1
x[i] = 1;
cw += w[i];
m a x L o a d i n g ( i + 1 ) ;
cw -= w[i];}
if (cw + r > bestw) {//尝试x[i] = 0
x[i] = 0;
m a x L o a d i n g ( i + 1 ) ; }
r += w[i];
}
template
T MaxLoading(T w[], T c, int n, int bestx[])
{// 返回最优装载及其值
Loading
// 初始化X
X.x = new int [n+1];
X.w = w;
X.c = c;
X.n = n;
X.bestx = bestx;
X.bestw = 0;
X.cw = 0;
// r的初始值为所有重量之和
X.r = 0;
for (int i = 1; i <= n; i++)
X.r += w[i];
X . m a x L o a d i n g ( 1 ) ;
delete [] X.x;
return X.bestw;
}
这段代码在L o a d i n g中增加了两个私有数据成员： x 和b e s t x。这两个私有数据成员都是整型的一维数组。数组x 用来记录从搜索树的根到当前节点的路径（即它保留了路径上的x i 值），b e s t x记录当前最优解。无论何时到达了一个具有较优解的叶节点， bestx 被更新以表示从根到叶的路径。为1的x i 值确定了要被装载的货箱。数据x 的空间由MaxLoading
因为bestx 可以被更新O ( 2n )次，故maxLoading 的复杂性为O (n2n )。使用下列方法之一，复杂性可降为O ( 2n )：
1) 首先运行程序1 6 - 2的代码，以决定最优装载重量，令其为W。然后运行程序1 6 - 3的一个修改版本。该版本以b e s t w = W开始运行，当c w + r≥b e s t w时搜索右子树，第一次到达一个叶节点时便终止（即i > n）。
2) 修改程序1 6 - 3的代码以不断保留从根到当前最优叶的路径。尤其当位于i 层节点时，则到最优叶的路径由x [ j ]（1≤j 5. 一个改进的迭代版本 可改进程序1 6 - 3的代码以减少它的空间需求。因为数组x 中记录可在树中移动的所有路径，故可以消除大小为(n)的递归栈空间。如例4 - 5所示，从解空间树的任何节点，算法不断向左孩子移动，直到不能再移动为止。如果一个叶子已被到达，则最优解被更新。否则，它试图移动到右孩子。当要么到达一个叶节点，要么不值得移动到一个右孩子时，算法回溯到一个节点，条件是从该节点向其右孩子移动有可能找到最优解。这个节点有一个特性，即它是路径中具有x [ i ] = 1的节点中离根节点最近的节点。如果向右孩子的移动是有效的，那么就这么做，然后再完成一系列向左孩子的移动。如果向右孩子的移动是无效的，则回溯到x [ i ] = 1的下一个节点。 该算法遍历树的方式可被编码成与程序1 6 - 4一样的迭代（即循环）算法。不像递归代码，这种代码在检查是否该向右孩子移动之前就移动到了右孩子。如果这个移动是不可行的，则回溯。迭代代码的时间复杂性与程序1 6 - 3一样。 程序16-4 迭代代码 template T MaxLoading(T w[], T c, int n, int bestx[]) {// 返回最佳装载及其值 // 迭代回溯程序 // 初始化根节点 int i = 1; // 当前节点的层次 // x[1:i-1] 是到达当前节点的路径 int *x = new int [n+1]; T bestw = 0, // 迄今最优装载的重量 cw = 0, // 当前装载的重量 r = 0; // 剩余货箱重量的和 for (int j = 1; j <= n; j++) r += w[j]; // 在树中搜索 while (true) { // 下移，尽可能向左 while (i <= n && cw + w[i] <= c) { // 移向左孩子 r -= w[i]; cw += w[i]; x[i] = 1; } if (i > n) {// 到达叶子 for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestw = cw;} else {// 移向右孩子 r -= w[i]; x[i] = 0; i + + ; } // 必要时返回 while (cw + r <= bestw) { // 本子树没有更好的叶子，返回 i - - ; while (i > 0 && !x[i]) { // 从一个右孩子返回 r += w[i]; i - - ; } if (i == 0) {delete [] x; return bestw;} // 移向右子树 x[i] = 0; cw -= w[i]; i + + ; } } } 4.2.2 0/1背包问题 0 / 1背包问题是一个N P-复杂问题，为了解决该问题，在1 . 4节采用了贪婪算法，在3 . 2节又采用了动态规划算法。在本节，将用回溯算法解决该问题。既然想选择一个对象的子集，将它们装入背包，以便获得的收益最大，则解空间应组织成子集树的形状（如图1 6 - 2所示）。该回溯算法与4 . 2节的装载问题很类似。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。 与程序1 6 - 2一样，左孩子表示一个可行的节点，无论何时都要移动到它；当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是令r 为还未遍历的对象的收益之和，将r 加到c p（当前节点所获收益）之上，若（r + c p）≤b e s t p（目前最优解的收益），则不需搜索右子树。一种更有效的方法是按收益密度p i / w i 对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量，当遇到第一个不能全部放入背包的对象时，就使用它的一部分。 例4-7 考察一个背包例子：n= 4，c= 7，p= [ 9 , 1 0 , 7 , 4 ]，w= [ 3 , 5 , 2 , 1 ]。这些对象的收益密度为[ 3 , 2 , 3 . 5 , 4 ]。当背包以密度递减的顺序被填充时，对象4首先被填充，然后是对象3、对象1。在这三个对象被装入背包之后，剩余容量为1。这个容量可 容纳对象2的0 . 2倍的重量。将0 . 2倍的该对象装入，产生了收益值2。被构造的解为x= [ 1 , 0 . 2 , 1 , 1 ]，相应的收益值为2 2。尽管该解不可行（x2 是0 . 2，而实际上它应为0或1），但它的收益值2 2一定不少于要求的最优解。因此，该0 / 1背包问题没有收益值多于2 2的解。 解空间树为图1 6 - 2再加上一层节点。当位于解空间树的节点B时，x1= 1，目前获益为c p= 9。该节点所用容量为c w= 3。要获得最好的附加收益，要以密度递减的顺序填充剩余容量c l e f t=ccw= 4。也就是说，先放对象4，然后是对象3，然后是对象2的0 . 2倍的重量。因此，子树A的最优解的收益值至多为2 2。当位于节点C时，c p=c w= 0，c l e f t= 7。按密度递减顺序填充剩余容量，则对象4和3被装入。然后是对象2的0 . 8倍被装入。这样产生出收益值1 9。在子树C中没有节点可产生出比1 9还大的收益值。 在节点E，c p= 9，c w= 3，c l e f t= 4。仅剩对象3和4要被考虑。当对象按密度递减的顺序被考虑时，对象4先被装入，然后是对象3。所以在子树E中无节点有多于c p+ 4 + 7 = 2 0的收益值。如果已经找到了一个具有收益值2 0或更多的解，则无必要去搜索E子树。 一种实现限界函数的好方法是首先将对象按密度排序。假定已经做了这样的排序。定义类K n a p（见程序1 6 - 5）来减少限界函数B o u n d（见程序1 6 - 6）及递归函数K n a p s a c k（见程序1 6 - 7）的参数数量，该递归函数用于计算最优解的收益值。参数的减少又可引起递归栈空间的减少以及每一个K n a p s a c k的执行时间的减少。注意函数K n a p s a c k和函数m a x L o a d i n g（见程序1 6 - 2）的相似性。同时注意仅当向右孩子移动时，限界函数才被计算。当向左孩子移动时，左孩子的限界函数的值与其父节点相同。 程序16-5 Knap类 template class Knap { friend Tp Knapsack(Tp *, Tw *, Tw, int); p r i v a t e : Tp Bound(int i); void Knapsack(int i); Tw c; / /背包容量 int n; // 对象数目 Tw *w; // 对象重量的数组 Tp *p; // 对象收益的数组 Tw cw; // 当前背包的重量 Tp cp; // 当前背包的收益 Tp bestp; // 迄今最大的收益 } ; 程序16-6 限界函数 template Tp Knap {// 返回子树中最优叶子的上限值Return upper bound on value of // best leaf in subtree. Tw cleft = c - cw; // 剩余容量 Tp 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; } 程序16-7 0/1背包问题的迭代函数 template void Knap {// 从第i 层节点搜索 if (i > n) {// 在叶节点上 bestp = cp; r e t u r n ; } // 检查子树 if (cw + w[i] <= c) {//尝试x[i] = 1 cw += w[i]; cp += p[i]; K n a p s a c k ( i + 1 ) ; cw -= w[i]; cp -= p[i];} if (Bound(i+1) > bestp) // 尝试x[i] = 0 K n a p s a c k ( i + 1 ) ; } 在执行程序1 6 - 7的函数Kn a p s a c k之前，需要按密度对对象排序，也要确保对象的重量总和超出背包的容量。为了完成排序，定义了类O b j e c t（见程序1 6 - 8）。注意定义操作符< =是为了使归并排序程序（见程序1 4 - 3）能按密度递减的顺序排序。 程序16-8 Object类 class Object { friend int Knapsack(int *, int *, int, int); p u b l i c : int operator<=(Object a) const {return (d >= a.d);} p r i v a t e : int ID; // 对象号 float d; // 收益密度 } ; 程序1 6 - 9首先验证重量之和超出背包容量，然后排序对象，在执行K n a p : : K n a p s a c k之前完成一些必要的初始化。K n a p : K n a p s a c k的复杂性是O (n2n )，因为限界函数的复杂性为O (n)，且该函数在O ( 2n )个右孩子处被计算。 程序16-9 程序1 6 - 7的预处理代码 template Tp Knapsack(Tp p[], Tw w[], Tw c, int n) {// 返回最优装包的值 // 初始化 Tw W = 0; // 记录重量之和 Tp P = 0; // 记录收益之和 // 定义一个按收益密度排序的对象数组 Object *Q = new Object [n]; for (int 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; // 可容纳所有对象 MergeSort(Q,n); // 按密度排序 // 创建K n a p的成员 K n a p < Tw, Tp> K; K.p = new Tp [n+1]; K.w = new Tw [n+1]; 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 . K n a p s a c k ( 1 ) ; delete [] Q; delete [] K.w; delete [] K.p; return K.bestp; } 4.2.3 最大完备子图 令U为无向图G的顶点的子集，当且仅当对于U中的任意点u 和v，(u , v)是图G的一条边时，U定义了一个完全子图（complete subgraph）。子图的尺寸为图中顶点的数量。当且仅当一个完全子图不被包含在G的一个更大的完全子图中时，它是图G的一个完备子图。最大的完备子图是具有最大尺寸的完备子图。 例4-8在图16-7a 中，子集{ 1 , 2 }定义了一个尺寸为2的完全子图。这个子图不是一个完备子图，因为它被包含在一个更大的完全子图{ 1 , 2 , 5 }中。{ 1 , 2 , 5 }定义了该图的一个最大的完备子图。点集{ 1 , 4 , 5 }和{ 2 , 3 , 5 }定义了其他的最大的完备子图。 当且仅当对于U中任意点u 和v，(u , v) 不是G的一条边时，U定义了一个空子图。当且仅当一个子集不被包含在一个更大的点集中时，该点集是图G的一个独立集（independent set），同时它也定义了图G的空子图。最大独立集是具有最大尺寸的独立集。对于任意图G，它的补图 （c o m p l e m e n t）是有同样点集的图，且当且仅当（u,v）不是G的一条边时，它是的一条边。 例4-9 图16-7b 是图16-7a 的补图，反之亦然。{ 2 , 4 }定义了16-7a 的一个空子图，它也是该图的一个最大独立集。虽然{ 1 , 2 }定义了图16-7b 的一个空子图，它不是一个独立集，因为它被包含在空子图{ 1 , 2 , 5 }中。{ 1 , 2 , 5 }是图16-7b 中的一个最大独立集。 如果U定义了G的一个完全子图，则它也定义了的一个空子图，反之亦然。所以在G的完备子图与的独立集之间有对应关系。特别的，G的一个最大完备子图定义了的一个最大独立集。 最大完备子图问题是指寻找图G的一个最大完备子图。类似地，最大独立集问题是指寻找图G的一个最大独立集。这两个问题都是N P-复杂问题。当用算法解决其中一个问题时，也就解决了另一个问题。例如，如果有一个求解最大完备子图问题的算法，则也能解决最大独立集问题，方法是首先计算所给图的补图，然后寻找补图的最大完备子图。 例4-10 假定有一个n 个动物构成的集合。可以定义一个有n 个顶点的相容图（c o m p a t i b i l i t yg r a p h）G。当且仅当动物u 和v 相容时，（u,v）是G的一条边。G的一个最大完备子图定义了相互间相容的动物构成的最大子集。 3 . 2节考察了如何找到一个具有最大尺寸的互不交叉的网组的集合问题。可以把这个问题看作是一个最大独立集问题。定义一个图，图中每个顶点表示一个网组。当且仅当两个顶点对应的网组交叉时，它们之间有一条边。所以该图的一个最大独立集对应于非交叉网组的一个最大尺寸的子集。当网组有一个端点在路径顶端，而另一个在底端时，非交叉网组的最大尺寸的子集能在多项式时间（实际上是(n2 )）内用动态规划算法得到。当一个网组的端点可能在平面中的任意地方时，不可能有在多项式时间内找到非交叉网组的最大尺寸子集的算法。最大完备子图问题和最大独立集问题可由回溯算法在O (n2n )时间内解决。两个问题都可使用子集解空间树（如图1 6 - 2所示）。考察最大完备子图问题，该递归回溯算法与程序1 6 - 3非常类似。当试图移动到空间树的i 层节点Z的左孩子时，需要证明从顶点i 到每一个其他的顶点j（x j = 1且j 在从根到Z的路径上）有一条边。当试图移动到Z的右孩子时，需要证明还有足够多的顶点未被搜索，以便在右子树有可能找到一个较大的完备子图。 回溯算法可作为类A d j a c e n c y G r a p h（见程序1 2 - 4）的一个成员来实现，为此首先要在该类 中加入私有静态成员x（整型数组，用于存储到当前节点的路径），b e s t x（整型数组，保存目 前的最优解），b e s t n（b e s t x中点的数量），c n（x 中点的数量）。所以类A d j a c e c y G r a p h的所有实 例都能共享这些变量。 函数m a x C l i q u e（见程序1 6 - 1 0）是类A d j a c e n c y G r a p h的一个私有成员，而M a x C l i q u e是一个 共享成员。函数m a x C l i q u e对解空间树进行搜索，而M a x C i q u e初始化必要的变量。M a x c l i q u e ( v ) 的执行返回最大完备子图的尺寸，同时它也设置整型数组v，当且仅当顶点i 不是所找到的最大完备子图的一个成员时，v [ i ] = 0。 程序16-10 最大完备子图 void AdjacencyGraph::maxClique(int i) {// 计算最大完备子图的回溯代码 if (i > n) {// 在叶子上 // 找到一个更大的完备子图，更新 for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestn = cn; r e t u r n ; } // 在当前完备子图中检查顶点i是否与其它顶点相连 int OK = 1; for (int j = 1; j < i; j++) if (x[j] && a[i][j] == NoEdge) { // i 不与j 相连 OK = 0; b r e a k ; } if (OK) {// 尝试x[i] = 1 x[i] = 1; // 把i 加入完备子图 c n + + ; m a x C l i q u e ( i + 1 ) ; x[i] = 0; c n - - ; } if (cn + n - i > bestn) {// 尝试x[i] = 0 x[i] = 0; m a x C l i q u e ( i + 1 ) ; } } int AdjacencyGraph::MaxClique(int v[]) {// 返回最大完备子图的大小 // 完备子图的顶点放入v [ 1 : n ] // 初始化 x = new int [n+1]; cn = 0; bestn = 0; bestx = v; // 寻找最大完备子图 m a x C l i q u e ( 1 ) ; delete [] x; return bestn; } 4.2.4 旅行商问题 旅行商问题（例4 . 3）的解空间是一个排列树。这样的树可用函数P e r m (见程序1 - 1 0 )搜索，并可生成元素表的所有排列。如果以x=[1, 2, ., n] 开始，那么通过产生从x2 到x n 的所 有排列，可生成n 顶点旅行商问题的解空间。由于P e r m产生具有相同前缀的所有排列，因此可以容易地改造P e r m，使其不能产生具有不可行前缀（即该前缀没有定义路径）或不可能比当前最优旅行还优的前缀的排列。注意在一个排列空间树中，由任意子树中的叶节点定 义的排列有相同的前缀（如图1 6 - 5所示）。因此，考察时删除特定的前缀等价于搜索期间不进入相应的子树。旅行商问题的回溯算法可作为类A d j a c e n c y W D i g r a p h（见程序1 2 - 1）的一个成员。在其他例子中，有两个成员函数： t S P和T S P。前者是一个保护或私有成员，后者是一个共享成员。函数G . T S P ( v )返回最少耗费旅行的花费，旅行自身 由整型数组v 返回。若网络中无旅行，则返回N o E d g e。t S P在排列空间树中进行递归回溯搜索， T S P是其一个必要的预处理过程。T S P假定x（用来保存到当前节点的路径的整型数组），b e s t x（保存目前发现的最优旅行的整型数组）， c c（类型为T的变量，保存当前节点的局部旅行的耗费），b e s t c（类型为T的变量，保存目前最优解的耗费）已被定义为A d j a c e n c y W D i g r a p h中的静态数据成员。T S P见程序1 6 - 11。t S P ( 2 )搜索一棵包含x [ 2 : n ]的所有排列的树。 程序1 6 - 11 旅行商回溯算法的预处理程序 template T AdjacencyWDigraph {// 用回溯算法解决旅行商问题 // 返回最优旅游路径的耗费，最优路径存入v [ 1 : n ] / /初始化 x = new int [n+1]; // x 是排列 for (int i = 1; i <= n; i++) x[i] = i; bestc = NoEdge; bestx = v; // 使用数组v来存储最优路径 cc = 0; // 搜索x [ 2 : n ]的各种排列 t S P ( 2 ) ; delete [] x; return bestc; } 函数t S P见程序1 6 - 1 2。它的结构与函数P e r m相同。当i=n 时，处在排列树的叶节点的父节点上，并且需要验证从x[n-1] 到x[n] 有一条边，从x[n] 到起点x[1] 也有一条边。若两条边都存在，则发现了一个新旅行。在本例中，需要验证是否该旅行是目前发现的最优旅行。若是，则将旅行和它的耗费分别存入b e s t x与b e s t c中。 当i＜n 时，检查当前i-1 层节点的孩子节点，并且仅当以下情况出现时，移动到孩子节点之一：1) 有从x[i-1] 到x[i] 的一条边（如果是这样的话， x [ 1 : i ]定义了网络中的一条路径）；2 )路径x[1:i] 的耗费小于当前最优解的耗费。变量cc 保存目前所构造的路径的耗费。每次找到一个更好的旅行时，除了更新bestx 的耗费外， tS P需耗时O ( (n- 1 ) ! )。因为需发生O ( (n-1)!) 次更新且每一次更新的耗费为(n) 时间，因此更新所需时间为O (n* (n- 1 ) ! )。通过使用加强的条件（练习1 6），能减少由tS P搜索的树节点的数量。 程序16-12 旅行商问题的迭代回溯算法 void AdjacencyWDigraph {// 旅行商问题的回溯算法 if (i == n) {// 位于一个叶子的父节点 // 通过增加两条边来完成旅行 if (a[x[n-1]][x[n]] != NoEdge && a[x[n]][1] != NoEdge && (cc + a[x[n-1]][x[n]] + a[x[n]][1] < bestc || bestc == NoEdge)) {// 找到更优的旅行路径 for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];} } else {// 尝试子树 for (int j = i; j <= n; j++) / /能移动到子树x [ j ]吗? if (a[x[i-1]][x[j]] != NoEdge && (cc + a[x[i-1]][x[i]] < bestc || bestc == NoEdge)) {//能 // 搜索该子树 Swap(x[i], x[j]); cc += a[x[i-1]][x[i]]; t S P ( i + 1 ) ; cc -= a[x[i-1]][x[i]]; Swap(x[i], x[j]);} } } 4.2.5 电路板排列 在大规模电子系统的设计中存在着电路板排列问题。这个问题的经典形式为将 n个电路板放置到一个机箱的许多插槽中，（如图1 6 - 8所示）。n个电路板的每一种排 列定义了一种放置方法。令B= {b1 , ., b n }表示这n个电路板。m个网组集合L= {N1, ., N m }由电路板定义，N i 是B的子集，子集中的元素需要连接起来。实际中用电线 将插有这些电路板的插槽连接起来。 例4 - 11令n=8, m= 5。集合B和L如下： B= {b1, b2, b3, b4, b5, b6, b7, b8 } L= {N1, N2, N3, N4, N5 } N1 = {b4, b5, b6 } N2 = {b2, b3 } N3 = {b1, b3 } N4 = {b3, b6 } N5 = {b7, b8 } 令x 为电路板的一个排列。电路板x i 被放置到机箱的插槽i 中。d e n s i t y(x) 为机箱中任意一对相邻插槽间所连电线数目中的最大值。对于图1 6 - 9中的排列，d e n s i t y 为2。有两根电线连接了插槽2和3，插槽4和5，插槽5和6。插槽6和7之间无电线，余下的相邻插槽都只有一根电线。板式机箱被设计成具有相同的相邻插槽间距，因此这个间距决定了机箱的大小。该间距必须保证足够大以便容纳相邻插槽间的连线。因此这个距离（继而机箱的大小）由d e n s i t y(x)决定。 电路板排列问题的目标是找到一种电路板的排列方式，使其有最小的d e n s i t y。既然该问题是一个N P-复杂问题，故它不可能由一个多项式时间的算法来解决，而象回溯这样的搜索方法则是解决该问题的一种较好方法。回溯算法为了找到最优的电路板排列方式，将搜索一个排列空间。 用一个n×m 的整型数组B表示输入，当且仅当N j 中包含电路板b i 时，B [ i ] [ j ] = 1。令t o t a l [ j ]为N j 中电路板的数量。对于任意部分的电路板排列x [ 1 : i ]，令n o w [ j ]为既在x [ 1 : i ]中又被包含在N j 中的电路板的数量。当且仅当n o w [ j ] > 0且n o w [ j ] ≠t o t a l [ j ]时，N j 在插槽i 和i + 1之间有连线。插槽i 和i + 1间的线密度可利用该测试方法计算出来。在插槽k和k + 1 ( 1≤k≤i ) 间的线密度的最大值给出了局部排列的密度。 为了实现电路板排列问题的回溯算法，使用了类B o a r d（见程序1 6 - 1 3）。程序1 6 - 1 4给出了私有方法B e s t O r d e r，程序1 6 - 1 5给出了函数A r r a n g e B o a r d s。ArrangeBoards 返回最优的电路板排列密度，最优的排列由数组bestx 返回。ArrangeBoards 创建类Board 的一个成员x 并初始化与之相关的变量。尤其是total 被初始化以使total[j] 等于N j 中电路板的数量。now[1:n] 被置为0，与一个空的局部排列相对应。调用x .BestOrder(1,0) 搜索x[1:n] 的排列树，以从密度为0的空排列中找到一个最优的排列。通常，x.BestOrder(i,cd) 寻找最优的局部排列x [ 1 : i - 1 ]，该局部排列密度为c d。函数B e s t O r d e r（见程序1 6 - 1 4）和程序1 6 - 1 2有同样的结构，它也搜索一个排列空间。当i=n 时，表示所有的电路板已被放置且cd 为排列的密度。既然这个算法只寻找那些比当前最优排列还优的排列，所以不必验证cd 是否比beste 要小。当i 注意每一个更新至少将b e s t d的值减少1，且最终b e s t d≥0。所以更新的次数是O (m)。B e s t O r d e r的整体复杂性为O (m n! )。 程序16-13 Board的类定义 class Board { friend ArrangeBoards(int**, int, int, int []); p r i v a t e : void BestOrder(int i, int cd); int *x, // 到达当前节点的路径 * b e s t x , // 目前的最优排列 * t o t a l , // total[j] = 带插槽j的板的数目 * n o w, // now[j] = 在含插槽j的部分排列中的板的数目 b e s t d , // bestx的密度 n , / /板的数目 m , // 插槽的数目 * * B ; // 板的二维数组 } ; 程序16-14 搜索排列树 void Board::BestOrder(int i, int cd) {// 按回溯算法搜索排列树 if (i == n) { for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestd = cd;} else // 尝试子树 for (int j = i; j <= n; j++) { // 用x[j] 作为下一块电路板对孩子进行尝试 // 在最后一个插槽更新并计算密度 int ld = 0; for (int k = 1; k <= m; k++) { now[k] += B[x[j]][k]; if (now[k] > 0 && total[k] != now[k]) l d + + ; } // 更新ld 为局部排列的总密度 if (cd > ld) ld = cd; // 仅当子树中包含一个更优的排列时，搜索该子树 if (ld < bestd) {// 移动到孩子 Swap(x[i], x[j]); BestOrder(i+1, ld); Swap(x[i], x[j]);} // 重置 for (k = 1; k <= m; k++) now[k] -= B[x[j]][k]; } } 程序16-15 BestOrder(程序1 6 - 1 4)的预处理代码int ArrangeBoards(int **B, int n, int m, int bestx[ ]) {// 返回最优密度 // 在b e s t x中返回最优排列 Board X; // 初始化X X.x = new int [n+1]; X.total = new int [m+1]; X.now = new int [m+1]; X.B = B; X.n = n; X.m = m; X.bestx = bestx; X.bestd = m + 1; // 初始化t o t a l和n o w for (int i = 1; i <= m; i++) { X.total[i] = 0; X.now[i] = 0; } // 初始化x并计算t o t a l for (i = 1; i <= n; i++) { X.x[i] = i; for (int j = 1; j <= m; j++) X.total[j] += B[i][j]; } // 寻找最优排列 X . B e s t O r d e r ( 1 , 0 ) ; delete [] X.x; delete [] X.total; delete [] X.now; return X.bestd; 练习 4. 证明在两船装载问题中，只要存在一种方法能装载所有货箱，则通过尽可能装满第一艘船就可找到一种可行的装载方法。 5. 运行程序1 6 - 3和1 6 - 4的代码，测试它们的相对运行时间。 6. 运用1 6 . 2 . 1节中第4小节的方法1) 来更新程序1 6 - 3，使其能得到时间复杂性O ( 2n )。 7. 运用1 6 . 2 . 1节中第4小节的方法2) 来修改程序1 6 - 3，使其运行时间减少至O ( 2n )。 8. 为子集之和问题写一个递归回溯算法。注意，只要找到一个子集，其和为c1，则可终止程序运行。没有必要记住目前的最优解。代码不应使用像程序1 6 - 3中的数组x。在找到和为c1 的子集之后展开递归，可以重构出最优解。 9. 优化程序1 6 - 7和1 6 - 9以便能产生出与背包问题最优解相对应的一个0 / 1数组x。 10. 用迭代回溯算法求解0 / 1背包问题。该算法与程序1 6 - 4类似。可以修改K n a p : : B o u n d，使其返回被装入背包的最后一个对象i，这样可避免根据B o u n d重新向左移动而可直接移动到最左节点（原先由B o u n d确定）。 11. 编写程序1 6 - 1 0（与程序1 6 - 4相对应）的迭代版本并比较这两个版本。 12. 改写程序1 6 - 1 0，使其首先按度的递减次序来排列各顶点。你认为该版本比程序1 6 - 1 0 好吗？ 13. 编写一个求解最大独立集问题的回溯算法。 14. 重写最大完备子图代码（见程序1 6 - 1 0），把它作为类U N e t w o r k的成员。对于类ADjacencyGraph, AdjacencyWGraph, LinkedGraph和L i n k e d W G r a p h（见1 2 . 7节）的成员，该代码同样有效。 15. 令G为一个n 顶点的有向图，M a x i 为从顶点i 出发的具有最大耗费的边的耗费 1) 证明旅行商的每一个旅行有一个小于n i =1M a x i + 1的耗费。 2) 使用上述界限作为b e s t c的初始值。重写T S P和t S P，尽可能简化它们。 16. 令G为具有n 个顶点的有向图，M i n O u t i 为从顶点i 出发的具有最小耗费的边的耗费1) 证明具有前缀x1 到x i 的旅行商的所有旅行耗费至少为i j =2A(x j - 1, x j )+n y=i M i n O u t xj 其中A(u,v)是边(u,v)的耗费。 2) 在程序1 6 - 1 2中，使用 if (a [x [i-1] ] [x [j] ] ! = NoEdge &&(cc + a [x [i-1] ] [x [i] ] < bestc | |bestc == NoEdge) ) 来决定何时移动到一个孩子节点。要求使用1) 的结果得到一个更强的条件。第一个和可根据cc 计算出来，通过用一个新变量r 保留不在当前路径中的顶点的M i n O u t [ i ]的和，可以很容易地计算出第二个和。 3) 测试t S P的新版本。与程序1 6 - 1 2比较，它访问了排列树的多少节点？ 17. 考察电路板排列问题。N i 的长度为N i 中第一块和最后一块电路板间的距离。N4 中第一个电路板在插槽3中，最后一个电路板在插槽6中，则N4 的长度为3。N2 的长度为2。N i 最大值为3。编写一个回溯算法以找到具有最小的最大长度的板排列。试测试代码的正确性。 18. [顶点覆盖] 令G为一个无向图。当且仅当对于G中的每一条边(u , v)，u 或v 或u , v 在U中时，G的顶点子集U是一个顶点覆盖（vertex cover）。U中顶点的数量是覆盖的大小。在 设计四 子集和数的回溯算法 班级通信08-2BF 学号1408230929 姓名杨福 成绩 分 一、 设计目的 1.掌握回溯法解题的基本思想； 2.掌握子集和数问题的回溯算法； 3.进一步掌握子集和数问题的回溯递归算法、迭代算法的基本思想和算法设计方法； 二、 设计内容 a) 任务描述 1）子集和数问题简介 子集和数问题是假定有n 个不同的正数（通常称为权），要求找出这些数中所有事的某和数为M 的组合。 2）设计任务简介 设计、编程、测试求解子集和数问题的回溯算法。 1． 子集和数问题的表示方案 本设计利用大小固定的元组来研究回溯算法，在此情况下，解向量的元素X （i ）取1或0值，它表示是否包含了权数W （i ）. 生成图中任一结点的儿子是很容易的。对于i 级上的一个结点，其左儿子对应于X （i ）=1，右儿子对应于X(i)=0。对于限界函数的 一种简单选择是，当且仅当∑∑+==≥+ n k i k i M i W i X i W 11)()()(时，B(X(1),〃〃〃，X （k ）)=true 。 显然，如果这个条件不满足，X(1),〃〃〃，X （k ）就不能导致一个答案结点。如果假定这些W （i ）一开始就是按非降次序列排列的，那么这些限界函数可以被强化。在这种情 况下，如果M k W i X i W k i >++∑=)1()()(1 ,则X(1),〃〃〃，X （k ）就不能导致一个答案结 点。因此，将要使用的限界函数是B k （X （1），〃〃〃，X （k ））=true,当且仅当 M i W i X i W n k i k i =+∑∑+==11)()()(。 2． 主要数据类型与变量 int M ; // 表示要求得到的子集和； int s; // 表示所选当前元素之前所选的元素和； 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） 补充2 回溯法 解回溯法的深度优先搜索策略 z理解回溯法的深度优先搜索策略。 z掌握用回溯法解题的算法框架 （1）递归回溯 （2）迭代回溯 （3）子集树算法框架 （4）排列树算法框架 通过应用范例学习回溯法的设计策略 z通过应用范例学习回溯法的设计策略。 Sch2-1z Sch2-1 方法概述搜索算法介绍 （1）穷举搜索 （2）盲目搜索 —深度优先(DFS)或回溯搜索( Backtracking); —广度优先搜索( BFS ); (Branch &Bound) —分支限界法(Branch & Bound)；—博弈树搜索( α-βSearch) （3）启发式搜索 —A* 算法和最佳优先( Best-First Search ) —迭代加深的A*算法 —B*AO*SSS*等算法B , AO , SSS 等算法 —Local Search, GA等算法 Sch2-1z Sch2-1 方法概述搜索空间的三种表示： —表序表示：搜索对象用线性表数据结构表示； —显示图表示：搜索对象在搜索前就用图（树）的数据结构表示； —隐式图表示：除了初始结点，其他结点在搜索过程中动态生成。缘于搜索空间大，难以全部存储。 z 搜索效率的思考：随机搜索 —上世纪70年代中期开始，国外一些学者致力于研究随机搜索求解困难的组合问题，将随机过程引入搜索； —选择规则是随机地从可选结点中取一个从而可以从统计角度分析搜选择规则是随机地从可选结点中取一个，从而可以从统计角度分析搜索的平均性能； —随机搜索的一个成功例子是：判定一个很大的数是不是素数，获得了第个多式时算法 第一个多项式时间的算法。 动态规划法、回溯法解0-1背包问题 2012级计科庞佳奇 一、问题描述与分析 1.动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会 有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。 不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。 多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。 01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。 2.回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目 标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 搜索与回溯算法介绍 一、概述： 计算机常用算法大致有两大类：一类叫蛮干算法，一类叫贪心算法。前者常使用的手段就是搜索，对全部解空间进行地毯式搜索，直到找到指定解或最优解。后者在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解。 二、搜索与回溯： 这里着重介绍搜索与回溯。当很多问题无法根据某种确定的计算法则来求解时可以利用搜索与回溯的技术求解。回溯是搜索算法中既带有系统性又带有跳跃性的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索。在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，然后继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进。如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。 【建立解空间】 问题的解应该如何描述，如何建立呢？问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。借助图论的思想，可以用图来描述，图的定义为G，由顶点集和边集构成，顶点即实实在在的数据、对象，而边可以抽象为关系，即顶点间的关系，这种关系不一定非要在数据结构上表现出来，用数据结构的语言来描述，如果关系是一对一，则为线性表，如果关系是一对多，则为树，如果关系是多对多，则为图，如果完全没有关系，则为集合。但在数据结构中这种关系不一定非要在数据的存储性质上一开始就表现出来，譬如，你可以用一个数组表示一个线性表，也可以表示完全二叉树，同样也可以用邻接表表示一个图，对于关系的描述不是数据结构本身的描述，而是算法的描述，正如数据结构是离不开特定的算法一样，不可分开单独而谈。 确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向 1、实验目的 （1）掌握回溯法设计策略。 （2）通过0-1背包问学习回溯法法设计技巧2.实验内容 源程序： #include } if(cw+w[i]<=c) //搜索左子树 { cw+=w[i]; cp+=p[i]; Backtrack(i+1); cp-=p[i]; cw-=w[i]; } if(bound(i+1)>bestp)//搜索右子树 Backtrack(i+1); } double Knapsack (double pp[],double ww[],double d) { int i; double TP=0,TW=0; cw=0.0;cp=0.0;bestp=0.0;//计算所有物品的重量及价值 for(i=1;i<=n;i++) { TP=TP+pp[i]; TW=TW+ww[i]; } if(TW<=d)//所有物品装入背包 bestp=TP; else { Backtrack(1); } return bestp; }; int main() { 应用数学学院信息安全专业班学号姓名 实验题目回溯算法 实验评分表 实验报告 一、实验目的与要求 1、理解回溯算法的基本思想； 2、掌握回溯算法求解问题的基本步骤； 3、了解回溯算法效率的分析方法。 二、实验内容 【实验内容】 最小重量机器设计问题：设某一个机器有n个部件组成，每个部件都可以m个不同供应商处购买，假设已知表示从j个供应商购买第i个部件的重量，表示从j个供应商购买第i个部件的价格，试用回溯法求出一个或多个总价格不超过c且重量最小的机器部件购买方案。 【回溯法解题步骤】 1、确定该问题的解向量及解空间树； 2、对解空间树进行深度优先搜索； 3、再根据约束条件（总价格不能超过c）和目标函数（机器重量最小）在搜索过程中剪去多余的分支。 4、达到叶结点时记录下当前最优解。 5、实验数据n,m, ] ][ [j i w,] ][ [j i c的值由自己假设。 三、算法思想和实现【实现代码】 【实验数据】 假设机器有3个部件，每个部件可由3个供应商提供（n=3，m=3）。总价不超过7（c<=7）。 部件重量表： 部件价格表： 【运行结果】 实验结果：选择供应商1的部件1、供应商1的部件2、供应商3的部件3，有最小重量机器的重量为4，总价钱为6。 四、问题与讨论 影响回溯法效率的因素有哪些？ 答：影响回溯法效率的因素主要有以下这五点： 1、产生x[k]的时间； 2、满足显约束得x[k]值的个数； 3、计算约束函数constraint的时间； 4、计算上界函数bound的时间； 5、满足约束函数和上界函数约束的所有x[k]的个数。 五、总结 这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了回溯算法的思想。 回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井 中原工学院信息商务学院 实验报告 实验项目名称回溯划算法的应用 课程名称算法设计与分析 学院(系、部)中原工学院信息商务学院学科专业计算机科学与技术系班级学号计科132班17号姓名程一涵 任课教师邬迎 日期2014年12月9日 实验五回溯算法的应用 一、实验目的 1．掌握回溯算法的基本概念 2．熟练掌握回溯算法解决问题的基本步骤。 3．学会利用回溯算法解决实际问题。 二．问题描述 题目一：N皇后问题 要在n*n的国际象棋棋盘中放n个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解要求：键盘输入皇后的个数n (n ≤ 13) 输出有多少种放置方法 输入输出实例： 三．算法设计 首先，确定第一行皇后的位置，再确定第二行的位置，并且要注意不能同行同列同对角线，若是发现有错则返回上一层，继续判断。满足约束条件时，则开始搜索下一个皇后的位置，直到找出问题的解。 四.程序调试及运行结果分析 五.实验总结 通过这次试验，使得我们面对问题时的解题思路变得更加灵活和多变，并且使我们的编写能力稍稍的提高一些。初步了解了回溯算法，回溯算法实际是一个类似枚举的搜索尝试方法，他的主题思想是在搜索尝试的过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径。他特别适用于求解那些涉及到寻求一组解的问题或者求满足某些约束条件的最优解的问题。此算法具有结构清晰，容易理解且可读性强等优点，并且通过稍加变通也可以适用于其他类似问题 附录：程序清单（程序过长，可附主要部分） #include 回溯法 回溯法也是搜索算法中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优秀搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。回溯法是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。 一、回溯法的基本思路 何谓回溯法，我们不妨通过一个具体实例来引出回溯法的基本思想及其在计算机上实现的基本方法。【例题12.2.1】n皇后问题 一个ｎ×ｎ（1≤n≤100）的国际象棋棋盘上放置ｎ个皇后，使其不能相互攻击，即任何两个皇后都不能处在棋盘的同一行、同一列、同一条斜线上，试问共有多少种摆法？ 输入： n 输出： 所有分案。每个分案为n+1行，格式： 方案序号 以下n行。其中第i行（1≤i≤n）行为棋盘i行中皇后的列位置。 在分析算法思路之前，先让我们介绍几个常用的概念： 1、状态（state） 状态是指问题求解过程中每一步的状况。在ｎ皇后问题中，皇后所在的行位置i(1≤i≤n)即为其时皇后问题的状态。显然，对问题状态的描述，应与待解决问题的自然特性相似，而且应尽量做到占用空间少，又易于用算符对状态进行运算。 2、算符（operater） 算符是把问题从一种状态变换到另一种状态的方法代号。算符通常采用合适的数据来表示，设为局部变量。n皇后的一种摆法对应1．．ｎ排列方案（a1，…，a n）。排列中的每个元素a i对应ｉ行上皇后的列位置（1≤i≤n）。由此想到，在ｎ皇后问题中，采用当前行的列位置i(1≤i≤n)作为算符是再合适不过了。由于每行仅放一个皇后，因此行攻击的问题自然不存在了，但在试放当前行的一个皇后时，不是所有列位置都适用。例如(l，ｉ)位置放一个皇后，若与前1．．l-1行中的j行皇后产生对角线攻击(｜ｊ－l｜=｜a j －i｜)或者列攻击(ｉ≠a j)，那么算符ｉ显然是不适用的，应当舍去。因此，不产生对角线攻击和列攻击是ｎ皇后问题的约束条件，即排列（排列a1，…，a i，…，a j，…，a n）必须满足条件(｜ｊ－ｉ｜≠｜a j－a i｜) and (a i≠a j) (1≤i，j≤n)。 3、解答树（analytic tree） 现在让我们先来观察一个简单的ｎ皇后问题。设ｎ＝4，初始状态显然是一个空棋盘。 此时第一个皇后开始从第一行第一列位置试放，试放的顺序是从左至右、自上而下。每个棋盘由４个数据表征相应的状态信息（见下图）： （××××） 【问题】填字游戏 问题描述：在3×3个方格的方阵中要填入数字1到N（N≥10）内的某9个数字，每个方格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。 可用试探发找到问题的解，即从第一个方格开始，为当前方格寻找一个合理的整数填入，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填证书，就要回退到前一方格，调整前一方格的填入数。当第九个方格也填入合理的整数后，就找到了一个解，将该解输出，并调整第九个的填入的整数，寻找下一个解。 为找到一个满足要求的9个数的填法，从还未填一个数开始，按某种顺序（如从小到大的顺序）每次在当前位置填入一个整数，然后检查当前填入的整数是否能满足要求。在满足要求的情况下，继续用同样的方法为下一方格填入整数。如果最近填入的整数不能满足要求，就改变填入的整数。如对当前方格试尽所有可能的整数，都不能满足要求，就得回退到前一方格，并调整前一方格填入的整数。如此重复执行扩展、检查或调整、检查，直到找到一个满足问题要求的解，将解输出。 回溯法找一个解的算法： { int m=0,ok=1; int n=8; do{ if (ok) 扩展; else 调整; ok=检查前m个整数填放的合理性; } while ((!ok||m!=n)&&(m!=0)) if (m!=0) 输出解; else 输出无解报告； } 如果程序要找全部解，则在将找到的解输出后，应继续调整最后位置上填放的整数，试图去找下一个解。相应的算法如下： 回溯法找全部解的算法： { int m=0,ok=1; int n=8; do{ if (ok) { if (m==n) { 输出解； 调整； } else 扩展; } else 调整; ok=检查前m个整数填放的合理性; } while (m!=0); } 实验五：0/1背包问题的回溯算法设计实验目的：0/1背包问题的回溯算法设计 实验原理：回溯算法设计。 实验要求：基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想:0-1背包问题:给定n种物品和一背包.物品i的重量是wi,其价值为ui,背包的容量为C.问如何选择装入背包的物品,使得装入背包中物品的总价值最大? 分析: 0-1背包是子集合选取问题,一般情况下0-1背包是个NP问题.第一步确定解空间：装入哪几种物品 第二步确定易于搜索的解空间结构： 可以用数组p,w分别表示各个物品价值和重量。 用数组x记录，是否选种物品 第三步以深度优先的方式搜索解空间，并在搜索的过程中剪枝要求：（1）使用C++或TC2.0 （2）上机前要有源代码或流程图。#include for(int m=1;m<=n;m++) { cout< 回溯算法的应用 课程名称：算法设计与分析 院系：************************ 学生姓名：****** 学号：************ 专业班级：***************************** 指导教师：****** 2013年12月27日 回溯法的应用 摘要：回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 回溯法，其意义是在递归直到可解的最小问题后，逐步返回原问题的过程。而这里所说的回溯算法实际是一个类似枚举的搜索尝试方法，它的主题思想是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。 回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”的思想，作为其控制结构。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。 全排列和求最优解问题是比较经典的问题，我们可以采用多种算法去求解此问题，比如动态规划法、分支限界法、回溯法。在这里我们采用回溯法来解决这个问题。 关键词：回溯法全排列最优值枚举 C语言设计之回溯算法（24点） 姚铸 问题叙述： 24点： 从键盘输入4个数字进行加减乘除，要求结果为24 输入要求 第一行：4 3 2 1 输出 24=12*2 2=2*1 12=4*3 问题分析：这个问题是我们小时候都应该玩过。问题的重点在于输入的数据要进行运算后得到24这个值是问题的难点。4个数之间无序的运算有很多种情况。用程序去实现24点，就需要4个数之间进行每一种的讨论。用穷举是能够计算出来的。但是时间复杂度值太大。 算法设计：这类型问题的解决方案重点在于4个数算出的结果如果不能在该步运算出24能否后悔还原会 上一次循环或递归。这里的后悔就联想到回溯算法。 算法思想：从算法设计得到了回溯算法。后悔正是回溯算法的中心思想。在得不到真正的结果的时候退回上一步。在结果计算的时候运用if或while语言对程序结束进行控制。 特殊测试：5 5 5 1 这组数据计算24点是成立的。在运算的过程中会出现小数。 参考程序（这是我自己写出的程序代码，经过测试没有问题。）： 递归算法实现回溯： #include 回溯算法 搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。 递归回溯法算法框架[一] procedure Try(k:integer); begin for i:=1 to 算符种数 Do if 满足条件 then begin 保存结果 if 到目的地 then 输出解 else Try(k+1); 恢复：保存结果之前的状态{回溯一步} end; end; 递归回溯法算法框架[二] procedure Try(k:integer); begin if 到目的地 then 输出解 else for i:=1 to 算符种数 Do if 满足条件 then begin 保存结果 Try(k+1); end; end; 例 1：素数环：把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。【算法分析】非常明显，这是一道回溯的题目。从1 开始，每个空位有 20（19）种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第 20个数还要判断和第1个数的和是否素数。 〖算法流程〗1、数据初始化； 2、递归填数： 判断第J种可能是否合法； A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个； B、如果不合法：选择下一种可能； 【参考程序】 program z74;框架[一] var a:array[0..20]of byte; b:array[0..20]of boolean; total:integer; function pd(x,y:byte):boolean; var k,i:byte; begin k:=2; i:=x+y; pd:=false; while (k<=trunc(sqrt(i)))and(i mod k<>0) do inc(k); if k>trunc(sqrt(i)) then pd:=true; end; procedure print; var j:byte; begin inc(total);write('<',total,'>:'); for j:=1 to 20 do write(a[j],' '); writeln; end; procedure try(t:byte); var i:byte; begin for i:=1 to 20 do if pd(a[t-1],i)and b[i] then begin a[t]:=i; b[i]:=false; if t=20 then begin if pd(a[20],a[1]) then print;end 《算法设计与分析》实验报告实验三回溯法 3.迷宫问题 一天Luna在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，. 和#，前者表示可以通行后者表示不能通行。同时当Luna处在某个格点时，她只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Luna想要从点A走到点B（不能走出迷宫）。如果起点或者终点有一个不能通行(为#)，则看成无法办到。 [输入] 第1行是测试数据的组数k，后面跟着k组输入。 每组测试数据的第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n 的。 接下来是一个n * n的矩阵，矩阵中的元素为. 或者#。 再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb 行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。 1.八皇后问题 1.1解题思路 八皇后问题的解法，很简单的解法。通过回溯实现枚举。 对于当前行，尝试是否可在当前列放置皇后，然后进入下一行的尝试，同时尝试完毕以后，要将当前行回复（回溯），来进行下一次尝试。 到达最后一行的时候，即递归结束条件，打印结果即可。 1.2程序运行情况 1.3所有的皇后解 见附录。（毕竟92个解...） 1.4程序源码（含注释） 2. 24点问题 2.1 解题思路 这题虽然使用dfs很简单，但是有一点思维在里面。我很惭愧，自己没有想出来怎么如意的独立AC此题。 遇到的最大的问题——如何插入括号？枚举插入、和运算符一同排列都不靠谱。解决方法是：用同等的办法转化。每一次从待组合的是数字中，任取两个数，随机用运算符计算完毕后，再放回去。下一次计算，再次重复这个过程，可以等价为有括号的运算方式了。 遇到第二个问题——如何实现这种“任取两个数”的选择方式。这里就直接体现出了我个人能力的不足。居然没想到。尝试使用STL的set，但是没成功。这里借鉴了网上的AC 思路，我感到自己思维太僵硬。解决方法是——对于当前的运算状态中，用两个循环实现枚举两个数，计算为完毕以后，结果覆盖在数组序号小的那个数的位置，再将第二个数与最后一个数字交换即可进入下一个状态。回溯的时候，只需要回复小序号的数字的位置的值，以及再一次swap即可。（因为第二个数字只是swap却没有改变过内容）。 一个细节问题，就是加法和乘法是没有顺序的，减法和除法是有顺序的，以及除法要考虑0异常。一共是6次枚举即可。 2.2 测试样例 5 5 5 1 ans is YES 1 1 4 2 ans is :NO 2.3 程序运行情况 样例一： 五、回溯法 回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。 1、回溯法的一般描述 可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi 的定义域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。 解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。 我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，…，xi）满足D中仅涉及到x1，x2，…，xi的所有约束意味着 j（j 回溯算法 Index > Alogri+Data str > 常用算法> 回溯 一、回溯法： 回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。 二、算法框架： 1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。 2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。 运用回溯法解题通常包含以下三个步骤： （1）针对所给问题，定义问题的解空间； （2）确定易于搜索的解空间结构； （3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索； 3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下： procedure try(i:integer); var begin if i>n then 输出结果 else for j:=下界to 上界do begin x[i]:=h[j]; if 可行{满足限界函数和约束条件} then begin 置值；try(i+1); end; end; end; 说明： 回溯算法 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。 基本思想 回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。回溯算法的定义：回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。 回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。解题的一般步骤是： 1.定义一个解空间，它包含问题的解； 2.利用适于搜索的方法组织解空间； 3.利用深度优先法搜索解空间； 4.利用限界函数避免移动到不可能产生解的子空间。 问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。话不多说，我们来看几个具体的例子慢慢理解它： 1 第七章 回溯 7.1 回溯法的思想方法 7.1.1 问题的解空间和状态空间树 一、解空间 问题的解向量为),,,(21n x x x X 。i x 的取值范围为有穷集i S 。把i x 的所有可能取值组合，称为问题的解空间。每一个组合是问题的一个可能解 例：0/1背包问题，}1,0{ S ，当3 n 时，0/1背包问题的解空间是： {(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)} 当输入规模为n 时，有n 2种可能的解。 例：货郎担问题，},,2,1{n S ，当3 n 时， }3,2,1{ S 。货郎担问题的解空间是： {(1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),┅,(3,3,1),(3,3,2),(3,3,3)} 当输入规模为n 时，它有n n 种可能的解。 考虑到约束方程j i x x 。因此，货郎担问题的解空间压缩为： {(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)} 当输入规模为n 时，它有!n 种可能的解。 二、状态空间树：问题解空间的树形式表示 当4 n 时，货郎担问题的状态空间树。 图7.1 n=4时货郎担问题的状态空间树 4 n 时，0/1背包问题的状态空间树 2 图7.2 n=4时背包问题的状态空间树 7.1.2 状态空间树的动态搜索 一、可行解和最优解 可行解：满足约束条件的解，解空间中的一个子集 最优解：使目标函数取极值（极大或极小）的可行解，一个或少数几个 例：货郎担问题，有n n 种可能解。!n 种可行解，只有一个或几个解是最优解。 例：背包问题，有n 2种可能解，有些是可行解，只有一个或几个是最优解。 有些问题，只要可行解，不需要最优解，例如八后问题和图的着色问题 二、状态空间树的动态搜索 l _结点（活结点）：所搜索到的结点不是叶结点，且满足约束条件和目标函数的界， 其儿子结点还未全部搜索完毕， e _结点（扩展结点）：正在搜索其儿子结点的结点，它也是一个l _结点； d _结点（死结点）：不满足约束条件、目标函数、或其儿子结点已全部搜索完毕的结 点、或者叶结点，。以d _结点作为根的子树，可以在搜索过程中删除。 例7.1 有4个顶点的货郎担问题，其费用矩阵如图7.3 所示，求从顶点1出发，最后回到顶点1的最短路线。 ∞ ∞ 1 7 8 ∞ 5 1 7 2 ∞ 6 2 5 3 ∞ 图7.3 4个顶点的货郎担问题的费用矩阵及搜索树 7.1.3 回溯法的一般性描述 题的解向量),,,(110 n x x x X ， i x 的取值范围i S ，},,,{.1.0.i m i i i i a a a S 。 问题的解空间由笛卡尔积110 n S S S A 构成。子集和数的回溯算法
算法设计与分析复习题目及答案
回溯搜索算法
算法分析与程序设计动态规划及回溯法解背包问题
搜索与回溯算法介绍
回溯算法之0-1背包问题
算法设计与分析：回溯法-实验报告
回溯算法实验
回溯法
回溯算法实例一
实验五：01背包问题的回溯算法设计
回溯算法的应用
C语言设计之回溯算法
回溯算法的一些例题
算法设计与分析---回溯实验报告
回溯算法
回溯算法
回溯算法
算法设计与分析学习提纲,第七章回溯
相关主题
文本预览