文档介绍：动态规划基础
长沙市雅礼中学朱全民
NOIP的动态规划试题
加分二叉树(2003)—树型动态规划
合唱队形(2004)—线型动态规划
青蛙过河(2005)—线型动态规划
能量项链(2006)—合并类型动态规划
金明的预算方案(2006)—资源类型动态规划
矩阵取数游戏(2007)—规则类型动态规划
传纸条(2008)—规则类型动态规划
最优贸易(2009)—也可以用动态规划处理
乌龟棋(2010) —线型动态规划
第1题:关键工程
有N个子工程,每一个子工程都有一个完成时间。
子工程之间的有一些依赖关系,即某些子工程必须在一些子工程完成之后才开工。
在满足子工程间的依赖关系前提下,可以有任何多个子工程同时在施工。
求整个工程的完成的最短时间。
求出所有关键子工程。
N≤200
一个实例
怎样确定关键工程
关键工程是不能提早开工也不能推迟开工的工程。
所谓不能提早,就是指“最早开工时间”,也就是该工程的所有前趋工程都完成后,即可开工
所谓不能推迟,就是指“最迟开工时间”也就是说,如果推迟,那么整个任务的工程进度将会受到影响。
若某工程“最早开工时间”= “最迟开工时间”,则该工程为关键工程。
求最早开工时间
最早开工时间,即从起点到该点的最长距离。
设 F[i]表示完成子工程i所需的最早时间。则
F[i]=Max{F[j]}+ A[i,j] {j为i的前趋}
F(1)=0,F(2)=6,F(3)=4,F(4)=5
F(5)=Max {6+1,4+1}=7,F(6)=5+2=7
F(7)=Max {F(5)+9}=16
F(8)=Max{F(6)+4,F(5)+7}=Max {7+4,7+7}=14
F(9)=Max {F(7)+2,F(8)+4}=Max {16+2,14+4}=18
求最迟开工时间
这需要从后往前推,找出最小值即可。
设设 G[i]表示完成子工程i所需的最早时间。则
G[i]=Min{G[j]}-A[i,j] {j为i的后继}
G(9)=18,
G(7)=18-2=16,G(8)=18-4=14
G(6)=G(8)-4=14-4=10, G(5)=Min{G(7)-9,G(8)-7}=Min{16-9,14-7}=7
G(4)=G(6)-2=8, G(3)=G(5)-1=6, G(2)=G(5)-1=6
G(1)=Min{G(2)-6,G(3)-4,G(4)-5}=Min{6-6,6-4,8-5}=0
阶段、状态、决策
由上例可以看出,整个问题分成了若干个阶段来做,每个阶段的数值(状态的值)的计算只会跟上一个阶段的数值(状态的值)相关(决策转移),这样一直递推下去直到目标。
这样可以由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条最优的活动路线。
状态转移方程
设fk(i)—k阶段状态i的最优权值,即初始状态至状态i的最优代价。
fk+1(i) = Max{ fk(j) + u(i,j) }
第k+1阶
段状态
第k阶
段状态
决策
动态规划的理论基础
最优性原理
作为整个过程的最优策略,它满足:相对前面决策所形成的状态而言,余下的子策略必然构成“最优子策略”。
无后效性原则
给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性。