动态规划.ppt

*§1 多阶段决策过程最优化问题举例例1最短路径问题下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACBDBCDEC412312312322164724838675611063751*§1 多阶段决策过程最优化问题举例用穷举法的计算量:如果从A到E的站点有k个,除A、E之外每站有3个位置则总共有3k-1×2条路径;计算各路径长度总共要进行(k+1)3k-1×2次加法以及3k-1×2-1次比较。随着k的值增加时,需要进行的加法和比较的次数将迅速增加;例如当k=20时,×1015次,×1014次。若用1亿次/秒的计算机计算需要约508天。*§1 多阶段决策过程最优化问题举例讨论:1、以上求从A到E的最短路径问题,可以转化为四个性质完全相同,但规模较小的子问题,即分别从Di、Ci、Bi、A到E的最短路径问题。第四阶段:两个始点D1和D2,终点只有一个;表10-1分析得知:从D1和D2到E的最短路径唯一。阶段4本阶段始点(状态)本阶段各终点(决策)到E的最短距离本阶段最优终点(最优决策)ED1D210*6106EE*第三阶段:有三个始点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 多阶段决策过程最优化问题举例阶段3本阶段始点(状态)本阶段各终点(决策)到E的最短距离本阶段最优终点(最优决策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D1*第二阶段:有4个始点B1,B2,B3,B4,终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3的最短路径问题:表10-3分析得知:如果经过B1,则走B1-C2-D2-E;如果经过B2,则走B2-C3-D1-E;如果经过B3,则走B3-C3-D1-E;如果经过B4,则走B4-C3-D1-E。§1 多阶段决策过程最优化问题举例阶段2本阶段始点(状态)本阶段各终点(决策)到E的最短距离本阶段最优终点(最优决策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C3*第一阶段:只有1个始点A,终点有B1,B2,B3,B4。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题:表10-4最后,可以得到:从A到E的最短路径为AB4C3D1E§1 多阶段决策过程最优化问题举例阶段1本阶段始点(状态)本阶段各终点(决策)到E的最短距离本阶段最优终点(最优决策)B1B2B3B4A4+12=163+13=163+14=172+12=1412C2*以上计算过程及结果,可用图2表示,可以看到,以上方法不仅得到了从A到D的最短路径,同时,也得到了从图中任一点到E的最短路径。以上过程,仅用了22次加法,计算效率远高于穷举法。BACBDBCDEC41231231233216472483867516106010612111112131414127512§1 多阶段决策过程最优化问题举例*一、基本概念:1、阶段k:表示决策顺序的离散的量,阶段可以按时间或空间划分。2、状态sk:能确定地表示决策过程当前特征的量。状态可以是数量,也可以是字符,数量状态可以是连续的,也可以是离散的。3、决策xk:从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数,记为xk(sk)。决策允许集合Dk(sk):在状态sk下,允许采取决策的全体。4、策略Pk,n(sk):从第k阶段开始到最后第n阶段的决策序列,称k子策略。P1,n(s1)即为全过程策略。5、状态转移方程sk+1=Tk(sk,xk):某一状态以及该状态下的决策,与下一状态之间的函数关系。§2 基本概念、基本方程与最优化原理*6、阶段指标函数vk(sk,xk):从状态sk出发,选择决策xk所产生的第k阶段指标。过程指标函数Vk,n(sk,xk,xk+1,…,xn):从状态sk出发,选择决策xk,xk+1,…,xn所产生的过程指标。动态规划要求过程指标具有可分离性,即Vk,n(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