〖问题12〗欧几里德货郎担问题和bitonic旅行路线问题

《〖问题12〗欧几里德货郎担问题和bitonic旅行路线问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、〖问题12〗欧几里德货郎担问题和Bitonic旅行路线问题——信息学NOI联赛辅导专题NOI竞赛辅导王建德教练讲稿无后效性即一个问题被划分阶段后，阶段I中的状态只能由阶段I-1中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。如果把问题中的状态定义成图中的顶点，两个状态之间的转移定义为边，转移过程中的权值增量定义为边的权值，则这个问题实际上就是在一个“有向无环加权图”中寻找两个顶点路径的问题。因为无后效性，所以没有环路（否则，无论如何划分阶段，都可以出现后效性）。即这个图可以进行“拓扑排序”，可以以拓扑排序的顺序划分阶段。

2、〖问题12〗欧几里德货郎担问题和Bitonic旅行路线问题欧几里德货郎担问题是对平面给定的n个点确定一条连结各点的、闭合的游历路线问题。下图(a)给出了七个点问题的解。Bitonic旅行路线问题是欧几里德货郎担问题的简化，这种旅行路线先从最左边开始，严格地由左至右到最右边的点，然后再严格地由右至左到出发点，求路程最短的路径长度。下图（b）给出了七个点问题的解。把两条路中起始顶点相同的状态归于一个阶段，设为阶段[P1,P2]。Bitonic旅行路线问题设Dis[i，j]—阶段（i，j）中i至n和j至n的最短路长和；1.Dis[N,N]←0;{初始化动态规划数组}2.Fo

3、rI←N-1Downto13.DoDis[I,N]←I点至I+1点的距离+Dis[I+1,N];4.Dis[N,I]←Dis[I,N];5.ForI←N-2Downto16.DoForJ←N-1DowntoI+1{递推最小值}7.DoIfI+1

4、7}推出；而道路{2—3—6—7，4—5—7}属于阶段[2,4]，可由属于阶段[3,4]的道路{3—6—7，4—5—7}推出。如果以顶点表示阶推出关系表示边，那么，阶段[3,4]与阶段[2,4]对应的关系就如图所示解决“动态规划”问题的基本方法与步骤：1：确定问题的研究对象，即确定状态。2：划分阶段，确定阶段之间的状态转移方程。3：考察此问题现在可否用“动态规划”来解决：①：考察此问题是否具有“最优子结构”。②：考察此问题是否为“无后效性”。4：如果发现此问题目前不能用“动态规划”来解决，则应该调整相应的定义与划分，以达到可以用“动态规划”来解决。