1 / 11
文档名称:

回溯算法原理.doc

格式:doc   大小:80KB   页数:11页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

回溯算法原理.doc

上传人:aibuaiwo1318 2018/4/26 文件大小:80 KB

下载得到文件列表

回溯算法原理.doc

相关文档

文档介绍

文档介绍:回溯算法原理
第 4 章回溯
寻找问题的解的一种可靠的方法是首先列出所有候选解,然后依次检查每一个,在检查完所有或部分候选解后,即可找到所需要的解。理论上,当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时,上述方法是可行的。不过,在实际应用中,很少使用这种方法,因为候选解的数量通常都非常大(比如指数级,甚至是大数阶乘),即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种,其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少(无论对于最坏情形还是对于一般情形)。事实上,这些方法可以使我们避免对很大的候选解集合进行检查,同时能够保证算法运行结束时可以找到所需要的解。因此,这些方法通常能够用来求解规模很大的问题。
本章集中阐述回溯方法,这种方法被用来设计货箱装船、背包、最大完备子图、旅行商和电路板排列问题的求解算法。
算法思想
回溯(b a c k t r a c k i n g)是一种系统地搜索问题解答的方法。为了实现回溯,首先需要为问题定义一个解空间( solution space),这个空间必须至少包含问题的一个解(可能是最优的)。在迷宫老鼠问题中,我们可以定义一个包含从入口到出口的所有路径的解空间;在具有n 个对象的0 / 1背包问题中(见1 . 4节和2 . 2节),解空间的一个合理选择是2n 个长度为n 的0 / 1向量的集合,这个集合表示了将0或1分配给x的所有可能方法。当n= 3时,解空间为{ ( 0 , 0 , 0 ),( 0 , 1 , 0 ),( 0 , 0 , 1 ),( 1 , 0 , 0 ),( 0 , 1 , 1 ),( 1 , 0 , 1 ),( 1 , 1 , 0 ),( 1 , 1 , 1 ) }。
下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。图1 6 - 1用图的形式给出了一个3×3迷宫的解空间。从( 1 , 1 )点到( 3 , 3 )点的每一条路径都定义了3×3迷宫解空间中的一个元素,但由于障碍的设置,有些路径是不可行的。
图1 6 - 2用树形结构给出了含三个对象的0 / 1背包问题的解空间。从i 层节点到i+ 1层节点的一条边上的数字给出了向量x 中第i个分量的值xi ,从根节点到叶节点的每一条路径定义了解空间中的一个元素。从根节点A到叶节点H的路径定义了解x= [ 1 , 1 , 1 ]。根据w 和c 的值,从根到叶的路径中的一些解或全部解可能是不可行的。
一旦定义了解空间的组织方法,这个空间即可按深度优先的方法从开始节点进行搜索。在迷宫老鼠问题中,开始节点为入口节点( 1 , 1 );在0 / 1背包问题中,开始节点为根节点A。开始节点既是一个活节点又是一个E-节点(expansion node)。从E-节点可移动到一个新节点。如果能从当前的E-节点移动到一个新节点,那么这个新节点将变成一个活节点和新的E-节点,旧的E-节点仍是一个活节点。如果不能移到一个新节点,当前的E-节点就“死”了(即不再是一个活节点),那么便只能返回到最近被考察的活节点(回溯),这个活节点变成了新的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时,搜索过程结束。
例4-1 [迷宫老鼠] 考察图16-3a 的矩阵中给出的3×3的“迷宫老鼠”问题。我们将利用图1 6 -1给出的解空间图来搜索迷宫。
从迷宫的入口到出口的每一条路径都与图1 6 - 1中从( 1 , 1 )到( 3 , 3 )的一条路径相对应。然而,图1 6 - 1中有些从( 1 , 1 )到( 3 , 3 )的路径却不是迷宫中从入口到出口的路径。搜索从点( 1 , 1 )开始,该点是目前唯一的活节点,它也是一个E-节点。为避免再次走过这个位置,置m a z e( 1 , 1 )为1。从这个位置,能移动到( 1 , 2 )或( 2 , 1 )两个位置。对于本例,两种移动都是可行的,因为在每一个位置都有一个值0。假定选择移动到( 1 , 2 ),m a z e( 1 , 2 )被置为1以避免再次经过该点。迷宫当前状态如图16-3b 所示。这时有两个活节点(1,1) (1,2)。( 1 , 2 )成为E-节点。
在图1 6 - 1中从当前E-节点开始有3个可能的移动,其中两个是不可行的,因为迷宫在这些位置上的值为1。唯一可行的移动是( 1 , 3 )。移动到这个位置,并置m a z e( 1 , 3 )为1以避免再次经过该点,此时迷宫状态为1 6 - 3 c。图1 6 - 1中,从( 1 , 3 )出发有两个可能的移动,但没有一个是可行的。所以E-节点( 1 , 3 )死亡,回溯到最近被检查的活节点( 1

最近更新

充分利用经济杠杆作用——企业内部经营承包的.. 2页

催化再生烟气废热锅炉的防振消音方法 2页

偏心侧冲斜楔平衡结构的设计和应用 2页

信贷催收的心理压力分析与控制工具应用 2页

一师一优课讲课课件 40页

促进中小企业技术创新的税收优惠政策研究 2页

供求关系与价格运动——有计划商品经济初探 2页

作物生育期间农业气象条件鉴定方法 2页

住宅建筑外立面材料精细化设计研究的开题报告.. 2页

低碳经济发展对我国贸易结构影响分析 2页

低温下板式橡胶桥梁支座力学性能及试验方法的.. 2页

低品位白钨精矿苏打压煮工艺的改进 2页

位移控制电液伺服系统特性的改善方法 2页

传动力对主轴刚度影响的分析研究 2页

优化设计方法的综述及其在飞航导弹设计中的应.. 2页

优化劳动组合 内部配套改革 2页

企业间合作创新对创新绩效影响研究综述 2页

《阿米巴经营》推行实施步骤详解 20页

灵活用工合同范本及解析 7页

价值分析结硕果——纺织行业应用VE五则 2页

以股份制为基础的社会共有制的几点思考 2页

以提高经济效益为目的 完善煤矿支护技术改革.. 2页

以RAM作为数字滤波延迟单元的寻址方法探讨 2页

从采石场碎石机问题检查我们技术组织措施的浪.. 2页

从纺织工程看现代工程技术的综合趋势及其方法.. 2页

深圳建筑项目合同汇总 6页

从德国的GT应用看我国GT的发展 2页

深圳办公用房租赁合同范本 6页

从再生产的价值补偿和物质补偿探讨商业的猪蛋.. 2页

从“卖粮难”到“难卖粮”的思考 2页