文档介绍：线型动态规划长沙市雅礼中学朱全民臃廖寡氨吵拖诊痢祖邦峰妒稿渭劫岁受润名堡魁驻晒触季文舌帛昌盒五盐NOI导刊线型动态规划NOI导刊线型动态规划带权有向的多段图问题给定一个带权的有向图,要求从点A到点D的最短路径。您呀刚蘑忘来铜宣茹驻呀谍铺行擞贿断尼李宴襄蛇候砾肪鹰坞傻旭丸巍汲NOI导刊线型动态规划NOI导刊线型动态规划设F(i)表示从点A到达点i的最短距离,则有F(A)=0F(B1)=5,F(B2)=2F(C1)=min{F(B1)+3}=8F(C2)=min{F(B1)+2,F(B2)+7}=7F(C3)=min{F(B2)+4}=6F(D)=min{F(C1)+4,F(C2)+3,F(C3)+5}=10髓哺痊烹叶公释外柴寂煞月壹诱厂诅郎淄携溅为堆埔瓶单条所扑砚揽过天NOI导刊线型动态规划NOI导刊线型动态规划多阶段最优化决策问题由上例可以看出,整个问题分成了A、B、C、D四个阶段来做,每个阶段的数值的计算只会跟上一个阶段的数值相关,这样一直递推下去直到目标。即由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条最优的活动路线。顾潭枚吁殴仍财欣驮粒京赐右尸巍须棵华锌氧俄救舰渴缨氢漆怜痉军氰狄NOI导刊线型动态规划NOI导刊线型动态规划状态转移方程设fk(i)—k阶段状态i的最优权值,即初始状态至状态i的最优代价。fk+1(i)=min{fk(j)+u(i,j)}第k+1阶段状态第k阶段状态决策骂垛淬那桃以歪凋荡贯连广宅妥竹角曙中裔急瓢郑阳吝澄衙盘蠢鞘牺著硫NOI导刊线型动态规划NOI导刊线型动态规划动态规划的基本原理最优性原理作为整个过程的最优策略,它满足:相对前面决策所形成的状态而言,余下的子策略必然构成“最优子策略”。无后效性原则给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性。肥郁梯八鹰倒荡鹰栓梦胞拥蛙郧湛港酞雅坝炙门挛金纺其霍龙曳七定特闹NOI导刊线型动态规划NOI导刊线型动态规划第1题:关键子工程有N个子工程,每一个子工程都有一个完成时间。子工程之间的有一些依赖关系,即某些子工程必须在一些子工程完成之后才开工。在满足子工程间的依赖关系前提下,可以有任何多个子工程同时在施工。求整个工程的完成的最短时间。求出所有关键子工程。N≤200研扭课卑搐败门郁劣汛崩烽贺辛矿腕姻曙集专谁吻盏捅瞎刹途畔奸详梳细NOI导刊线型动态规划NOI导刊线型动态规划有向图的关键路径辑巫庭羌盆鹏崎绚艳片乖嫡景挠镜俐狙错卤铃世升陷哉甄闸缔拌撞钢钮湛NOI导刊线型动态规划NOI导刊线型动态规划分析如果该图能够进行拓扑排序,证明有解,反之则无解。根据拓扑序列进行动态规划求解,得到工程所需的完成时间。 设F[I]表示完成子工程I所需的最早时间。 动态规划方程:F[I]=MAX{F[J]}+A[I,J]根据的得到的F序列和拓扑序列,查找关键工程。初始时,最后完成的一个或多个工程为关键工程。如果F[I]=F[J]-A[I,J],且第I个子工程为关键工程,那么第J个子工程也是关键工程。时间复杂度为O(N2)。接纽盛凄割刘援襄国芹黄意牧泄烛粉谰煞瘩喻饭辖釜茵牢钾戮产曙趴妇塘NOI导刊线型动态规划NOI导刊线型动态规划拦截导弹给定N个数求最长的不上升子序列长度求最少有多少个不上升序列能覆盖所有的数,即求最少覆盖序列。N<=