第3章 蛮力法

算法设计与分析算法设计与分析清华大学出版社清华大学出版社第第3章章蛮力法蛮力法3.1蛮力法的设计思想蛮力法的设计思想3.2查找问题中的蛮力法查找问题中的蛮力法3.3排序问题中的蛮力法排序问题中的蛮力法3.4组合问题中的蛮力法组合问题中的蛮力法3.5图问题中的蛮力法图问题中的蛮力法3.6几何问题中的蛮力法几何问题中的蛮力法3.7实验项目实验项目串匹配问题串匹配问题算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.1蛮力法的设计思想蛮力法的设计思想蛮力法的设计思想：直接基于问题的描述。蛮力法的设计思想：直接基于问题的描述。例：计算例：计算ann次an=aaa算法设计与分析算法设计与分析清华大学出版社清华大学出版社n蛮力法所赖的基本技术蛮力法所赖的基本技术扫描技扫描技术术n关键关键依次处理所有元素依次处理所有元素n 基本的扫描技术基本的扫描技术遍历遍历（1）集合的遍历）集合的遍历（2）线性表的遍历）线性表的遍历（3）树的遍历）树的遍历（4）图的遍历）图的遍历 算法设计与分析算法设计与分析清华大学出版社清华大学出版社 虽然巧妙和高效的算法很少来自于蛮力法，基于虽然巧妙和高效的算法很少来自于蛮力法，基于以下原因，蛮力法也是一种重要的算法设计技术：以下原因，蛮力法也是一种重要的算法设计技术：（1）理论上，蛮力法可以解决可计算领域的各种问题。）理论上，蛮力法可以解决可计算领域的各种问题。（2）蛮力法经常用来解决一些较小规模的问题。）蛮力法经常用来解决一些较小规模的问题。（3）对对于于一一些些重重要要的的问问题题蛮蛮力力法法可可以以产产生生一一些些合合理理的的算算法，他们具备一些实用价值，而且不受问题规模的限制。法，他们具备一些实用价值，而且不受问题规模的限制。（4）蛮力法可以作为某类问题时间性能的底限，来衡量）蛮力法可以作为某类问题时间性能的底限，来衡量同样问题的更高效算法。同样问题的更高效算法。算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.2 查找问题中的蛮力法查找问题中的蛮力法 3.2.1顺序查找顺序查找3.2.2串匹配问题串匹配问题算法设计与分析算法设计与分析清华大学出版社清华大学出版社 顺序查找从表的一端向另一端顺序查找从表的一端向另一端逐个逐个将元素与给定值进行将元素与给定值进行比较，若相等，则查找成功，给出该元素在表中的位置；若比较，若相等，则查找成功，给出该元素在表中的位置；若整个表检测完仍未找到与给定值相等的元素，则查找失败，整个表检测完仍未找到与给定值相等的元素，则查找失败，给出失败信息。给出失败信息。3.2.1顺序查找顺序查找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i查找方向查找方向算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法3.1顺序查找顺序查找 int SeqSearch1(int r,int n,int k)/数组r1 rn存放查找集合 i=n;while(i0&ri!=k)i-;return i;算法算法3.1的的基本语句基本语句是是i0和和ri!=k，其执行次数为，其执行次数为:基本语句基本语句？算法设计与分析算法设计与分析清华大学出版社清华大学出版社将将待查值待查值放在查找方向的放在查找方向的尽头尽头处，免去了在查找过处，免去了在查找过程中每一次比较后都要判断查找位置是否程中每一次比较后都要判断查找位置是否越界越界，从，从而提高了查找速度。而提高了查找速度。k 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i查找方向查找方向哨兵哨兵改进的顺序查找改进的顺序查找算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法3.2改进的顺序查找 intSeqSearch2(intr,intn,intk)/数组数组r1rn存放查找集合存放查找集合r0=k;i=n;while(ri!=k)i-;returni;算法3.2的基本语句是ri!=k，其执行次数为:数量级相同，系数相差一半算法设计与分析算法设计与分析清华大学出版社清华大学出版社 用蛮力法设计的算法，一般来说，经过适度的用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能，但只能减少系数，而数的改良，改进其时间性能，但只能减少系数，而数量级不会改变。量级不会改变。v 一般观点：一般观点：算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.2.2串匹配问题串匹配问题 串匹配问题属于易解问题。串匹配问题属于易解问题。串匹配问题的特征：串匹配问题的特征：（1）算法的一次执行时间不容忽视：问题规模）算法的一次执行时间不容忽视：问题规模 n 很大，很大，常常需要在大量信息中进行匹配；常常需要在大量信息中进行匹配；（2）算法改进所取得的积累效益不容忽视：串匹配操作）算法改进所取得的积累效益不容忽视：串匹配操作经常被调用，执行频率高。经常被调用，执行频率高。串匹配问题串匹配问题给定两个串给定两个串S=“s1s2sn”和和T=“t1t2tm”，在，在主串主串S中查找子串中查找子串T的过程称为的过程称为串匹配串匹配，也称模式匹配。，也称模式匹配。算法设计与分析算法设计与分析清华大学出版社清华大学出版社 基基本本思思想想：从从主主串串S的的第第一一个个字字符符开开始始和和模模式式T的的第第一一个个字字符符进进行行比比较较，若若相相等等，则则继继续续比比较较两两者者的的后后续续字字符符；若若不不相相等等，则则从从主主串串S的的第第二二个个字字符符开开始始和和模模式式T的的第第一一个个字字符符进进行行比比较较，重重复复上上述述过过程程，若若T中中的的字字符符全全部部比比较较完完毕毕，则则说说明明本本趟趟匹匹配配成成功功；若若最最后后一一轮轮匹匹配配的的起起始始位位置置是是n-m，则则主主串串S中中剩剩下下的的字字符符不不足足够够匹匹配配整整个个模模式式T，匹匹配配失失败败。这这个算法称为朴素的模式匹配算法，简称个算法称为朴素的模式匹配算法，简称BF算法。算法。蛮力法解决串匹配问题蛮力法解决串匹配问题BF算法算法算法设计与分析算法设计与分析清华大学出版社清华大学出版社本趟匹配开始位置本趟匹配开始位置si主串主串S模式模式Ttjj回溯回溯回溯回溯i算法设计与分析算法设计与分析清华大学出版社清华大学出版社设主串设主串s=“ababcabcacbab”，模式，模式t=“abcacababcabcacbababci=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=S0&jT0)return(i-j+1);elsereturn0;BFC+算算法法算法设计与分析算法设计与分析清华大学出版社清华大学出版社 设串设串S长度为长度为n，串，串T长度为长度为m，在匹配成功的情况下，在匹配成功的情况下，考虑最坏情况，即每趟不成功的匹配都发生在串考虑最坏情况，即每趟不成功的匹配都发生在串T的最后一的最后一个字符。个字符。例如：例如：S=aaaaaaaaaaab T=aaab设设匹匹配配成成功功发发生生在在si处处，则则在在i-1趟趟不不成成功功的的匹匹配配中中共共比比较较了了(i-1)m次次，第第i趟趟成成功功的的匹匹配配共共比比较较了了m次次，所所以以总共比较了总共比较了im次，因此平均比较次数是：次，因此平均比较次数是：算法设计与分析算法设计与分析清华大学出版社清华大学出版社改进的串匹配算法改进的串匹配算法KMP算法算法设计思想设计思想：尽量利用已经尽量利用已经部分匹配部分匹配的结果信息，的结果信息，尽量让尽量让i不回溯，加快模式串的滑动速度。不回溯，加快模式串的滑动速度。算法设计与分析算法设计与分析清华大学出版社清华大学出版社ababcabcacbababci=3，j=3失败；失败；第第1趟趟iiijababcabcacbabaij第第2趟趟s2=t2;t1t2t1s2jj算法设计与分析算法设计与分析清华大学出版社清华大学出版社第第3趟趟ababcabcacbababcaci=7，j=5失败失败ijijijijij第第4趟趟ababcabcacbabaijs4=t2;t1t2t1s4算法设计与分析算法设计与分析清华大学出版社清华大学出版社第第5趟趟ababcabcacbabijas5=t3;t1t3t1s5第第6趟趟ababcabcacbababcaci=11，j=6，t中中全全部部字字符符都比较完毕，匹配成功。都比较完毕，匹配成功。ijijijijij算法设计与分析算法设计与分析清华大学出版社清华大学出版社需要讨论两个问题：需要讨论两个问题：如何由当前部分匹配结果确定模式向右滑如何由当前部分匹配结果确定模式向右滑动的新比较起点动的新比较起点k？模式应该向右滑多远才是最高效率的模式应该向右滑多远才是最高效率的?结论：结论：i可以不回溯，模式向右滑动到的新比可以不回溯，模式向右滑动到的新比较起点较起点k，并且，并且k仅与模式串仅与模式串T有关！有关！算法设计与分析算法设计与分析清华大学出版社清华大学出版社请抓住部分匹配时的两个特征：请抓住部分匹配时的两个特征：两式联立可得：两式联立可得：T T1 1T Tk k-1-1T Tj j-(-(k k-1)-1)T Tj j-1-1S=ababcabcacbabT=abcacik（1）设模式滑动到第）设模式滑动到第k个字符，则个字符，则T T1 1T Tk k-1-1 S Si i-(-(k k-1)-1)Si i-1-1（2）则）则Tj-(k-1)Tj-1S Si i-(-(k k-1)-1)Si i-1-1jS=ababcabcacbabT=abcacikiS=ababcabcacbabT=abcacjk算法设计与分析算法设计与分析清华大学出版社清华大学出版社T T1 1TTk k-1-1T Tj j-(-(k k-1)-1)TTj j-1-1说明了什么？说明了什么？说明了什么？说明了什么？（1）k与与 j具有函数关系，具有函数关系，由当前失配位置由当前失配位置j，可以计算出可以计算出滑动位置滑动位置k（即比较的（即比较的新起点）新起点）；（2）滑动位置滑动位置k仅与模式串仅与模式串T有关有关。从第从第1位往右位往右经过经过k-1位位从从j-1位往左位往左经过经过k-1位位kmaxk|1kj且且T1Tk-1Tj-(k-1)Tj-1T T1 1TTk k-1-1T Tj j-(-(k k-1)-1)TTj j-1-1的物理意义是什么？的物理意义是什么？的物理意义是什么？的物理意义是什么？模式应该向右滑多远才是最高效率的模式应该向右滑多远才是最高效率的?算法设计与分析算法设计与分析清华大学出版社清华大学出版社nextj0当当j1时时/不比较不比较maxk|1kj且且T1Tk-1=Tj-(k-1)Tj-11其他情况其他情况令令k=nextj，则：，则：t1t2t3t4t5t6a b a b a c真前缀真前缀真后缀真后缀t1=t5,t1t2t3=t3t4t5a和和aba都是都是ababa的真前缀和真后缀，的真前缀和真后缀，但但aba的长度最大的长度最大next6=3+1=4即当即当t6和和si匹配失败后，将匹配失败后，将t4和和si进行比较进行比较nextj函数表征着模式函数表征着模式T中最大相同首子串和尾子串（真中最大相同首子串和尾子串（真子串）的长度。可见，模式中相似部分越多，则子串）的长度。可见，模式中相似部分越多，则nextj函数越函数越大，模式串向右滑动得越远，与主串进行比较的次数越少，时大，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低。间复杂度就越低。算法设计与分析算法设计与分析清华大学出版社清华大学出版社此时，比较此时，比较tk和和tj，可能出现两种情况：，可能出现两种情况：（1）tktj：说说明明t1tk-1tktj-k+1tj-1tj，由由前前缀缀函函数数定定义义，nextj=k1；由由模模式式T的的前前缀缀函函数数定定义义易易知知，next1=0，假假设设已已经经计计算算出出next1，next2，nextj，如如何何计计算算nextj1呢呢？设设k=nextj，这这意意味味着着t1tk-1既既是是t1tj-1的的真真后后缀缀又又是是t1tj-1的真前缀，即：的真前缀，即：t1tk-1tj-k+1tj-k+2tj-1计算计算nextj的方法：的方法：算法设计与分析算法设计与分析清华大学出版社清华大学出版社t1tnextk-1tnextktk-1tktj-nextk+1tj-1tjtj+1t1tnextk-1tnextktk-1tktj-nextk+1tj-1tjtj+1最大真前缀最大真后缀最2大真前缀最2大真后缀（2）tktj：此时要找出：此时要找出t1 tj-1的后缀中第的后缀中第2大真前缀，显然，大真前缀，显然，这个第这个第2大的真前缀就是大的真前缀就是nextnextj=nextk。算法设计与分析算法设计与分析清华大学出版社清华大学出版社再比较再比较tnextk和和tj，此时仍会出现两种情况，当，此时仍会出现两种情况，当tnextktj时，与时，与情况（情况（1）类似，）类似，nextj=nextk+1；当；当tnextktj时，与情况时，与情况（2）类似，再找）类似，再找t1tj-1的后缀中第的后缀中第3大真前缀，重复（大真前缀，重复（2）的）的过程，直到找到过程，直到找到t1tj-1的后缀中的最大真前缀，或确定的后缀中的最大真前缀，或确定t1tj-1的后缀中不存在真前缀，此时，的后缀中不存在真前缀，此时，nextj+1=1。t1tnextk-1tnextktk-1tktj-nextk+1tj-1tjtj+1最2大真前缀最2大真后缀算法设计与分析算法设计与分析清华大学出版社清华大学出版社j=6时，时，t2t5，next6=3；j=7时，时，t3t6，next7=4；j=8时，时，t4t7，k=next4=2，t2t7，next8=k+1=3。例如，模式例如，模式T=a b a a b a b c的的next值计算如下：值计算如下：j=1时时，next1=0；j=2时时，next2=1；j=3时时，t1t2，next3=1；j=4时，时，t1t3，next4=2；j=5时，时，t2t4，令令k=next2=1，t1t4，next5=k+1=2；算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法3.4KMP算法中求next数组void GetNext(char T,int next)next1=0;j=1;k=0;while(jT0)if(k=0)|(Tj=Tk)j+;k+;nextj=k;else k=nextk;算法设计与分析算法设计与分析清华大学出版社清华大学出版社KMP算法用伪代码描述如下：算法3.5KMP算法 1.在串S和串T中分别设比较的起始下标i和j；2.循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕 2.1 如果Si=Tj，则继续比较S和T的下一个字符；否则 2.2 将j向右滑动到nextj位置，即j=nextj；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选择排序选择排序选选择择排排序序第第i趟趟排排序序从从第第i个个记记录录开开始始扫扫描描序序列列，在在n-i+1（1in-1）个个记记录录中中找找到到关关键键码码最最小小的的记记录录，并并和和第第i个个记录交换作为有序序列的第记录交换作为有序序列的第i个记录。个记录。r1r2ri-1 ri ri+1rmin rn 有序区有序区无序区无序区已经位于最终位置已经位于最终位置rmin为无序区的最小记录为无序区的最小记录交换交换算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法3.6选择排序选择排序voidSelectSort(intr,intn)/数组下标从数组下标从1 1开始开始for(i=1;i=n-1;i+)/对对n个记录进行个记录进行n-1趟简单选择排序趟简单选择排序index=i;for(j=i+1;j=n;j+)/在无序区中找最小记录在无序区中找最小记录if(rjrindex)index=j;if(index!=i)ririndex;/若最小记录不在最终位置则交换若最小记录不在最终位置则交换 该算法的基本语句是内层循环体中的比较语句该算法的基本语句是内层循环体中的比较语句rjrindex，其执行次数为：，其执行次数为：算法设计与分析算法设计与分析清华大学出版社清华大学出版社起泡排序在扫描过程中两两比较相邻记录，如果反序则交起泡排序在扫描过程中两两比较相邻记录，如果反序则交换，最终，最大记录就被换，最终，最大记录就被“沉到沉到”了序列的最后一个位置，了序列的最后一个位置，第二遍扫描将第二大记录第二遍扫描将第二大记录“沉到沉到”了倒数第二个位置，重了倒数第二个位置，重复上述操作，直到复上述操作，直到n-1遍扫描后，整个序列就排好序了。遍扫描后，整个序列就排好序了。3.3.2起泡排序起泡排序rjrj+1 ri+1 rn-1rn无序区无序区有序区有序区1ji-1位于最终位置位于最终位置反序则交换反序则交换算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法3.7起泡排序起泡排序voidBubbleSort(intr,intn)/数组下标从数组下标从1 1开始开始for(i=1;i=n-1;i+)for(j=1;jrj+1)rjrj+1；/如果反序，则交换元素如果反序，则交换元素 该算法的基本语句是内层循环体中的比较语句该算法的基本语句是内层循环体中的比较语句rjrj+1，其执行次数为：，其执行次数为：算法设计与分析算法设计与分析清华大学出版社清华大学出版社注意到，在一趟起泡排序过程中，如果有多个记录交换到注意到，在一趟起泡排序过程中，如果有多个记录交换到最终位置，则下一趟起泡排序将不处理这些记录；另外，最终位置，则下一趟起泡排序将不处理这些记录；另外，在一趟起泡排序过程中，如果没有记录相交换，那么表明在一趟起泡排序过程中，如果没有记录相交换，那么表明这个数组已经有序，算法将终止。这个数组已经有序，算法将终止。算法算法3.8改进的起泡排序改进的起泡排序voidBubbleSort(intr,intn)/数组下标从数组下标从1 1开始开始exchange=n;/第一趟起泡排序的范围是第一趟起泡排序的范围是r1到到rnwhile(exchange)/仅当上一趟排序有记录交换才进行本趟排序仅当上一趟排序有记录交换才进行本趟排序bound=exchange;exchange=0；for(j=1;jrj+1)rjrj+1；exchange=j；/记录每一次发生记录交换的位置记录每一次发生记录交换的位置算法设计与分析算法设计与分析清华大学出版社清华大学出版社在最好情况下，待排序记录序列为正序，算法只执行一趟，在最好情况下，待排序记录序列为正序，算法只执行一趟，进行了进行了n-1次关键码的比较，不需要移动记录，时间复杂性次关键码的比较，不需要移动记录，时间复杂性为为O(n)；在最坏情况下，待排序记录序列为反序，每趟排序在无序在最坏情况下，待排序记录序列为反序，每趟排序在无序序列中只有一个最大的记录被交换到最终位置，故算法执序列中只有一个最大的记录被交换到最终位置，故算法执行行n-1趟，第趟，第i（1in）趟排序执行了）趟排序执行了n-i次关键码的比较和次关键码的比较和n-i次记录的交换，这样，关键码的比较次数为次记录的交换，这样，关键码的比较次数为 ，记录的移动次数为，记录的移动次数为 ，因此，时间复杂性，因此，时间复杂性为为O(n2)；在平均情况下，其时间复杂性与最坏情况同数量级。在平均情况下，其时间复杂性与最坏情况同数量级。算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.4 3.4 组合问题中的蛮力法组合问题中的蛮力法 3.4.1生成排列对象生成排列对象3.4.2生成子集生成子集3.4.30/1背包问题背包问题3.4.4任务分配问题任务分配问题算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.4.1生成排列对象生成排列对象假设已经生成了所有假设已经生成了所有(n-1)!个排列，可以把个排列，可以把n插入到插入到n-1个元个元素的每一种排列中的素的每一种排列中的n个位置中去，来得到问题规模为个位置中去，来得到问题规模为n的的所有排列。按照这种方式生成的所有排列都是独一无二的，所有排列。按照这种方式生成的所有排列都是独一无二的，并且他们的总数应该是并且他们的总数应该是n(n-1)!=n!。开始开始1插入插入21221插入插入3123132312213231321生成排列的过程生成排列的过程算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法3.9生成排列对象生成排列对象1生成初始排列生成初始排列1；2for(i=2;i=n;i+)for(j=1;j=1;k-)将将i插入到第插入到第j个排列中的第个排列中的第k个位置；个位置；显然，算法显然，算法3.9的时间复杂性为的时间复杂性为O(n!)，也就是说和排，也就是说和排列对象的数量成正比。列对象的数量成正比。算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.4.2生成子集生成子集n个个元元素素的的集集合合A=a1,a2,an的的所所有有2n个个子子集集和和长长度度为为n的所有的所有2n个比特串之间的一一对应关系。个比特串之间的一一对应关系。建建立立对对应应关关系系：为为每每一一个个子子集集指指定定一一个个比比特特串串b1b2bn，如如果果ai属属于于该该子子集集，则则bi1；如如果果ai不不属属于于该该子子集集，则则bi0（1in）。）。比特串比特串000001010011100101110111子集子集a3a2a2,a3a1a1,a3a1,a2a1,a2,a2算法设计与分析算法设计与分析清华大学出版社清华大学出版社生成n个元素子集的算法如下：算法算法3.10生成子集生成子集1初始化一个长度为初始化一个长度为n的比特串的比特串s=000并将对应的子集输出；并将对应的子集输出；2for(i=1;i2n;i+)2.1s+；2.2将将s对应的子集输出；对应的子集输出；显然，算法显然，算法3.10的时间复杂性为的时间复杂性为O(2n)，也就是说和子，也就是说和子集的数量成正比。集的数量成正比。算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.4.30/1背包问题背包问题0/1背背包包问问题题是是给给定定n个个重重量量为为w1,w2,wn、价价值值为为v1,v2,vn的的物物品品和和一一个个容容量量为为C的的背背包包，求求这这些些物物品品中中的的一一个个最最有有价价值值的的子子集集，并并且且要要能能够够装到背包中。装到背包中。用用蛮蛮力力法法解解决决0/1背背包包问问题题，需需要要考考虑虑给给定定n个个物物品品集集合合的的所所有有子子集集，找找出出所所有有可可能能的的子子集集（总总重重量量不不超超过过背背包包容容量量的的子子集集），计计算算每每个个子子集集的的总总价价值，然后在他们中找到价值最大的子集。值，然后在他们中找到价值最大的子集。算法设计与分析算法设计与分析清华大学出版社清华大学出版社10w1=7v1=42w2=3v2=12w3=4v3=40w4=5v4=25背包背包物品物品1物品物品2物品物品3物品物品481,412161,2,3,419序号序号子集子集总重量总重量总价值总价值序号序号子集子集总重量总重量总价值总价值10092,375221742102,483732312113,496543440121,2,314不可行不可行54525131,2,41561,21054141,3,41671,311不可行不可行152,3,412不可行不可行不可行不可行不可行不可行不可行不可行不可行不可行算法设计与分析算法设计与分析清华大学出版社清华大学出版社 对于一个具有n个元素的集合，其子集数量是2n，所以，不论生成子集的算法效率有多高，蛮力法都会导致一个(2n)的算法。算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.4.4任务分配问题任务分配问题 假设有假设有n个任务需要分配给个任务需要分配给n个人执行，个人执行，每个任务只分配给一个人，每个人只分配一每个任务只分配给一个人，每个人只分配一个任务，且第个任务，且第j个任务分配给第个任务分配给第i个人的成本是个人的成本是Ci,j（1i,jn），任务分配问题要求找出），任务分配问题要求找出总成本最小的分配方案。总成本最小的分配方案。算法设计与分析算法设计与分析清华大学出版社清华大学出版社 下图是一个任务分配问题的成本矩阵，矩阵元下图是一个任务分配问题的成本矩阵，矩阵元素素Ci,j代表将任务代表将任务j分配给人员分配给人员i的成本。的成本。C=927643581任务任务1任务任务2任务任务3人员人员1人员人员2人员人员3 任务分配问题就是在分配成本矩阵中的每一行任务分配问题就是在分配成本矩阵中的每一行选取一个元素，这些元素分别属于不同的列，并且选取一个元素，这些元素分别属于不同的列，并且元素之和最小。元素之和最小。算法设计与分析算法设计与分析清华大学出版社清华大学出版社可以用一个可以用一个n元组元组(j1,j2,jn)来描述任务分配问题的一个可能来描述任务分配问题的一个可能解，其中第解，其中第i个分量个分量ji（1in）表示在第）表示在第i行中选择的列号，因行中选择的列号，因此用蛮力法解决任务分配问题要求生成整数此用蛮力法解决任务分配问题要求生成整数1n的全排列，然的全排列，然后把成本矩阵中的相应元素相加来求得每种分配方案的总成后把成本矩阵中的相应元素相加来求得每种分配方案的总成本，最后选出具有最小和的方案。本，最后选出具有最小和的方案。序号序号分配方案分配方案总成本总成本11,2,39+4+1=1421,3,29+3+8=2032,1,32+6+1=942,3,12+3+5=1053,1,27+6+8=2163,2,17+4+5=16算法设计与分析算法设计与分析清华大学出版社清华大学出版社由于任务分配问题需要考虑的排列数由于任务分配问题需要考虑的排列数量是量是n!，所以，除了该问题的一些规模非，所以，除了该问题的一些规模非常小的实例，蛮力法几乎是不实用的。常小的实例，蛮力法几乎是不实用的。算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.5图问题中的蛮力法图问题中的蛮力法3.5.1哈密顿回路问题哈密顿回路问题3.5.2TSP问题问题算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.5.1哈密顿回路问题哈密顿回路问题 著著名名的的爱爱尔尔兰兰数数学学家家哈哈密密顿顿（WilliamHamilton，18051865）提提出出了了著著名名的的周周游游世世界界问问题题。他他用用正正十十二二面面体体的的20个个顶顶点点代代表表20个个城城市市，要要求求从从一一个个城城市市出出发发，经过每个城市恰好一次，然后回到出发城市。经过每个城市恰好一次，然后回到出发城市。1983141202131545679101112161718正十二面体的展开图，正十二面体的展开图，按照图中的顶点编号所按照图中的顶点编号所构成的回路，就是哈密构成的回路，就是哈密顿回路的一个解。顿回路的一个解。算法设计与分析算法设计与分析清华大学出版社清华大学出版社使使用用蛮蛮力力法法寻寻找找哈哈密密顿顿回回路路的的基基本本思思想想是是：对对于于给给定定的的无无向向图图G=(V,E)，首首先先生生成成图图中中所所有有顶顶点点的的排排列列对对象象(vi1,vi2,vin)，然然后后依依次次考考察察每每个个排排列列对象是否满足以下两个条件：对象是否满足以下两个条件：（1）相邻顶点之间存在边，即）相邻顶点之间存在边，即(vij,vij+1)E（1jn-1）（2）最后一个顶点和第一个顶点之间存在边，即）最后一个顶点和第一个顶点之间存在边，即(vin,vi1)E 满足这两个条件的回路就是哈密顿回路。满足这两个条件的回路就是哈密顿回路。算法设计与分析算法设计与分析清华大学出版社清华大学出版社12453路径路径(vij,vij+1)E1234512345（是）（是）1235412354（否）（否）1243512435（否）（否）否否否否1245312453（否）（否）1253412534（否）（否）1254312543（是）（是）(vin,vi1)E是是是是是是是是(a)一个无向图一个无向图(b)哈密顿回路求解过程哈密顿回路求解过程 显然，蛮力法求解哈密顿回路在最坏情况下需要考察显然，蛮力法求解哈密顿回路在最坏情况下需要考察所有顶点的排列对象，其时间复杂性为所有顶点的排列对象，其时间复杂性为O(n!)。算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.5.2TSP问题问题 TSP问题是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。用蛮力法解决TSP问题，可以找出所有可能的旅行路线，从中选取路径长度最短的简单回路。算法设计与分析算法设计与分析清华大学出版社清华大学出版社8abdc23571序号序号路径路径路径长度路径长度是否最短是否最短1abcda18 否否2abdca11 是是3acbda23 否否4acdba11 是是5adbca23 否否6adcba18 否否 注注意意到到，在在图图3.16中中有有3对对不不同同的的路路径径，对对每每对对路路径径来来说说，不不同同的的只只是是路路径径的的方方向向，因因此此，可可以以将将这这个个数数量量减减半半，则则可可能能的的解解有有(n-1)!/2个个。这这是是一一个个非非常常大大的的数数，随随着着n的的增增长，长，TSP问题的可能解也在迅速地增长，例如：问题的可能解也在迅速地增长，例如：算法设计与分析算法设计与分析清华大学出版社清华大学出版社l一个一个10城市的城市的TSP问题有大约有问题有大约有180,000个可能解。个可能解。l一个一个20城市的城市的TSP问题有大约有问题有大约有60,000,000,000,000,000个可能解。个可能解。l一个一个50城市的城市的TSP问题有大约问题有大约1062个可能解，而一个个可能解，而一个行星上也只有行星上也只有1021升水。升水。v用蛮力法求解用蛮力法求解TSP问题，只能解决问题规模很小的问题，只能解决问题规模很小的实例。实例。算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.6几何问题中的蛮力法几何问题中的蛮力法3.6.1最近对问题最近对问题3.6.2 凸包问题凸包问题算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.6.1最近对问题最近对问题最近对问题要求找出一个包含最近对问题要求找出一个包含n个点的集合中距个点的集合中距离最近的两个点。离最近的两个点。简单起见，只考虑二维的情况，并假设所讨论简单起见，只考虑二维的情况，并假设所讨论的点是以标准笛卡儿坐标形式（的点是以标准笛卡儿坐标形式（x,y）给出的。因）给出的。因此，在两个点此，在两个点Pi=(xi,yi)和和Pj=(xj,yj)之间的距离是之间的距离是标准的欧几里德距离：标准的欧几里德距离：算法设计与分析算法设计与分析清华大学出版社清华大学出版社 蛮力法求解最近对问题的过程是：分别计算蛮力法求解最近对问题的过程是：分别计算每一对点之间的距离，然后找出距离最小的那一每一对点之间的距离，然后找出距离最小的那一对，为了避免对同一对点计算两次距离，只考虑对，为了避免对同一对点计算两次距离，只考虑ij的那些点对的那些点对(Pi,Pj)。算法设计与分析算法设计与分析清华大学出版社清华大学出版社算法算法3.11最近对问题最近对问题intClosestPoints(intn,intx,inty,int&index1,int&index2)minDist=+;for(i=1;in;i+)for(j=i+1;j=n;j+)d=(xi-xj)*(xi-xj)+(yi-yj)*(yi-yj);if(d2个点（不共线）的集合个点（不共线）的集合S的凸包的凸包是以是以S中的某些点为顶点的凸多边形；如果所有点都位于中的某些点为顶点的凸多边形；如果所有点都位于一条直线上，则凸多边形退化为一条线段。一条直线上，则凸多边形退化为一条线段。算法设计与分析算法设计与分析清华大学出版社清华大学出版社蛮蛮力力法法求求解解凸凸包包问问题题的的基基本本思思想想：对对于于一一个个由由n个个点点构构成成的的集集合合S中中的的两两个个点点Pi和和Pj，当当且且当当该该集集合合中中的的其其他他点点都都位位于于穿穿过过这这两两点点的的直直线线的的同同一一边边时时（假假定定不不存存在在三三点点同同线线的的情情况况），他他们们的的连连线线是是该该集集合合凸凸包包边边界界的的一一部部分分。对对每每一一对对顶顶点点都都检检验验一一遍遍后后，满满足足条条件件的的线线段段构构成成了了该该凸凸包包的的边界。边界。在在平平面面上上，穿穿过过两两个个点点(x1,y1)和和(x2,y2)的的直直线线是是由由下下面面的方程定义的：的方程定义的：ax+by=c (其中，其中，a=y2-y1,b=x1-x2,c=x1y2-y1x2)这这样样一一条条直直线线把把平平面面分分成成两两个个半半平平面面：其其中中一一个个半半平平面面中中的的点点都都满满足足ax+byc，另另一一个个半半平平面面中中的的点点都都满满足足ax+byc，因因此此，为为了了检检验验这这些些点点是是否否位位于于这这条条直直线线的的同同一一边边，可可以以简简单单地地把把每每个个点点代代入入方方程程ax+by=c，检检验验这这些些表表达式的符号是否相同。达式的符号是否相同。算法设计与分析算法设计与分析清华大学出版社清华大学出版社该算法的效率如何呢？所有不同的点共组成了n(n-1)/2边，对每条边都要对其他n-2个顶点求出在直线方程ax+by=c中的符号，所以，其时间复杂性是O(n3)。算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.7实验项目实验项目串匹配问题串匹配问题1.实验题目实验题目给定一个文本，在该文本中查找并定位任意给定字符串。给定一个文本，在该文本中查找并定位任意给定字符串。2实验目的实验目的深刻理解并掌握蛮力法的设计思想；深刻理解并掌握蛮力法的设计思想；提高应用蛮力法设计算法的技能；提高应用蛮力法设计算法的技能；理解这样一个观点：用蛮力法设计的算法，一般来说，理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。程度的改良，改进其时间性能。算法设计与分析算法设计与分析清华大学出版社清华大学出版社3.实验要求实验要求实现实现BF算法；算法；实现实现BF算法的改进算法：算法的改进算法：KMP算法和算法和BM算法；算法；对对上上述述三三个个算算法法进进行行时时间间复复杂杂性性分分析析，并并设设计计实实验验程程序验证分析结果。序验证分析结果。