回溯法和分支限界法优秀PPT.ppt
《回溯法和分支限界法优秀PPT.ppt》由会员分享,可在线阅读,更多相关《回溯法和分支限界法优秀PPT.ppt(21页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、回溯法和分支限界法第1页,本讲稿共21页2回溯法有许多问题,当需要找出它的解集或者要求回答什么解是有许多问题,当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时,往往要使用回溯法。满足某些约束条件的最佳解时,往往要使用回溯法。回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。大的问题。回溯法在问题的解空间树中,按深度优先策略,从根结回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。
2、算法搜索至解空间树的任意一点点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。回溯;否则,进入该子树,继续按深度优先策略搜索。第2页,本讲稿共21页3问题的解空间 问题的解向量:回溯法希望一个问题的解能够表示成一个问题的解向量:回溯法希望一个问题的解能够表示成一个n n元式元式(x1,x2,(x1,x2,xn),xn)的形式。的形式。显约束:对分量显约束:
3、对分量xixi的取值限定。的取值限定。隐约束:为满足问题的解而对不同分量之间施加的约束。隐约束:为满足问题的解而对不同分量之间施加的约束。解空间:对于问题的一个实例,解向量满足显式约束条件的所有多元解空间:对于问题的一个实例,解向量满足显式约束条件的所有多元组,构成了该实例的一个解空间。组,构成了该实例的一个解空间。注意:同一个问题可以有多种表示,有些表示方法更简单,所需表示的状态空间更小(存储量少,搜索方法简单)。第3页,本讲稿共21页4问题的解空间n=3时的时的0-1背包问题用完全背包问题用完全二叉树表示的解空间二叉树表示的解空间 子集树子集树旅行商问题旅行商问题:某售货员要:某售货员要到
4、若干城市推销商品,已知到若干城市推销商品,已知各个城市之间的路程(或旅各个城市之间的路程(或旅费)。他要选定一条从驻地费)。他要选定一条从驻地出发,经过每个城市一遍,出发,经过每个城市一遍,最后回到驻地的路线,使总最后回到驻地的路线,使总的路线(或旅费)最小。的路线(或旅费)最小。排列树排列树12343061020第4页,本讲稿共21页5生成问题状态的基本方法 扩展结点扩展结点扩展结点扩展结点:一个正在产生儿子的结点称为扩展结点一个正在产生儿子的结点称为扩展结点一个正在产生儿子的结点称为扩展结点一个正在产生儿子的结点称为扩展结点活结点活结点活结点活结点:一个自身已生成但其儿子还没有全部生成的节
5、点称一个自身已生成但其儿子还没有全部生成的节点称一个自身已生成但其儿子还没有全部生成的节点称一个自身已生成但其儿子还没有全部生成的节点称做活结点做活结点做活结点做活结点 死结点死结点死结点死结点:一个所有儿子已经产生的结点称做死结点一个所有儿子已经产生的结点称做死结点一个所有儿子已经产生的结点称做死结点一个所有儿子已经产生的结点称做死结点深度优先的问题状态生成法:如果对一个扩展结点深度优先的问题状态生成法:如果对一个扩展结点深度优先的问题状态生成法:如果对一个扩展结点深度优先的问题状态生成法:如果对一个扩展结点R R,一旦,一旦,一旦,一旦产生了它的一个儿子产生了它的一个儿子产生了它的一个儿子
6、产生了它的一个儿子C C,就把,就把,就把,就把C C当做新的扩展结点。在完成当做新的扩展结点。在完成当做新的扩展结点。在完成当做新的扩展结点。在完成对子树对子树对子树对子树C C(以(以(以(以C C为根的子树)的穷尽搜索之后,将为根的子树)的穷尽搜索之后,将为根的子树)的穷尽搜索之后,将为根的子树)的穷尽搜索之后,将R R重新变成重新变成重新变成重新变成扩展结点,继续生成扩展结点,继续生成扩展结点,继续生成扩展结点,继续生成R R的下一个儿子(如果存在)的下一个儿子(如果存在)的下一个儿子(如果存在)的下一个儿子(如果存在)宽度优先的问题状态生成法:在一个扩展结点变成死结点之宽度优先的问题
7、状态生成法:在一个扩展结点变成死结点之宽度优先的问题状态生成法:在一个扩展结点变成死结点之宽度优先的问题状态生成法:在一个扩展结点变成死结点之前,它一直是扩展结点前,它一直是扩展结点前,它一直是扩展结点前,它一直是扩展结点 回溯法:为了避免生成那些不可能产生最佳解的问题状态,要不断回溯法:为了避免生成那些不可能产生最佳解的问题状态,要不断回溯法:为了避免生成那些不可能产生最佳解的问题状态,要不断回溯法:为了避免生成那些不可能产生最佳解的问题状态,要不断地利用限界函数地利用限界函数地利用限界函数地利用限界函数(bounding function)(bounding function)来处死那些实
8、际上不可能产来处死那些实际上不可能产来处死那些实际上不可能产来处死那些实际上不可能产生所需解的活结点,以减少问题的计算量。生所需解的活结点,以减少问题的计算量。生所需解的活结点,以减少问题的计算量。生所需解的活结点,以减少问题的计算量。具有限界函数的深度优具有限界函数的深度优具有限界函数的深度优具有限界函数的深度优先生成法称为回溯法先生成法称为回溯法先生成法称为回溯法先生成法称为回溯法第5页,本讲稿共21页6回溯法的基本思想(1)(1)针对所给问题,定义问题的解空间;针对所给问题,定义问题的解空间;(2)(2)确定易于搜索的解空间结构;确定易于搜索的解空间结构;(3)(3)以深度优先方式搜索解
9、空间,并在搜索过程中用剪以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。枝函数避免无效搜索。常用剪枝函数:用约束函数在扩展结点处剪去不满足约束的子树;用限界函数剪去得不到最优解的子树。用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻,算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n),则回溯法所需的计算空间通常为O(h(n)。而显式地存储整个解空间则需要O(2h(n)或O(h(n)!)内存空间。第6页,本讲稿共21页7递归回溯回溯法对解空间作深度优先搜索,因此,在一般情况下用递归回溯法对解空间作深度优先搜索,
10、因此,在一般情况下用递归方法实现回溯法。方法实现回溯法。voidvoidbacktrack backtrack(intt)(intt)if if(tn)outputoutput(x);(x);elseelse for for(inti=(inti=f f(n,t);i=(n,t);i0)if if(f(n,t)=(n,t)=g g(n,t)for(inti=f(n,t);i=(n,t);in)output(x);elsefor(inti=0;in)output(x);elsefor(inti=t;i=n;i+)swap(xt,xi);if(legal(t)backtrack(t+1);swap
11、(xt,xi);第9页,本讲稿共21页10n后问题在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。1 2 3 4 5 6 7 812345678QQQQQQQQ第10页,本讲稿共21页11解向量:(x1,x2,xn)显约束:xi=1,2,n隐约束:1)不同列:xi xj2)不处于同一正、反对角线:|i-j|xi-xj|n后问题后问题int n=8;int x9;int num=0;/解的个数/判断第k个皇后能否放在第xk列bool Pl
12、ace(int k)int i=1;while(i 0)while(k 0)xk+=1;/xk+=1;/转到下一行转到下一行 while(xk=n&while(xk=n&Place(k)=false)Place(k)=false)/如果无解,最后一个皇后就会安排到如果无解,最后一个皇后就会安排到格子外面去格子外面去 xk+=1;xk+=1;if(xk=n)if(xk=n)/第第k k个皇后仍被放置在格子内,有解个皇后仍被放置在格子内,有解 if(k=n)if(k=n)num+;num+;cout num :t;cout num :t;for(int i=1;i=n;i+)for(int i=1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 回溯 分支 限界 优秀 PPT
限制150内