动态规划初步.doc

目录
1、引言
2、动态规划的基本原理




3、动态规划解题的实际应用







官方教程
我的讲稿
1、引言
动态规划算法十分重要,其实质是分支思想和解决冗余,因此它与分支法和贪心法类似,他们都是将问题的实例分解为更小、相似的子问题,但是动态规划又有自己的特点。
贪心法的当前选择可能要以来于已经做出的选择,但不依赖还未做出的选择和子问题,因此他的特征是由顶向下,一步一步地做出贪心选择,但不足的是,如果当前选择可能要依赖子问题的解时,则难以通过局部的贪心策略达到全局最优解。相比而言,动态规划则可以处理不具有贪心实质的问题。
在用分支法解决问题时,由于子问题的数目往往是问题规模的指数函数,因此对时间的消耗太大。动态规划的思想在于,如果各个子问题不是独立的,不同的子问题的个数只是多项式数量级,如果我们能够保存已经解决的子问题的答案,而在需要的时候再找出已求得的答案,这样就可以避免大量的重复计算。由此而来的基本思路是:用一个表记录所有已解决的自问题的答案,不管该问题以后是否被用到,只要它被计算过,就将结果填入表中。所以动态规划思想实质是记忆化搜索的思想。
动态规划的思想是对于贪心法和分支法的一种折衷,它解决的问题往往不具有贪心算法的实质,但是各个子问题又不是完全零散的,这时候我们用一定的空间来换取时间,就可以提高解题的效率。
动态规划是对最优化问题的一种新的算法设计方法。由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题有不同特色的表示方法。
2、动态规划的基本原理

在现实生活中,有一类活动的过程,由于他的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要做出决策,从而使整个过程达到最佳的活动效果。因此各个阶段决策的选取不是任何确定的,它依赖于当前面临的状态,又影响以后的发展,当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线。这种把问题看作是一个前后关联且具有链装结构的多阶段过程,被称为多阶段决策问题,这种问题就称为多阶段决策问题。如图所示:
决策2
阶段n
状态1
决策1
决策n
状态0
状态2
阶段1
阶段2
状态2
例最短路径问题:如图所示的是一个带权有向的多段图,要求从A到D的最短路径的长度(下面简称最短距离)。
C1
C3
D1
A
B1
B3
B2
D2
E
C2
2
5
1
12
14
10
6
10
4
13
11
12
3
9
6
5
8
10
5
2

如果用穷举法,则从A到E一共有3×3×2=18条不同的路径,逐个计算每条路径的长度,总共需要进行4×18=72次加法计算;对18条路径的长度做两两比较,找出其中最短的一条,总共要进行18-1=17次比较。如果从A到C的站点有k个,则总共有3k-1×2条路径, 用穷举法求最短路径总共要进行(k+1)3k-1×2次加法,3k-1×2-1次比较。当k的值增加时,需要进行的加法和比较的次数将迅速增加。例如当k=10时,加法次数为433026次,比较39365次。
以上这求从A到E的最短路径问题,可以转化为三个性质完全相同,但规模较小的子问题,即分别从B1、B2、B3到E的最短路径问题。
记从Bi (i=1, 2, 3) 到E的最短路径为S(Bi),则从A到E的最短距离S(A)可以表示为:

同样,计算S(B1)又可以归结为性质完全相同,但规模更小的问题,即分别求C1,C2,C3到E的最短路径问题S(Ci) (i=1, 2, 3),而求S(Ci)又可以归结为求S(D1)和S(D2)这两个子问题。,在这个问题中,S(D1)和S(D2)是以知的,它们分别是:
S(D1)=5,S(D2)=2
因而,可以从这两个值开始,逆向递归计算S(A)的值。计算过程如下:
即
S(C1)=8 且如果到达C1,则下一站应到达D1;
S(C2)=7 且如果到达C2,则下一站应到达D2;
S(C3)=12 且如果到达C3,则下一站应到达D2;
由此,可以计算S(Bi):
即
S(B1)=20 且如果到达B1,则下一站应到达C1;
S(B2)=14 且如果到达B2,则下一站应到达C1;
S(B3)=19 且如果到达B3,则下一站应到达C2;
由此,可以计算