第六章 动态规划第章 动态规划.doc

第六章 动态规划 Chapter 6 Dynamic Programming §6.1引例 例6.1 最短路径问题 图6.1表示从起点A到终点E之间各点的距离。求A到E的最短路径。 如果用穷举法，则从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)这两个子问题。从图1.1.1可以看出，在这个问题中，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； 由此，可以计算S(A)： 最后，可以得到：从A到E的最短路径为A( B2( C1( D1( E 以上计算过程及结果，可用图6.2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。 以上过程，仅用了18次加法，11次比较，计算效率远高于穷举法。§6.2 动态规划的基本概念 最短路径问题 由例6.1可以看出，动态规划问题具有以下基本特征： 1、问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。 2、每一阶段都有相应的“状态”与之对应，描述状态的量称为“状态变量”。 3、每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态，同时，不同的决策将会导致这一阶段不同的目标函数值。 4、每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。能否构造这样的递推归结，是解决动态规划问题的关键。这种递推归结的过程，称为“不变嵌入”。 为了将以上特征形式化，我们提出以下动态规划的基本概念。 阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。 状态Sk：能确定地表示决策过程决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。 状态变量xk：表示每一状态可以取不同值的变量。 决策（Decision）dk：从某一状态向下一状态过度时所做的选择。决策是所在状态的函数，记为dk(xk)。 决策允许集合Dk(xk)：在状态xk下，允许采取决策的全体。 状态转移方程xk+1=T(xk,dk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。 阶段指标函数vk(xk,dk)：从状态xk出发，选择决策dk所产生的第k阶段指标。 过程指标函数V(xk,dk,dk+1,…,dn)：从状态xk出发，选择决策dk,dk+1,…,dn所产生的过程指标。动态规划要求过程指标具有可分离性，即 Vk,n(xk, dk,dk+1,…,dn)=vk(xk,dk)+Vk+1(xk+1,dk+1,…,dn) 称指标具有可加性，或 Vk,n(xk, dk,dk+1,…,dn)=vk(xk,dk)×Vk+1(xk+1,dk+1,…,dn) 称指标具有可乘性。 最优指标函数fk(xk)：从状态xk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即 对于可加性指标函数，上式可以写为 对于可乘性指标函数，上式可以写为 以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。 终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，即确定最后一个状态n下最优指标fn(xn)的值。 例6.2 利用以上基本概念，重新求解例6.1。 将问题