动规 Dynamic Programming(DP 动态规划—— Dynamic Programming 动态规划的基本概念和基本原理 请看如下典例—最短路线问题
6 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 动态规划的基本概念和基本原理 请看如下典例——最短路线问题
动规划 Dynamie Programming(DP 动态规划—— Dynamic Programming 动态规划的基本概念和基本原理 7该点到G点的最短距离 2 13 3 B1)3 18 5 16 8 12 第一阶段⊥第二阶段1第三阶段⊥第四阶段1第五阶段1第六阶段7
7 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 动态规划的基本概念和基本原理 B1 A C3 F2 F1 E3 E2 E1 D3 D2 D1 C4 C2 C1 B2 G 第一阶段 第二阶段 第三阶段 第四阶段 第五阶段 第六阶段 5 3 1 3 6 8 7 6 6 8 3 5 3 4 2 1 3 8 2 2 3 3 3 5 5 2 6 6 4 3 4 3 7 5 9 7 6 8 13 10 9 12 13 16 18 该点到G点的最短距离
动规划 Dynamie Programming(DP 动态规划 Dynamic Programming 动态规划的基本概念和基本原理 1、阶段( stage) 对整个决策过程的自然划分,通常根据时间顺序或空间特征来 划分阶段,以便按阶段的次序逐段解决整个过程的优化问题。阶段 变量通常用k表示(k=1,2,3,…,n)。 2、状态( state) 每个阶段开始时过程所处的自然状况或客观条件。它应能描述 过程的特征并具有“无后效性”,即当前阶段状态给定时,这个阶 段以后过程的演变与该阶段以前各阶段的状态无关 状态变量—sk( state variable) 状态集合—Sk( set of admissible states)
8 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 动态规划的基本概念和基本原理 1、阶段（stage） 对整个决策过程的自然划分，通常根据时间顺序或空间特征来 划分阶段，以便按阶段的次序逐段解决整个过程的优化问题。阶段 变量通常用k表示（k = 1，2，3，…，n）。 2、状态（state） 每个阶段开始时过程所处的自然状况或客观条件。它应能描述 过程的特征并具有“无后效性”，即当前阶段状态给定时，这个阶 段以后过程的演变与该阶段以前各阶段的状态无关。 状态变量 —— sk（state variable） 状态集合 —— Sk（set of admissible states）
动规划 Dynamie Programming(DP 动态规划—— Dynamic Programming 动态规划的基本概念和基本原理 3、决策( decision) 当一个阶段的状态确定后,可以作出不同的决定或选择 从而演变到下一阶段的某个状态,这种决定或选择称为决策。 决策变量—uk(sk)( decision variable)简记为uk 决策集合 k( Sk)(set of admissible decision 4、策略( policy) 组有序的决策序列构成一个策略,从第k阶段至第n阶段 的一个策略称为后部子策略记为p,n→(uk,uk+1,…,un)
9 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 动态规划的基本概念和基本原理 3、决策（decision） 当一个阶段的状态确定后，可以作出不同的决定或选择， 从而演变到下一阶段的某个状态，这种决定或选择称为决策。 决策变量 —— uk（sk） （decision variable）简记为 uk 决策集合 —— Dk（sk）（set of admissible decision） 4、策略（policy） 一组有序的决策序列构成一个策略，从第k阶段至第n阶段 的一个策略称为后部子策略记为 pk，n →（uk，uk+1，…，un）
动规划 Dynamie Programming(DP 动态规划 Dynamic Programming 动态规划的基本概念和基本原理 5、状态转移方程( equation of state transition) 在确定型多阶段决策过程中,一旦某阶段的状态和决策为已知, 下一阶段的状态便完全确定,用状态转移方程反映这种状态间的演 变规律,写作: Sk+1= Tk(Sk, uk) k=1, 2,...,n 6、阶段指标值( objective value in a stage) 衡量在一个阶段某个状态下各决策所对应的某种数量指标或效 果,通常表示为vk(sk,uk)。 10
10 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 动态规划的基本概念和基本原理 5、状态转移方程（equation of state transition） 在确定型多阶段决策过程中，一旦某阶段的状态和决策为已知， 下一阶段的 状态便完全确定，用状态转移方程反映这种状态间的演 变规律，写作： sk+1 = Tk（sk，uk） k =1，2，…，n 6、阶段指标值（objective value in a stage） 衡量在一个阶段某个状态下各决策所对应的某种数量指标或效 果，通常表示为 vk（sk，uk）