《数据结构域算法设计-第六章 动态规划 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第六章 动态规划 课件（83页珍藏版）》请在金锄头文库上搜索。
1、,第六章 动态规划 Dynamic Programming,运筹学 第六章 动态规划,Slide 2,多阶段决策过程最优化问题：有一些活动，它在时间或空间上可以分成若干个阶段，需要对每个阶段进行决策(有若干个方案可供选择)，使得活动的整体效果最好。 每个阶段的决策都不是可以任意确定的，它依赖于当前的状况，同时，它的决策结果又影响到以后的决策。组成了一个决策序列。 这样的决策过程是在变化的过程中产生的，故有动态的含义。处理它的方法称为动态规划的方法。 方法：多阶段问题转化成一系列互相联系的较容易的单阶段问题。,1,2,n,状态,决策,状态,决策,决策,状态,状态,状态,第一节 动态规划的基本思想
2、和方法,一、多阶段决策过程最优化问题举例 P169 例4.3：最短路线问题（P176） 从A点到E点可分成4个阶段。以A为起点，终点有三个B1、B2、B3，有三个选择。若选择B2，则B2为第一阶段决策的结果。同时它又是第二阶段的开始状态。当每个阶段做出决策的结果，直接影响到后面的选择和决策的结果。 最短路线有一个重要特性： 如果从起点A经过C2点和D1点到达终点E是一条最短的路线，则由C2 点经过D1 点到达E点的这条子路线，是由C2 点出发到达E点所有路线中的最短路线。 寻找最短路线的方法，从最后一段开始，由后向前逐步推进，找出各点到E点的最短路线，最后就能确定一条从A点到E点的最短路线。,
3、运筹学 第六章 动态规划,Slide 4,运筹学 第六章 动态规划,Slide 5,运筹学 第六章 动态规划,Slide 6,运筹学 第六章 动态规划,Slide 7,最短线路：AB1 C2 D2 E，总长度为15。,作业例1：如图给定一个线路网络，两点之间连线上的数字表示两点间的距离(或费用)。试求一条从A到G的铺管线路，使总距离最短(或总费用最小)。,A,C1,E3,E2,E1,F2,F1,G,D3,D2,D1,C4,C3,C2,B2,B1,5,3,1,3,6,6,8,2,2,3,5,4,8,7,6,5,3,3,3,1,2,5,2,6,6,3,8,4,3,3,运筹学 第六章 动态规划,Sl
4、ide 9,运筹学 第六章 动态规划,Slide 10,运筹学 第六章 动态规划,Slide 11,运筹学 第六章 动态规划,Slide 13,运筹学 第六章 动态规划,Slide 14,最短路线为AB1C2D1E2F2G,A,C1,E3,E2,E1,F2,F1,G,D3,D2,D1,C4,C3,C2,B2,B1,0,3,4,9,5,7,8,6,7,12,9,10,13,16,13,18,运筹学 第六章 动态规划,Slide 16,二、动态规划的最优性原理 作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简言之，一个
5、最优策略的子策略总是最优的。 但“最优性原理”仅仅是策略最优性的必要条件，非充分条件。 充分条件应是动态规划的基本方程。,运筹学 第六章 动态规划,Slide 17,三、动态规划的基本概念和基本方程 1、阶段 把所给问题的过程，分成若干个相互联系的阶段，以便按一定的次序去求解。 阶段变量常用K来表示。阶段的划分一般是按照时间和空间的自然特征来划分，但要便于将问题的过程转化为多阶段决策的过程。 K1，2，3，4，5，6 2、状态 每个阶段开始时所处的状况，同时又是前一阶段的终点。用Sk来表示第K阶段的状态。 如：S2=B1，B2；S3=C1，C2，C3，C4。 注意：要明确每个阶段状态的集合或者
6、范围。,运筹学 第六章 动态规划,Slide 18,“状态”具有 “无后效性”（“马尔科夫性”）：如果某阶段的状态给定后，当前的状态是以往历史的总结，则在这阶段以后过程的发展不受这阶段以前各阶段的影响。 3、决策 决策表示当过程处于某一阶段的某个状态的选择，Uk(Sk)表示第k阶段处于Sk状态时的决策。 如：U2(B1)C2，表示处于第二阶段，以B1为始点选择C2作为第二阶段的终点。 Dk(Sk)表示第k阶段处于Sk状态时的允许决策集合。D2(B1) C1 ,C2 ,C3。Uk(Sk)Dk(Sk)。 4、策略 由各个阶段的决策所组成的决策函数序列为全过程策略。 P1,n(S1)= U1(S1)
7、, U2(S2), Un(Sn),运筹学 第六章 动态规划,Slide 19,Pk,n(Sk)= Uk(Sk), Uk+1(Sk+1), Un(Sn)为k子过程的策略。 允许策略集合，用P来表示。从允许策略集合中找出达到最优效果的策略称为最优策略。 5、状态转移方程 第k+1阶段的状态是由第k阶段的状态和第k阶段的决策所决定的，用方程的形式表示这种关系为Sk+1=Tk(Sk,Uk),它反映了由第k阶段到第k+1阶段的状态转移规律，称为状态转移方程，状态转移函数。如：S3=T2(S2,U2) C2T2(B1，C2) 6、指标函数和最优值函数 用来衡量所实现过程优劣（全过程策略，或k子过程策略优劣
8、）的一种数量指标，称为指标函数。常用Vk,n表示。 Vk,nVk,n(Sk，Uk ，Sk1 ，,Sn+1) k=1,2,n,运筹学 第六章 动态规划,Slide 20,对于要构成动态规划模型的指标函数，应具有可分离性，并满足递推关系，即Vk,n可表示为Sk，Uk ，Vk1,n的函数。Vk,n(Sk,Uk ,Sk1 ,Sn+1)k(Sk,Uk ,Vk1,n(Sk1,Uk1,Sn+1) 常见的指标函数有： 1)整个过程和它的任一子过程的指标函数是它所包含的各阶段的指标的和。 Vk,n（Sk，Uk ，Sk1 ，,Sn+1） Vk,n（Sk，Uk ，Sk1 ，,Sn+1）vk(sk,uk)+ Vk+1
9、,n（Sk+1，Uk+1 ，Sk2 ，,Sn+1） 2)整个过程和它的任一子过程的指标函数是它所包含的各阶段的指标的乘积，即： Vk,n（Sk，Uk ，Sk1 ，,Sn+1）,Vk,n(Sk，Uk ，Sk1 ，,Sn+1)vk(sk,uk) Vk+1,n(Sk+1，Uk+1 ，Sk2 ，,Sn+1) 指标函数的最优值称为最优值函数：f1(S1)，fk(Sk)，表示从第k阶段开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。如：f1(A)18，f2(B1)13。 fk(Sk)opt Vk,n（Sk，Uk ，Sk1 ，,Sn+1） “opt”：optimization，最优化的缩写。
10、可以是min或max。 一般情况下，k阶段和k+1阶段之间的递推关系式可写成： fk(Sk)opt vk(Sk,Uk(Sk)+ fk+1(Sk+1) k=n,n-1,2,1 fk(Sk)opt vk(Sk,Uk(Sk)+ fk+1(Uk(Sk) k=n,n-1,2,1 边界条件为: fn+1(Sn+1)=0 这种递推关系式称为动态规划的基本方程。,运筹学 第六章 动态规划,Slide 22,四、如何给一个实际问题建立动态规划模型 将问题的过程分成恰当的阶段； 正确选择状态变量Sk，使它既能描述过程的演变，又能满足无后效性； 确定决策变量Uk，及每一阶段的允许决策集合Dk； 正确写出状态转移方程
11、： Sk+1=Tk(Sk,Uk) ； 正确写出指标函数Vk,n的关系，它应满足下面三个性质： 1）Vk,n是定义在全过程和所有后部子过程上的指标函数; 2）具有可分离性，并满足递推关系，即 Vk,n(Sk，Uk ，Sk1 ，,Sn+1)k(Sk，Uk ，Vk1,n(Sk1，Uk1,Sn+1) 3）函数k（Sk，Uk ，Vk1,n）对于变量Vk1,n要严格单调。,运筹学 第六章 动态规划,Slide 23,恰当地定义最优值函数。 写出恰当的边界条件 ，从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优结果，就是这个问题的最优
12、解，并找到相应的最优策略。 例1：用dk(sk,uk)vk(sk,uk)表示从点Sk到Sk1的距离。 Vk,n表示在第k阶段从点Sk到终点的距离。 fk(Sk) 表示第k阶段状态为Sk时，从第k阶段开始到第n阶段的最短距离。 f7(S7)0 当k6时，f6(F1)4，f6(F2)3； 当k5时， f5(E1)min d5(E1,F1)+ f6(F1), d5(E1,F2)+ f6(F2)=min3+4, 5+3=7，相应的决策为U5(E1)F1,f5(E2)min d5(E2,F1)+ f6(F1), d5(E2,F2)+ f6(F2)=min5+4, 2+3=5，相应的决策为U5(E2)F2
13、 f5(E3)min d5(E3,F1)+ f6(F1), d5(E3,F2)+ f6(F2)=min6+4, 6+3=9，相应的决策为U5(E3)F2； 当k4时， f4(D1)7 U4(D1)E2 f4(D2)6 U4(D2)E2 f4(D3)8 U4(D3)E2 当k3时， f3(C1)13 U3(C1)D1 f3(C2)10 U3(C2)D1 f3(C3)9 U3(C3)D2 f3(C4)8 U3(C4)D3 当k2时， f2(B1)13 U2(B1)C2 f2(B2)16 U2(B2)C3,当k1时， f1(A)min d1(A,B1)+ f2(B1), d1(A,B2)+ f2(B
14、2)=min5+13, 3+16=18 相应的决策为U1(A)B1 最短路线为AB1C2D1E2F2G。 在求解的过程中，我们用了k阶段和k+1阶段之间的递推关系： fk(Sk)min dk(Sk,Uk(Sk)+ fk+1(Uk(Sk) k=6,5,4,3,2,1 边界条件： f7(S7)=0或者 f6(S6)= d6(S6,G) 五、用动态规划求解静态规划问题 与时间无关的的某些静态规划问题，可以人为地引入时间因素，把它看作是按阶段进行的一个动态规划问题。,第二节 动态规划应用举例,一、资源分配问题 1、例2（P190习题4-8）：某工业部门按国家计划的安排，拟将某高效率的设备五台，分配给所
15、属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如下表所示。问：这五台设备如何分配给各工厂，才能使国家得到的盈利最大。,运筹学 第六章 动态规划,Slide 27,例2一维资源分配，资源平行分配 1)将问题按工厂分为三个阶段，甲乙丙三个工厂的编号分别为1、2、3； 2)设Sk表示为分配给第k个工厂到第n个工厂的设备台数， Xk设为决策变量，表示为分配给第k个工厂的设备台数， 状态转移方程为 Sk1SkXk。 Pk(Xk)表示为Xk台设备分到第k个工厂所得的盈利值。 fk(Sk)表示为Sk台设备分配给第k个工厂到第n个工厂的最大盈利值。 3)递推关系式： fk(Sk)max Pk(Xk)+ fk+1(SkXk) k=3,2,1 边界条件：f4(S4)0 4)从最后一个阶段开始向前逆推计算。,
