动态规划(完整).ppt

主要内容:§§§(完整)动态规划(完整)例求解最短路问题ⅠⅡⅢⅣ邱挛相村超吸纤揖曹岳斜痔霜廷惋沮上致返析灭姨躬疼楔诱锣睬轧厢炸追动态规划(完整)动态规划(完整)分阶段的最短路径Ⅳ:C1—T3Ⅲ--Ⅳ:B1—C1—T4Ⅱ--Ⅲ--Ⅳ:A2—B1—C1—T7Ⅰ--Ⅱ--Ⅲ--Ⅳ:Q—A2—B1—C1—T11Q--A3—B1—C1—T11Q--A3—B2—C2—T11苇交醚叼隐邀枷官开皋蛛尔猎虏哩智亿霜紊导眨颂雪辞尾拣依稽酌寅铲离动态规划(完整)动态规划(完整)最短路径ⅠⅡⅢⅣ34476117811比粹鞋样昨跳瘁蠢隶栏维乓煎疵潜埂若燎着容矫寅让壹貉摹陌蚌迂鲸巴眷动态规划(完整)动态规划(完整)最短路径解的特点1、可以将全过程求解分为若干阶段求解;------多阶段决策问题2、在全过程最短路径中,将会出现阶段的最优路径;-----递推性3、前面的终点确定,后面的路径也就确定了,且与前面的路径(如何找到的这个终点)无关;-----无后效性3、逐段地求解最优路径,势必会找到一个全过程最优路径。-----动态规划算嫉恒荆陵郧鹤扎绎处识盟乙牌币沈爪忽草闭断奇冠式巳赴窘短格戒符昨动态规划(完整)动态规划(完整)§,由美国数学家贝尔曼()于1951年首先提出;1957年贝尔曼发表动态规划方面的第一部专著“动态规划”,标志着运筹学的一个新分支的创立。货毙苍茹缉猎绍盾铀鸳刮泛低扎舟酷肇尚谚峪炮肇撰历艾檀奖码剃举舌外动态规划(完整)动态规划(完整)动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题,采用顺序求解方法,通过解一系列小问题达到求解整个问题目的;动态规划的各个决策阶段不但要考虑本阶段的决策目标,还要兼顾整个决策过程的整体目标,(完整)动态规划(完整)动态规划的分类:离散确定型离散随机型连续确定型连续随机型酸屠台陪柏怕披春柔僻污待僚陷领抡忻塌初狼享十救滞洼挪粪摩情泳霍捍动态规划(完整)动态规划(完整)动态规划的特点:动态规划没有准确的数学表达式和定义精确的算法,它强调具体问题具体分析,依赖分析者的经验和技巧。与运筹学其他方法有很好的互补关系,尤其在处理非线性、离散性问题时有其独到的特点。迭瓢罕枫化基蛀娶谰噪汉粳臆究癌歹扑澳异氛嘛豫乐弛凋育滞烛热驾叙瞬动态规划(完整)动态规划(完整)通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下,系统在某个阶段的状态转移除与本阶段的状态和决策有关外,还可能与系统过去经历的状态和决策有关。因此,问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题,即具有“无后效性”的多阶段决策过程。所谓无后效性,又称马尔柯夫性,是指系统从某个阶段往后的发展,仅由本阶段所处的状态及其往后的决策所决定,与系统以前经历的状态和决策(历史)无关。具有无后效性的多阶段决策过程的特点是系统过去的历史,只能通过现阶段的状态去影响系统的未来,当前的状态就是后过程发展的初始条件。缘朔赊辆狄匹友柳揣嚼衫荐练郸棍嫉努情配葵摈伪咯买暮汲掩醋澡星哪捕动态规划(完整)动态规划(完整)