《算法设计的基本思路.ppt》由会员分享，可在线阅读，更多相关《算法设计的基本思路.ppt（21页珍藏版）》请在三一文库上搜索。
1、算法设计的基本思路,赵建华 南京大学计算机系,一些基本思路,复用已有的计算结果 通过预处理或改变计算方法，计算出可共用的中间结果 避免或减少无效的计算,保存/查询中间计算结果的方法,待求解的问题可以逐层分解成多个小问题； Q分解成为Q1，Q2，Qn Qi分解成为Qi1，Qi2，Qim 如果Qij之间有很多重合的地方，那么我们可以在第一次求解Qij的时候记录结果，并且在之后通过查询来避免重复求解Qij。 在应用中，有某个问题需要多次求解。且每次求解有很多可以重复利用的情况。 这个可以看作是上面一个问题的衍生情况。,保存/查询的例子（1）,棋类博弈问题 每个玩家的得分是他的最大块棋子的个数。 得分
2、高的人赢得比赛。 问题：当棋盘上只有10个空格的时候，求是否某人一定赢。,描述,使用一个Config数据结构来描述棋局 记录了各个棋子的位置； 记录了下一步谁下 最基本的博弈递归函数 boolean win(Configure cfg) if(cfg是最终结局) 计算各个player的得分，并返回胜负结果 for(每个可能的后继结局cfg) if(!win(cfg) return true；/存在使对方必输的走法 return false ,中间结果的保存,Configure数据类型最多有1024个取值。 win函数的计算过程：有10!个执行轨迹，因此必然有很多次重复的计算过程。 解决方法：
3、使用数据结果保存各个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) /存在使对方必输的
4、走法 将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的一部
5、分。 那么，我们可以给每个数据分量添加一个额外的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(iT.Length) retu
6、rn 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的关键是求
7、出K到K的映射，它和S无关,K,K, ,串S：,KMP的总体算法,int Index_KMP(String S,String T,int pos) i=pos;j=1;/这里的串的第1个元素下标是1 while(iT.Length) return i-T.Length;/匹配成功 else return 0; ,KMP的NEXT,void get_nextval(String T,int ,通过预处理或改变计算方法,考虑如下的问题： 针对一个很长的数组的重复查询：第i到j个元素之间的所有元素的和（或者其它运算结果）？ 简单的做法就是对每个查询做一次 for(k = i; kj; k+) sum
8、 += Ak; 但是每次的计算结果都被抛弃了。 最简单的预处理： 将每n个元素分成n段，首先计算出各段的和。计算i到j的和时，如果整段都在i-j的范围内就可以直接使用这个和。,树型结构的预处理更好的方法,假设数组有N个元素，预处理如下： 首先，将相邻的2个元素组成一组，得到N/2个和。 将相邻的和再合并成为一组，得到N/4个和。 如此重复，直到最后合并成为一个和。 将这些和作为结点，就得到一个二叉树。,A,查询的实现,查询就变成了对树型结构的查询，每次查询的复杂度为O(lnN)： getSum(node, i, j) if(node.leftBnd j ) return 0; if(node.
9、rightBnd I ) return 0; if(node.leftBnd i 其中，node.sum表示这个结点的子树的叶子结点之和。,指定源结点的最短路径算法,问题： 有n个结点。结点之间的路径使用矩阵M表示：Mi,j表示i和j之间的距离。 指定一个结点I，求出各个结点到I的最短路径长度。 最原始的迭代算法： 使用一个数组D ，Dk表示从I到k的最短路径长度。 初始化时DI=0，其余为无穷大； 对于结点v，如果存在结点w满足DvDw+Mw,v，那么将Dv修改为Dw+Mw,v。 不断迭代，到收敛为止。 这个算法可以得出正确结果，但是效率差。 原因是有很多无效的计算 在迭代中得到了某个结点w
10、的某个Dw之后，很可能以后会被覆盖掉。而由这个Dw 产生的其他路径长度也会被覆盖掉。这些计算过程都是无效的。,例子,如果首先按照abc，abe这样的计算过程，那么计算得到的a-c，a-e的距离都是无效的。,5,2,1,5,4,3,a,b,c,e,d,f,尽可能地减少无效值的计算,Dijkstra的最短路径算法 算法： 、 在中选择一个k最小的结点k，将k并入，并从中去掉，如果为则转到； 、 用k结点和中其余结点进行一遍比较，如果DiDk+Mki，则用Dk+Mki取代原来的i，重复； 、算法结束，此时m中保存的就是从到m结点的最短路径。 原理：每次被加入到S的结点k的Dk值不会被改变。,例子（1）,POJ2227 The Wedding Juicer 由高度不一，底部为单位正方形的木柱组成的一个正方形； 问这样的正方形可以装多少液体； 某个木柱上方可以存放的液体的高度相当于最小的从该木柱到达边缘的路径上的最高高度。 可以使用类似于Dijkstra算法的思想解决；,例子二,POJ3467 CrossCounting 存在一个NXM个单元组成的矩形； 每个单元被染有c种颜色之一 操作： 将某个单元染成某种颜色； 询问某种颜色的十字架有多少个； 方法： 中间结果记录下各种颜色的十字架的个数； 每次染色之后，更改这个中间结果；,