算法设计的基本思路

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法设计的基本思路,1,一些基本思路,复用已有的计算结果,通过预处理或改变计算方法，计算出可共用的中间结果,避免或减少无效的计算,2,保存,/,查询中间计算结果的方法,待求解的问题可以逐层分解成多个小问题；,Q,分解成为,Q1,，,Q2,，,，,Qn,Qi,分解成为,Qi1,，,Qi2,，,，,Qim,如果,Qij,之间有很多重合的地方，那么我们可以在第一次求解,Qij,的时候记录结果，并且在之后通过查询来避免重复求解,Qij,。,在应用中，有某个问题需要多次求解。且每次求解有很多可以重复利用的情况。,这个可以看作是上面一个问题的衍生情况。,3,保存,/,查询的例子（,1,）,棋类博弈问题,每个玩家的得分是他的最大块棋子的个数。,得分高的人赢得比赛。,问题：当棋盘上只有,10,个空格的时候，求是否某人一定赢。,4,描述,使用一个,Config,数据结构来描述棋局,记录了各个棋子的位置；,记录了下一步谁下,最基本的博弈递归函数,boolean win(Configure cfg),if(cfg,是最终结局,),计算各个,player,的得分，并返回胜负结果,for(,每个可能的后继结局,cfg),if(!win(cfg),return true,；,/,存在使对方必输的走法,return false,5,中间结果的保存,Configure,数据类型最多有,1024,个取值。,win,函数的计算过程：有,10!,个执行轨迹，因此必然有很多次重复的计算过程。,解决方法：,使用数据结果保存各个,Configure,的结果；,win,函数在每次调用之前首先查询，如果已经计算过则不需要查询；,在调用返回之前，将此结果存放到,map,中,保证了每个,Configure,只需要计算一次,如何保存结果？,6,伪代码,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,；,7,进一步考虑,可以改变计算得分的方法来提高效率。,只有最终格局才可以算出最后的得分，但是,一个格局可以生成多个后继格局；,可以改变计算得分的方法,对于每个格局，计算中间结果：分成多少相连的块，每块的棋子个数是多少；,后继格局的中间结果可以依据前驱格局的结果快速计算得到；,。,8,另一个情况,对于某个数据类型,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,）,9,字符串匹配算法,原始匹配算法,int Index(String S,String T,int pos) i=pos;j=1;/,这里的串的第,1,个元素下标是,1 while(iT.Length) return i-T.Length;/,匹配成功,else return 0;,在没有匹配成功的时候，从下一个位置开始重新匹配。,其实我们在尝试匹配的时候，可以得到有关,S,的很多信息。,KMP,算法就能够充分利用这些信息,10,串匹配的,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,无关,K,K, ,串,S,：,11,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;,12,KMP,的,NEXT,void get_nextval(String T,int ,/,消去多余的可能的比较,next,再向前跳, else j=nextj; ,13,通过预处理或改变计算方法,考虑如下的问题：,针对一个很长的数组的重复查询：第,i,到,j,个元素之间的所有元素的和（或者其它运算结果）？,简单的做法就是对每个查询做一次,for(k = i; kj; k+),sum += Ak;,但是每次的计算结果都被抛弃了。,最简单的预处理：,将每,n,个元素分成,n,段，首先计算出各段的和。计算,i,到,j,的和时，如果整段都在,i-j,的范围内就可以直接使用这个和。,14,树型结构的预处理,更好的方法,假设数组有,N,个元素，预处理如下：,首先，将相邻的,2,个元素组成一组，得到,N/2,个和。,将相邻的和再合并成为一组，得到,N/4,个和。,如此重复，直到最后合并成为一个和。,将这些和作为结点，就得到一个二叉树。,A,15,查询的实现,查询就变成了对树型结构的查询，每次查询的复杂度为,O(lnN),：,getSum(node, i, j),if(node.leftBnd j ) return 0;,if(node.rightBnd Dw+Mw,v,，那么将,Dv,修改为,Dw+Mw,v,。,不断迭代，到收敛为止。,这个算法可以得出正确结果，但是效率差。,原因是有很多无效的计算,在迭代中得到了某个结点,w,的某个,Dw,之后，很可能以后会被覆盖掉。而由这个,Dw,产生的其他路径长度也会被覆盖掉。这些计算过程都是无效的。,17,例子,如果首先按照,a,bc,，,abe,这样的计算过程，那么计算得到的,a-c,，,a-e,的距离都是无效的。,5,2,1,5,4,3,a,b,c,e,d,f,18,尽可能地减少无效值的计算,Dijkstra,的最短路径算法,算法：,、 在中选择一个,k,最小的结点,k,，将,k,并入，并从中去掉，如果为则转到；,、 用,k,结点和中其余结点进行一遍比较，如果,DiDk+Mki,，则用,Dk+Mki,取代原来的,i,，重复；,、算法结束，此时,m,中保存的就是从到,m,结点的最短路径。,原理：每次被加入到,S,的结点,k,的,Dk,值不会被改变。,19,例子（,1,）,POJ2227 The Wedding Juicer,由高度不一，底部为单位正方形的木柱组成的一个正方形；,问这样的正方形可以装多少液体；,某个木柱上方可以存放的液体的高度相当于最小的从该木柱到达边缘的路径上的最高高度。,可以使用类似于,Dijkstra,算法的思想解决；,2,4,4,5,6,4,1,3,2,5,1,5,3,7,8,10,7,9,2,10,4,5,20,10,4,20,例子二,POJ3467 CrossCounting,存在一个,NXM,个单元组成的矩形；,每个单元被染有,c,种颜色之一,操作：,将某个单元染成某种颜色；,询问某种颜色的十字架有多少个；,方法：,中间结果记录下各种颜色的十字架的个数；,每次染色之后，更改这个中间结果；,21,