问题12欧几里德货郎担问题和Bitonic旅行路线问题.doc_第1页
问题12欧几里德货郎担问题和Bitonic旅行路线问题.doc_第2页
问题12欧几里德货郎担问题和Bitonic旅行路线问题.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

问题12欧几里德货郎担问题和Bitonic旅行路线问题信息学NOI联赛辅导专题NOI竞赛辅导 王建德教练讲稿 无后效性即一个问题被划分阶段后，阶段I中的状态只能由阶段I-1中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。如果把问题中的状态定义成图中的顶点，两个状态之间的转移定义为边，转移过程中的权值增量定义为边的权值，则这个问题实际上就是在一个“有向无环加权图”中寻找两个顶点路径的问题。因为无后效性，所以没有环路（否则，无论如何划分阶段，都可以出现后效性）。即这个图可以进行“拓扑排序”，可以以拓扑排序的顺序划分阶段。问题12欧几里德货郎担问题和Bitonic旅行路线问题欧几里德货郎担问题是对平面给定的n个点确定一条连结各点的、闭合的游历路线问题。下图(a)给出了七个点问题的解。Bitonic旅行路线问题是欧几里德货郎担问题的简化，这种旅行路线先从最左边开始，严格地由左至右到最右边的点，然后再严格地由右至左到出发点，求路程最短的路径长度。下图（b）给出了七个点问题的解。把两条路中起始顶点相同的状态归于一个阶段，设为阶段P1,P2。Bitonic旅行路线问题设 Disi，j阶段（i，j）中i至n和j至n的最短路长和；1. DisN,N 0; 初始化动态规划数组2. For IN-1 Downto 1 3. Do DisI,NI点至I+1点的距离+DisI+1,N;4. DisN,IDisI,N;5. For IN-2 Downto 16. DoFor JN-1 Downto I+1 递推最小值7. Do If I+1J Then NowDisI+1，J+ I点至I+1点的距离8. Else Now9. Now10. DisI,JNow;11. DisJ,INow;12. 输出对于欧几里德货郎担问题,阶段与阶段之间没有什么必然的“顺序”。如道路3257,467属于阶段3,4，可由属于阶段2,4的道路257，467推出；而道路2367，457属于阶段2,4，可由属于阶段3,4的道路367，457推出。如果以顶点表示阶推出关系表示边，那么，阶段3,4与阶段2,4对应的关系就如图所示解决“动态规划”问题的基本方法与步骤：1：确定问题的研究对象，即确定状态。2：划分阶段，确定阶段之间的状态转移方程。3：考察此问题现在可否用“动态规划”来解决： ：考察此问题是否具有“最优子结构”。 ：考察此问题是否为“无后效性”。
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论