【教学课件】第5章回溯法.ppt

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

1、第5章 回溯法学习要点学习要点p5.1 回溯法概述回溯法概述p5.2 回溯法的典型示例回溯法的典型示例p5.3 回溯法的效率分析回溯法的效率分析p本章小结本章小结算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 2 5.1 回溯法概述5.1.1 问题的解空间问题的解空间问题的解空间问题的解空间两类典型的解空间两类典型的解空间5.1.2 回溯法的基本思想回溯法的基本思想回溯法的基本思想回溯法的基本思想算法的框架算法的框架例：排列与组合例：排列与组合小结小结算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 3 问题的解空间|复杂问题的求解复杂问题

2、的求解复杂问题常常有很多的可能解，这些可能解构成了问复杂问题常常有很多的可能解，这些可能解构成了问题的题的解空间解空间。解空间也就是进行穷举的搜索空间，所以，解空间中解空间也就是进行穷举的搜索空间，所以，解空间中应该包括所有的可能解。应该包括所有的可能解。|问题解的求解方法问题解的求解方法搜索问题的解空间，获得问题的解，依据搜索策略的搜索问题的解空间，获得问题的解，依据搜索策略的不同，可以分为：不同，可以分为：回溯法回溯法分支限界法分支限界法算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 4|问题的解向量：问题的解向量：问题的解可以表示成一个问题的解可以表示成一个n

3、元式元式(x1,x2,xn)的形式。的形式。|问题的解空间问题的解空间E=(x1,x2,xn)|xi si,si为有限集为有限集 称为问题的称为问题的解空间解空间|约束条件约束条件隐约束隐约束:元组的分量间满足函数关系元组的分量间满足函数关系 f(x1,.xn)显约束显约束:每个每个xi的范围都给定的约束。的范围都给定的约束。问题的解空间算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 5 问题的解空间|问题的解空间问题的解空间由笛卡儿积由笛卡儿积AS1S2Sn构成，且构成，且第第1层的根结点有层的根结点有|S1|棵子树，棵子树，第第2层共有层共有|S1|个结点，个结

4、点，第第3层共有层共有|S1|S2|个结点，个结点，依此类推，依此类推，第第n1层共有层共有|S1|S2|Sn|个结点，他们都是叶子个结点，他们都是叶子结点，代表问题的所有可能解。结点，代表问题的所有可能解。|显式图和隐式图显式图和隐式图算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 6 两类典型的解空间|两类典型的解空间两类典型的解空间子集树子集树排列树排列树算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 7 子集树|例例1：0-1背包问题背包问题(0-1 Knapsack Problem)|分析：分析：可能解由一个等长向量（可能解由一

5、个等长向量（x1,x2,xn）组成，）组成，其中其中xi1(1in)表示物品表示物品i装入背包装入背包xi0(1in)表示物品表示物品i没有装入背包没有装入背包如：如：当当n3时，其解空间是：时，其解空间是：(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 8 子集树可以用一棵满二叉树表示解空间树可以用一棵满二叉树表示解空间树|例如：例如：W(20,15,15)，V (40,25,25)，C30|问题的求解过程：问题的求解过程：相当于在解空间树

6、中搜索满足条件的叶结点。相当于在解空间树中搜索满足条件的叶结点。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 9 子集树|例例2：集合集合Aa1,a2,an，求，求A的所有子集合（如的所有子集合（如n3）。）。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 10 子集树|子集树（子集树（Subset Trees）当所给问题是从当所给问题是从n个元素的集合中找出满足某种性质个元素的集合中找出满足某种性质的子集时，相应的解空间树称为的子集时，相应的解空间树称为子集树子集树。在子集树中，一般地：在子集树中，一般地：|S1|S2|Sn|2，即每

7、即每个结点有个结点有2棵的子树。棵的子树。解空间为：解空间为：（0，0，0，0）（0，0，0，1）（1，1，1，1）算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 11 子集树|所以，所以，解空间有解空间有2n个元素。个元素。若表示为树形结构就是一棵有若表示为树形结构就是一棵有2n个叶结点的二叉树，个叶结点的二叉树，遍历子集树需遍历子集树需(2n)的计算时间。的计算时间。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 12 排列树|排列树（排列树（Permutation Trees）：）：当所给问题是确定当所给问题是确定n个元素满足某种性

8、质的排列时，个元素满足某种性质的排列时，相应的解空间树称为排列树。相应的解空间树称为排列树。在排列树中，通常情况下，在排列树中，通常情况下，|S1|n，|S2|n1，|Sn|1，解空间为：解空间为：（1，2，3，n1，n）（2，1，3，n1，n）（n，n1，3，2，1）算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 13 排列树|所以：所以：解空间有解空间有n!个元素个元素若表示为树形就是一个若表示为树形就是一个n度树，这样的树有度树，这样的树有n!个叶结个叶结点，遍历排列树需点，遍历排列树需(n!)计算时间。计算时间。算法设计与分析算法设计与分析回溯法回溯法四川师

9、范大学 计算机科学学院 刘芳 14 排列树|例：旅行商问题例：旅行商问题问题提出：问题提出：某售货员要到若干个城市去推销商品。已知各个城市某售货员要到若干个城市去推销商品。已知各个城市之间的路程（或旅费）。之间的路程（或旅费）。要选定一条从驻地出发，经过每个城市一遍，最后回要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使得总的路程（或总旅费）最小。到驻地的路线，使得总的路程（或总旅费）最小。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 15 1 12 23 34 43 33 33 33 34 44 44 44 42 22 22 22 2排列树|分析分

10、析求赋权图求赋权图G的具有最小权的的具有最小权的Hamilton圈圈|解空间：解空间：3065204101423当起点当起点1固定时，上图有固定时，上图有3!个周游路线（排列问题）个周游路线（排列问题）算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 16 回溯法的基本思想|回溯法回溯法回溯法是一种选优搜索法，按选优条件向前搜索，以回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。达到目标。但当探索到某一步时，发现原先选择并不优或达不到但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走目标，就退回一步重新选择，这种走不通

11、就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称的技术为回溯法，而满足回溯条件的某个状态的点称为为“回溯点回溯点”。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 17 回溯法的基本思想|主要应用主要应用解决一些复杂问题在求解的过程中，需要经过解决一些复杂问题在求解的过程中，需要经过若干步若干步骤骤，而每一个步骤都有若干种可能的分支，为了完成，而每一个步骤都有若干种可能的分支，为了完成这一过程，又必须这一过程，又必须遵守一些规则遵守一些规则，但这些规则又但这些规则又无法精确无法精确地用数学公式或语言来描述的地用数学公式或语言来描述的一类问题中。一类问题中。算

12、法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 18|1.基本思想基本思想设问题的解可表示为设问题的解可表示为n元组元组(x1,x2,xn),xi si,si为有限集为有限集,设已有满足约束条件的部分解设已有满足约束条件的部分解(x1,x2,xi)添加添加xi+1 si+1,若若(x1,x2,xi xi+1)满足约束条件满足约束条件,则继续添加则继续添加xi+2；若所有可能的若所有可能的xi+1 si+1均不满足约束条件均不满足约束条件,则去掉则去掉xi,回溯到回溯到(x1,x2,xi-1),添加尚未考虑过的添加尚未考虑过的xi；如此反复进行如此反复进行,直到直到(x

13、1,x2,xk)k n满足所有的约满足所有的约束条件或证明无解。束条件或证明无解。回溯法的基本思想算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 19 回溯法的基本思想|2.求解过程求解过程求解过程可表示为在一棵解空间树作深度优先搜索。求解过程可表示为在一棵解空间树作深度优先搜索。具体过程：具体过程：搜索按深度优先策略从根开始搜索按深度优先策略从根开始,当搜索到任一结点时，判断该点是否满足约束条件当搜索到任一结点时，判断该点是否满足约束条件D(剪枝函数剪枝函数)，若满足则继续向下深度优先搜索，若满足则继续向下深度优先搜索，否则跳过该结点以下的子树否则跳过该结点以下的

14、子树(剪枝剪枝)，向上逐级回溯。，向上逐级回溯。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 20 回溯法的基本思想|3.回溯法解题的步骤：回溯法解题的步骤：(1)针对所给问题，定义问题的解空间；针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。剪枝函数避免无效搜索。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 21 例：排列与组合|计算排列数计算排列数如何找出如何找出m个自然数个自然

15、数(1,2,3,m)中中n个数的所有排列。个数的所有排列。|分析分析设设(x1,x2,xn）一组解）一组解约束条件：约束条件：显约束：显约束：1xim隐约束：隐约束：xi xj (1ijn )|参考程序：参考程序：算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 22 例：排列与组合|计算组合数计算组合数算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 23 例：排列与组合|计算组合数：计算组合数：找出找出m个自然数个自然数(1,2,3,m)中中n个个数的组合。数的组合。要求：要求：输入：输入：m,n5 3输出：输出：Total10种种543

16、542532432541531431521421321算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 24 例：排列与组合|分析：分析：设设(x1,x2,xn）一组解）一组解约束条件：约束条件：显约束：显约束：1xim隐约束：隐约束：x1x2 xn i xi mni 即：即：xi-1 xi mni|参考程序：参考程序：算法设计与分析算法设计与分析n)output(x);else for(int j=f(n,i);j=g(n,i);j+)xi=h(j);if(constraint(i)&bound(i)backtrack(i+1);剪枝函数算法设计与分析算法设计与分析

17、回溯法回溯法四川师范大学 计算机科学学院 刘芳 26 算法的框架|一般来说，非递归回溯（迭代回溯）的算法过程：一般来说，非递归回溯（迭代回溯）的算法过程：1.数据初始化数据初始化2.如果如果当前状态合法当前状态合法 判断是否到达目标：判断是否到达目标：是，打印结果；然后换下一种情况是，打印结果；然后换下一种情况 不是，则继续向前探索不是，则继续向前探索 否则：否则：选择下一种可能；选择下一种可能；检查是否合法检查是否合法4.重复上述过程，直至所有情况都搜索完毕，结束。重复上述过程，直至所有情况都搜索完毕，结束。算法设计与分析算法设计与分析0)if(f(n,i)=g(n,i)for(int j=

18、f(n,i);j=g(n,i);j+)xi=h(j);if(constraint(i)&bound(i)if(solution(i)output(x);else i+;/for else i-;/while /iterativeBacktrack 算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 28 小结|回溯法解题的特征回溯法解题的特征在深度优先搜索过程中动态产生问题的解空间。在深度优先搜索过程中动态产生问题的解空间。几个术语几个术语扩展结点扩展结点:一个正在产生儿子的结点称为扩展结点一个正在产生儿子的结点称为扩展结点活结点活结点:一个自身已生成但其儿子还没有全部

19、生成的一个自身已生成但其儿子还没有全部生成的结点称做活结点结点称做活结点死结点死结点:一个所有儿子已经产生的结点称做死结点。一个所有儿子已经产生的结点称做死结点。需要注意的是：需要注意的是：问题的解空间树是虚拟的，并不需要在算法运行时构问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构。在任何时刻，算法造一棵真正的树结构。在任何时刻，算法只保存从根只保存从根结点到当前扩展结点的路径结点到当前扩展结点的路径。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 29 小结|避免无效搜索的策略避免无效搜索的策略回溯法的搜索过程涉及的结点（称为搜索空间）回溯法的搜

20、索过程涉及的结点（称为搜索空间）只是整个解空间树的一部分，在搜索过程中，通只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：常采用两种策略避免无效搜索：用约束条件用约束条件（约束函数）（约束函数）剪去得不到可行解的剪去得不到可行解的子树；子树；用目标函数（用目标函数（限界函数限界函数）剪去得不到最优解的）剪去得不到最优解的子树。子树。这两类函数统称为这两类函数统称为剪枝函数剪枝函数（Pruning Function）。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 30 5.2 回溯法的典型用例|几个应用专题几个应用专题图问题中的回溯法图问题中的

21、回溯法组合问题中的回溯法组合问题中的回溯法其他应用其他应用算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 31 应用专题一|图问题中的回溯法图问题中的回溯法例例1：n后问题后问题排列树的算法框架排列树的算法框架例例2：图的图的m着色问题着色问题例例3：TSP问题问题算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 32 例1：n后问题|问题描述：问题描述：在在nn格的棋盘上放置彼此不受攻击的格的棋盘上放置彼此不受攻击的n个皇后。按照个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同国际象棋的规则，皇后可以攻击与之处在同一行或同一列或

22、同一斜线上的棋子。一列或同一斜线上的棋子。n后问题等价于在后问题等价于在nn格的棋盘上放置格的棋盘上放置n个皇后，任何个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。个皇后不放在同一行或同一列或同一斜线上。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 33 例1：n后问题|例如：例如：88棋盘的一个可行放置。棋盘的一个可行放置。1 2 3 4 5 6 7 812345678QQQQQQQQ算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 34|分析：分析：解向量：解向量：(x1,x2,xn)约束条件约束条件显约束：显约束：xi=1,

23、2,n隐约束：隐约束：u不同列：不同列：xi xju不处于同一正、反对角线：不处于同一正、反对角线：|ij|xi-xj|过程演示过程演示例1：n后问题算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 35 例1：n后问题法法1：4后问题解空间的搜索过程（后问题解空间的搜索过程（nn）31422413算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 36 法法2：4后问题的解空间（排列树）后问题的解空间（排列树）例1：n后问题算法设计与分析算法设计与分析n)output(x);else for(int j=i;j=n;j+)swap(xj,xi

24、);if(legal(i)backtrack(i+1);swap(xj,xi);算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 38 例2：图的m着色问题|问题描述：问题描述：给定无向连通图给定无向连通图G和和m种不同的颜色。用这些颜色为种不同的颜色。用这些颜色为图图G的各顶点着色，每个顶点着一种颜色。是否有一的各顶点着色，每个顶点着一种颜色。是否有一种着色法使种着色法使G中每条边的中每条边的2个顶点着不同颜色。这个问个顶点着不同颜色。这个问题是题是图的图的m可着色判定问题可着色判定问题。若一个图最少需要若一个图最少需要m种颜色才能使图中每条边连接的种颜色才能使图中

25、每条边连接的2个顶点着不同颜色，则称这个数个顶点着不同颜色，则称这个数m为该为该图的色数图的色数。求。求一个图的色数一个图的色数m的问题称为图的的问题称为图的m可着色优化问题。可着色优化问题。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 39 例2：图的m着色问题|分析：分析：本题实际上就是著名的本题实际上就是著名的“地图四色地图四色”问题。无论地图问题。无论地图多么复杂，只需用四种颜色就可以将相邻的区域分开。多么复杂，只需用四种颜色就可以将相邻的区域分开。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 40 例2：图的m着色问题|数据

26、结构数据结构:为了解题方便，我们可以把每一个区域看成一个顶点，为了解题方便，我们可以把每一个区域看成一个顶点，若两个区域相邻，则相应的顶点间用一条边相连，这若两个区域相邻，则相应的顶点间用一条边相连，这样，该问题就转化为图的问题了。样，该问题就转化为图的问题了。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 41 例2：图的m着色问题|例如：例如：1235674算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 42 例2：图的m着色问题|分析：分析：解向量：解向量：(x1,x2,xn)约束条件约束条件显约束：显约束：1xim隐约束：隐约束：

27、顶点顶点i与已着色的相邻顶点的颜色不重复与已着色的相邻顶点的颜色不重复 (aki=1)&(xk=xi)|算法设计算法设计回溯法回溯法|参考程序参考程序算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 43 例3：TSP问题|问题提出：问题提出：|分析分析解空间：排列树解空间：排列树1 12 23 34 43 33 33 33 34 44 44 44 42 22 22 22 23065204101423算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 44 例3：TSP问题|分析：分析：解向量解向量x=(x1,x2,xn)约束条件：约束条件：显

28、约束：显约束：1xin隐约束：隐约束：xixj (ij)目标函数：回路的代价最短目标函数：回路的代价最短|剪枝函数：剪枝函数：用用约束函数约束函数在扩展结点处剪去不满足约束的子树；在扩展结点处剪去不满足约束的子树；用用限界函数限界函数剪去得不到最优解的子树。剪去得不到最优解的子树。算法设计与分析算法设计与分析253064354011261424556021361929算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 46|算法设计算法设计|参考程序参考程序Travle.cpp例3：TSP问题算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 4

29、7 应用专题二|组合问题中的回溯法组合问题中的回溯法子集树的算法框架子集树的算法框架例例1：子集问题子集问题例例2：01背包问题背包问题例例3：符号三角形问题符号三角形问题算法设计与分析算法设计与分析n)output(x);else for(int j=0;j=1;j+)xi=j;if(legal(i)backtrack(i+1);算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 49 例1：子集问题|问题描述问题描述集合集合Aa1,a2,an，求，求A的所有子集合。的所有子集合。|问题分析问题分析子集树空间子集树空间|算法设计算法设计回溯法回溯法|参考程序参考程序子

30、集合子集合.cpp算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 50 例2：0-1背包问题|问题描述：问题描述：给定给定n个物品和一个背包，物品个物品和一个背包，物品 i 的重量为的重量为wi,其价值其价值为为pi,背包的容量为背包的容量为c。问如何装物品，使得装入背包中物品总价值最大？问如何装物品，使得装入背包中物品总价值最大？算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 51|解空间：解空间：子集树子集树|可行性约束函数：可行性约束函数：例2：0-1背包问题算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳

31、 52|例如：例如：n=3,c=30,w=(16,15,15),p=(45,25,25)A(-,-,-)B(1,-,-)C:(0,-,-)D(1,1,-)D(1,0,-)F(0,1,-)G(0,0,-)H(1,1,1)I(1,1,0)K(1,0,0)J(1,0,1)L(0,1,1)M(0,1,0)N(0,0,1)O(0,0,0)001645164516450015253050152515250000例2：0-1背包问题算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 53 例2：0-1背包问题|参考程序参考程序（tryload1.cpp）|进一步的改进进一步的改进加入

32、限界函数加入限界函数如果扩展结点和它的子孙所导致的最好可行解的上界如果扩展结点和它的子孙所导致的最好可行解的上界不大于至今为止所确定的最好解之值，就可以剪去该不大于至今为止所确定的最好解之值，就可以剪去该右子树。右子树。剪枝函数剪枝函数约束函数约束函数限界函数限界函数算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 54|例如：例如：n=3,c=30,w=(16,15,15),p=(45,25,25)A(-,-,-)B(1,-,-)C:(0,-,-)D(1,1,-)D(1,0,-)F(0,1,-)G(0,0,-)H(1,1,1)I(1,1,0)K(1,0,0)J(1,

33、0,1)L(0,1,1)M(0,1,0)N(0,0,1)O(0,0,0)001645164516450015253050例2：0-1背包问题算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 55|问题：问题：如何设计限界函数如何设计限界函数Bound(i,cw,cp)|参考程序参考程序tryload2.cpp|思考：思考：n=4,c=7,w=(3,5,2,1),p=(9,10,7,4)的的0-1背包问题的解空背包问题的解空间，及搜索回溯过程。间，及搜索回溯过程。例2：0-1背包问题算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 56 例3：

34、符号三角形问题|问题描述问题描述下图是由下图是由14个个“”号和号和14个个“”号组成的符号三号组成的符号三角形。角形。2个同号下面是个同号下面是“”号，号，2个异号下面是个异号下面是“”号。号。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 57 例3：符号三角形问题一般情况下，符号三角形的第一行有一般情况下，符号三角形的第一行有n个符号。个符号。符号三角形问题要求对于给定的符号三角形问题要求对于给定的n，计算有多少个不，计算有多少个不同的符号三角形，使同的符号三角形，使“”和和“”号相同。号相同。|注意：注意：在符号三角形的第一行的前在符号三角形的第一行的前t个

35、符号个符号(x1,x2,xt)确定后，就确定了一个由确定后，就确定了一个由 t*(t+1)/2 个符号组成的符号个符号组成的符号三角形。三角形。在确定在确定xt+1的值后，只要在前面已确定的符号三角形的值后，只要在前面已确定的符号三角形的右边加一条边，就可以扩展为的右边加一条边，就可以扩展为(x1,x2,xt+1)所所对应的符号三角形。对应的符号三角形。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 58 例3：符号三角形问题|分析分析解向量解向量x=(x1,x2,xn)约束条件约束条件显约束：显约束：xt 0，1uxt1：符号三角形的第一行的第符号三角形的第一行的

36、第t个元素为个元素为“”；uxt0：符号三角形的第一行的第符号三角形的第一行的第t个元素为个元素为“”；隐约束：隐约束：u显然：显然：(x1,x2,xn)确定的符号三角形总符号数为：确定的符号三角形总符号数为：total n(n+1)/2。于是符合条件的符号三角形中。于是符合条件的符号三角形中“+”和和“”个数个数不超过不超过half n(n+1)/4，若超过，若超过half，则剪去不满足条件的子，则剪去不满足条件的子树树算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 59 例3：符号三角形问题|解空间解空间由于由于xt是二值的，故该问题的解空间为子集树。是二值的，

37、故该问题的解空间为子集树。|数据结构设计：数据结构设计：三角矩阵三角矩阵|参考程序：参考程序：trytriangle.cpp 算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 60 应用专题三|其他应用其他应用例例1：批处理作业调度问题批处理作业调度问题例例2：工作安排问题工作安排问题例例3：整数的划分问题整数的划分问题例例4：棋盘覆盖问题棋盘覆盖问题例例5：八数码难题八数码难题例例6：迷宫问题迷宫问题例例7：马踏棋盘问题马踏棋盘问题算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 61 例1：批处理作业调度问题|问题描述问题描述给定给定n个

38、作业的集合个作业的集合J1,J2,Jn。每个作业必须先由机器每个作业必须先由机器1处理，然后由机器处理，然后由机器2处理。作处理。作业业Ji需要机器需要机器j的处理时间为的处理时间为tij。对于一个确定的作业调度，设对于一个确定的作业调度，设Fij是作业是作业i在机器在机器j上完成上完成处理的时间。所有作业在机器处理的时间。所有作业在机器2上完成处理的时间和上完成处理的时间和称为该作业调度的完成时间和。称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的批处理作业调度问题要求对于给定的n个作业，制定个作业，制定最佳作业调度方案最佳作业调度方案，使其完成时间和达到最小。，使其完成时间和达

39、到最小。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 62 例1：批处理作业调度问题|例如：例如：tij机器机器1机器机器2作业作业121作业作业231作业作业323u 这这3个作业的个作业的6种可能的调度方案种可能的调度方案 1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；u 它们所相应的完成时间和分别是它们所相应的完成时间和分别是19，18，20，21，19，19。u 易见，最佳调度方案是易见，最佳调度方案是1,3,2，其完成时间和为，其完成时间和为18。算法设计与分析算法设计与分析 n)for(int j=1;j=n;j+)bestx

40、j=xj;bestf=f;else for(int j=i;j f1)?f2i-1:f1)+Mxj2;f+=f2i;if(f bestf)Swap(xi,xj);Backtrack(i+1);Swap(xi,xj);f1-=Mxj1;f-=f2i;算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 64 例2：工作安排问题|问题描述问题描述设有设有n项工作要安排给项工作要安排给n个人去完成。让第个人去完成。让第i个人去完成个人去完成第第j项工作产生的效益为项工作产生的效益为aij。试设计一个算法，为每个。试设计一个算法，为每个人安排一件不同的工作，并使总效益最大。人安排

41、一件不同的工作，并使总效益最大。|例如：例如：算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 65 例2：工作安排问题|分析：分析：思路：思路：每个人选择每个人选择n项工作中的一项，在各种选择的组合中，项工作中的一项，在各种选择的组合中，找到效益最大的一种组合输出。找到效益最大的一种组合输出。解向量解向量x=(x1,x2,xn)解空间：解空间：排列树空间排列树空间参考程序参考程序算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 66 例3：整数的划分问题|问题提出：问题提出：将一个正整数将一个正整数n表示成形如下式的一系列正整数的和，表示成

42、形如下式的一系列正整数的和，称为称为n的一个划分。的一个划分。nn1n2nk(ni1,i1,2,k,k1且且nn1n2nk 1算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 67 例3：整数的划分问题|例如：例如：整数整数6的分划数有的分划数有11种种:6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1;算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 68|分析分析解向量解向量x=(x1,x2,xn)约束条件约束条件显约束：显约束：1xi n隐约束：隐

43、约束：unx1x2xk(xi1,i1,2,k,k1)unx1x2xk 1问题的解空间问题的解空间|参考程序参考程序例3：整数的划分问题算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 69 例4：棋盘覆盖问题|问题描述：问题描述：在一个在一个nn个方格组成的棋盘中，要用图示的个方格组成的棋盘中，要用图示的4种不同种不同形态的形态的L型骨牌覆盖给定的棋盘上的所有方格，且任型骨牌覆盖给定的棋盘上的所有方格，且任何何2个个L型骨牌不得重叠覆盖。（必要时，需要挖掉型骨牌不得重叠覆盖。（必要时，需要挖掉1块）块）算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学

44、院 刘芳 70|例如：例如：554453342311221121111109912121110109877655887665433211443221例4：棋盘覆盖问题算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 71 例4：棋盘覆盖问题|考虑几个问题考虑几个问题L型骨牌的表示方式型骨牌的表示方式约束条件约束条件求解过程求解过程|参考程序：参考程序：算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 72 例5：八数码难题|问题描述：问题描述：|求解过程示意图：求解过程示意图：|程序实现：程序实现：(a)57461382(b)56748321

45、算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 73 算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 74 例6：迷宫问题|问题描述问题描述|问题分析问题分析|过程演示过程演示|算法设计算法设计算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 75 例例7：马踏棋盘问题：马踏棋盘问题|问题描述问题描述在在n x n棋盘（有棋盘（有n x n个格点的棋盘）的某个格点上有一个中国个格点的棋盘）的某个格点上有一个中国象棋马，马走日字。求一条周游棋盘的路径，使得马能够从起象棋马，马走日字。求一条周游棋盘的路径，使得马能够

46、从起始位置起沿着该路径每个格点恰好走一次最后回到出发位置。始位置起沿着该路径每个格点恰好走一次最后回到出发位置。|输入输入n (棋盘规格棋盘规格)|输出输出周游路线周游路线|分析分析回溯回溯+贪心贪心算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 76 例如：66132291871030173692819332316118162314352027334252251224154132621算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 77 例如：16161182372402551223523275583128776433362382412

47、561923623325413302776573235786317223981120231234597429686556373424271622122914253266960475467627932222191015228212307346496661405538624342472202325222770257285485380412232482452182252502292445848750438239522445224249246217226251887144838651428119117421120819318021321613311689150135122919421020719217

48、321221519417915214913411590931361211751902091841811721532141171321511261231149592206185176163170183178195148127118105112125120137189162165182177156171154131104107124119981139618620518820116416919615712814713014310611113899161200203166159198155168103142145108101140971102041871601992021671581971461291

49、02141144109100139算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 78 5.3 回溯法效率分析|影响回溯法效率的几个因素：影响回溯法效率的几个因素：1.生成结点所花费的时间；生成结点所花费的时间；2.计算约束条件所花费的时间；计算约束条件所花费的时间；3.计算目标函数的界所花费的时间；计算目标函数的界所花费的时间；4.所生成的结点个数。所生成的结点个数。算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 79|解向量中分量排列顺序的影响解向量中分量排列顺序的影响重排原理重排原理解向量中分量的取值范围不同时，在解向量中的不同解向

50、量中分量的取值范围不同时，在解向量中的不同排列顺序，其对应的状态空间树的结构也不同。排列顺序，其对应的状态空间树的结构也不同。在其他条件相当的前提下，让可取值最少的在其他条件相当的前提下，让可取值最少的xi。例如：例如：从下图中关于同一问题的从下图中关于同一问题的2棵不同解空间树，可以体棵不同解空间树，可以体会到这种策略的潜力。会到这种策略的潜力。5.3 回溯法效率分析算法设计与分析算法设计与分析回溯法回溯法四川师范大学 计算机科学学院 刘芳 80|解空间解空间：(x1,x2,x3)|xi si,i=1,2,3,|s1|=3,|s2|=4,|s3|=2|解空间树解空间树1：对应于对应于(x1,