动态规划的基本概念和基本方程.ppt
《动态规划的基本概念和基本方程.ppt》由会员分享,可在线阅读,更多相关《动态规划的基本概念和基本方程.ppt(19页珍藏版)》请在三一文库上搜索。
1、5.2 5.2 动态规划的基本概念和基本方程动态规划的基本概念和基本方程(一一)基本概念基本概念(1)阶段:阶段:k(2)状态变量:状态变量:Sk(3)决策变量:决策变量:uk(Sk)(4)策略策略(5)状态转移方程:状态转移方程:Sk1 T(Sk,uk)(6)指标函数:指标函数:Vk,n(Sk)(7)最优指标函数:最优指标函数:fk(Sk)1(二二)前例前例1(1)阶段:阶段:k1,2,6 n=6(2)状态变量:状态变量:Sk第第k阶段所处的位置阶段所处的位置 状态集合状态集合 如如S2:(B1,B2)(3)决策变量决策变量uk:在第在第k段段Sk状态时决定状态时决定选选 取的下一段的某点取
2、的下一段的某点(4)状态转移方程状态转移方程:Sk1 uk2(6)阶段效益:阶段效益:d(Sk,uk)为第为第k段,采取策略段,采取策略uk 到下一到下一状状 态的距离态的距离(5)最优指标函数:最优指标函数:fk(Sk):第:第k段,在段,在Sk状态时到终点状态时到终点G的的最最 短距离短距离3例例1 最短路径问题最短路径问题AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876658333 84222133355266434k6,f6(F1)4 f6(F2)3k5 d(E1,F1)+f6(F1)f5(E1)min d(E1,F2)+f6(F2)3+4 min =7 u
3、5(E1)=F1 5+35同理同理 f5(E2)5 u5(E2)F2 f5(E3)9 u5(E3)F2k4 d(D1,E1)+f5(E1)f4(D1)min d(D1,E2)+f5(E2)2+7 min =7 u4(D1)=E2 2+56同理同理 f4(D2)6 u4(D2)E2 f4(D3)8 u4(D3)E2K=3 7k1 d(A ,B1)+f2(B1)f1(A)min d(A ,B2)+f2(B2)5+13 min =18 u1(A)=B1 3+168(三三)基本方程基本方程fk(Sk)mind(Sk,uk)+fk+1(Sk+1)k=6,1f7(S7)0或或fk(Sk)mind(Sk,u
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 基本概念 基本 方程
