(4)状态转移方程：确定过程由一个状态到另一个状态的演变过程。若给定第k阶段的状态，则 当该段的决策4一经确定，第k+1阶段的状态S+1也就完全确定，即s+1的值随s和4的值变化而变化。 把这种确定的对应关系，记为sk+=T(Sk,),它描述了由k阶段到k+1阶段的状态转移规律，称为状态 转移方程。 如例4.1.1中，如果S2=B2,为→C2,则s3=C2,即=T2(B2,→C2=C2。 (5)策略：是一个按顺序排列的决策组成的集合。由过程的第k阶段开始到终止状态为止的过程， 称为问题的k后子过程。由k后子过程中每段的决策按顺序排列组成的决策序列{(S),+1(S+),… 山n(s)}称为k后子过程策略。记为 Pn(S)={uk(S,+i(s+i）,…,n(sn）} 其中s+=TS%),…,Ssm=Tm1(Sm-l,-)。当k=1时，P1n()称为全过程策略，简称策略。 显然，Pn()={(S),Pk+1n(S+i)},其中Sk+1=T(Sk,)。 在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集，用P(S)表示。显然， Bsx)={(k,Pk+,n川山：∈Uk(S),Pk+n∈P+1n(Sk+i),Sk+1=T(Sk,山)}。从允许策略集中找出达到最优 效果的策略，称为最优策略。 (6)指标函数：用来衡量所实现过程优劣的一种数量指标。 阶段指标函数：用来衡量一个阶段优劣的一种数量指标，用(S%)表示第k阶段状态为s%所做决 策为时的指标函数。 k后子过程指标函数：用来衡量k后子过程优劣的一种数量指标，用 'kn(Sk,,Sk+l,k+l,…,Sm,m,Sn+l） 表示，其中s+1=T(S%k),,…,S+1=TSn山n)。特别地， ,,产立y,（G,西)一和式 i=k 或 (s4s+1,h,…,Smn+1F石y,（S,4）—乘式 = 如在例4.1.1中，指标函数的含义为距离。当s2=B2,为→C2时，阶段指标函数2(S2,)=d(B2,C2=8, 后子过程的指标函数是阶段指标函数的和。 当S给定，k后子过程策略P(s)给定，则k后子过程的指标函数'n也就确定了，故可记 Vn(SkPn(Sx)）='n(Skk,sk+l,+l,…,Sm4,Sn+I） (T)最优值函数：指标函数的最优值，即'(S,P,(s)在最优策略下的值，它表示从第k阶段状 态s开始到第n阶段终止在最优策略下的指标函数值，记作(s)。因此 fi(Sk)=opt Vkn(sk,pkn(SK)) Pkn(5g )EPn(5k) 其中“op”表示“min”或“mar”,最优解即为最优策略，记作Pk,n(Sk)。 如在例4.1.1中，(s)表示s到G的最短距离。 4.2.2动态规划的基本思想和基本方程 1.最短路线的特性 如果由起点S经过P点和H点而到达终点E是一条最短路线，则由点P出发经过H点到达E点的这 条子路线，对于从点P出发到达终点的所有可能选择的不同路线来说，必定是最短路线。 33 （4）状态转移方程: 确定过程由一个状态到另一个状态的演变过程。若给定第 k 阶段的状态 sk，则 当该段的决策 uk一经确定，第 k+1 阶段的状态 sk+1也就完全确定，即 sk+1 的值随 sk和 uk的值变化而变化。 把这种确定的对应关系，记为 sk+1=Tk(sk,uk)，它描述了由 k 阶段到 k+1 阶段的状态转移规律，称为状态 转移方程。 如例 4.1.1 中，如果 s2 =B2，u2 为→C2，则 s3=C2，即=T2(B2,→C2)=C2。 （5）策略： 是一个按顺序排列的决策组成的集合。由过程的第 k 阶段开始到终止状态为止的过程， 称为问题的 k 后子过程。由 k 后子过程中每段的决策按顺序排列组成的决策序列{uk(sk), uk+1(sk+1),… un(sn)}称为 k 后子过程策略。记为 pk,n(sk)={uk(sk), uk+1(sk+1),…，un(sn)} 其中 sk+1=Tk(sk,uk)，…，sn=T n-1(sn-1,un-1)。当 k=1 时，p1,n(s1)称为全过程策略，简称策略。 显然，pk,n(sk)= {uk(sk), pk+1,n(sk+1)}，其中 sk+1=Tk(sk,uk)。 在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集，用 Pk,n(sk)表示。显然， Pk,n(sk)= 1, 1, 1, 1 1 {( , ) | ( ), ( ), ( , )} k kn k k k kn knk k k k k u p u U s p P s s Tsu + + + ++ ∈∈ = 。从允许策略集中找出达到最优 效果的策略，称为最优策略。 （6）指标函数：用来衡量所实现过程优劣的一种数量指标。 阶段指标函数：用来衡量一个阶段优劣的一种数量指标，用 vk(sk,uk)表示第 k 阶段状态为 sk所做决 策为 uk时的指标函数。 k 后子过程指标函数：用来衡量 k 后子过程优劣的一种数量指标，用 Vk,n(sk,uk,sk+1,uk+1,…,sn,un,sn+1) 表示，其中 sk+1=Tk(sk,uk), ,…，sn+1=Tn(sn,un)。特别地， Vk,n(sk,uk,sk+1,uk+1,…,sn,un,sn+1)= (, ) n jjj j k vsu = ∑ ——和式 或 Vk,n(sk,uk,sk+1,uk+1,…,sn,un,sn+1)= (, ) n jj j j k π vsu = ——乘式 如在例 4.1.1 中，指标函数的含义为距离。当 s2=B2,u2 为→C2 时，阶段指标函数 v2(s2,u2)=d(B2,C2)=8， 后子过程的指标函数是阶段指标函数的和。 当 sk给定，k 后子过程策略 pk,n(sk)给定，则 k 后子过程的指标函数 Vk,n 也就确定了，故可记 Vk,n(sk,pk,n(sk))=Vk,n(sk,uk,sk+1,uk+1,…,sn,un,sn+1) （7）最优值函数：指标函数的最优值，即 Vk,n(sk,pk,n(sk))在最优策略下的值，它表示从第 k 阶段状 态 sk开始到第 n 阶段终止在最优策略下的指标函数值，记作 fk(sk)。因此 fk(sk)= , , () () kn k kn k p sPs opt ∈ Vk,n(sk,pk,n(sk)) 其中“opt”表示“min”或“max”，最优解即为最优策略，记作 * , ( ) kn k p s 。 如在例 4.1.1 中，fk(sk)表示 sk到 G 的最短距离。 4.2.2 动态规划的基本思想和基本方程 1. 最短路线的特性 如果由起点 S 经过 P 点和 H 点而到达终点 E 是一条最短路线,则由点 P 出发经过 H 点到达 E 点的这 条子路线,对于从点 P 出发到达终点的所有可能选择的不同路线来说，必定是最短路线