动态规划的模型构建与优化方法

动态规划模型构建与优化长沙市第一中学曹利国综述动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。动态规划活跃在各种信息学竞赛，是因为其强大的实用性，可扩展性。动态规划程序设计是对解最优化问题的一种途径、一种方法、一种思维方式，而不是一种明确算法。分析思路1234动态规划是一种用于求解前后关联具有链状结构的多阶段决策过程的最优化问题的方法是否包含：重叠子结构是否具有：最优子结构构建对应模型编程求解什么是动态规划？（一）动态规划是解决多阶段决策问题的一种方法。多阶段决策问题对于整个问题，可以根据其时间或其他顺序分成若干个前后相关联的子问题，问题的全局最优包含其子问题的局部最优，即满足最优子结构性质，并且无后效性，有边界条件，且一般划分为很明显的阶段，存在一条或多条状态转移方程。取石子游戏N堆石子排成一行，每堆石子中有X[i]个石子，两人轮流从中取出石子，规定每次只能从最左边或最右边取出一堆石子，直至石子被全部取出，每个人所取的石子的总个数为个人的最后得分，得分多的人获胜。若两人得分相同，则规定首先取的人获胜。如果游戏开始时N为偶数，则对首先取的人来说，存在一种必胜的策略。请你编一个程序，作为首先取石子的人，寻找一种必胜的策略和计算机玩这个游戏，并让你自己保持不败。分析对于这道题，第一感觉便是贪心，但贪心存在反例：6,10,4,5。便也只能采用动态规划的方法。因为N是偶数，所以可将问题划分成N/2个阶段，第i个阶段处理所有相邻的2i堆石子，相当于双方的第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个数，按从左往右的顺序选择m个满足这m个数保持非降。用F[i]表示以第i个数结尾的序列最长能有多长。F[i]:=max(F[j])+1;jianda[j]=a[i]对例一的优化我们期望对于每个i，快速找到最优决策j，而这可以通过线段树进行优化。或者是换一个方程，用G[i]表示长度为i的最长不下降子串结尾最少是多少。很明显G[i]是不下降的。那么对于每个a[i]用二分查找最大的j是的G[j]=a[i]，那么F[i]:=G[j]+1，同时令G[F[i]]:=a[i]。例题二（区间模型）决斗问题已知n个人之间的决斗的胜负情况，现在n个人围成一圈，相邻的人可以决斗，输的就挂了，然后被移走，问是否有一种决斗顺序让X最终获胜。解法把x差成两个点x1,x2，展开，问题转化成两个x能否相遇。正难则反，从最后一步考虑。最后肯定剩下3个x1,t,x2。x1到t之间的都输了，t到x2之间的都输了。现在要x1打败t或x2打败t就行了。注意这些事件发生的顺序：首先用某种顺序让x1与t相遇，然后用某准顺序让x2与t相遇，最后让x1或x2打败t。继续用meet[i,j]表示i,j能否相遇，如果存在一个k(ikj),meet[i,k]andmeet[k,j]=true，并且i或j能击败k。注意到[i,k],[k,j]都是[i,j]的子区间，也就是说对于某个区间的决策都是它的子区间。所以可以按区间长度从小到大来动规。序列压缩给出一个N个正整数的序列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，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=MJ，K1取所有F[I，M]可以压缩成的数。边界：F[I，I，I]=TRUE如果F[1，N，T]的值为真，该问题有解，否则无解。至于求具体方案，可以用一个父结点数组记下推出F[I，J，K]的M、K1值。也可在最后用一个反向的动态规划找最优方案。从上面的动态规划方程可以看出，该算法在最坏的情况下时间复杂度将接近于10000^2*100^3，由于最后要输出最优方案，不可用滚动数组，因此它的空间复杂度为o(10000*100^2)，无论从时间还是空间上来看，该算法都不适合于该问题。算法二只要仔细分析问题不难看出，该问题是要我们在输入的第2至第N-1个数前面加减号，并且在这个式子中添入N-1个括号，使得式子最终的计算结果为给定的数T。我们不妨将所有的括号都拆掉，最后该式子将会成为一个没有括号的加减式。注意：只要稍加分析即可发现，该加减式的第二个数前面肯定是减号。反过来考虑，如果一个加减式的第二个数前面为减号，其余的数前面为“+”号或“-”号（第一个前面没有符号），那么该式子能否变为一个由N-1个括号和和减号组成的等价式呢？答案是肯定的。我们将连续的带“+”号的数用一个大括号括起来，就可把所有的“+”号变为减号，然后再在减号前面加一些无意义的括号即可（无意的括号实际上是加上以后不改变式子计算结果的括号）。一个实例：a1-a2+a3+a4+a5-a6-a7+a8+a9+a10-a11我们首先将连续带加号的数用括号括起来，那么式子就变为：a1-(a2-a3-a4-a5)-a6-(a7-a8-a9-a10)-a11此时所有的加号就变为了减号，我们还要在不将减号变为加号的情况下添完剩下的括号，其实这一步已经很好做了，最后的式子如下：(a1-(((((a2-a3)-a4)-a5)-a6)-(((a7-a8)-a9)-a10)))-a11))如果要按问题的要求输出方案，我们只要拿几个式子推一下即可发现，只要将所有加减号按其在式子中的位置顺序记录到一个字符串数组中，先输出所有加号当前在数组中的位置（按左到右的顺序输出），每输出一个加号的位置就将该加号从字符串中删去，当没有加号时，看式子中有多少个减号就输出多少个2。该方法不太好证明，不过只要用实例试着推一下就可以肯定它是正确的。12-（10-4）+（3-5）=12-10+4+3-5S=‘-++-’输出2321有了上面的分析，我们不难得出下面的动态规划算法：设F[I，J]表示在前I个数中添加减号，可否使式子的值为J。显然：F[I，J]=F[I-1，J+A[I]]ORF[I–1，J–A[I]]A[I]表示数I的值。边界：F[1，2]=A[1]-A[2]（第二个数前面必须添减号）当F[N，T]的值为真时，该问题有解，否则无解。由于最后求最优方案时要找路径，所以该算法最大空间复杂度为o(100*10000)时间复杂度最大为o(100*10000*2)最长公共子串问题（lcs)有两个字符串A，B，当存在一个严格递增的整数序列i1，i2，…，im，满足a1=bi1，a2=bi2，…，am=bim，我们则说A包含于B。例如，“adg”包含于“abcdefg”，而不包含于“gfedcba”。现在有三个字符串A，B，C，要求你找出一个满足以下条件的最长的字符串D。①D包含于A；②D包含于B；③D包含于C。输入：A，B，C。输出：D。分析首先，定义一个字串“前缀”的概念：给定一个字串s=s1…sm。对于I=0..m，定义s的第I个前缀为s’I=s1…si。三个输入串A，B，C的所有前缀组成了最长公共子串的子问题空间。由此，我们发现最长公共子串的最优子结构性质。设：A={a1，…，am}；B={b1，…，bn}；C={c1，…，ch}。A，B，C的最长公共子串为D={d1，…，dk}，D的长度为k。性质1：am=bn=ch，则dk=am=bn=ch且d’k-1是a’m-1，b’n-1，c’h-1的一个最长公共子串。性质2：am≠bn，am≠ch，bn=ch，则蕴含D是a’m-1和B、C的一个最长公共子串。性质3：bn≠am，bn≠ch，am=ch，则蕴含D是b’n-1和A、C的一个最长公共子串。性质4：ch≠am，ch≠bn，am=bn，则蕴含D是c’h-1和A、B的一个最长公共子串。由此可见，字串A、B和C的最长公共字串包含了三个字串前缀的最长公共字串，说明该问题具备最优子结构的性质。设f[I，j，k]为a’i，b’j，c’k的一个最长公共子串的长度（0≤i≤m，0≤j≤n，0≤k≤h）。f[m，n，h]为问题的解，则状态转移方程为：当（j=0）or（k=0）时，f[I，j，k]=0；当（ai=bj=ck）时，f[I，j，k]=f[I-1，j-1，k-1]+1；当（ai≠bj）或（bj≠ck）时，f[I，j，k]=max{f[I-1，j，k]，f[I，j-1，k]，f[I，j，k-1]}。拓展值得一提，最长公共子串类问题应用了一个技术。F[i,j]实际上是表示a的前i个b的前j个的最长公共子串，这种技术，我们称之为压缩技术。如果决策范围是随着状态的求值单调不减时可以使用这种技术。以后题目中经常出现。例子•在一个数列中找一个和最大的子序列。•用sum(i)表示前i个数的和，问题转化为要找max(sum(i)-sum(j))(ji)，sum(i)是确定的，维护sum(1)~sum(i-1)中最小的。注意随着i的增加j的可选域是增加的。这样才能使用压缩技术。例子的扩展•如果上述题目修改成，子序列的长度不超过m那要怎么做？决策变量满足单调性问题例题：火车票问题矩阵处理类动态规划模型工业时代（ski)某矿区是被划分成一个n*m的矩形区