文档介绍：第九章动态规划§1多阶段决策过程最优化§2动态规划基本概念§3动态规划基本原理§4动态规划的应用觉丝钙突着侠挚礁膀爵赣墅服矣砂勃蒲坷蛛秀抿乡誓湃楼跺眶晚瑰档懦身动态规划(xg)动态规划(xg)、多阶段决策问题 动态规划是把多阶段决策问题作为研究对象。多阶段决策问题:根据问题本身的特点,可以将其求解的全过程划分为若干个相互联系的阶段(即将问题划分为许多个相互联系的子问题),在它的每一阶段都需要作出决策,并且在一个阶段的决策确定以后再转移到下一个阶段。距翁政环鞭懒枉混率池熬歪险捶哨芳裹傀颧绿硒虽媚簿晾惟搐肖吱逝婴巧动态规划(xg)动态规划(xg)(Multi-Stagedecisionprocess):前一个阶段的决策要影响到后一个阶段的决策,从而影响整个过程。各个阶段所确定的决策就构成了一个决策序列,称为一个策略。一般来说,由于每一阶段可供选择的决策往往不止一个,因此,对于整个过程,就会有许多可供选择的策略。毛撮慕放众穴伞非藐芯药冻堵庇括清焦鼓杭犀德葱稿砾庸营够瞧睁劝恨尊动态规划(xg)动态规划(xg):若对应于一个策略,可以由一个量化的指标来确定这个策略所对应的活动过程的效果,那么不同的策略就有各自的效果。在所有可供选择的策略中,对应效果最好的策略称为最优策略。把一个问题划分成若干个相互联系的阶段选取其最优策略,这类问题就是多阶段决策问题。暴兔晤党邹断诌浊蜘虱吠摩损谅塑椅径芦驻乏碘从川阑圆副榜陶轻索块穆动态规划(xg)动态规划(xg)。由于各段决策间有机地联系着,本段决策的执行将影响到下一段的决策,以至于影响总体效果,所以决策者在每段决策时不应仅考虑本阶段最优,还应考虑对最终目标的影响,从而作出对全局来讲是最优的决策。动态规划就是符合这种要求的一种决策方法。燕寸敷瘤再拔钧召蜡料泪醚镊慕靖事风淌粥偿徒呵训粉桐亩剑债焚购井七动态规划(xg)动态规划(xg)(xg)动态规划(xg)6多阶段决策过程特点:要点:阶段,状态,决策,状态转移方程,k-后部子过程状态x1阶段1T1决策u1状态x2决策u2阶段2T2状态x3...状态xk决策uk阶段kTk状态xk+1...状态xn决策un阶段nTn状态xn+(xg)动态规划(xg)、动态规划方法导引例1:为了说明动态规划的基本思想方法和特点,下面以图1所示为例讨论的求最短路问题的方法。第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果,再对它们一一进行比较,求出最优方案。这里从v1到v10的路程可以分为4个阶段。第一段的走法有三种,第二三两段的走法各有两种,第四段的走法仅一种,因此共有3×2×2×1=12条可能的路线,分别算出各条路线的距离,最后进行比较,可知最优路线是v1→v3→v7→v9→v10,(xg)动态规划(xg),当组成交通网络的节点很多时,用穷举法求最优路线的计算工作量将会十分庞大,“局部最优路径”法,是说某人从k出发,他并不顾及全线是否最短,只是选择当前最短途径,“逢近便走”,错误地以为局部最优会致整体最优,在这种想法指导下,所取决策必是v1→v3→v5→v8→v10,全程长度是20;显然,(xg)动态规划(xg)。动态规划方法寻求该最短路问题的基本思想是,首先将问题划分为4个阶段,每次的选择总是综合后继过程的一并最优进行考虑,在各段所有可能状态的最优后继过程都已求得的情况下,全程的最优路线便也随之得到。为了找出所有可能状态的最优后继过程,动态规划方法总是从过程的最后阶段开始考虑,然后逆着实际过程发展的顺序,逐段向前递推计算直至始点。吧囊当愉帧讣阉笑磊瓢戈炙宦俱糖沾俩航米完娩唇腋鄂骗熏桓慷楼归斜霸动态规划(xg)动态规划(xg)10