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

最近更新

如何在人力资源管理中提高决策的科学性 5页

奥克斯的薪酬管理浅析 6页

大数据下企业财务共享分析——以TCL集团为例 4页

《税收与博弈》 81页

多级模糊综合评价方法在企业人力资源信息系统.. 6页

基层安全生产和应急管理思考 4页

基于守敬创新工作室的技术创新型人才培养模式.. 4页

基于单片机的电机调速系统课程设计 5页

基于单片机的循环彩灯设计开题报告 5页

基于作业成本法的高校成本核算业务流程研究 6页

基于PLC的皮带集中控制系统设计毕业论文 4页

基于AT89C52单片机的智能家居系统设计 6页

培训师评估模型与评估方法(共43) 4页

在线论文管理系统及其方法 7页

国美电器案例分析 5页

国有企业优化考核分配工作,完善市场化经营机制.. 4页

国有企业专业技术人才梯队建设工作探究 6页

导购天工作流程 49页

《嗜血细胞综合征》 15页

员工绩效考评存在的问题与对策 3页

员工关系管理包含的要素及发展情况 5页

《市场营销策略模块》 36页

采购管理考试资料 26页

印章管理审计的17个核心要点 6页

银行大堂经理工作要点 39页

单位管理制度范文汇编【人力资源管理】 5页

单位管理制度优秀大全【人力资源管理】 6页

华南理工大学网络教育人力资源管理随堂练习 4页

华东理工大学论文开题报告模版-清爽大气优秀完.. 5页

医院人力成本构成、控制与分析 5页