算法设计的基本思路

算法设计的基本思路赵建华南京大学计算机系一些基本思路 复用已有的计算结果 通过预处理或改变计算方法，计算出可共用的中间结果 避免或减少无效的计算保存/查询中间计算结果的方法 待求解的问题可以逐层分解成多个小问题；Q分解成为Q1，Q2，Qn Qi分解成为Qi1，Qi2，Qim 如果Qij之间有很多重合的地方，那么我们可以在第一次求解Qij的时候记录结果，并且在之后通过查询来避免重复求解Qij。在应用中，有某个问题需要多次求解。且每次求解有很多可以重复利用的情况。这个可以看作是上面一个问题的衍生情况。保存/查询的例子（1）棋类博弈问题 每个玩家的得分是他的最大块棋子的个数。得分高的人赢得比赛。问题：当棋盘上只有10个空格的时候，求是否某人一定赢。描述使用一个Config数据结构来描述棋局记录了各个棋子的位置；记录了下一步谁下最基本的博弈递归函数boolean win(Configure cfg)if(cfg是最终结局)计算各个player的得分，并返回胜负结果for(每个可能的后继结局cfg)if(!win(cfg)return true；/存在使对方必输的走法return false中间结果的保存 Configure数据类型最多有1024个取值。win函数的计算过程：有10!个执行轨迹，因此必然有很多次重复的计算过程。解决方法：使用数据结果保存各个Configure的结果；win函数在每次调用之前首先查询，如果已经计算过则不需要查询；在调用返回之前，将此结果存放到map中 保证了每个Configure只需要计算一次 如何保存结果？伪代码boolean win(int playerNo,Configure cfg)if(map(PlayerNo,cfg)有定义)return map(PlayerNo,cfg)if(cfg是最终结局)计算各个player的得分，并返回胜负结果for(每个可能的后继结局cfg)if(!win(1-playerNo,Configure cfg)/存在使对方必输的走法将map(PlayerNo,cfg)设置为true；return true；将map(PlayerNo,cfg)设置为falsereturn false；进一步考虑 可以改变计算得分的方法来提高效率。只有最终格局才可以算出最后的得分，但是 一个格局可以生成多个后继格局；可以改变计算得分的方法 对于每个格局，计算中间结果：分成多少相连的块，每块的棋子个数是多少；后继格局的中间结果可以依据前驱格局的结果快速计算得到；。另一个情况 对于某个数据类型D，我们需要计算其函数值f，且f(D)定义为F(g(D1),g(D2),g(Dn)，其中 Di是D的数据分量，或者是D的一部分。那么，我们可以给每个数据分量添加一个额外的cache域g。当cache有效时，g的值就等于g(Di)。当Di的值被修改时，Di.g的值无效。计算f的时候，如果Di.g的值有效，那么不需要计算g(Di)；否则在计算g(Di)之后，将Di.g设置为结果值。当f的执行次数较多，而对Di的修改相对不频繁的时候，这个技术适用。大家考虑一下排版的算法如何提高效率。（假设一个字符就是一个box）字符串匹配算法原始匹配算法int Index(String S,String T,int pos)i=pos;j=1;/这里的串的第1个元素下标是1 while(i=S.Length&jT.Length)return i-T.Length;/匹配成功 else return 0;在没有匹配成功的时候，从下一个位置开始重新匹配。其实我们在尝试匹配的时候，可以得到有关S的很多信息。KMP算法就能够充分利用这些信息串匹配的KMP算法 由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现。如果我们在尝试到T的第K的字符时失败，那么说明从i开始的k的字符就是T的一个前缀。这个信息可以告诉我们什么呢？我们可以预先求出这个信息：如果有一个串是T的长度为K的前缀，那么它的同样为T的前缀的、最长真后缀有多长？假设长度为K，那么我们可以跳过K-K个符号，试图匹配这个符号。KMP的关键是求出K到K的映射，它和S无关KK 串S：KMP的总体算法int Index_KMP(String S,String T,int pos)i=pos;j=1;/这里的串的第1个元素下标是1 while(i=S.Length&jT.Length)return i-T.Length;/匹配成功 else return 0;KMP的NEXTvoid get_nextval(String T,int&next)i=1;j=0;next1=0;while(i j)return 0;if(node.rightBnd Dw+Mw,v，那么将Dv修改为Dw+Mw,v。不断迭代，到收敛为止。这个算法可以得出正确结果，但是效率差。原因是有很多无效的计算 在迭代中得到了某个结点w的某个Dw之后，很可能以后会被覆盖掉。而由这个Dw 产生的其他路径长度也会被覆盖掉。这些计算过程都是无效的。例子 如果首先按照abc，abe这样的计算过程，那么计算得到的a-c，a-e的距离都是无效的。521543abcedf尽可能地减少无效值的计算Dijkstra的最短路径算法算法：、在中选择一个k最小的结点k，将k并入，并从中去掉，如果为则转到；、用k结点和中其余结点进行一遍比较，如果DiDk+Mki，则用Dk+Mki取代原来的i，重复；、算法结束，此时m中保存的就是从到m结点的最短路径。原理：每次被加入到S的结点k的Dk值不会被改变。例子（1）POJ2227 The Wedding Juicer 由高度不一，底部为单位正方形的木柱组成的一个正方形；问这样的正方形可以装多少液体；某个木柱上方可以存放的液体的高度相当于最小的从该木柱到达边缘的路径上的最高高度。可以使用类似于Dijkstra算法的思想解决；24456413251537810792104520104例子二 POJ3467 CrossCounting 存在一个NXM个单元组成的矩形；每个单元被染有c种颜色之一 操作：将某个单元染成某种颜色；询问某种颜色的十字架有多少个；方法：中间结果记录下各种颜色的十字架的个数；每次染色之后，更改这个中间结果；