北航 动态规划03级考试题目.doc

算法分析讲课 张 引 第 PAGE 9页 第一小节 动态规划问题 ——最短路径问题 一 在正式提出动态规划法前我们先看一个数学例子： 例1：在 x+x2+x3+…+xn =a是约束条件下，求的极大值. 令 ( 0 ) 令 且 可得a?x=x, 所以 x=a/2 故 同理 令 所以 a?x=2x , x=a/3 所以 f3(a)= 用数学归纳法可以证明：fn(a) = , x1=x2=x3=…=xn= 证明：1：n=1 … 2：设fn(a) = , x1=x2=x3=…=xn= 成立，则 fn+1(a)=max(+fn(a-x))=max( ) 令 y= y’== 所以 nx=a-x ,(n+1)x=a x= fn+1(a)=+n= 我们刚才的解题策略是：“摸着石头过河”，f2 利用f1的结果，f3又利用f2的结果。。。。。。类似于游戏中的一个勇士打败了一些敌人后得到一件武器，然后去打败另一个强大一些的对手，得到一件更好的武器，接着打败更强大的敌人。。。。。最后取得胜利。。。 在实际生活中，有这么一类问题，它们的活动过程可分为若干个阶段，而且在任一阶段 后的行为仅依赖于第I阶段的过程状态，而与I阶段之前的过程如何达到这种过程如何达到这种状态的方式无关，这样的过程就构成了一个多阶段决策过程。在50年代，贝尔曼（Richard Bellman）等人根据这类问题的多阶段决策的特性，提出了解决问题的“最优性原理”从而创建了最优化问题的一种必威体育精装版的算法设计方法——动态规划。 分治法和动态规划法的比较 动态规划算法与分治法类似，其根本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的.以从16个数据中找出最大者为例，说明 分治法的“静”和动态规划法的“动”的区别。 下面我们以具体的例子来说明如何运用动态规划算法来求解问题，并分析可用动态规划算法解的问题的所应具备的一般特征。 对教材68页上的里子给予简要说明（因为书上的文字叙述有些含混晦涩，对符号的说明不清晰） y 1 O A F 2 K 3 P 1 S 2 U 下面精讲一个例子 2 1 2 2 3 C 2 G 3 L 4 Q 5 T 3 4 1 2 3 D H M R 2 2 1 3 4 3 2 3 介绍这个图的特点…..从而说明从O到A的最短路径必由7段而不是更多或更少段组成。其行进路线必然是x和y单调递增的（非严格单调）。从O(0,0)到U（4，3）点的每一条路径对应于由4个x上的和3个y上的字符构成的字符串，这种字符串的数目为C=35.如果采用穷举法进行有哪些信誉好的足球投注网站，需要进行35*6=210次加法，34次比较。 下面我们采用动态规划法来解决这一问题。令O为起点到U的最短距离为Do，以A为起点到U的最短距离为DA - - - ,用dij表示（i , j）边的长度。 显然Ds=dsu=2,Dt=dTU=3, DQ=min{2+2,5+3}=4 DP=1+Ds=1+2=3 DR=3+DT=3+3=6 DL=min{Dlq+DQ,dLP+DP}=