线型动态规划.ppt

文档介绍：线型动态规划
带权有向的多段图问题
给定一个带权的有向图,要求从点A到点D的最短路径。
设F(i)表示从点A到达点i的最短距离,则有
F(A)=0
F(B1)=5,F(B2)=2
F(C1)=min{F(B1)+3}=8
F(C2)=min{F(B1)+2,F(B2)+7}=7
F(C3)=min{F(B2)+4}=6
F(D)=min{F(C1)+4,F(C2)+3,F(C3)+5}=10
多阶段最优化决策问题
由上例可以看出,整个问题分成了A、B、C、D四个阶段来做,每个阶段的数值的计算只会跟上一个阶段的数值相关,这样一直递推下去直到目标。
即由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条最优的活动路线。
状态转移方程
设fk(i)—k阶段状态i的最优权值,即初始状态至状态i的最优代价。
fk+1(i) = min{ fk(j) + u(i,j) }
第k+1阶
段状态
第k阶
段状态
决策
动态规划的基本原理
最优性原理

作为整个过程的最优策略,它满足:相对前面决策所形成的状态而言,余下的子策略必然构成“最优子策略”。
无后效性原则

给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性。
第1题:关键子工程
有N个子工程,每一个子工程都有一个完成时间。
子工程之间的有一些依赖关系,即某些子工程必须在一些子工程完成之后才开工。
在满足子工程间的依赖关系前提下,可以有任何多个子工程同时在施工。
求整个工程的完成的最短时间。
求出所有关键子工程。
N≤200
有向图的关键路径
分析
如果该图能够进行拓扑排序,证明有解,反之则无解。
根据拓扑序列进行动态规划求解,得到工程所需的完成时间。
设 F[I]表示完成子工程I所需的最早时间。
动态规划方程:F[I]=MAX{F[J]}+ A[I,J]
根据的得到的F序列和拓扑序列,查找关键工程。初始时,最后完成的一个或多个工程为关键工程。如果F[I]=F[J]- A[I,J] ,且第I个子工程为关键工程,那么第J个子工程也是关键工程。
时间复杂度为O(N2)。
拦截导弹
给定N个数
求最长的不上升子序列长度
求最少有多少个不上升序列能覆盖所有的数,即求最少覆盖序列。
N<=10000.