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)

最近更新

充分利用经济杠杆作用——企业内部经营承包的.. 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页