蛮力法

算法设计与分析清华大学出版社第3章蛮力法3.1蛮力法的设计思想3.2查找问题中的蛮力法3.3排序问题中的蛮力法3.4组合问题中的蛮力法3.5图问题中的蛮力法3.6几何问题中的蛮力法3.7实验项目——串匹配问题算法设计与分析清华大学出版社3.1蛮力法的设计思想蛮力法的设计思想：直接基于问题的描述。例：计算ann次an=a×a×…×a算法设计与分析清华大学出版社蛮力法所赖的基本技术——扫描技术关键——依次处理所有元素基本的扫描技术——遍历（1）集合的遍历（2）线性表的遍历（3）树的遍历（4）图的遍历算法设计与分析清华大学出版社虽然巧妙和高效的算法很少来自于蛮力法，基于以下原因，蛮力法也是一种重要的算法设计技术：（1）理论上，蛮力法可以解决可计算领域的各种问题。（2）蛮力法经常用来解决一些较小规模的问题。（3）对于一些重要的问题蛮力法可以产生一些合理的算法，他们具备一些实用价值，而且不受问题规模的限制。（4）蛮力法可以作为某类问题时间性能的底限，来衡量同样问题的更高效算法。算法设计与分析清华大学出版社3.2查找问题中的蛮力法3.2.1顺序查找3.2.2串匹配问题算法设计与分析清华大学出版社顺序查找从表的一端向另一端逐个将元素与给定值进行比较，若相等，则查找成功，给出该元素在表中的位置；若整个表检测完仍未找到与给定值相等的元素，则查找失败，给出失败信息。3.2.1顺序查找101524612354098550123456789i查找方向算法设计与分析清华大学出版社算法3.1——顺序查找intSeqSearch1(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{i=n;while(i0&&r[i]!=k)i--;returni;}算法3.1的基本语句是i0和r[i]!=k，其执行次数为:ninininiiiiinOninninncpbp1111)(1)1(1)1(1基本语句？算法设计与分析清华大学出版社将待查值放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高了查找速度。k101524612354098550123456789i查找方向哨兵改进的顺序查找算法设计与分析清华大学出版社算法3.2——改进的顺序查找intSeqSearch2(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{r[0]=k;i=n;while(r[i]!=k)i--;returni;}算法3.2的基本语句是r[i]!=k，其执行次数为:niniiinOninncp11)(21)1(1数量级相同，系数相差一半算法设计与分析清华大学出版社用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能，但只能减少系数，而数量级不会改变。一般观点：算法设计与分析清华大学出版社3.2.2串匹配问题串匹配问题属于易解问题。串匹配问题的特征：（1）算法的一次执行时间不容忽视：问题规模n很大，常常需要在大量信息中进行匹配；（2）算法改进所取得的积累效益不容忽视：串匹配操作经常被调用，执行频率高。串匹配问题——给定两个串S=“s1s2…sn”和T=“t1t2…tm”，在主串S中查找子串T的过程称为串匹配，也称模式匹配。算法设计与分析清华大学出版社基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是n-m，则主串S中剩下的字符不足够匹配整个模式T，匹配失败。这个算法称为朴素的模式匹配算法，简称BF算法。蛮力法解决串匹配问题——BF算法算法设计与分析清华大学出版社本趟匹配开始位置si……主串S模式Ttjj回溯回溯i…算法设计与分析清华大学出版社设主串s=“ababcabcacbab”，模式t=“abcac”ababcabcacbababci=3，j=3失败；i回溯到2，j回溯到1第1趟ijijijij算法设计与分析清华大学出版社ababcabcacbabaijij第2趟i=2，j=1失败i回溯到3，j回溯到1第3趟ababcabcacbababcaci=7，j=5失败i回溯到4，j回溯到1ijijijijijji算法设计与分析清华大学出版社第4趟ababcabcacbabaiji=4，j=1失败i回溯到5，j回溯到1ji第5趟ababcabcacbabijajii=5，j=1失败i回溯到6，j回溯到1算法设计与分析清华大学出版社第6趟ababcabcacbababcaci=11，j=6，t中全部字符都比较完毕，匹配成功。ijijijijijij算法设计与分析清华大学出版社intBF(charS[],charT[]){i=1;j=1;while(i=S[0]&&j=T[0]&&j=T[0])){if(S[i]==T[j]){i++;j++;}else{i=i-j+2;j=1;}}if(jT[0])return(i-j+1);elsereturn0;}BFC++算法算法设计与分析清华大学出版社设串S长度为n，串T长度为m，在匹配成功的情况下，考虑最坏情况，即每趟不成功的匹配都发生在串T的最后一个字符。例如：S=aaaaaaaaaaabT=aaab设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了(i-1)×m次，第i趟成功的匹配共比较了m次，所以总共比较了i×m次，因此平均比较次数是：11112)2()(11)(mnimniimnmmimnmip算法设计与分析清华大学出版社改进的串匹配算法——KMP算法设计思想：尽量利用已经部分匹配的结果信息，尽量让i不回溯，加快模式串的滑动速度。算法设计与分析清华大学出版社ababcabcacbababci=3，j=3失败；第1趟iiijababcabcacbabaij第2趟s2=t2;t1≠t2∴t1≠s2jj算法设计与分析清华大学出版社第3趟ababcabcacbababcaci=7，j=5失败ijijijijij第4趟ababcabcacbabaijs4=t2;t1≠t2∴t1≠s4算法设计与分析清华大学出版社第5趟ababcabcacbabijas5=t3;t1≠t3∴t1≠s5第6趟ababcabcacbababcaci=11，j=6，t中全部字符都比较完毕，匹配成功。ijijijijij算法设计与分析清华大学出版社需要讨论两个问题：①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？②模式应该向右滑多远才是最高效率的?结论：i可以不回溯，模式向右滑动到的新比较起点k，并且k仅与模式串T有关！算法设计与分析清华大学出版社请抓住部分匹配时的两个特征：两式联立可得：T1～Tk-1＝Tj-(k-1)～Tj-1S=ababcabcacbabT=abcacik（1）设模式滑动到第k个字符，则T1～Tk-1＝Si-(k-1)～Si-1（2）则Tj-(k-1)～Tj-1＝Si-(k-1)～Si-1jS=ababcabcacbabT=abcacikiS=ababcabcacbabT=abcacjk算法设计与分析清华大学出版社T1…Tk-1＝Tj-(k-1)…Tj-1说明了什么？（1）k与j具有函数关系，由当前失配位置j，可以计算出滑动位置k（即比较的新起点）；（2）滑动位置k仅与模式串T有关。从第1位往右经过k-1位从j-1位往左经过k-1位k＝max{k|1kj且T1…Tk-1＝Tj-(k-1)…Tj-1}T1…Tk-1＝Tj-(k-1)…Tj-1的物理意义是什么？模式应该向右滑多远才是最高效率的?算法设计与分析清华大学出版社next[j]＝0当j＝1时//不比较max{k|1kj且T1…Tk-1=Tj-(k-1)…Tj-1}1其他情况令k=next[j]，则：t1t2t3t4t5t6ababac真前缀真后缀∵t1=t5,t1t2t3=t3t4t5∴a和aba都是ababa的真前缀和真后缀，但aba的长度最大∴next[6]=3+1=4即当t6和si匹配失败后，将t4和si进行比较next[j]函数表征着模式T中最大相同首子串和尾子串（真子串）的长度。可见，模式中相似部分越多，则next[j]函数越大，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低。算法设计与分析清华大学出版社此时，比较tk和tj，可能出现两种情况：（1）tk＝tj：说明t1…tk-1tk＝tj-k+1…tj-1tj，由前缀函数定义，next[j+1]=k＋1；由模式T的前缀函数定义易知，next[1]=0，假设已经计算出next[1]，next[2]，…，next[j]，如何计算next[j＋1]呢？设k=next[j]，这意味着t1…tk-1既是t1…tj-1的真后缀又是t1…tj-1的真前缀，即：t1…tk-1＝tj-k+1tj-k+2…tj-1计算next[j]的方法：算法设计与分析清华大学出版社t1…tnext[k]-1tnext[k]…tk-1tk…tj-next[k]+1…tj-1tjtj+1t1…tnext[k]-1tnext[k]…tk-1tk…tj-next[k]+1…tj-1tjtj+1最大真前缀最大真后缀最2大真前缀最2大真后缀（2）tk≠tj：此时要找出t1…tj-1的后缀中第2大真前缀，显然，这个第2大的真前缀就是next[next[j]]=next[k]。算法设计与分析清华大学出版社再比较tnext[k]和tj，此时仍会出现两种情况，当tnext[k]＝tj时，与情况（1）类似，next[j]=next[k]+1；当tnext[k]≠tj时，与情况（2）类似，再找t1…tj-1的后缀中第3大真前缀，重复（2）的过程，直到找到t1…tj-1的后缀中的最大真前缀，或确定t1…tj-1的后缀中不存在真前缀，此时，next[j+1]=1。t1…tnext[k]-1tnext[k]…tk-1tk…tj-next[k]+1…tj-1tjtj+1最2大真前缀最2大真后缀算法设计与分析清华大学出版社j=6时，t2＝t5，next[6]=3；j=7时，t3＝t6，next[7]=4；j=8时，t4≠t7，k=next[4]=2，t2＝t7，next[8]=k+1=3。例如，模式T=abaababc的next值计算如下：j=1时，next[1]=0；j=2时，next[2]=1；j=3时，t1≠t2，next[3]=1；j=4时，t1＝t3，next[4]=2；j=5时，t2≠t4，令k=next[2]=1，t1＝t4，next[5]=k+1=2；算法设计与分析清华大学出版社算法3.4——KMP算法中求next数组voidGetNext(charT[],intnext[]){next[1]=0;j=1;k=0;while(jT[0])if((k==0)||(T[j]==T[k])){j++;k++;next[j]=k;}elsek=next[k];}算法设计与分析清华大学出版社KMP算法用伪代码描述如下：算法3.5——KMP算法1.在串S和串T中分别设比较的起始下标i和j；2.循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕2.1如果S[i]=T[j]，则继续比较S和T的下一个字符；否则2.2将j向右滑动到next[j]位置，即j=next[j]；2.3如果j=0，则将i和j分别加1，准备下一趟比较；3.如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0；KMP算法的时间复杂性是O(n+m)，当mn时，KMP算法的时间复杂性是O(n)。算法设计与分析清华大学出版社3.3排序问题中的蛮力法3.3.1选择排序3.3.2起泡排序算法设计与分析清华大学出版社3.3.1选择