算法设计基本思路.pptVIP

* * * * * * * * * * * 算法设计的基本思路 赵建华 南京大学计算机系 一些基本思路 复用已有的计算结果 通过预处理或改变计算方法，计算出可共用的中间结果 避免或减少无效的计算 保存/查询中间计算结果的方法 待求解的问题可以逐层分解成多个小问题； 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)设置为false return 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 j=T.Length)?? {???? if(S[i]==T[j]){++i;++j;}???? else{i=i-j+2;j=1;} ?? }?? if(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的关键是求出