第5章-回溯法-New剖析.ppt

《第5章-回溯法-New剖析.ppt》由会员分享，可在线阅读，更多相关《第5章-回溯法-New剖析.ppt（86页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5章章回溯法回溯法第第5章章回溯法回溯法引入问题引入问题回溯是重要的算法之一回溯是重要的算法之一 要求找到一组解，或要求找到一个满足某些限制的要求找到一组解，或要求找到一个满足某些限制的最优解。最优解。-通过彻底的搜寻方法来解决。通过彻底的搜寻方法来解决。*彻底搜寻的运算量很大，有时大到计算机承受彻底搜寻的运算量很大，有时大到计算机承受不了的程度。不了的程度。*彻底的搜寻，以进行大量的比较、舍弃、运算彻底的搜寻，以进行大量的比较、舍弃、运算时间为代价。因此，用穷举法解某些实际问题是不时间为代价。因此，用穷举法解某些实际问题是不现实的现实的.-运用回溯法可以大大削减实际的搜寻。例如，迷运用回

2、溯法可以大大削减实际的搜寻。例如，迷宫问题，八皇后问题，骑士周游世界问题。宫问题，八皇后问题，骑士周游世界问题。第第5章章回溯法回溯法引入问题引入问题关键：找到回溯的条件。关键：找到回溯的条件。算法思想：算法思想：通过对问题的分析，找出一个解决问题的线通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索往前摸索，若摸索成功，索，然后沿着这个线索往前摸索，若摸索成功，就得到解，若摸索失败，就逐步往回退，换别的就得到解，若摸索失败，就逐步往回退，换别的路途再往前摸索。路途再往前摸索。事实上是广度与深度搜寻结合的搜寻，深度事实上是广度与深度搜寻结合的搜寻，深度搜寻过程中遇到条件不满足，则退回上

3、一层，在搜寻过程中遇到条件不满足，则退回上一层，在每一层上也进行全面的搜寻。每一层上也进行全面的搜寻。第第5章章回溯法回溯法回溯法的基本思想回溯法的基本思想回溯法是带优化的穷举法。回溯法是带优化的穷举法。回溯法的基本思想：在一棵含有问题全部可回溯法的基本思想：在一棵含有问题全部可能解的状态空间树上进行深度优先搜寻，解为叶能解的状态空间树上进行深度优先搜寻，解为叶子结点。搜寻过程中，每到达一个结点时，则推子结点。搜寻过程中，每到达一个结点时，则推断该结点为根的子树是否含有问题的解，假如可断该结点为根的子树是否含有问题的解，假如可以确定该子树中不含有问题的解，则放弃对该子以确定该子树中不含有问题的

4、解，则放弃对该子树的搜寻，退回到上层父结点，接着下一步深度树的搜寻，退回到上层父结点，接着下一步深度优先搜寻过程。优先搜寻过程。在回溯法中，并不是先构造出整棵状态空间在回溯法中，并不是先构造出整棵状态空间树，再进行搜寻，而是在搜寻过程中逐步构造出树，再进行搜寻，而是在搜寻过程中逐步构造出状态空间树，即边搜寻，边构造。状态空间树，即边搜寻，边构造。第第5章章回溯法回溯法回溯法是一个既带有系统性又带有跳动性的搜回溯法是一个既带有系统性又带有跳动性的搜寻算法。寻算法。它在包含问题的全部解的解空间树中，依据深它在包含问题的全部解的解空间树中，依据深度优先的策略，从根结点动身搜寻解空间树。度优先的策略，

5、从根结点动身搜寻解空间树。算法搜寻至解空间树的任一结点时，总是先推算法搜寻至解空间树的任一结点时，总是先推断该结点是否确定不包含问题的解。断该结点是否确定不包含问题的解。（1）假如确定不包含，则跳过对以该结点为根）假如确定不包含，则跳过对以该结点为根的子树的系统搜寻，逐层向其祖先结点回溯。的子树的系统搜寻，逐层向其祖先结点回溯。（2）否则，进入该子树，接着按深度优先的策）否则，进入该子树，接着按深度优先的策略进行搜寻。略进行搜寻。回溯法在用来求问题的全部解时，要回溯到根，回溯法在用来求问题的全部解时，要回溯到根，且根结点的全部子树都已被搜寻遍才结束。且根结点的全部子树都已被搜寻遍才结束。回溯法

6、在用来求问题的任一解时，只要搜寻到回溯法在用来求问题的任一解时，只要搜寻到问题的一个解就可以结束。问题的一个解就可以结束。第第5章章回溯法回溯法ABCDEFGHIJKLMNO11100011110000例如，对于有n种可选物品的0-1背包问题，其解空间由长度为n的0-1向量组成。以3件物品实例第第5章章回溯法回溯法n扩展结点：一个正在产生儿子的结点称扩展结点：一个正在产生儿子的结点称为扩展结点为扩展结点n活结点：一个自身已生成但其儿子还没活结点：一个自身已生成但其儿子还没有全部生成的结点称做活结点有全部生成的结点称做活结点n死结点：一个全部儿子已经产生的结点死结点：一个全部儿子已经产生的结点称

7、做死结点称做死结点第第5章章回溯法回溯法从起先结点（根结点）动身，以深度优先的方式搜从起先结点（根结点）动身，以深度优先的方式搜寻整个解空间。这个起先结点寻整个解空间。这个起先结点-活结点，同时也成为活结点，同时也成为当前的扩展结点。当前的扩展结点。在当前的扩展结点处，搜寻向纵深方向移至一个新在当前的扩展结点处，搜寻向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。前扩展结点。假如在当前的扩展结点处不能再向纵深方向移动，假如在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动则当前扩展结点

8、就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜寻，回溯法即以这种工作方式递归地在解空间中搜寻，直至找到所要求的解或解空间中已没有活结点时为止。直至找到所要求的解或解空间中已没有活结点时为止。第第5章章回溯法回溯法n深度优先的问题状态生成法：假如对一个扩展深度优先的问题状态生成法：假如对一个扩展结点结点R，一旦产生了它的一个儿子，一旦产生了它的一个儿子C，就把，就把C当当做新的扩展结点。在完成对子树做新的扩展结点。在完成对子树C（以（以C为根的为

9、根的子树）的穷尽搜寻之后，将子树）的穷尽搜寻之后，将R重新变成扩展结重新变成扩展结点，接着生成点，接着生成R的下一个儿子（假如存在）的下一个儿子（假如存在）n宽度优先的问题状态生成法：在一个扩展结点宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它始终是扩展结点变成死结点之前，它始终是扩展结点n回溯法：为了避开生成那些不行能产生最佳解回溯法：为了避开生成那些不行能产生最佳解的问题状态，要不断地利用限界函数的问题状态，要不断地利用限界函数(boundingfunction)来剔除那些事实上不行来剔除那些事实上不行能产生所需解的活结点，以削减问题的计算量。能产生所需解的活结点，以削减问题的

10、计算量。具有限界函数的深度优先生成法称为回溯法。具有限界函数的深度优先生成法称为回溯法。第第5章章回溯法回溯法示例示例1 0-11 0-1背包问题背包问题n=3,C=30,w=16,15,15,v=45,25,25ACr=C=30，V=0LNMBw1=16，v1=45Cr=14，V=45G Cr=30，V=0CCrw2不可行解ECr45x=(0,1,1)Hw2=15，v2=25Cr=15，V=25J2550不是最优解示例示例1 0-11 0-1背包问题背包问题起先时，起先时，Cr=C=30，V=0，A为唯一活结点，也是当为唯一活结点，也是当前扩展结点前扩展结点扩展扩展A，先到达，先到达B结点结

11、点Cr=Cr-w1=14，V=V+v1=45；此时；此时A、B为活结为活结点，点，B成为当前扩展结点；扩展成为当前扩展结点；扩展B，先到达，先到达CCrw2，C导致一个不行行解，回溯到导致一个不行行解，回溯到B再扩展再扩展B到达到达DD可行，此时可行，此时A、B、D是活结点，是活结点，D成为新的扩展结成为新的扩展结点；扩展点；扩展D，先到达，先到达ECr45，皆得到一个可行解，皆得到一个可行解x=(0,1,1)，V=50I不行扩展，成为死结点，返回到不行扩展，成为死结点，返回到H再扩展再扩展H到达到达JJ是叶结点，且是叶结点，且2550，不是最优解，不是最优解J不行扩展，成为死结点，返回到不行

12、扩展，成为死结点，返回到HH没有可扩展结点，成为死结点，返回到没有可扩展结点，成为死结点，返回到G再扩展再扩展G到达到达LCr=30，V=0，活结点为，活结点为A、G、L，L为当前扩展结点为当前扩展结点扩展扩展L，先到达，先到达M，M是叶结点，且是叶结点，且2550，不是最优解，又，不是最优解，又M不行扩展，返回不行扩展，返回到到L再扩展再扩展L到达到达N，N是叶结点，且是叶结点，且0n)output(x);/当搜寻到叶结点，输出可行解当搜寻到叶结点，输出可行解 else for(int i=f(n,t);in)output(x);elsefor(inti=0;in)output(x);els

13、efor(inti=t;i=n;i+)swap(xt,xi);if(legal(t)backtrack(t+1);swap(xt,xi);第第5章章回溯法回溯法八皇后问题是一个古老而著名的问题。该问题是十九是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯世纪著名的数学家高斯1850年提出。年提出。在在8X8格的国际象棋上摆放八个皇后，使格的国际象棋上摆放八个皇后，使其不能相互攻击，即随意两个皇后都不能其不能相互攻击，即随意两个皇后都不能处于同一行、同一列或同一斜线上，问有处于同一行、同一列或同一斜线上，问有多少种摆法。多少种摆法。高斯认为有高斯认为有76种方案。种方案。1854年在柏林

14、的年在柏林的象棋杂志上不同的作者发表了象棋杂志上不同的作者发表了40种不同的种不同的解，后来有人用图论的方法解出解，后来有人用图论的方法解出92种结果。种结果。第第5章章回溯法回溯法N N皇后问题皇后问题问题描述问题描述在在*的棋盘上，放置个皇后，要求每的棋盘上，放置个皇后，要求每一横行，每一列，每一对角线上均只能放置一个皇后，一横行，每一列，每一对角线上均只能放置一个皇后，求可能的方案及方案数。求可能的方案及方案数。问题的状态即棋盘的布局状态，状态空间树的根为空棋问题的状态即棋盘的布局状态，状态空间树的根为空棋盘，每个布局的下一步可能布局为该布局结点的子结盘，每个布局的下一步可能布局为该布局

15、结点的子结点；点；随意两个王后不放在同一行或同一列或同一斜线。因此随意两个王后不放在同一行或同一列或同一斜线。因此为了简化状态空间树，接受逐行布局的方式，即每个为了简化状态空间树，接受逐行布局的方式，即每个布局有布局有n个子结点；个子结点；第第5章章回溯法回溯法N皇后问题皇后问题一、回溯过程分析：一、回溯过程分析：1、从空棋盘起，逐行放置棋子。、从空棋盘起，逐行放置棋子。2、每在一个布局中放下一个棋子，即推演、每在一个布局中放下一个棋子，即推演到一个新的布局。到一个新的布局。3、假如当前行上没有可合法放置棋子的位、假如当前行上没有可合法放置棋子的位置，则回溯到上一行，重新布放上一行的置，则回溯

16、到上一行，重新布放上一行的棋子。棋子。第第5章章回溯法回溯法N皇后问题皇后问题第第5章章回溯法回溯法N皇后问题皇后问题二、存储结构二、存储结构(1)二维数组二维数组ANN存储皇后位置存储皇后位置若第若第i行第行第j列放列放有皇后有皇后,则则Aij为非为非0值值,否则否则值为值为0。(2)一维数组一维数组Mk、Lk、Rk分别表示竖列、分别表示竖列、左斜线、右斜线是否放有棋子左斜线、右斜线是否放有棋子,有则值为有则值为1,否否则值为则值为0。第第5章章回溯法回溯法ji01230123M0M1M2M3第第5章章回溯法回溯法ji01230123k值和皇后位置坐值和皇后位置坐标标i，j的关联？的关联？k

17、=i+jk=02*(N-1)第第5章章回溯法回溯法ji01230123k值和皇后位置坐值和皇后位置坐标标i，j的关联？的关联？k=i-jk会出现负值会出现负值k=i-j+Nk=12*(N+1)右右第第5章章回溯法回溯法ji01230L0,R4L1,R3L2,R2L3,R11L1,R5L2,R4L3,R3L4,R22L2,R6L3,R5L4,R4L5,R33L3,R7L4,R6L5,R5L6,R4M0M1M2M3Mk（k=j）Lk（k=i+j）Rk（k=i-j+N）第第5章章回溯法回溯法三、算法描述三、算法描述初始化初始化for(某一行的每个位置某一行的每个位置)if(平安平安)放皇后放皇后;i

18、f(已到最终一行已到最终一行)输出输出;else摸索下一行摸索下一行;去皇后去皇后;N皇后问题皇后问题平安算法：平安算法：!Mj&!Ri-j+N&!Li+j;放皇后：放皇后：Aij=Mj=Ri-j+N=Li+j=1;去皇后：去皇后：Aij=Mj=Ri-j+N=Li+j=0;第第5章章回溯法回溯法#defineN4/*N为皇后个数为皇后个数*/intcount=0;intMN=0,L2*N=0,R2*N=0;intANN=0;/*皇后位置皇后位置*/voidprint(intANN);intmytry(inti,intMN,intL2*N,intR2*N,intANN);voidmain()in

19、tn=mytry(0,M,L,R,A);/代表从代表从0行起先摸索行起先摸索cout“ncount=”n;/n可行解数目可行解数目/*摸索每一行皇后的位置摸索每一行皇后的位置*/intmytry(inti,intMN,intL2*N,intR2*N,intANN)for(intj=0;jN;j+)/放置在放置在i行行j列列if(!Mj&!Li-j+N&!Ri+j)/平安检查平安检查Aij=i+1;/放皇后放皇后Mj=Li-j+N=Ri+j=1;if(i=N-1)print(A);coutendl;count+;elsemytry(i+1,M,L,R,A);/摸索下一行摸索下一行Aij=0;/去

20、皇后去皇后Mj=Li-j+N=Ri+j=0;returncount;第第5章章回溯法回溯法voidprint(intANN)/*输出输出*/inti,j;for(i=0;iN;i+)for(j=0;jN;j+)coutAij;coutendl;第第5章章回溯法回溯法图的图的m着色问题着色问题给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少须要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。把

21、n个板块抽象为一个图的n个顶点第第5章章回溯法回溯法图的着色问题是由地图的着色问题引申而来的，用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。一、产生背景一、产生背景第第5章章回溯法回溯法二、问题描述二、问题描述给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。假如有则称这个图是m可着色，否则称这个图不是m可着色。若一个图最少须要k种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数k为该图的色数。第第5章章回溯法回溯法三、算法设计三、算法设计输入：颜色种类m输出：假如这个图不

22、是m可着色，给出否定回答；假如这个图是m可着色的，找出全部不同的着色法。思考？思考？如何将给定的如何将给定的无向图存储在无向图存储在计算机中？计算机中？第第5章章回溯法回溯法1423可以用以下邻接矩阵来表示 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1邻接矩阵中通常用二维数组来存放边之间的关系，用一维邻接矩阵中通常用二维数组来存放边之间的关系，用一维数组来存放顶点的信息。所以在接下来的求解问题中我们数组来存放顶点的信息。所以在接下来的求解问题中我们将用到二维数组将用到二维数组a来存放两边是否相邻，来存放两边是否相邻，用一维数组用一维数组x来

23、来存放每个顶点的颜色存放每个顶点的颜色;xi=j表示第表示第i个节点图第个节点图第j中颜色中颜色。5第第5章章回溯法回溯法我们可以把问题简化为3个点来分析，现给定如下图，怎样求解呢？123该图的色数是多少？怎样用解空间树来表示呢？第第5章章回溯法回溯法由图可知，对于每一个顶点可选的颜色可以有3种不同的选择，所以每一个节点有3个儿子节点，有4层。第第5章章回溯法回溯法推断条件是什么？推断条件是什么？新加入的节点t取某一种颜色i时，依次和上层的每一个节点j(jt)比较。假如atj=1并且xt=xj=i,那么它是不行着色的。int OK(int t)int j;for(j=1;jt;j+)if(at

24、j=1&xj=xt)return 0;return 1;第第5章章回溯法回溯法模拟演示t=1t=2t=3t=4第第5章章回溯法回溯法void Backtrace(int t，int m)当前节点颜色的种类当搜寻的当前节点tN），即可输出一种方案for(i=1;iN)sum+;printf(第%d种方案：n,sum);for(i=1;i=N;i+)printf(%d,xi);第第5章章回溯法回溯法四、程序代码#include#include#define N 3/图中节点的个数图中节点的个数int aN+1N+1=0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,;/邻接矩阵邻接矩

25、阵int xN+1;/记录颜色记录颜色int sum=0;/保存可以着色的方案数保存可以着色的方案数int OK(int t,int i)/推断函数推断函数 int j;for(j=1;jN)/算法搜寻至叶子节点算法搜寻至叶子节点 sum+;printf(第第%d种方案：种方案：n,sum);for(i=1;i=N;i+)printf(%d,xi);printf(n);else for(i=1;i=m;i+)if(OK(t,i)xt=i;Backtrace(t+1,m);第第5章章回溯法回溯法int main()int m;int i;printf(请输入颜色种类：请输入颜色种类：n);sca

26、nf(%d,&m);for(i=1;in)/*n:顶点数*/sum+;输出xi；elsefor(inti=1;i=m;i+)xt=i;/*设置颜色*/if(ok(t)backtrack(t+1);intColor:ok(intk)/*检查颜色可用性*/for(intj=1;j=n;j+)if(akj=1)&(xj=xk)/*k,j间有边且颜色相同*/return0;/*所用颜色非法*/return1;Akj12345101110210111311010411101501010 xt1234512341第第5章章回溯法回溯法图的图的m着色问题着色问题复杂度分析复杂度分析图m可着色问题的解空间树中

27、内结点个数是对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。因此，回溯法总的时间耗费是第第5章章回溯法回溯法考场支配图的着色原理之运用考场支配图的着色原理之运用【问题描述】【问题描述】设学校共有设学校共有n门课，须要进行期末考试，因为不少学生不门课，须要进行期末考试，因为不少学生不止选修一门课程，所以不能把同一个学生选修的两门课止选修一门课程，所以不能把同一个学生选修的两门课程支配在同一场次进行考试，问学期的期末考试最少需程支配在同一场次进行考试，问学期的期末考试最少需多少场次考完？多少场次考完？【问题分析】【问题分析】本问题可转换成是对一

28、平面图的顶点着色问题判定，接本问题可转换成是对一平面图的顶点着色问题判定，接受回溯法求解。将所选的每门课程变成一个结点，若一受回溯法求解。将所选的每门课程变成一个结点，若一个同学选了个同学选了m(1mn)门课程时，则这门课程时，则这m门课程所对应门课程所对应的结点相互用一条边连接起来。则相邻边的顶点不能着的结点相互用一条边连接起来。则相邻边的顶点不能着同一种颜色，既不能支配在同一场次考试。但本题又不同一种颜色，既不能支配在同一场次考试。但本题又不同于同于m-着色问题，而是要求最少场次考完，故本问题是着色问题，而是要求最少场次考完，故本问题是求求min-着色问题，既全部的顶点最少可用多少种颜色来

29、着色问题，既全部的顶点最少可用多少种颜色来着色，则本问题可解。着色，则本问题可解。第第5章章回溯法回溯法【数据结构】【数据结构】图的邻接矩阵图的邻接矩阵testMAXMAX来表示一个图来表示一个图G，其，其中若（中若（i，j）是）是G的一条边，则的一条边，则testij=testji=1，否则，否则testij=testji=0，因为本问题只关切一，因为本问题只关切一条边是否存在，所以用邻接矩阵。颜色总数用总课条边是否存在，所以用邻接矩阵。颜色总数用总课程数目程数目N表示。生成解则用数组表示。生成解则用数组valueMAX来记录，来记录，其中其中valuei是结点是结点i的颜色，即课程的颜色，

30、即课程i可支配在第可支配在第valuei场考试，场考试，resultMAX用来记录最优解。程序用来记录最优解。程序中中N表示课程总数，表示课程总数，minSum表示最少的考试场次。表示最少的考试场次。第第5章章回溯法回溯法【主要算法主要算法】testArrange()/找一个图的考试方案if(k=N)if(jminSum)/记录最少的考试场数minSum=j;for(t=1;t=N;t+)resultt=valuet;/记录最优解elsetestArrange(k+1);/递归调用第第5章章回溯法回溯法回溯法求解回溯法求解0-1背包问题背包问题解空间：子集树解空间：子集树可行性约束函数：可行性

31、约束函数：第第5章章回溯法回溯法解题的基本指导思想解题的基本指导思想:按贪心法的思路，优先装入价值按贪心法的思路，优先装入价值/重量比大重量比大的物品。当剩余容量装不下最终考虑的物的物品。当剩余容量装不下最终考虑的物品时，再用回溯法修改从前的装入方案，品时，再用回溯法修改从前的装入方案，直到得到全局最优解为止。直到得到全局最优解为止。第第5章章回溯法回溯法/*数据结构数据结构*/#defineN5/物品数目物品数目intv=6,3,6,5,4,w=2,2,4,6,5;intC=10;/背包涵量背包涵量intcp;/当前价值当前价值intbestp=0;/最优价值最优价值intxN;/当前解当前

32、解intbestxN;/*当前最优解当前最优解*/第第5章章回溯法回溯法voidmain()/按物品价值重量比排降序按物品价值重量比排降序/输出物品初始价值、重量（略）输出物品初始价值、重量（略）knap(0);cout最优价值最优价值:bestpt;cout此时放入背包物品此时放入背包物品:;for(j=0;jN;j+)if(bestxj=1)coutj+1;cout=N)if(bestpcp)bestp=cp;/保存最优解保存最优解for(intj=0;jN;j+)bestxj=xj;putout();elseif(wt=C)/搜寻左枝搜寻左枝xt=1;cp+=vt;C-=wt;knap(

33、t+1);/接着向下深度搜寻接着向下深度搜寻xt=0;C+=wt;cp-=vt;/回退回退xt=0;/搜寻右枝搜寻右枝knap(t+1);第第5章章回溯法回溯法/*输出输出*/voidputout()cout物品放入背包状态为：物品放入背包状态为：;for(inti=0;iN;i+)coutsetw(5)xi;cout获得的价值获得的价值=cp;coutendl;第第5章章回溯法回溯法实际搜寻解空间树策略实际搜寻解空间树策略:只要其左儿子结点是一个可行结点，搜寻就只要其左儿子结点是一个可行结点，搜寻就进入其左子树。进入其左子树。约束函数约束函数当右子树有可能包含最优解时才进入右子树当右子树有可

34、能包含最优解时才进入右子树搜寻，否则将右子树剪去。搜寻，否则将右子树剪去。限界函数限界函数前面算法完全搜寻解空间树前面算法完全搜寻解空间树:即用约束条件确定是否搜寻其左子树；即用约束条件确定是否搜寻其左子树；对右子树没有任何推断，确定进入右子树搜对右子树没有任何推断，确定进入右子树搜寻。寻。-耗时耗时 第第5章章回溯法回溯法剪枝方法：剪枝方法：r:当前当前剩余物品价值总和剩余物品价值总和；cv:当前获得价值；当前获得价值；bestp:当前最优价值。当前最优价值。当当cv+r=bestp时，可剪去右子树。时，可剪去右子树。计算右子树上界方法计算右子树上界方法:将将剩余物品剩余物品依其依其单位重量

35、价值排序单位重量价值排序，然后依，然后依次装入物品，直至装不下时，再装入该物品次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是右的一部分而装满背包。由此得到的价值是右子树中解的子树中解的上界上界。第第5章章回溯法回溯法intBound(inti)/计算当前结点处上界计算当前结点处上界intleft=C-cw;/剩余容量剩余容量intb=cv;/cv当前价值当前价值while(wi=left&i=N)b+=vi;left-=wi;i+;/*装满背包装满背包*/if(iN)/*到叶结点到叶结点*/for(j=1;j=N;j+)bestxj=xj;bestv=cv;else

36、if(cw+wibestv)/*搜寻右子树搜寻右子树*/xi=0;Backtrack(i+1);第第5章章回溯法回溯法voidputout()cout放入背包的物品是放入背包的物品是:;cw=0;for(inti=1;i=N;i+)if(bestxi=1)coutit;cw+=wi;coutendl放入背包物品总重为：放入背包物品总重为：cwt;cout最大价值和为最大价值和为:bestvendl;第第5章章回溯法回溯法0-1背包课件演示背包课件演示.cppw=,2,2,4,6,5,N=5,C=10,v=,6,3,6,5,40Cr=C=10，V=01w1=2,v1=6Cr=8,cv=652w2

37、=2,v2=3Cr=6,cv=9Bound=15bestpBound=1631:bestp=1510Bound=124w3=4,v3=6Cr=2,cv=156Cr=2,cv=157Bound=15Cr=2,cv=158Bound=14n)/到达叶结点到达叶结点更新最优解更新最优解bestx,bestw;return;r-=wi;if(cw+wibestw)xi=0;/搜寻右子树搜寻右子树backtrack(i+1);r+=wi;第第5章章回溯法回溯法批处理作业调度批处理作业调度给定给定n个作业的集合个作业的集合J1,J2,Jn。每个作。每个作业必需先由机器业必需先由机器1处理，然后由机器处理，

38、然后由机器2处理。处理。机器机器j处理作业处理作业Ji须要时间为须要时间为tij（i=1,2n;j=1,2）。对于一个确定的作业）。对于一个确定的作业调度，设调度，设Fij是作业是作业i在机器在机器j上完成处理的时上完成处理的时间。全部作业在机器间。全部作业在机器2上完成处理的时间和称上完成处理的时间和称为该作业调度的完成时间和。为该作业调度的完成时间和。批处理作业调度问题要求对于给定的批处理作业调度问题要求对于给定的n个作业，个作业，制定最佳作业调度方案，使其完成时间和达制定最佳作业调度方案，使其完成时间和达到最小。到最小。第第5章章回溯法回溯法批处理作业调度批处理作业调度tij机器机器1

39、1机器机器2 2作业作业1 12 21 1作业作业2 23 31 1作业作业3 32 23 3这这3个作业的个作业的6种可能的调度方案是种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间；它们所相应的完成时间和分别是和分别是19，18，20，21，19，19。易见，最佳调。易见，最佳调度方案是度方案是1,3,2，其完成时间和为，其完成时间和为18。第第5章章回溯法回溯法批处理作业调度批处理作业调度0 2 5 70 2 3 5 6 7 10调度方案是1,2,3，相应的完成时间和是19=3+6+10调度方案是1,3,2，相应的完成时间和是

40、18=3+7+80 2 4 70 2 3 4 7 8第第5章章回溯法回溯法解空间：排列树voidFlowshop:Backtrack(inti)if(in)for(intj=1;j=n;j+)bestxj=xj;bestf=f;elsefor(intj=i;jf1)?f2i-1:f1)+Mxj2;f+=f2i;if(fbestf)Swap(xi,xj);Backtrack(i+1);Swap(xi,xj);f1-=Mxj1;f-=f2i;int *M,/各作业所需的处理时间各作业所需的处理时间 *x,/当前作业调度当前作业调度 *bestx,/当前最优作业调度当前最优作业调度 *f2,/机器机

41、器2完成处理时间完成处理时间 f1,/机器机器1完成处理时间完成处理时间 f,/完成时间和完成时间和 bestf,/当前最优值当前最优值 n;/作业数作业数 第第5章章回溯法回溯法连续邮资问题连续邮资问题【问题描述】假设国家发行了【问题描述】假设国家发行了N种不同面值的邮票，种不同面值的邮票，并且规定每张信封上最多只允许贴并且规定每张信封上最多只允许贴M张邮票。连续邮张邮票。连续邮资问题要求对于给定的资问题要求对于给定的N和和M的值，给出邮票面值的最的值，给出邮票面值的最佳设计，在佳设计，在1张信封上可贴出从邮资张信封上可贴出从邮资1起先，增量为起先，增量为1的最大连续邮资区间。的最大连续邮资

42、区间。例如，当例如，当N=5和和M=4时，面值为时，面值为(1,3,11,15,32)的的5种种邮票可以贴出邮资的最大连续邮资区间是邮票可以贴出邮资的最大连续邮资区间是1到到70。第第5章章回溯法回溯法x1：N：表示：表示N种不同的邮票面值，并约定它们从种不同的邮票面值，并约定它们从小到大排列。小到大排列。x1=1是惟一的选择。是惟一的选择。（1）在未确定剩余其它）在未确定剩余其它N1种邮票面值的状况下，种邮票面值的状况下，只用只用x1一种邮票面值，所能得到的最大连续邮资一种邮票面值，所能得到的最大连续邮资区间是区间是1：M。（2）确定）确定x2的取值范围的取值范围x2的值最小可以取到的值最小

43、可以取到2，最大可以取到，最大可以取到M+1。（3）一般的状况下，若已选定）一般的状况下，若已选定x1到到xi-1，最大，最大连续邮资区间是连续邮资区间是1：r时，接下来时，接下来xi的可取值范围的可取值范围是是xi-1+1：r+1。第第5章章回溯法回溯法连续邮资问题连续邮资问题若若x1到到xi-1，最大连续邮资区间是，最大连续邮资区间是1：r时，时，接下来接下来xi的可取值范围是的可取值范围是xi-1+1：r+1。例如，当例如，当N=3和和M=2时时可选值可选值 最大连续邮资最大连续邮资X111，2X221，431，4X331，2，31，641，2，41，61，3，41，851，2，51，7

44、1，3，51，6第第5章章回溯法回溯法【解决方案及基本思想解决方案及基本思想】（1）基本思路：）基本思路：搜寻全部可行解，当搜寻全部可行解，当i=N时，当前结点时，当前结点Z是解是解空间中的内部结点。在该结点处空间中的内部结点。在该结点处x1:i-1能贴出最大能贴出最大连续区间为连续区间为r。因此，在结点。因此，在结点Z处，处，x的可能取值范围的可能取值范围是是xi-1+1：r+1，从而，结点，从而，结点Z有有r-xi-1+1个儿个儿子结点。算法对当前结点子结点。算法对当前结点Z的每一个儿子结点以深度的每一个儿子结点以深度优先遍历的方式递归的对应子树进行搜寻，从而找出优先遍历的方式递归的对应子

45、树进行搜寻，从而找出最大连续邮资区间的方案。最大连续邮资区间的方案。（2）解向量：）解向量：用用n元组元组x1:n表示表示N种不同的邮票面值，并约种不同的邮票面值，并约定它们从小到大排列。定它们从小到大排列。x1=1是唯一的选择。（是唯一的选择。（x表表第第i张邮票的面值）张邮票的面值）第第5章章回溯法回溯法【解决方案及基本思想解决方案及基本思想】（3）可行性约束函数：）可行性约束函数：已选定已选定x1:i-1，最大连续邮资区间是，最大连续邮资区间是1r,下来下来x的可取值范围是的可取值范围是xi-1+1r+1。（。（r表表x1:i-1所能达所能达到的连续区间的上界）到的连续区间的上界）第第5

46、章章回溯法回溯法连续邮资问题连续邮资问题如何确定如何确定r的值？的值？(1)计算计算X1:i的最大连续邮资区间在本算法中被频繁的最大连续邮资区间在本算法中被频繁运用到，因此势必要找到一个高效的方法。运用到，因此势必要找到一个高效的方法。(2)干脆递归的求解困难度太高，尝试计算用不超过干脆递归的求解困难度太高，尝试计算用不超过M张面值为张面值为x1:i的邮票贴出邮资的邮票贴出邮资k所需的最少邮票数所需的最少邮票数yk。通过。通过yk可以很快推出可以很快推出r的值。的值。(3)yk可以通过递推在可以通过递推在O(n)时间内解决：时间内解决：具体代码参见附件回溯法具体代码参见附件回溯法“连续邮资问题

47、连续邮资问题”第第5章章回溯法回溯法回溯和递归的区分回溯和递归的区分递归法好比是一个军队要通过一个迷宫，到了递归法好比是一个军队要通过一个迷宫，到了第一个分岔口，有第一个分岔口，有3条路，将军吩咐条路，将军吩咐3个小队分个小队分别去探哪条路能到出口，别去探哪条路能到出口，3个小队沿着个小队沿着3条路分条路分别前进，各自到达了路上的下一个分岔口，于别前进，各自到达了路上的下一个分岔口，于是小队长再分派人手各自去探路是小队长再分派人手各自去探路只要人手只要人手足够（比照而言，就是计算机的堆栈足够），足够（比照而言，就是计算机的堆栈足够），最终必将有人找到出口，从这人起先只要层层最终必将有人找到出口

48、，从这人起先只要层层上报直属领导，最终，将军将得到一条通路。上报直属领导，最终，将军将得到一条通路。回溯法则是一个人走迷宫的思维模拟，只寄希回溯法则是一个人走迷宫的思维模拟，只寄希望于自己的记忆力。回溯事实上是递归的绽开。望于自己的记忆力。回溯事实上是递归的绽开。第第5章章回溯法回溯法练习练习问题描述问题描述原始部落居民为了争夺资源常常发生原始部落居民为了争夺资源常常发生冲突，几乎每个居民都有仇敌。部落酋长为了组冲突，几乎每个居民都有仇敌。部落酋长为了组织一支队伍，希望从部落中挑出最多的居民入伍，织一支队伍，希望从部落中挑出最多的居民入伍，并保证队伍中任何两个人都不是仇敌。并保证队伍中任何两个人都不是仇敌。任务任务给定居民间仇敌关系，输出组成队伍的最给定居民间仇敌关系，输出组成队伍的最佳方案。佳方案。输入输入居民人数，居民间仇敌个数，仇敌关系居民人数，居民间仇敌个数，仇敌关系输出输出部队人数，那些居民入选部队人数，那些居民入选第第5章章回溯法回溯法居民 1234567111211111311141115111161117第第5章章回溯法回溯法TheEnd