DP-线型动态规划

《DP-线型动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线型动态规划长沙市雅礼中学朱全民带权有向的多段图问题给定一个带权的有向图，要求从点A到点D的最短路径。设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多阶段最优化决策问题由上例可以看出，整个问题分成了A、B、C、D四个阶段来做，每个阶段的数值的计算只会跟上一个阶段的数值相关，这样一直递推下去直到目标。即

2、由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条最优的活动路线。状态转移方程设fk(i)—k阶段状态i的最优权值，即初始状态至状态i的最优代价。fk+1(i)=min{fk(j)+u(i,j)}第k+1阶段状态第k阶段状态决策动态规划的基本原理最优性原理作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。无后效性原则给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。这个性

3、质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。第1题：关键子工程有N个子工程，每一个子工程都有一个完成时间。子工程之间的有一些依赖关系，即某些子工程必须在一些子工程完成之后才开工。在满足子工程间的依赖关系前提下，可以有任何多个子工程同时在施工。求整个工程的完成的最短时间。求出所有关键子工程。N≤200有向图的关键路径分析如果该图能够进行拓扑排序，证明有解，反之则无解。根据拓扑序列进行动态规划求解，得到工程所需的完成时间。设F[I]表示完成子工程I所需的最早时间。动态规划方程：F[I]=MAX{F[J]}+A[I

4、，J]根据的得到的F序列和拓扑序列，查找关键工程。初始时，最后完成的一个或多个工程为关键工程。如果F[I]=F[J]-A[I，J]，且第I个子工程为关键工程，那么第J个子工程也是关键工程。时间复杂度为O(N2)。拦截导弹给定N个数求最长的不上升子序列长度求最少有多少个不上升序列能覆盖所有的数，即求最少覆盖序列。N<=10000.分析设f(i)表示前i个数的最长不上升序列的长度。则,f(i)=max{f(j)+1},其中j=a[i]这里0

5、i个数小,对于所有的j取f(j)的最大值。优化分析样例这里找j,是在1~i之间进行寻找，那么我们能否快速查找到我们所要更改的j呢?要能更改需要两个条件：j=a[i]f(j)尽可能大以上两个条件提示我们后面的值一定要小于等于前面的值。因此我们试着构建一个下降的序列。在这个下降的序列中查找可以更改的f值,使得序列的值尽可能大。i1234567838920715530029917015865f12323456具体过程：i1234567838920715530029917015865第1次389第2次389207第3次3892071

6、55第4次389300155（由于207<300<389,因此更新）第5次389300299（由于155<299<300,因此更新）第6次389300299170第7次389300299170158第8次38930029917015865思考？有些同学可能会问:对于每个f,为什么只保留一个数值呢?而对于该序列，为什么要保留较大的值呢？1.再回过头来看方程:f(i)=max{f(j)+1},其中j=a[i]该式子表示找前面的一个最大f的符合条件的j,因此只要保存符合条件的最大的j就可以了。在f值相同的情况下，保留较大的数显然更

7、好。因为后面的数若能跟较小的数构成下降序列也一定能能较大的数构成下降序列，反之则不一定。例如207与300的f=2,但207不能与299构成下降序列，而300则可以。因为生成的序列为有序序列，因此我们可以采用二分查找的方法很快查找到更新的值，时间复杂度为O(n㏒n)求导弹的最小覆盖第二问很容易想到贪心法：那就是采取多次求最长不上升序列的办法，然后得出总次数。上述贪心法不正确，很容易就能举出反例。例如：“7541632”用多次求最长不上升序列所有为“75432”、“1”、“6”共3套系统；但其实只要2套，分别为：“7541”与“632”。那么，正

8、确的做法又是什么呢？分析上述问题的原因是若干次最优决策值和不一定能推导出整个问题的最优。为了解决这个问题下面介绍一个重要性质：最少链划分=最长反链长度