动态规划模型建立与优化方法ppt课件.ppt

《动态规划模型建立与优化方法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划(三)模型构建与优化方法动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。动态规划活跃在各种信息学竞赛，是因为其强大的实用性，可扩展性。动态规划程序设计是对解最优化问题的一种途径、一种方法、一中思维方式，而不是一种明确算法。动态规划的核心——记忆化动态规划算法通过将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解的方法得到原问题的解。对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。例题一最长非降子序列问题。给

2、你一字排开的n个数，按从左往右的顺序选择m个满足这m个数保持非降。用F[i]表示以第i个数结尾的序列最长能有多长。F[i]:=max(F[j])+1;j

3、X[i]个石子，两人轮流从中取出石子，规定每次只能从最左边或最右边取出一堆石子，直至石子被全部取出，每个人所取的石子的总个数为个人的最后得分，得分多的人获胜。若两人得分相同，则规定首先取的人获胜。如果游戏开始时N为偶数，则对首先取的人来说，存在一种必胜的策略。请你编一个程序，作为首先取石子的人，寻找一种必胜的策略和计算机玩这个游戏，并让你自己保持不败。分析对于这道题，第一感觉便是贪心，但贪心存在反例：6,10,4,5。便也只能采用动态规划的方法。因为N是偶数，所以可将问题划分成N/2个阶段，第i个阶段处理所有相邻的2i堆石

4、子，相当于双方的第N/2-i+1个回合。对每一种状态，作出取左边还是取右边的决策，同时，还需要考虑计算机作出决策后，人也要作出相应的最佳决策。看起来对于人的两种决策，似乎有些难以考虑，但只要将人作出最佳决策转化为计算机作出较差决策，问题便迎刃而解。分析设b[i,j]表示第i到第j堆石子中，计算机最多可获得的得分，且总堆数j-i+1为偶数动态转移方程为：b[i,j]=max(a[i]+min(b[i+2,j],b[i+1,j-1]),a[j]+min(b[i,j-2],b[i+1,j-1]))初始条件为？序列压缩给出一个N个

5、正整数的序列A=[A1,A2,……,AN],我们可以对其进行压缩操作.所谓压缩操作是指:将两个相邻的元素AI和AI+1的差(AI-AI+1)去替代第I个元素,同时删去第I+1个元素,严格地可以定义如下:CON(A,I)=[A1,,A2,….,AI-1,AI-AI+1,AI+2,…….AN]经过一次序列压缩之后,我们可以得到一个N-1个元素的序列,如此进行下去,我们可以仅得到单一的一个整数。现给定一个正整数序列和一个目标整数T，求解并输出压缩顺序。1〈=N〈=100，-10000〈=T〈=10000示例：con（[12，10

6、，4，3，5]，2）=[12，6，3，5]con（[12，6，3，5]，3）=[12，6，-2]con（[12，6，-2]，2）=[12，8]con（[12，8]，1）=[4]算法一看了题目最容易想到动态规划算法是石子合并问题与骨牌问题相结合的方法。其算法如下：设F[I，J，K]表示将第I个数到第J个数按规则压缩，最后能否压缩成数K。不难得出动态转移方程为：F[I,J,K]=Falseor(F[I,M,K1]andF[M+1,J,K1-K])其中I<=M

7、RUE如果F[1，N，T]的值为真，该问题有解，否则无解。至于求具体方案，可以用一个父结点数组记下推出F[I，J，K]的M、K1值。也可在最后用一个反向的动态规划找最优方案。从上面的动态规划方程可以看出，该算法在最坏的情况下时间复杂度将接近于10000^2*100^3，由于最后要输出最优方案，不可用滚动数组，因此它的空间复杂度为o(10000*100^2)，无论从时间还是空间上来看，该算法都不适合于该问题。算法二只要仔细分析问题不难看出，该问题是要我们在输入的第2至第N-1个数前面加减号，并且在这个式子中添入N-1个括号，

8、使得式子最终的计算结果为给定的数T。我们不妨将所有的括号都拆掉，最后该式子将会成为一个没有括号的加减式。注意：只要稍加分析即可发现，该加减式的第二个数前面肯定是减号。反过来考虑，如果一个加减式的第二个数前面为减号，其余的数前面为“+”号或“-”号（第一个前面没有符号），那么该式子能否变为一个由N-1个括