- 1、本文档共40页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
提纲一.回溯算法的含义二.用回溯算法解决问题的一般步骤三.回溯法解题思路--应用递归函数求解一.回溯算法的含义一.回溯算法的含义以组合问题为例:找出从自然数1、2、……、n中任取r个数的所有组合(要求r个数从小到大排列)。 例如n=5,r=3的所有组合为: (1)1,2,3 (2)1,2,4 (3)1,2,5(4)1,3,4 (5)1,3,5 (6)1,4,5 (7)2,3,4 (8)2,3,5 (9)2,4,5(10)3,4,5一.回溯算法的含义求n=5,r=3的所有组合算法1:使用前面学的穷举算法罗列出3个数字剔重之后的5×4×3=60种候选解。利用限制条件(r个数从小到大排列)来剔除不符合要求的解。算法评价:计算量大,可能候选解中只有一小部分解是符合要求的解。一.回溯算法的含义求n=5,r=3的所有组合算法2:使用回溯算法提纲一.回溯算法的含义二.用回溯算法解决问题的一般步骤三.回溯法解题思路--应用递归函数求解二.用回溯算法解决问题的一般步骤二.用回溯算法解决问题的一般步骤:针对所给问题,定义问题的解空间,它至少包含问题的一个(最优)解。确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间。以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。问题的解空间通常是在搜索问题解的过程中动态产生的,这是回溯算法的一个重要特性。二.用回溯算法解决问题的一般步骤第1步.定义问题的解空间。问题的解空间应至少包含问题的一个(最优)解。例:求n=5,r=3的所有组合二.用回溯算法解决问题的一般步骤第1步.定义问题的解空间。可用回溯法求解的问题P,下述集合E中的n元组组成了问题P的解空间:E={(x1,x2,…,xn)∣xi∈Si,1≤i≤n}其中Si是xi的定义域,且Si中元素个数有限。问题P的解:E中所有满足约束集D的n元组(D是对x1~xn取值的全部约束条件)。二.用回溯算法解决问题的一般步骤第2步.确定易于搜索的解空间结构。 通常可以将解空间组织成一棵树,使得能用回溯法方便地搜索整个解空间。二.用回溯算法解决问题的一般步骤第3步.以深度优先的方式搜索解空间 回溯法的基本思想:确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。搜索问题解,建立解空间-1搜索问题解,建立解空间-2搜索问题解,建立解空间-3搜索问题解,建立解空间-4提纲一.回溯算法的含义二.用回溯算法解决问题的一般步骤三.回溯法解题思路--应用递归函数求解三.回溯法解题思路三.回溯法解题思路就是求所有满足条件D的n元组(x1,x2,…,xn)为求n元组(x1,x2,…,xn),可以先求出x1,然后再求n-1元组(x2,…,xn)。这样,求(x1,x2,…,xn)的问题被转化为规模小一级但同性质的求(x2,…,xn)的问题。同理,求(x2,…,xn)的问题可以转化为求(x3,…,xn)的问题,如此不断转化,问题规模不断减小。当被转化为求一元组(xn)时,可以直接给出结果,而不需要继续转化。这就是递归算法实现回溯法的思想。三.回溯法解题思路-应用递归函数求解例1.求n=5,r=3的所有组合。问题分析:求组合其实就是求满足条件的3元组(x1,x2,x3)。可以设计递归函数进行求解元组(xi,…,xn)。递归函数参数设计考虑:i肯定是作为一个参数,那么n是作为参数还是其他采用方式(如全局变量、常量)?xi的取值范围是递归函数必须要获得的。求得的元组采用什么数据结构存放?采用全局变量还是作为参数?三.回溯法解题思路-应用递归函数求解递归函数设计:求元组(xi,…,xn)voidtry(inti,intn,i
您可能关注的文档
- gre常考单词最新完整版本.pdf
- jbt92062021钢铁热浸铝工艺及质量检验.pdf
- K12教育行业发展洞察2024-月狐数据-2024.5-30页最新完整版本.pdf
- knawfrankeconvimplicrevised202210171502page11inter最新完整版本.pdf
- kuka介绍最新完整版本.ppt
- layoutplus培训教材最新完整版本.doc
- lcdfrontpanel之cae分析标准工作流程范玉文最新完整版本.ppt
- lcd相关简报101120最新完整版本.ppt
- led加速合作整并彰显照明来临最新完整版本.pdf
- loctite乐泰焊锡膏技术培训最新完整版本.ppt
文档评论(0)