1、1第五章第五章 动态规划动态规划所谓多阶段决策问题是有这样一类决策过程 ,它可以划分为若干个相互联系的阶段，在任一阶段都有若干种方案可供选择，选择哪一种方案需要作出决策，这样就形成一个决策序列，通常称为一种 策略 。不同的策略就产生不同的效果，在所有可能的策略当中，选择一个效果最好的最优策略，就是解决多阶段决策问题的主要目的。下面通过例子来说明。第第 一一 节节 多阶段决策过程及实例多阶段决策过程及实例2例 1： （最短路问题）设从 A地到 E地要铺设一条管道，其中要经过若干个中间点 (如图 )。图中两点之间连线上的数字表示两地间的距离。现在要选择一条铺设管道的路线，使总长度最短。251121
2、4106104131112396581052C1C3D1AB1B3B2D2EC23在这个问题中，从 A到 B1 ,B2 , B3中的哪一个点要作出一项决策，从 B1,B2 , B3某点到 C1,C2,C3 中的哪一个点又要作出一项决策等等。所以总共要作出四个决策。因此，我们可以把整个路程分为 A,B ( 包括 B1,B2 , B3), C (包括 C1, C2 , C3),D(包括 D1和 D2),E四个阶段。这就是一个多阶段的决策问题。用动态规划求解多阶段决策问题，是把整个问题划分为若干阶段后，依次地为每一个阶段作出最优决策，而每个阶段的最优决策应该是包含本阶段和以后所有各阶段在内的最优决策
3、。因此，在确定了第一个阶段的决策之后，整个问题的最优决策序列也就随之产生。这就是用动态规划解多阶段决策问题的基本思想。4以上面的 例 1来说明动态规划解决问题的思想。设：Sk 第 k阶段的起点（状态变量） d(x, y) 第 k阶段的从状态 x 到状态 y 的 “距离 ”；fk(sk) 第 k阶段从状态 Sk出发到终点 E的 “最短路 ”。 最短路线的重要特征是：如果最短路线在第 k阶段通过点 Pk。则由点 Pk出发到达终点的这条路线，对于从点 Pk出发到达终点的所有可能选择的不同路线来说，必定也是最短路线。5例如在最短路问题中，如果找到了从 A到 E的最短路：则 C2D 1E 应该是由 C2
4、 出发到 E点的所有可能不同线路中的最短路线。最短路线这一特性，启发我们找最短路线的方法：那就是从最后一段开始，用由后向前逐步递推的方法，求出各点到 E点的最短路线，最后求得由 A点到 E点的最短路线。所以动态规划的常用的方法是 从终点逐段向始点方向寻找 “最短路线 ” 。如图所示：行进方向起点 终点动态规划寻优途径6下面按上述思想，将例 1从最后一段开始计算，由后向前逐步推移至 A点。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0设想有 k= 5， f5(E)= 0 。72511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0K=4时：82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=592511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5K=3时：102511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8
