第10章+动态规划ppt课件.ppt

《第10章+动态规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章动态规划§1多阶段决策过程最优化问题举例§2基本概念、基本方程与最优化原理§3动态规划的应用(1)§4动态规划的应用(2)1§1多阶段决策过程最优化问题举例例1最短路径问题下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACBDBCDEC4123123123221647248386756110637512§1多阶段决策过程最优化问题举例用穷举法的计算量:如果从A到E的站点有k个，除A、E之外每站有3个位置则总共有3k-1×2条路径；计算各路径长度总共要进行(k+1)3k-1×2次加法以及3k-

2、1×2-1次比较。随着k的值增加时，需要进行的加法和比较的次数将迅速增加；例如当k=20时，加法次数为4.2550833966227×1015次，比较1.3726075472977×1014次。若用1亿次/秒的计算机计算需要约508天。3§1多阶段决策过程最优化问题举例讨论：1、以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路径问题。第四阶段：两个始点D1和D2，终点只有一个；表10-1分析得知：从D1和D2到E的最短路径唯一。4第三阶段：有三

3、个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2的最短路径问题：表10-2分析得知：如果经过C1，则最短路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路为C3-D1-E。§1多阶段决策过程最优化问题举例5第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3的最短路径问题：表10-3分析得知：如果经过B1，则走B1-C2-D2-E；如果经过B

4、2，则走B2-C3-D1-E；如果经过B3，则走B3-C3-D1-E；如果经过B4，则走B4-C3-D1-E。§1多阶段决策过程最优化问题举例6第一阶段：只有1个始点A，终点有B1,B2,B3,B4。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：表10-4最后，可以得到：从A到E的最短路径为AB4C3D1E§1多阶段决策过程最优化问题举例7以上计算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。以上过程，仅用了

5、22次加法，计算效率远高于穷举法。BACBDBCDEC41231231233216472483867516106010612111112131414127512§1多阶段决策过程最优化问题举例8一、基本概念：1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。2、状态sk：能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。决策允许集合Dk(sk)：在状态sk下，

6、允许采取决策的全体。4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。5、状态转移方程sk+1=Tk(sk,xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。§2基本概念、基本方程与最优化原理96、阶段指标函数vk(sk,xk)：从状态sk出发，选择决策xk所产生的第k阶段指标。过程指标函数Vk,n(sk,xk,xk+1,…,xn)：从状态sk出发，选择决策xk,xk+1,…,xn所产生的过程指标。动态规划要求过程指标具有可分离性，即Vk,n

7、(sk,xk,xk+1,…,xn)=vk(sk,xk)+Vk+1(sk+1,xk+1,…,xn)称指标具有可加性，或Vk,n(sk,xk,xk+1,…,xn)=vk(sk,xk)×Vk+1(sk+1,xk+1,…,xn)称指标具有可乘性。二、基本方程：最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即§2基本概念、基本方程与最优化原理10对于可加性指标函数，上式可以写为上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以写为以上式子称为动态规划最优指标

8、的递推方程，是动态规划的基本方程。终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1)=0。§2基本概念、基本方程与最优化原理11三、最优化原理作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意