下载文档原格式
![回溯法和分支限界法解决0-1背包题(精)[精品文档]](https://img.taocdn.com/s1/m/4b32afcc84868762caaed595.png)
0-1背包问题计科1班朱润华 2012040732方法1：回溯法一、回溯法描述：用回溯法解问题时，应明确定义问题的解空间。
问题的解空间至少包含问题的一个（最优）解。
对于0-1背包问题，解空间由长度为n的0-1向量组成。
该解空间包含对变量的所有0-1赋值。
例如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）｝然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。
物品i的重量是wi，其价值为vi，背包的容量为C。
问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,),xi∈{0,1}, ? ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。
二、回溯法步骤思想描述：0-1背包问题是子集选取问题。
0-1 背包问题的解空间可以用子集树表示。
在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。
当右子树中有可能含有最优解时，才进入右子树搜索。
否则，将右子树剪去。
设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。
当cp+r<=bestp时，可剪去右子树。
计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。
例如：对于0-1背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。
这4个物品的单位重量价值分别为[3,2,3,5,4]。
以物品单位重量价值的递减序装入物品。
先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。
由此得一个解为[1,0.2,1,1]，其相应价值为22。
计算机算法设计与分析第4版(王晓东著)课后答
案下载
计算机算法设计与分析第4版内容简介
第1章算法概述
1.1 算法与程序
1.2 算法复杂性分析
1.3 NP完全性理论
算法分析题1
算法实现题1
第2章递归与分治策略
2.1 递归的概念
2.2 分治法的基本思想
2.3 二分搜索技术
2.4 大整数的乘法
2.5 Strassen矩阵乘法
2.6 棋盘覆盖
2.7 合并排序
2.8 快速排序
2.9 线性时间选择
2.10 最接近点对问题
第3章动态规划
第4章贪心算法
第5章回溯法
第6章分支限界法
第7章随机化算法
第8章线性规划与网络流
附录A C++概要
参考文献
计算机算法设计与分析第4版目录
本书是普通高等教育“十一五”__规划教材和国家精品课程教材。
全书以算法设计策略为知识单元，系统介绍计算机算法的设计方法与分析技巧。
主要内容包括：算法概述、递归与分治策略、动态规划、贪心算法、回溯法、分支限界法、__化算法、线性规划与网络流等。
书中既涉及经典与实用算法及实例分析，又包括算法热点领域追踪。
为突出教材的`可读性和可用性，章首增加了学习要点提示，章末配有难易适度的算法分析题和算法实现题;配套出版了《计算机算法设计与分析习题解答(第2版)》;并免费提供电子课件和教学服务。
算法设计与分析实验报告1.骑士游历问题（采用回溯法）：在国际象棋的棋盘（8行×8列）上放置一个马，按照“马走日字”的规则，马要遍历棋盘，即到达棋盘上的每一格，并且每格只到达一次。
若给定起始位置（x0,y0）,编程探索出一条路径，沿着这条路径马能遍历棋盘上的所有单元格。
2. 行列变换问题（采用分支限界法）：给定两个m n方格阵列组成的图形A和图形B，每个方格的颜色为黑色或白色，如下图所示。
行列变换问题的每一步变换可以交换任意2行或2列方格的颜色，或者将某行或某列颠倒。
上述每次变换算作一步。
试设计一个算法，计算最少需要多少步，才能将图形A变换为图形B。
图形A图形B2. 行列变换问题的程序：package .t8;import java.util.LinkedList;import java.util.Scanner;class graph{static int sour, dest;//sour是图形的初始整数，dest是图形的目的整数static int ans[]=new int[1<<16];//静态变量（即全局变量），用于存放图形变换的路径int m=4,n=4,x;int row[]=new int[4];int col[]=new int[4];void setx(int x){this.x=x;}int getx(){return this.x;}void rowx(){//将一个整数划分成四行二进制int y;for(int i=0;i<m;i++){y=1;row[i]=0;for(int j=0;j<n;j++){if((x&1)!=0) //如果x的最低位是1row[i]|=y;y<<=1;x>>=1;}}}}实例：总结实验心得体会：掌握回溯法解决问题的一般步骤。
学会使用回溯法解决实际问题。
掌握分支限界法解决问题的基本思想。
算法设计与分析目录算法设计与分析 (1)第6章回溯与分支限界 (3)6.1回溯法的设计技术 (3)6.2用回溯法求解装载问题 (7)6.3用回溯法求解n皇后问题 (9)6.4用回溯法求解0-1背包问题 (11)6.5用回溯法求解旅行商问题 (13)6.6 分支限界法的设计技术 (15)6.7 用分支限界法求问题的解 (15)本章小结 (15)参考文献 (16)第6章回溯与分支限界内容导读回溯法(Back Tracking Algorithm)与分支限界法（Branch and Bound Algorithm）都是基本的算法设计策略，属于树的搜索技术的范畴。
在使用这两种算法求解问题前，均需要把解空间规划成一棵解空间树，并且在求解过程中使用剪枝策略来提高搜索效率。
回溯法也称试探法，可以把它看成是一个在约束条件下对解空间树进行深度优先搜索的过程，并在搜索过程中剪去那些不满足条件的分支。
当用回溯法搜索到解空间树的某个结点时，如果发现当前路径不满足约束条件或不是历史最优时，则放弃对该结点的子树的搜索，并逐层向其祖先结点返回。
否则，进入该结点的子树，继续进行深度优先搜索。
实质上，这是一个先根遍历解空间树的过程，只是这个棵树不是遍历前预先建立的，而是隐含在遍历过程当中的。
分支限界法则是以最小代价优先的方式在解空间树上进行搜索，它可以找出满足问题约束的一个可行解，或者是从满足约束条件的可行解中找出一个使得目标函数达到极值的最优解。
这里的可行解在搜索树中表现为一条由根到叶子结点的路径，这条路径上权值的和为可行解的值。
其中，最优解就是使可行解的值达到最优的那条路径。
分支限界算法的核心思想就是增加更多的约束条件，剪掉更多的分支，当对当前的树结点进行扩展时，一次性产生其所有儿子结点，并抛弃那些不可能产生可行解或最优解的结点，即剪枝；对于留下的儿子结点，计算一个函数值（限界），然后选取一个最有利的结点继续进行扩展，使得搜索朝着最优解的分支推进。
重复这个过程直到找到最优解或没有可扩展的结点。
6.1回溯法的设计技术6.1.1算法思想回溯算法是一种有组织的系统最优化搜索技术，用它可以求解问题的所有解、一组解或一个解。
例如经典的n皇后问题，它是指在一个n*n的棋盘上放置n个不能够互相攻击的皇后的问题。
按照国际象棋的规则，任意两个皇后之间不能处在同一行、同一列和同一斜线上，否则皇后就可以攻击与之处在同一行、同一列或同一斜线上的棋子。
如图6-1所示为一个4个皇后的合理摆放格局。
那么，如何找到这样一个格局或者找到所有满足要求的解呢？图6-1 4皇后的一个格局可以采用这样一种策略：设每一行的棋格为一层，用x i代表第i层皇后的摆放位置（共有4个值，表示棋格的列），那么，4皇后问题可以描述为一个4元组（x1，x2，x3，x4），这4个元素代表每一层皇后的摆放位置（列），当它们都取得满足题目要求值时，则得到一组解。
图6-2展示了4皇后问题的求解过程：（1）第一层，由于没有其它皇后，4个摆放位置均可摆放，x1的值可取1、2、3、4。
（2）第二层，可针对于x1的每一个取值进行扩展，为第二层皇后选择位置，即给x2赋值。
那么，针对于x1=1，x2有4个位置可以选择。
尝试摆放的过程如下：x2=1的位置，不能摆放，因为两个皇后在同一列上，因此，不对其继续进行扩展，回退到上一层进行重新摆放。
x2=2的位置不能摆放，因为两个皇后在同一对角线上，再次回退到上一层。
尝试在x2=3位置摆放，此时，满足要求，第二层摆放成功，可沿这分支继续进行扩展。
（3）第三层，沿x2=3的位置进行扩展，给x3进行赋值。
由图6-2可知，由这一分支而下的所尝试均不满足要求，最终回退至第二层，它同时也宣告了x2=3摆放的失败，即沿这一分支不可能找到解，则再回溯到第一层，重新摆放皇后、为x2取值，让x2=4，满足要求，沿此分支进行扩展。
（4）第三层，沿x2=4尝试向下扩展，给x3取值，方法与上面描述的相同，尝试成功，则继续向下搜索，不成功则返回上一层，给x3重新取值……，依此，直到第4层摆放完毕，且x1、x2、x3、x4均得到满足要求的值，则找到一组解，如图6-2中的X(2,4,1,3)。
通过上述不断的测试，可以把n皇后问题的所有解全部找出来。
这个求解策略就是回溯法。
图6-2 4皇后问题的回溯过程采用回溯法求解问题，需要将问题的解表达为n元组(X1,…,X i,…X n)，其中X i选自有限集S i，当选出一组值X=(x1,…,x i,…x n)能够使评价函数P(x1,…,x i,…x n) 满足问题的某种约束条件或到达极值，则X为此问题的解或最优解。
这里4皇后问题的评价函数就是对“同一行、同一列和同一斜线”的判断。
若采用枚举搜索技术，则需要枚举出所有可能的n元组，并用P(X1,…,X i,…X n)去一一评价，所需的时空复杂性一般令人难以接受。
回溯法可以看作枚举搜索技术的改进，它通过剪枝技术（参看（2）、（3）、（4）中的回溯），可以避免搜索所有可能的解。
回溯法的基本策略是每次只考虑一个分量，逐次扩大建立n元组，并随时用评价函数P i(X1,…,X i,…X n)去判断正在形成的n元组是否有成功的希望，一旦确定部分元组(X1,…,X i)不能求出解时，则立即停止这种搜索，“剪掉”以当前结点为根的分枝，并逐次向上一个分量回溯，然后向其它分支继续探索。
上述搜索过程通常会形成一棵包含问题解的树，称之为解空间树。
树的每一个结点表示问题求解过程中的一个状态，从树根到其它结点的全部路径构成了问题的解空间，每条自根到叶子的路径代表了解空间中的一个元组，所有满足约束条件的元组构成了问题的解集合，而约束描述了X i彼此相关的情况。
解空间树是在求解的过程中，一个结点一个结点逐步生成的，为了更好的理解和讲解算法，可以将这些结点分为活结点、扩展结点和死结点三类。
在解空间树中那些已经生成了部分子结点，但还没有全部生产完毕的结点叫做活结点；当前正在生成子结点的活结点叫做扩展结点；那些不再进一步扩展或已经将全部子结点生成完毕的结点叫做死结点。
6.1.2算法框架通过4皇后问题生成解的过程，可以了解到回溯算法是从开始结点进行深度优先搜索，并通过剪枝技术提高搜索效率的算法策略，其过程可描述如下：(1)开始结点是一个活结点，也是一个扩展结点；(2)如果能从当前的扩展结点移动到一个新的结点，那么这个新结点将变成一个活结点和可扩展结点，旧的扩展结点仍是一个活结点。
(3)如果不能移动到一个新结点(已经找到一个解或违反约束的情况)，当前的扩展结点就变成了一个死结点，便只能返回到最近被考察的活结点(回溯),这个活结点就变成了新的扩展结点。
(4)当找到了最优解或者没有活结点的时候（回溯尽了所有的活结点），搜索过程结束。
根据这一描述过程，可以得到回溯算法策略的框架：输入：n6.1.3回溯算法的适用条件回溯算法需要满足多米诺性质，才能得到正确的应用。
多米诺性质设向量X i=<x1, x2,…,x i >，X i⊆X，X=< x1, x2,…,x i,…,x n >，将X i输入评价函数P，可以得到X i的一组特征值P(Xi)，取X i+1=<x1, x2,…,x i, x i+1 >，X i+1⊆X，则P(Xi+1)真蕴涵P(Xi)，即P(X i+1)→P(X i) i∈(0,n)其中，n代表解向量的维数。
【例6-1】求满足下列不等式的所有整数解：5x1+4x2-x3≤10 1≤x i≤3 i=1, 2, 3解：令X i=<x1, x2,…,x i>，P(X i)为对Xi的评估，判断其Xi是否满足不等式，即P(Xi) ≤10。
依据题目可知，本例中向量为一个三元组< x1, x2, x3>，其搜索过程如图6-3所示。
x1x2x3图6-3 例6-1的解空间树注意图6-3的虚线部分，当x1=1、x2=2时，P(x1,x2)= 5x1+4x2=5*1+4*2=13>10，不满足约束条件，x2=2这条分支将被剪去，然而，当x1=1、x2=2、x3=3时，P(x1,x2,x3)= 5x1+4x2- x3=5*1+4*2 - 3=10，满足约束条件，即<1, 2, 3>是不等式的解，显然，此例中P(X3)不真蕴涵P(X2)，违反了多米诺性质，从而丢解了。
如果令x’3=4-x3，将原不等式变换为：x1+4x2+x’3≤10 1≤x i, x’3≤3 i=1, 2则该不等式满足多米诺性质，可以使用回溯法，对所得到的解x1、x2、x’3转换成原不等式的解x1、x2、x3即可。
6.2回溯算法的经典例题6.2.1装载问题【例6-2】有一批共n个集装箱要装上一艘载重量为c的轮船，其中集装箱i的重量为w i。
找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。
问题分析假设集装箱数量n=5，轮船的载重量c=10，每个集装箱的重量w={7,2,6,5,4}即w1=7，w2=2，w3=6，w4=5，w5=4。
5个物品的装载可以表示为一个五元组X=（x1，x2，x3，x4，x5），每个x代表一个集装箱，其值表示装载情况，由于每个集装箱装载只有两种可能：装和不装，所以，x i (i=1,2,3,4,5，表示集装箱编号)只能从0和1中选择其一，其中，0表示不装，1表示装载。
能否装载当前的集装箱，要看船上已装箱子的重量加上当前箱子的重量是否超过轮船的载重量，这个判断构成了评估函数P。
用回溯法进行求解，可以生成一棵解空间树。
因为有5个集装箱可以选择装载，所以最多判断到第5个箱子时，一轮搜索结束，并能得到问题的部分解，因此，问题的解空间树高为5，如图6-4所示。
解空间树的每一层代表一个集装箱，它有两个分支，左分支代表装载：x i =1，右分支代表不装载：x i =0。
执行的过程为：（1）选择第一个集装箱x1=1，判断是否超过船的载重：w1×x1＝7×1＝7<10，可装载。
（2）选择第二个集装箱x2=1，判断是否超过船的载重：w1×x1+ w2×x2＝7+2×1＝9<10，可装载。
（3）选择第三个集装箱x3=1，判断是否超过船的载重：w1×x1+ w2×x2+ w3×x3＝9+6×1＝15>10，不可装载。
观察图6-4，当不选择第三个集装箱时，第三层最左端下方结点以下的分支被裁掉（图6-4中虚线所示，即不再往下尝试），应当沿此结点的弧线向上回溯到第二层下面的结点，并沿其右分支继续选择，令x3 =0，有w1×x1+ w2×x2+ w3×x3＝9+6×0＝9<10。
