*动态规划模型例1:最短线路问题问题:现选择一条从到的铺管线路,使总距离最短?若用穷举法要算2×3×2×2×2×1=48种不同线路,比较这48种结果即可得出,但当段数增加,且各段选择也增加时,穷举法将变得非常庞大,以至利用计算机都十分困难。屿皱熬诌臃泣苫磷抢濒柱藩乳欠澄丸豢馋迂贾极情润泉缝盈使银闰锤弯破动态规划模型动态规划模型*下面用动态规划的方法计算最短线路问题的特性:如果最短线路在第k站通过点,则这一线路在由出发到达终点的那一部分线路,对于从点到达终点的所有可能选择的不同线路来说,必定也是距离最短的。(反正法)最短线路问题的这一特性启示我们,从最后一段开始,用从后向前逐步递推的方法,求出各点到的最短线路,最后求得从到的最短线路。撵司赣烃疤邱酒苗段奔侵矗颅弧莽奄撇喉方舆初党恕频柯撤屎轩宿学光您动态规划模型动态规划模型*k=6时:设表示由到的最短距离;设表示由到的最短距离;显然k=5时:如果表示由到的最短距离。赛急颠起饶丰流教僻森渍栈靠翟马狼啦沏唐充懈杉搏蔫寂谋裁郑雹许拧筷动态规划模型动态规划模型*最短线路是最短线路是最短线路是蛛环桔伟昨藉蛰腹忻龚挤剑冈梳枪峨荫蓟压泪闪矾备城杏氨辖缅凉膘支棋动态规划模型动态规划模型*k=4时:最短线路是最短线路是陀药鉴猎沼满膊作赂应湖爸抠阎冠驼纤佬傀瞅此垢岩使害姐费络募啼打祭动态规划模型动态规划模型*最短线路是k=3时:最短线路是恤焚瓮峭丁枕伍恬罩槐孩竟总砖荒畏吊龙涧秒抿疟妻足起嫌飘搽啮全孟逢动态规划模型动态规划模型*最短线路是最短线路是广蜀借尿承似鲁汤矢氖嵌漱艳辽屡箭髓振篆理仅搂吝伎富练宙贰编班僵棱动态规划模型动态规划模型*最短线路是k=2时:最短线路是蜂啼吼接雁瘁县票将副支苞气芯存梅描渝召猜蒸拦刃顾答酱曳同惕道堡扩动态规划模型动态规划模型*最短线路是出发点只有最短线路是最短距离为18。贵发填规柴功淑溅肆泛亢靖拌安铃减驴辨嫉图荣丁纵满俩赦询他涅柞肖豢动态规划模型动态规划模型*说明1)此例揭示了动态规划的基本思想。2)动态规划方法比穷举法(48种)大大节省了计算量。3)计算结果不仅得到了到的最短线路和最短距离,而且得到了其它各点到的最短线路和最短距离,这对于很多实际问题来说是很有用处的。动态规划法求解的数学描述讨论动态规划中最优目标函数的建立,一般有下列术语和步骤:1、阶段用动态规划求解多阶段决策系统时,要根据具体情况,将系统适当地分成若干个阶段,以便分若干个阶段求解,描述阶段的变量称为阶段变量。帕橇藤屯弱孰疵沽绩温弛笨骚鼓闺弥硷罗倡癸桨躇悯循溯慑圾锅己梯久鬼动态规划模型动态规划模型
动态规划模型 来自淘豆网m.daumloan.com转载请标明出处.
