- 1、本文档共18页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
TSP问题之动态规划法 提纲 什么是TSP问题 一般的解决办法——穷举法 动态的解决办法 什么是动态规划法 使用动态规划法的条件 动态规划法解决常见问题 动态规划法(一) 动态规划法: 定义:将每个子问题只求解一次,并将其解保存在一个表格中,当需要再次求解此子问题时,只是简单地通过查表获得该子问题的解,从而避免了大量的重复计算。 特点:最优子结构、自底向递归、子问题相互重叠。 动态规划法使用的条件:问题符合最优性原理 动态规划法(二) 最优性原理: 对于一个具有n个输入的最优化问题,其求解过程往往可以划分为若干个阶段,每一阶段的决策仅依赖于前一阶段的状态,由决策所采取的动作使状态发生转移,成为下一阶段决策的依据。 无论过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。 原理告诉我们,一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成。 一般来说,如果所求解问题对于最优性原理成立,则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获取各阶段问题的递推关系式。 动态规划法(三) 动态规划法步骤 (1)分段:将原问题分解为若干个相互重叠的子问题; (2)分析:分析问题是否满足最优性原理,找出动态规划函数的递推式; (3)求解:利用递推式自底向上计算,实现动态规划过程。 动态规划法解决的常用问题(一) 斐波那契数 动态规划法解决的常用问题(二) 多段图的最短路径问题 动态规划法解决的常用问题(三) POJ 1163 数字三角形 问题描述:在上面的数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可,不必给出具体路径 动态规划法解决的常用问题(四) 近似串匹配问题 最长公共子序列问题 0/1背包问题 * 主讲人:葛忠雷 TSP问题 TSP问题的描述: 旅行家要旅行n个城市,要求经历各个城市且仅经历一次,然后回到出发城市,并要求所走的路程最短。 0 1 3 2 3 6 6 7 5 3 7 2 6 3 2 5 TSP问题——穷举法解决 a b d c 2 3 5 1 8 7 否 18 a-d-c-b-a 6 否 23 a-d-b-c-a 5 是 11 a-c-d-b-a 4 否 23 ac-b-d-a 3 是 11 a-b-d-c-a 2 否 18 a-b-c-d-a 1 是否最短 路径长度 路径 序号 TSP问题——动态规划 假设找出的一条最短的回路:S0?S1?S2 ? S3?S0 我们可以利用结论: “S1?S2 ? S3?S0 “必然是从S1 到S0通过其它各点的一条最短路径。(如果不是,则会出现矛盾) S0 S1 S3 S2 Length(总回路) = Length(S0?S1) + Length(S1? S2 ? S3?S0) 可以把问题简化: 把求通过各点的一条最短的回路 ? 求解从某个(任意)确定点到回路中最后一个点的最短路径 TSP问题——动态规划 从上面的公式把总回路长度分解: Length(回路) = Min{ Length(0?1) + Length(1?…?0), Length(0?2) + Length(2?…?0), Length(0?3) + Length(3?…?0) } 规范化地表达上面的公式 d(i,V) 表示从i点经过点集V各点一次之后回到出发点的最短距离 d(i,V‘) = min {Cik+d(k,V-{k})} (k∈V) d(k,{ }) = Cik (k≠i) 其中,Cik表示i?k的距离 0 1 3 2 3 6 6 7 5 3 7 2 6 3 2 5 从城市0出发,经城市1、2、3然后回到城市0的最短路径长度是: d(0, {1, 2, 3})=min{ C01+ d(1, { 2, 3}), C02+ d(2, {1, 3}), C03+ d(3, {1, 2}) } 这是最后一个阶段的决策,它必须依据d(1, { 2, 3})、 d(2, {1, 3})和d(3, {1, 2})的计算结果,而: d(1, {2, 3})=min{C12+d(2, {3}), C13+ d(3, {2})} d(2, {1, 3})=min{C21+d(1, {3}), C23+ d(3, {1})} d(3, {1, 2})=min{C31+d(1, {2}), C32+ d(2, {1})} 继续写下去: d(1, {2})= C12+d(2, {}) d(2, {3})
您可能关注的文档
- study pln攻略.doc
- STM的原理和应总结.ppt
- SQE实战基础培.ppt
- street msic 外研 选修六Module 4.ppt
- SWM工法桩施工织设计.doc
- SWOT分析PP(最好的SWOT模板)(免费).ppt
- SWOT分析法PT详解.ppt
- SPSS二项Loistic回归.ppt
- SYB创业培训第步:企业的人员组织.ppt
- SYB创业计划书文.doc
- 浙教版2021-2022学年度七年级数学上册模拟测试卷 (59).docx
- 浙教版2021-2022学年度七年级数学上册模拟测试卷 (258).docx
- 浙教版 2021-2022学年度七年级数学下册模拟测试卷 (3593).docx
- 浙教版2021-2022学年度七年级数学上册模拟测试卷 (16).docx
- 浙教版2021-2022学年度七年级数学上册模拟测试卷 (133).docx
- 浙教版2021-2022学年度七年级数学上册模拟测试卷 (84).docx
- 浙教版2021-2022学年度七年级数学上册模拟测试卷 (162).docx
- 浙教版2021-2022学年度七年级数学上册模拟测试卷 (60).docx
- 浙教版2021-2022学年度七年级数学上册模拟测试卷 (35).docx
- 浙教版2021-2022学年度七年级数学上册模拟测试卷 (44).docx
文档评论(0)