数据结构域算法设计-第八章 动态规划教案

《数据结构域算法设计-第八章 动态规划教案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章动态规划动态规划（DynamicProgramming，简记为DP）是运筹学的另一个重要分支，是解决多阶段决策过程最优化的一种数量化方法，是由美国数学家贝尔曼（R.Bellman）所建立.1951年他提出了解决多阶段决策问题的“最优化原理”并且研究了许多实际问题，从而创建了解决多阶段决策最优化问题的一种新的方法——动态规划（相对于它，前面讨论的规划问题称为静态规划）.实践证明，DP方法在工程技术、企业管理、工农业生产及军事等部门都有广泛的应用.动态规划的成功之处在于，它可以把一个n维决策问题变换为一个一维最优化问题，（把一个多阶段决策问题变换为一系列互相联系的单阶段问题

2、），然后一个一个地求解，这是经典极值方法所做不到的，特别对于离散性问题，由于解析数学无法施展其术，而动态规划的方法就成为非常有用的工具.应该指出的是动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊的算法，它不象线性规划那样有统一的数学模型和算法（如单纯形法），而必须对具体问题进行具体分析，针对不同问题运用DP的原理和方法，建立起相应的模型，然后再用动态规划方法去求解..因此，学习动态规划时，除了要对动态规划的基本原理和方法正确理解外，还应以丰富的想象力去建立模型（数学与艺术的结晶），用灵活的技巧去求解.§1多阶段决策问题在实践中，人们常会遇到这样一类决策

3、问题，即由于过程的特殊性，可以将决策的全过程依据时间或空间划分为若干个互相联系的阶段，在每一阶段要做出决策，而一个阶段的决策，不仅影响本阶段的活动，还会影响下一阶段的活动及其决策，从而影响整个决策过程.各个阶段的决策，构成一个决策序列，称为一个策略，由于每一阶段常有很多方案可供选择，因此，每一阶段也能作出若干不同的决策.这样各阶段的各自很多不同决策就构成了许多不同的策略.由于每阶段的不同决策其效果是不同的.因而由此所构成的不同策略的效果一般也不同，那么在诸多可供选择的策略中，选择哪一策略才能使一项待行的活动取得最佳效果？这类问题就是多阶段决策问题.例8.1100多年前，有位美

4、国推销员乘驿站马车，经过不友好的印地安地区向东旅行，虽然他的起点州A(state,状态)和目的地州E是固定的，但在途中要走过哪些州，却有相当大的选择余地.如图8-1所示：2C1B16442D13436742343AEC2B2431D235C3B3331234图8-1旅行线路图他从州A出发，旅行至州E目的地，需要4个驿程（stage，阶段），而从第1天开始每天都有不同的选择，此推销员是一个谨慎的人，十分关心他这次旅行中的安全，在经过一番思考后，他想到一个相当巧妙的办法来确定他的最安全途径，人身保险当时是很欢迎驿站乘客投保的，因为每张保险单（policy，策略）的收费是考虑了该行

5、程的安全程度后订出的，所以最安全的途径应当是人身保险单最低廉的途径，设州i至州j的行程上，保险费记cij，如图8-1所示.问题为求从StateA到StateE走哪条途径使保险单的总费用达到最小？（如果把cij看成是距离，则问题是求A®E的最短路）这是一个典型的多阶段决策问题.值得注意的是，作出各相继驿程上最佳决策.不一定产生总的最佳决策（即Greedy算法未必取得最佳策略）.如A2B14C23D24E费用和为13而A3B31C2更低廉求解该问题可以有以下两种思路：方法一：穷举法即列出所有的可行路径，逐个路径进行比较，并从中选出最佳路径.对于例8-1，分为4个阶段：AB(B1,

6、B2,B3)为第一阶段；3条路BC(C1,C2,C3)为第二阶段；3条路CD(D1,D2)为第三阶段；2条路DE为第四阶段；1条路从而所有的可行路径共有3×3×2×1=18最短路径为A3B31C23D24E总费用（最短时间）为11.方法二：运用了如下常识性的结论：如果A=S1®S2®…®Sk®…Sn®E是A®E的最短路，则该路上任一点Sk®Sk+1®…Sn®E是Sk®E的最短路.（可以反证）利用该结论，我们构造求解方法.设Sk表示在第k个驿程上出发州的集合（状态集合），S1=A，S2={B1，B2，B3}，S3={C1，C2，C3}，S4={D1，D2}；uk(sk)=sk+

7、1表示在第k个驿程从sk出发所作的决策,如：u2(B1)=C1或C2或C3({C1，C2，C3}表示第k驿程从B1出发的允许决策集合)；fk(sk)表示从第k个驿程的出发州sk®E的最短路的费用和，f1(S1)即为所求.显然，求A®E的最短路，可转化为求三个性质完全相同、但规模较小的子问题，即分别从B1，B2，B3到E的最短路问题，若已知f2（B1）、f2（B2）、f2（B3），则，同样，……也可转化为三个性质完全相同，但规模更33小的子问题，依次类推，我们可从最后驿程开始，逆向求出A→E的最短路.当k