滇池学院算法分析期末复习.pdfVIP

Yunnan University 1 动态规划的基本思想 动态规划(Dynamic Programming)算法与分治 法类似，其基本思想也是将待求解问题分解成 若干个子问题 经分解得到的子问题往往不是互相独立的 不同子问题的数目常常只有多项式数量级 保存已解决的子问题的答案，在需要时再找出 已求得的答案 可以避免大量重复计算，从而得到多项式时间 算法 2 图问题中的动态规划法 TSP问题 多段图的最短路径问题 3 TSP问题 TSP问题是指旅行家要旅行n个城市，要求各个城市经 历且仅经历一次然后回到出发城市，并要求所走的路 程最短。  各个城市间的距离可以用代价矩阵来表示，如果(i,j） E，则c ＝∞。图6.6所示是一个带权图的代价矩阵。 ij ∞ 3 6 7 C= 5 ∞ 2 3 6 4 ∞ 2 3 7 5 ∞ 图6.6 带权图的代价矩阵 4 设s,s ,s ,…,s ,s是从s出发的一条路径长度最短的 1 2 p 简单回路，假设从s到下一个城市s 已经求出，则问 1 题转化为求从s 到s的最短路径，显然s ,s ,…,s ,s 1 1 2 p 一定构成一条从s 到s的最短路径，如若不然，设 1 s ,r ,r ,…,r ,s是一条从s 到s的最短路径且经过n-1 1 1 2 q 1 个不同城市，则s,s ,r ,r ,… r ,s将是一条从s出发 1 1 2 q 的路径长度最短的简单回路且比s,s ,s ,…,s ,s要短， 1 2 p 从而导致矛盾。所以，TSP问题满足最优性原理。 5 假设起始顶点是l，令d(i, V′)表示从顶点i出发经过V′ 中各个顶点一次且仅一次，最后回到起始点1的最短路 径长度，开始时，V′＝V －{1}，于是，TSP问题的动态 规划函数为： d(i,V′)=min{c +d(k,V －{k})}(k ∈V′) （式6.5） ik d(k,{})=c (k≠1) （式6.6） k1