第六章动态规划

1、第六章 动态规划6.1 动态规划的思想方法6.1.1 动态规划的最优决策原理活动过程划分为若干个阶段，每一阶段的决策，依赖于前一阶段的状态，由决策所采取的动作，使状态发生转移，成为下一阶段的决策依据。图6.1 动态规划的决策过程最优性原理：无论过程的初始状态和初始决策是什么，其余决策都必须相对于初始决策所产生的状态，构成一个最优决策序列。令最优状态为，由此倒推：最优决策序列，状态转移序列：赖以决策的策略或目标，称为动态规划函数。整个决策过程，可以递归地进行，或用循环迭代的方法进行。动态规划函数可以递归地定义，也可以用递推公式来表达。最优决策是在最后阶段形成的，然后向前倒推，直到初始阶段；而决策

2、的具体结果及所产生的状态转移，却是由初始阶段开始进行计算的，然后向后递归或迭代，直到最终结果。6.1.2 动态规划实例、货郎担问题例6.1 货郎担问题。在有向赋权图中，寻找路径最短的哈密尔顿回路问题。一、解货郎担问题的过程令：从顶点出发，经中各顶点一次，最终回到顶点的最短路径的长度，开始时，。动态规划函数：（6.1.1）（6.1.2）4个城市的费用矩阵是：根据（6.1.1）式，由城市1出发，经城市2,3,4然后返回1的最短路径长度为：它必须依据的计算结果：这一阶段的决策，又必须依据下面的计算结果：再向前倒推，有：有了这些结果，再向后计算，有：路径顺序是：2,3,4,1路径顺序是：3,2,4,1

3、路径顺序是：4,3,2,1最后：路径顺序是：1,2,3,4,1图6.2 货郎担问题求解过程示意图二、复杂性分析令是计算从顶点出发，返回顶点所需计算的形式为的个数。开始计算时，集合中有个城市。以后，在计算时，集合的城市数目，在不同的决策阶段，分别为,0。在整个计算中，需要计算大小为的不同城市集合的个数为，。因此，总个数为：当集合中的城市个数为时，为计算，需次加法， 次比较。从城市出发，经其它城市再回到，总的运算时间为：由二项式定理：令；可得：则用动态规划方法求解货郎担问题，总的花费为：6.2 多段图的最短路径问题6.2.1 多段图的决策过程定义6.1 有向连通赋权图，顶点集合划分成个不相交的子集

4、，使得中的任一边，必有，。称为多段图。令，称为源点，为收点。多段图的最短路径问题，是求从源点到达收点的最小花费的通路一、顶点编号：根据多段图的个不相交的子集，把多段图划分为段，每一段包含顶点的一个子集。把顶点集合中的所有顶点，按照段的顺序进行编号。子集中的顶点互不邻接，它们之间的相互顺序无关紧要。顶点个数为，顶点的编号为0，则收点的编号为，对中的任何一条边，顶点的编号小于顶点的编号。二、决策过程数组元素：存放顶点到达收点的最小花费数组元素：存放顶点到达收点的最小花费通路上的前方顶点编号数组：存放从源点出发，到达收点的最短通路上的顶点编号第一阶段，确定第段的所有顶点到达收点的花费最小的通路。第二

5、阶段，用第一阶段的信息，确定第段的所有顶点到达收点的花费最小的通路。如此依次进行，直到最后确定源点到达收点的花费最小的通路。最后，从源点的信息中，确定它的前方顶点编号，从的信息中，确定的前方顶点编号，如此递推，直到收点。动态规划函数：（6.2.1）（6.2.2）三、步骤：(n为顶点个数)1. 对所有的，把初始化为最大值，初始化为-1；初始化为0；2. 令；3. 根据（6.2.1）式和（6.2.2）式计算和；4. ，若，转3；否则，转5；5. 令，；6. 如果，算法结束；否则，转7；7. ，；转6；例6.2 求解图6.3所示的最短路径问题。图6.3 动态规划方法求解多段图的例子(i表示顶点编号)

6、： ： ： ： ： ： ： ： ： 最后，得到最短的路径为0，2，3，5，8，9，费用是15。6.2.2 多段图动态规划算法的实现struct NODE /* 邻接表结点的数据结构 */ intv_num;/* 邻接顶点的编号 */Typelen;/* 邻接顶点与该顶点的费用 */struct NODE *next;/* 下一个邻接顶点 */;struct NODE noden;/* 多段图邻接表头结点 */Typecostn;/* 在阶段决策中,各个顶点到收点的最小费用 */introuten;/* 从源点到收点的最短路径上的顶点编号 */intpathn;/* 在阶段决策中,各个顶点到收点

7、的最短路径上的前方顶点编号 */算法6.1 多段图的动态规划算法输入：多段图邻接表头结点node,顶点个数n输出：最短路径费用,最短路径上的顶点编号顺序route 1. template <class Type> 2. #define MAX_TYPE max_value_of_Type 3. #define ZERO_TYPE zero_value_of_Type4. Type fgraph(struct NODE node,int route,int n)5. 6. int i;7. struct NODE *pnode;8. int *path = new intn;9. T

8、ype min_cost,*cost = new Typen;10. for (i=0;i<n;i+) 11. costi = MAX_TYPE; pathi = -1; roueti = 0;12. 13. costn-1 = ZERO_TYPE;14. for (i=n-2;i>=0;i-) 15. pnode = nodei->next;16. while (pnode!=NULL) 17. if (pnode->len+costpnode->v_num<costi) 18. costi = pnode->len + costpnode->

9、v_num;19. pathi = pnode->v_num;20. 21. pnode = pnode->next;22. 23. 24. i = 0;25. while (routei!=n-1)&&(pathi!=-1) 26. i+;27. routei = pathroutei-1;28. 29. min_cost = cost0;30. delete path; deleye cost;31. return min_cost; 32. 时间复杂性：1013行的初始化，花费时间。1423行局部决策，假定图的边数为，则花费时间为。2428行形成最优决策序列，

10、若多段图分为段，花费时间。空间复杂性是。6.3 资源分配问题资源总数为，工程个数为。给每项工程投入的资源不同，所获得的利润也不同。要求把总数为的资源，分配给个工程，以获得最大利润的分配方案。6.3.1 资源分配的决策过程一、目标函数和约束方程资源划分为个相等的部分，每份资源为，为整数。利润函数： 份资源分配给第个工程所得到的利润，已知分配份资源给所有工程，所得到的利润总额为：使最大的分配方案： 二、决策过程各个工程按顺序编号，阶段划分： ：把份资源分配给前个工程时，所得到的最大利润，：使最大时，分配给第个工程的资源份额。在第一阶段，只把份资源分配给第一个工程，有：（6.3.1）在第二阶段，只把

11、份资源分配给前面两个工程，有：一般的，在第阶段，把份资源分配给前面个工程，有：（6.3.2）令第阶段的最大利润为，则：（6.3.3）设是使达最大时，分配给前面个工程的资源份额，则：（6.3.4）在每个阶段，把所得到的所有局部决策值,保存起来。最后，在第阶段结束之后，令全局的最大利润为，则：（6.3.5）在全局最大利润下，所分配工程项目的最大编号（即所分配工程项目的最大数目）为，则：（6.3.6）分配给前面个工程的最优份额为：（6.3.7）分配给第个工程的最优份额为：分配给其余个工程的剩余的最优份额为：由此回溯，得到分配给前面各个工程的最优份额的递推关系式：（6.3.8）由上面的决策过程，可以把

12、求解资源分配问题，划分为下面四个步骤：1. 按(6.3.1)(6.3.2)式，对各个阶段，各个不同份额的资源，计算及；2. 按(6.3.3)(6.3.4)式，计算各个阶段的最大利润，及获得此最大利润的分配份额；3. 按(6.3.5)(6.3.6) (6.3.7)式，计算全局的最大利润，总的最优分配份额,及编号最大的工程项目；4. 按(6.3.8)式递推计算各个工程的最优分配份额。例6.3 有8个份额的资源，分配给3个工程，其利润函数如下： x0123456780426404550515253051540607073747505154080909598100求资源的最优分配方案。解 在第一阶段，

13、只把资源的份额分配给第一个工程，由(6.3.1)式，有： x0123456780426404550515253012345678其次，把资源的份额分配给前面两个个工程，当，显然有：，；当，由(6.3.2)式有：当，有：类似地计算时的及的值，有：x012345678052640607086100110010045445同样，计算出及的值，有：x0123456780526408090106120140010045444第二步，按(6.3.3)(6.3.4)式，求各个阶段的最大利润，及在此利润下的分配份额，有：第三步，按(6.3.5)(6.3.6) (6.3.7)式，计算全局的最大利润，最大的工程数

14、目、及总的最优分配份额，有：第四步，按(6.3.8)式计算各个工程的最优分配份额，有：最后的决策结果：分配给第2、3工程各4个份额，可得最大利润140。6.3.2 资源分配算法的实现数据结构。下面的数据用于算法的输入：intm;/* 可分配的资源份额 */intn;/* 工程项目个数 */TypeGnm+1;/* 各项工程分配不同份额资源时可得到的利润表 */下面的数据用于算法的输出：Typeoptg;/* 最优分配时所得到的总利润 */intoptqn;/* 最优分配时各项工程所得到的份额 */下面的数据用于算法的工作单元：Typefnm+1;/* 前i项工程分配不同份额资源时可得到的最大利

15、润 */intdnm+1;/* 使fix最大时,第i项工程分配的份额 */Typegn;/* 只分配给前i项工程时,可得到的最大利润 */intqn;/* 只分配给前i项工程时,第i项工程最优分配份额 */intoptx;/* 最优分配时的资源最优分配份额 */intk;/* 最优分配时的工程项目的最大编号 */算法6.2 资源分配算法输入：工程项目个数n, 可分配的资源份额m, 各项工程分配不同份额资源时可得到的利润表G输出：最优分配时所得到的总利润optg, 最优分配时各项工程所得到的份额optq 1. template <class Type> 2. Type allot_r

16、es(int n,int m,Type G,int optq) 3. 4. int optx,k,i,j,s; 5. int *q = new intn;/* 分配工作单元 */ 6. int (*d)m+1 = new intnm+1; 7. Type (*f)m+1 = new Typenm+1; 8. Type *g = new Typen; 9. for (j=0;j<=m;j+) /* 第一个工程的份额利润表 */10. f0j = G0j; d0j = j;11. 12. for (i=1;i<n;i+) /* 前i个工程的份额利润表*/13. fi0 = Gi0 +

17、fi-10;14. di0 = 0;15. for (j=1;j<=m;j+) 16. fij = fi0; dij = 0;17. for (s=0;s<=j;s+) 18. if (fij<Gis+fi-1j-s) 19. fij = Gis + fi-1j-s;20. dij = s; 21. 22. 23. 24. 25. for (i=0;i<n;i+) /* 前i个工程的最大利润和最优分配份额 */24. gi = fi0; qi = 0;25. for (j=1;j<=m;j+) 26. if (gi<fij) 27. gi = fij; qi

18、 = j;28. 29. 30. 31. optg = g0; optx = q0; k = 0;32. for (i=1;i<n;i+) /* 全局的最大利润和最优分配份额 */33. if (optg<gi) /* 以及最大数目的工程项目及其编号*/34. optg = gi; optx = qi; k = i;35. 36. 37. if (k<n-1) /* 最大编号之后的工程项目不分配份额 */38. for (i=k+1;i<n;i+)39. optqi = 0;40. for (i=k;i>=0;i-) /* 给最大编号之前的工程项目分配份额 */4

19、1. optqi = dioptx;42. optx = optx optqi;43. 44. delete q; delete d; /* 释放工作单元 */45. delete f; delete g; 46. return optg;/* 返回最大利润 */47. 时间复杂性：911行执行一个循环，花费时间；1224行执行一个三重循环，花费；2530行花费时间；3136行花费时间；空间复杂性是。6.4 设备更新问题设备每年的运转都可为公司创造利润收入，设备的性能随使用年限的增加而变坏，导致收入减少，维修费增加，利润下降。设备的更新，需付出一笔经费，但可增加利润收入。设备的更新问题是确定设

20、备的最优更新策略，使得在一个确定期限里，为公司创造最大的利润。6.4.1 设备更新问题的决策过程设备更新问题的有关数据如表6.1所示。I = 0列，表明现有设备的有关数据；I = 1列，表示第一年购买的设备的有关数据 其余类推；使用年限：第0列：当年的有关数据，第一列：使用一年后的有关数据，其余类推；利润、维修费用、更新费用：在第年购买的设备，使用了年后，可以创造的利润、必须付出的维修费用、以及进行更新时需要付出的费用。表6.1 设备更新的有关数据购买时间I = 0I = 1I = 2I = 3I = 4I = 5使用年限2 3 4 5 6 0 1 2 3 4 0 1 2 30 1 2 0 1

21、0利 润13 12 11 10 9 16 15 14 13 1217 16 15 14 18 17 1619 1820维修费用2 3 4 4 5 1 1 2 2 31 1 2 21 1 21 11更新费用25 26 27 28 2920 22 24 25 26 20 22 24 2520 22 2421 2221变量和函数：第年购买的设备使用了年后，在第年所创造的利润；第年购买的设备使用了年后，在第年所付出的维修费用；第年购买的设备使用了年后，在第年进行更新的费用；使用了年后的设备，第年被更新，在第年及其以后的年份所创造的总利润（在今后的年份里，设备还可能被更新）；使用了年后的设备，第年继续使

22、用，在第年及其以后的年份所创造的总利润（在今后的年份里，设备还可能被更新）；使用了年后的设备，在第年及其以后的年份里，所创造的总利润；对使用了年后的设备，在第年所作出的更新设备、或保留继续使用的决策；以现有设备为基础，在第年作出的更新设备、或保留继续使用的最优决策；现有设备已经使用了年。则设备更新问题表示为在今后年里，使得最大的最优决策序列，。对使用了年后的设备，第年决定更新，则利润函数如下：（6.4.1）如果第年决定保留继续使用，则有利润函数如下：（6.4.2）于是，可以定义如下的规划函数：（6.4.3）（6.4.4）假定，所要决策的年限为年，对所有的，令（6.4.5）阶段划分：把年划分为个

23、阶段。第阶段，设备的使用年限为。计算，确定；第阶段，设备的使用年限为。计算,确定；依此类推，第一阶段，设备的使用年限，只能为，计算，并确定。第一年的决策由作出，如果是买，则第二年的决策，应由作出；如果是留，则应由作出。决策序列的递推公式：（6.4.6）例6.4 设备已使用2年，按照表6.1的数据，确定5年内的设备更新决策，及在此决策下的最大利润。假定，用数组和分别存放和的值，按照上面所述步骤，计算和，得到下面的表。表6.2 例6.4中各年限可得利润及决策f1D=41 rf21=46 rf21+D=30 bf31=40 rf32=32 rf32+D=20 bf41=30 rf42=25 rf43

24、=20 rf43+D=10 rf51=17 rf52=14 rf53=12 rf54=9 rf54+D=4 r5年中的更新策略为留、买、留、留、留，5年内可得总利润41。决策过程如图6.4所示，其中，粗线表示最优决策。图6.4 设备更新的决策过程6.4.2 设备更新算法的实现数据结构。下面的数据用于算法的输入：intn;/* 决策年限 */intD;/* 设备当前的使用年限 */Typernn+D;/* 使用了年后的设备,在第年所创造的利润 */Typemnn+D;/* 使用了年后的设备,在第年的维修费用利润 */Typeunn+D;/* 使用了年后的设备,在第年的更新费用 */下面的数据用于

25、算法的输出：BOOLpn;/* 每年的最优决策 */下面的数据用于算法的工作单元：Typefnn;/* 使用了年后的设备,在第年及其以后所创造的利润 */Boolxnn;/* 使用了年后的设备,在第年的更新决策 */算法描述：算法6.3 设备更新算法输入：决策年限n,设备已使用年限D,设备利润表r,维修费用表m,更新费用表u输出：最优利润optg,及最优更新方案p 1. template <class Type> 2. Type update_dev(int n,int D,Type r,Type m,Type u,BOOL p) 3. 4. int i,j,k;/* 分配工作空间

26、 */ 5. Type optg,rem; 6. Type (*f)n+1 = new Typen+2n+1; 7. BOOL (*x)n+1 = new BOOLn+1n+1; 8. for (i=1;i<=n;i+)/* 第n+1年的利润初始化为0 */ 9. fn+1i = 0;10. for (i=n;i>0;i-) /*第1年第n年各种设备使用年限的利润*/11. for (j=1;j<=i;j+) 12. if (i>j) /* 买,可得到的利润 */ 13. fij = ri0 mi0 ui-jj + fi+11;14. else15. fij = ri0

27、 mi0 u0j-1+D + fi+11; 16. xij = TRUE;17. if (i>j) /* 留,可得到的利润 */18. rem = ri-jj mi-jj + fi+1j+1;19. else20. rem = r0j-1+D m0j-1+D +fi+1j+1;21. if (fij<rem) /* 决策,取二者中只最大者 */22. fij = rem; xij = FALSE;23. 24. 25. 26. j = 1;/* 全局的更新决策 */27. for (i=1;i<=n;i+) 28. pi = xij;/* 从第一年的决策开始 */29. if

28、 (pi) /* 当年的决策：更新 */30. j = 1;/* 下一年决策时,设备年限为1年 */31. else 32. j = j + 1;/*否则,下一年决策时,设备年限增1 */33. 34. optg = f11;35. delete f; delete x;/* 释放工作空间 */36. return optg;/* 返回最优更新时可得到的利润 */37. 时间复杂性：89行需要时间。1026行，内循环的循体共执行次，花费时间。2633行花费时间。空间复杂性是。6.5 最长公共子序列问题一、字符子序列上的字符序列，存在上的另一字符序列，对所有的，有，其中， ，是的下标递增序列，称

29、是的子序列。例：， 是的长度为3的子序列。子序列中的字符，相应于的下标是1,5,7。是的长度为5的子序列。子序列中的字符，相应于的下标是1,3,4,6,7。子序列有多个。例：和，长度为3的公共子序列，长度为4的公共子序列。长度为6的最长公共子序列。二、最长公共子序列问题：给定序列和，寻找和的一个公共子序列，使得它是和的最长公共子序列。6.5.1 最长公共子序列的搜索过程一、最长公共子序列的性质，。记为序列中最前面连续个字符的子序列，记为序列中最前面连续个字符的子序列。有如下性质：1. 若，是和的长度为的最长公共子序列。有，且序列是和的长度为的最长公共子序列；2. 若,且，则是和的长度为的最长公

30、共子序列；3. 若,且，则是和的长度为的最长公共子序列；二、最长公共子序列的的搜索过程1、最长公共子序列的长度记为和的最长公共子序列的长度，则为和的最长公共子序列的长度。有：（6.5.1）（6.5.2）第一阶段，计算和的最长公共子序列的长度。第二阶段，计算和的最长公共子序列的长度。第阶段，计算和的最长公共子序列的长度。第阶段的便是序列和的最长公共子序列的长度。2、最长公共子序列的获取二维状态字数组， 若 （6.5.3）若 ，且 （6.5.4）若 ，且 （6.5.5）设，是和的长度为的最长公共子序列。搜索过程如下：若：。根据性质1，下一个搜索方向是；若：，且。由性质2，下一个搜索方向是；若：，且

31、。由性质3，下一个搜索方向是。得到递推关系：若 则，（6.5.6）若 则（6.6.7）若 则（6.7.8）从，开始搜索，直到或结束，即可得到和的最长公共子序列。例6.5 求，的最长公共子序列。解 用两个的表，来分别存放和状态。的计算结果如图6.5所示。由图中看到，最长公共子序列的长度为8。图6.5 最长公共子序列长度的计算例子图6.6表示用搜索公共子序列的过程。公共子序列是。图6.6 最长公共子序列字符的搜索过程6.4.2 最长公共子序列算法的实现数据结构。下面的数据用于算法的输入和输出：charAn+1,Bm+1;/* 序列A和B */char Cn+1;/* 序列A和B的公共子序列 */下

32、面的数据用于算法的工作单元：int Ln+1m+1;/* 搜索过程中的子序列长度 */int sn+1m+1;/* 搜索过程中的子序列状态 */为了简便起见，字符序列及其公共子序列，均从下标为1的数组元素开始存放。算法6.4 求最长公共子序列算法输入：字符序列A和B,序列A的长度n,序列B的长度m输出：最长公共子序列C,及其长度len 1. int lcs(char A,char B,char C,int n,int m) 2. 3. int i,j,k,len;/* 分配工作空间 */ 4. int (*L)m+1 = new intn+1m+1; 5. int (*s)m+1 = new

33、intn+1m+1; 6. for (i=0;i<=n;i+)/* 初始化第0列 */ 7. Li0 = 0; 8. for (i=0;i<=m;i+)/* 初始化第0行 */ 9. L0i = 0;10. for (i=1;i<=n;i+) /* 计算长度及状态字 */11. for (j=1;j<=m;j+) 12. if (Ai=Bj) 13. Lij = Li-1j-1;14. sij = 1;15. 16. else if (Li-1j>=Lij-1) 17. Lij = Li-1j;18. sij = 2;19. 20. else 21. Lij =

34、Lij-1;22. sij = 3;23. 24. 25. 26. i = n; j = m; k = len = Lij;27. while (i!=0)&&(j!=0) /* 搜索最长公共子序列字符 */28. switch (sij) 29. case 1: Ck = Ai; k-;30. j-; 31. case 2: i-; break;32. case 3: j-; break; 33. 34. 35. delete L; delete s;/* 释放工作空间 */36. return len;/* 返回最长公共子序列长度 */37. 时间复杂性:第67行花费时间；第89行花费时间；第1025行花费时间；第2634行花费；空间复杂性是。6.6 0/1背包问题6.6.1 0/1背包问题的求解过程一、动态规划函数：物体被装入背包的情况，。约束方程和目标函数：解向量。背包的载重量： ：前个物体中，能装入载重量为的背包中的物体的最大价值，。动态规划函数：（6.6.1）（6.6.2）二、求解过程 1、决策阶段第一阶段，只装入一个物体，确定在各种不同载重量的背包下，能够得到的最大价值；第二阶段，装入前两个物体，确定在各种不同载重量的背包下，能够得到的最大价值；依此类推，直到第个阶段。最后，便是在载重量为的背包下