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

本文格式为Word版，下载可任意编辑——北航动态规划03级考试题目算法分析讲课张引第一小节动态规划问题

——最短路径问题

一在正式提出动态规划法前我们先看一个数学例子：

例1：在x1+x2+x3+…+xn=a是约束条件下，求z?x1?x2???xn的极大值.令f1(a)?maxx?a(0?x?a)f2(a)?max(x?f1(a?x))?max(x?a?x)令y?x?a?x且dy?1?dx2x12a?x?a?x?x2x(a?x)?0

可得a?x=x,所以x=a/2

aa??2a22同理f3(a)?max(x?f2(a?x)?max(x?2(a?x))

故f2(a)?令y?x?2(a?x)

dy12a?x?2x????0dx2x2a?x2x(a?x)所以a?x=2x,x=a/3所以f3(a)=f3(a)?111a?2a?3a?3a333用数学归纳法可以证明：fn(a)=na,x1=x2=x3=…=xn=证明：1：n=1…

2：设fn(a)=na,x1=x2=x3=…=xn=fn+1(a)=max(令y=y’=

anx+fn(a-x))=max(

a成立，则nx?n(a?x))

x?n(a?x)

1n2a?x2xan?1=

a?x?nx2x(a?x)?0

所以nx=a-x,(n+1)x=ax=

fn+1(a)=

aa+n=(n?1)an?1n?1我们方才的解题策略是：“摸着石头过河〞，f2利用f1的结果，f3又利用f2的结果。。。。。。

类似于游戏中的一个勇士击败了一些敌人后得到一件武器，然后去击败另一个强大一些的对手，得到一件更好的武器，接着击败更强大的敌人。。。。。最终取得胜利。。。

在实际生活中，有这么一类问题，它们的活动过程可分为若干个阶段，而且在任一阶段后的行为仅依靠于第I阶段的过程状态，而与I阶段之前的过程如何达到这种过程如何达到这种状态的方式无关，这样的过程就构成了一个多阶段决策过程。在50年代，贝尔曼（RichardBellman）等人根据这类问题的多阶段决策的特性，提出了解决问题的“最优性原理〞从而创立了最优化问题的一种最新的算法设计方法——动态规划。分治法和动态规划法的比较

动态规划算法与分治法类似，其根本思想也是将待求解问题分解成若干个子问题，先求第1页

算法分析讲课张引

解子问题，然后从这些子问题的解得到原问题的解，与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是相互独立的.以从16个数据中找出最大者为例，说明分治法的“静〞和动态规划法的“动〞的区别。

下面我们以具体的例子来说明如何运用动态规划算法来求解问题，并分析可用动态规划算法解的问题的所应具备的一般特征。

对教材68页上的里子给予简要说明（由于书上的文字表达有些含混晦涩，对符号的说明不明了）

y2K3P1S2UF

下面精讲一个例子212232G3L4Q5TC34123DHMR22134A323

1

O

1.介绍这个图的特点…..从而说明从O到A的最短路径必由7段而不是更多或更少段组成。

其行进路线必然是x和y单调递增的（非严格单调）。从O(0,0)到U（4，3）点的每一

4条路径对应于由4个x上的和3个y上的字符构成的字符串，这种字符串的数目为C7=35.

假使采用穷举法进行探寻，需要进行35*6=210次加法，34次比较。

2.下面我们采用动态规划法来解决这一问题。令O为起点到U的最短距离为Do，以A为

起点到U的最短距离为DA---,用dij表示（i,j）边的长度。显然Ds=dsu=2,Dt=dTU=3,

DQ=min{2+2,5+3}=4DP=1+Ds=1+2=3DR=3+DT=3+3=6

DL=min{Dlq+DQ,dLP+DP}=min{4+DQ,2+Dp}=min{4+4,2+3}=5Dk=3+Dp=3+3=6

DM=min{2+DQ,4+DR}=min{2+4,4+6}=6DN=4+DR=4+6=10DF=2+DK=2+6=8

DG=min{1+DK,3+DL}=min{1+6,3+5}=7DH=min{1+5,1+6}=6

DJ=min{3+DM,3+DN}=min{3+6,3+10}=9DC=min{2+DF,2+DG}=min{2+8,2+7}=9DD=min{4+DG,2+DH}=min{4+7,2+6}=8DE=min{1+DH,2+DJ}=min{1+6,2+9}=7DA=min{3+DC,2+DD}=min{3+9,2+8}=10DB=min{2+DD,3+DE}==min{2+8,3+7}=10Do==min{1+DB,2+DA}=min{1+10,2+10}=11

共进行了29次加法，12次比较。由Do=1+DB=11回溯，可得到最短路径为

O—>B-?D->H?L—>P-?S-?UO-?B-?E-?H-?L-?P-?S-?U

推广到x轴m段y轴n段的情形：用动态规划法需要做2mn+（m+n-2）次加法，mm次比第2页

算法分析讲课张引

较；而假使用穷举法，需要

若m=n,动态规划法要做2n2+2n-2次加法，n2次比较，因此繁杂度为O(n2);而穷举法需要

(m?n)!(m?n)!*(m?n?1)次加法，?1次比较。m!n!m!n!(2n)!(2n)!*(2n?1)次加法，?1次比较，>O(n2n+1)。n!n!n!n!其次小节动态规划问题

——货郎担问题

1.动态规划方法的思想

动态规划是一种将问题实例分解为更小的、相像的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。2.货郎担问题：

某售货员要到若干个村庄售货，各村庄之间的路程是已知的，为了提高效率，售货员决定从所在商店出发，到每个村庄售一次货然后返回商店，问他应选择一条什么路线才能使所走的总路程最短？

实质从某点出发,遍历其余点,再回到原点,求总路径消耗最少的路线.

[例]设共有4个要经过的点---1，2，3，4各个点之间的花费如下：1>2:10;1>3:15;1>4:20;2>1:5;2>3:9;2>4:10;3>1:6;3>2:13;3>4:12;4>1:8;4>2:8;4>3:9;（最短路径：1>2>4>3>1））

12254678557885343.问题的解决1.)问题的描述:?T(V1;V)表示从V1出发,经过顶点集合V中的点各一次,再回到点

V1的最短路径.第3页

算法分析讲课张引

2.)动态规划函数:

T(vi;V)=min{dij+T(vj;V-{vj})}(vj属于V)

?T(vi;V):就是从V中任何一点vi出发,经过V中的点各一次,再回到

点vi的最短路径.

?Dij:表示从点vi出发,到某点vj的花费(有方向性).

?注:这是一个递归定义的函数,关键是每次的函数T(vi;V)它所处理的点

集逐渐减少.

3.)实例:(如上图)求从v1出发的货郎担问题.解:T(v1;V)=T(v1;v1,v2,v3,v4)

=min{d12+T(v2;v3,v4),d13+T(v3;v2,v4),d14+T(v4;v2,v3)}

//实例意义:初始的货郎担问题是从点v1出发,涉及其余3点

v2,v3,v4;那依照动态规划“分而治之〞的思想(这里就是把问题规模缩小,而问题的数量可多一些),我们可先计算分别从v2,v3,v4出发,涉及(v2,v3,v4)三点的三条货郎担路线的路耗,再各自加上相应的dij,这样,最终就得到3个总路耗,再做一个min运算,就可求出初始问题的解.

T(v2;v3,v4)=min{d23+T(v3;v4),d24+T(v4;v3)}T(v3;v4)=d34+T(v4,@)T(v4;v3)=d43+T(v3,@)T(v4,@)=d41T(v3,@)=d31

T(v3;v4)=d34+d41=6+9=15T(v4;v3)=d43+d31=8+8=16

T(v2;v3,v4)=min{d23+d34+d41,d24+d43+d31}=min{7+6+9,6+8+8}=22

同理:

T(v3;v2,v4)=min{d32+d24+d41,d34+d42+d21}=min{5+6+9,6+5+4}=15

T(v4;v2,v3)=min{d42+d23+d31,d43+d32+d21}=min{5+7+8,8+5+4}=17则最终:T(v1;v1,v2,v3,v4)

=min{d12+T(v2;v3,v4),

d13+T(v3;v2,v4),

d14+T(v4;v2,v3)}

=min{2+22,5+15,8+17}=20所选的路线是:1->3->4->2->1

第三小节动态规划问题

——投资问题

一问题描述：投资问题就是考虑如何把有限资源分派给若干个工程的问题。

二给定条件：1.资源总数（设为a）

2.工程个数（设为n）3.每项工程投资的利润（不同数目的投资所获得的利润不同），用向量Gi(1≦i第4页

算法分析讲课张引

≦n)表示。n三问题求解：求出一个a的分划x1,x2,…..,xn,0≦xi≦a,且∑xi≦a,使得以下式表示的利润为最大：i=1nG(a)=∑Gi(xj)0≦xj≦a

i=1

其中Gi(xj)是把资源xj分派给第I项工程能获得的最大利润。

四问题分析：

i）若Gi是x的线性函数，则为线性规划问题。

ii）若Gi不是线性函数，则要用动态规划求最正确分派。

用总量为a的资金在n个项目上进行投资以取得最大的利润，可以转化为下述的问题：

将总量资金a分为两部分z(0≦z≦a)及a-z，分别用在第n个项目及剩下的n-1个项目上进行投资，获得的最大利润G(a)=max(第n个项目上资金量为z的利润与用a-z的资金在n-1个项目上投资的最大利润之和)。这样问题就转化为〞求用a-z的资金在n-1个项目上投资的最大利润〞，与我们的原问题〞求总量为a的资金在n个项目上进行投资以取得最大的利润〞性质完全一致，仅仅是问题的规模比原问题少了一个项目，如此将问题的规模细化下去，一直到项目数为1为止，则问题迎刃而解。我们在对原问题进行〞分而治之〞的过程当中，最终实现了最优化的求解。

五问题解决方案：设fi(x)：前i个项目共投资资金x所产生的最大利润；di(x)：产生fi(x)在项目i上的资金数。

由上分析可给出投资问题的动态规划函数方程：f1(x)=G1(x);

d1(x)=xx=0,1……a

fi(x)=max[Gi(z)+fi-1(x-z)]z=0,1……x;x=0,1……adi(x)=产生fi(x)的z值i=2,3…..n;

六问题举例：设有8（万元）的投资可分给3个项目，每个项目的利润函数如下表（一）所示：表（一）利润函数表x012345678G1(x)0