1 / 10
文档名称:

回溯算法四例.doc

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

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

分享

预览

回溯算法四例.doc

上传人:花开一叶 2019/2/4 文件大小:64 KB

下载得到文件列表

回溯算法四例.doc

文档介绍

文档介绍:第三章回溯算法四例第一节回溯方法在程序设计中,,完成某一件事需要经过若干步骤,。问题是要在其中找出满足题目条件的一种或多种方法。这类问题一般只能借助搜索与回溯算法求解。回溯法的基本思想是:“试探着走”。如果试的不成功退回一步,再换一个办法试试。反复进行这种试探性选择与返回纠错过程,直到求出问题的解为止。回溯算法比前面介绍的其它方法复杂,但它是程序设计中最重要的基础算法之一。【主要思想】回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题。【算法框架】 1、问题的解空间:应用回溯法解问题时,首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个(最优)解。 2、回溯法的基本思想:确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。换句话说,这个结点不再是一个活结点。此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。【回溯步骤】(1)针对所给问题,定义问题的解空间;(2)确定易于搜索的解空间结构;(3)以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索;3、递归回溯:由于回溯法是对解空间的深度优先搜索,因此在一般情况下可用递归函数来实现回溯法如下:PROCEDURETRY(I:INTEGER);VARBEGINIFI>NTHEN输出结果ELSEFORJ:=下界TO上界DOBEGINX[I]:=H[J];IF可行{满足限界函数和约束条件}THENBEGIN置值;TRY(I+1);END;END;END;说明:I是递归深度;N是深度控制,即解空间树的的高度;可行性判断有两方面的内容:不满约束条件则剪去相应子树;若限界函数越界,也剪去相应子树;两者均满足则进入下一层;第二节例题分析例1【问题描述】有一个N*M的棋盘(2<=N<=50,2<=M<=50),如下图,在棋盘上左下角有一个中国象棋马,马走的规则为::当N,M给出之后,同时给出马起始的位置和终点的位置,:(N=10,M=10),(1,5)(起点),(3,5)(终点)有2条路径,(即由(1,5)

最近更新

如何在人力资源管理中提高决策的科学性 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页