算法设计与分析回溯法.pptx
《算法设计与分析回溯法.pptx》由会员分享,可在线阅读,更多相关《算法设计与分析回溯法.pptx(48页珍藏版)》请在咨信网上搜索。
1、回溯法回溯法有许多问题,当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时,往往要使用回溯法。回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。问题的解空间问题的解空间问题的解向量:回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。显约束:对分量xi的
2、取值限定。隐约束:为满足问题的解而对不同分量之间施加的约束。解空间:对于问题的一个实例,解向量满足显式约束条件的所有多元组,构成了该实例的一个解空间。注意:同一个问题可以有多种表示,有些表示方法更简单,所需表示的状态空间更小(存储量少,搜索方法简单)。n=3时的0-1背包问题用完全二叉树表示的解空间生成问题状态的基本方法生成问题状态的基本方法扩展结点:一个正在产生儿子的结点称为扩展结点活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点死结点:一个所有儿子已经产生的结点称做死结点深度优先的问题状态生成法:如果对一个扩展结点R,一旦产生了它的一个儿子C,就把C当做新的扩展结点。在完成对子
3、树C(以C为根的子树)的穷尽搜索之后,将R重新变成扩展结点,继续生成R的下一个儿子(如果存在)宽度优先的问题状态生成法:在一个扩展结点变成死结点之前,它一直是扩展结点回溯法:为了避免生成那些不可能产生最佳解的问题状态,要不断地利用限界函数(boundingfunction)来处死那些实际上不可能产生所需解的活结点,以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法回溯法的基本思想回溯法的基本思想(1)针对所给问题,定义问题的解空间;(2)确定易于搜索的解空间结构;(3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。常用剪枝函数:用约束函数在扩展结点处剪去不满足约束的子
4、树;用限界函数剪去得不到最优解的子树。用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻,算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n),则回溯法所需的计算空间通常为O(h(n)。而显式地存储整个解空间则需要O(2h(n)或O(h(n)!)内存空间。递归回溯递归回溯回溯法对解空间作深度优先搜索,因此,在一般情况下用递归方法实现回溯法。void backtrack(int t)if(tn)output(x);else for(int i=f(n,t);i0)if(f(n,t)=g(n,t)for(int i=f(n,t);i
5、n)output(x);else for(int i=0;in)output(x);else for(int i=t;i=n;i+)swap(xt,xi);if(legal(t)backtrack(t+1);swap(xt,xi);0-1背包问题背包问题给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。01背包问题:背包问题:n=3,w=20,30,10,p=100,120,60且且C=50.三个对象的背包问题的解空间三个对象的背包问题的解空间10101010101010A
6、BGIFHELDC回溯法解决回溯法解决01背包问题背包问题1.解向量:一维数组2.约束:取值范围,重量限制3.解空间:子集树4.代码实现5.改进0-1背包问题背包问题解空间:子集树可行性约束函数:上界函数:private static double bound(int i)/计算上界 double cleft=c-cw;/剩余容量 double bound=cp;/以物品单位重量价值递减序装入物品 while(i=n&wi=cleft)cleft-=wi;bound+=pi;i+;/装满背包 if(i n)/到达叶结点 更新最优解bestx,bestw;return;r-=wi;if(cw+w
7、i bestw)xi=0;/搜索右子树 backtrack(i+1);r+=wi;批处理作业调度批处理作业调度给定n个作业的集合J1,J2,Jn。每个作业必须先由机器1处理,然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度,设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小。tji机器1机器2作业121作业231作业323这3个作业的6种可能的调度方案是1,2,3;1,3,2;2,1,3;2,3,1;3,1,2;3,2,1;它
8、们所相应的完成时间和分别是19,18,20,21,19,19。易见,最佳调度方案是1,3,2,其完成时间和为18。批处理作业调度批处理作业调度解空间:排列树private static void backtrack(int i)if(i n)for(int j=1;j=n;j+)bestxj=xj;bestf=f;else for(int j=i;j f1)?f2i-1:f1)+mxj2;f+=f2i;if(f half)|(t*(t-1)/2-counthalf)return;if(tn)sum+;else for(int i=0;i2;i+)p1t=i;count+=i;for(int j
9、=2;j=t;j+)pjt-j+1=pj-1t-j+1pj-1t-j+2;count+=pjt-j+1;backtrack(t+1);for(int j=2;j=t;j+)count-=pjt-j+1;count-=i;+-+-+-+-+-+-+-+复杂度分析复杂度分析计算可行性约束需要O(n)时间,在最坏情况下有 O(2n)个结点需要计算可行性约束,故解符号三角形问题的回溯算法所需的计算时间为 O(n2n)。n后问题后问题在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后,任何2个皇
10、后不放在同一行或同一列或同一斜线上。1 2 3 4 5 6 7 812345678QQQQQQQQ解向量:(x1,x2,xn)显约束:xi=1,2,n隐约束:1)不同列:xi xj 2)不处于同一正、反对角线:|i-j|xi-xj|n后问题后问题 private static boolean place(int k)for(int j=1;jn)sum+;else for(int i=1;i=n;i+)xt=i;if(place(t)backtrack(t+1);21【问题问题】填字游戏填字游戏问题描述:在33个方格的方阵中要填入数字1到N(N10)内的某9个数字,每个方格填一个整数,使得所有
11、相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。12349815145请按任意键继续.12349141585请按任意键继续.12341589145请按任意键继续.12341514985请按任意键继续.1 2 36 5 87 12 11请按任意键继续.1 2 36 5 1411 8 9请按任意键继续.1 2 36 5 1411 8 15请按任意键继续.23练习:走台阶问题练习:走台阶问题【题目叙述】你眼前一共有n级台阶(n为正整数),现在你要走完这n级台阶,已知你只能一步走一级或一步走两级,请你算算一共有多少种走法,并把这些走法都给出。【输入输出样例】输入:3输出:11
12、11221找数【题目叙述】键盘输入n个正整数(互不相等),找出其中和等于m的数的组合。【输入输出样例】输入:5(m的值)12345输出:1423524液晶数字问题液晶数字问题【题目叙述】如下图所示:0.9这10个数字可以由下列7个发光二极管组成。0-9十个数字排成一排,每个数字只可以用一次。排列要求:相邻数字后一个是由前一个数字添上几笔或是减去几笔得到的,不允许同时加减。例如:3和8,8和3可以相邻,3和5不能相邻等。问:有多少符合要求的排列?给出所有排列方法。25最大团问题最大团问题给定无向图G=(V,E)。如果UV,且对任意u,vU有(u,v)E,则称U是G的完全子图。G的完全子图U是G的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 回溯
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。