4.2动态规划的 基本原理
对最短路问题: 来源于动态规划 最短路问题的特点: 的最优化原理 如果最短路线在第阶段通过s点,则由s点出发到 达终点的这段路线对于从s出发到达终点的所有可 能选择的不同路线来说,必是最短的 找最短路线的方法: 从最后一阶段开始,用由后向前的方法,求出各点到 终点的最短路线,最后求得由起点到终点的最短路线 最短路问题的基本方程: 由后向前迭代 min d(sy, u x)+sri))k=4.3,2,1 f(s)=0 递推公式
对最短路问题： 最短路问题的特点： 找最短路线的方法： 能选择的不同路线来说，必是最短的 达终点的这段路线对于从 出发到达终点的所有可 如果最短路线在第 阶段通过 点，则由 点出发到 s k s s 终点的最短路线，最后求得由起点到终点的最短路线 从最后一阶段开始，用由后向前的方法，求出各点到 来源于动态规划 的最优化原理 最短路问题的基本方程： min ( k , k )+ k+1 ( k+1 ) u d s u f s k f k (sk ) = k=4,3,2,1 f 5 (s5 ) = 0 由后向前迭代 递推公式
最优化原理: 个过程的最优策略具有这样的性质,即无论初始 状态及初始决策如何,对于先前决策所形成的状态 而言,其以后的所有决策必构成最优策略 对最短路问题: = 若C→D2→>E1→>F是C到F的最优策略(最短路) 则不论前面A如何到达B,B又如何到达C1 对状态C1来说,必有: D2→>E1→>F是D2到F的最优策略 E1→F是E1到F的最优策略
最优化原理： 一个过程的最优策略具有这样的性质，即无论初始 状态及初始决策如何，对于先前决策所形成的状态 而言，其以后的所有决策必构成最优策略 对最短路问题： 若C1 → D2 → E1 → F 是C1 到F的最优策略（最短路） 对状态C1 来说，必有： ○A ○B1 ○F ○B2 ○B3 ○C1 ○C2 ○ ○C3 D2 ○D1 ○E2 ○E1 则不论前面A如何到达B，B又如何到达C1 D2 → E1 → F是D2 到F的最优策略 E1 → F是E1 到F的最优策略
上堂课的主要内容: 动态规划的基本概念 1、阶段:指对整个过程的自然划分,用k表示 2、状态变量sk:第k阶段开始时所处的自然状况 Sk={s}—第k阶段的状态集合 3、决策变量: 当一个阶段的状态确定后,可以作出各种选 择从而演变到下一阶段的某个状态,这种选 择手段称为决策 lk(k)--第k阶段处于状态时的决策变量 UA(sk)--决策变量uk(sk)允许取值的范围
上堂课的主要内容： 一、动态规划的基本概念 1、阶段：指对整个过程的自然划分 ，用k表示 2、状态变量sk Sk ={sk} 第k阶段的状态集合 ：第k阶段开始时所处的自然状况 3、决策变量： 当一个阶段的状态确定后，可以作出各种选 择从而演变到下一阶段的某个状态，这种选 择手段称为决策 ( ) k k u s − − −第k阶段处于状态sk 时的决策变量 ( ) k k U s − −决策变量uk (sk )允许取值的范围
4、状态转移方程 sk—第k阶段的状态变量 lk()--表示第阶段处于状态时的决策变量 状态转移方程:SA1=T(SA2uk) 5、策略:由各阶段的决策组成的序列称为策略 原过程的策略pn(s1)---从第一阶段初始状态s开 始到第n阶段全过程的策略 p1n(s1)={1(s)a2(s2)…un(sn)} 后部子过程的策略pn(sA)--从第阶段状态S开 始到第n阶段的策略 即pn(sk)={x4(3)421(Sx)…un(sn) P={策略}允许策略集合
4、状态转移方程 sk 第k阶段的状态变量 ( ) k k u s − −表示第k阶段处于状态sk 时的决策变量 ( , ) k 1 k k uk s = T s 状态转移方程： + 5、策略：由各阶段的决策组成的序列称为策略 ( ) 始到第 阶段全过程的策略 原过程的策略 从第一阶段初始状态 开 n p s s 1,n 1 − − − 1 即p1,n (s1 ) = u1 (s1 ),u2 (s2 ), un (sn ) P = 策略——允许策略集合 ( ) 始到第 阶段的策略 后部子过程的策略 从第 阶段状态 开 n p s k s k ,n k − − − k 即pk ,n (sk ) = uk (sk ),uk+1 (sk+1 ), un (sn )