算法設(shè)計(jì)與分析第3章蠻力法

1、算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社第第3章章 蠻力法蠻力法 3.1 蠻力法的設(shè)計(jì)思想蠻力法的設(shè)計(jì)思想 3.2 查找問題中的蠻力法查找問題中的蠻力法3.3 排序問題中的蠻力法排序問題中的蠻力法3.4 組合問題中的蠻力法組合問題中的蠻力法3.5 圖問題中的蠻力法圖問題中的蠻力法3.6 幾何問題中的蠻力法幾何問題中的蠻力法3.7 實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)項(xiàng)目串匹配問題串匹配問題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.1 蠻力法的設(shè)計(jì)思想蠻力法的設(shè)計(jì)思想 蠻力法的設(shè)計(jì)思想：直接基于問題的描述。蠻力法的設(shè)計(jì)思想：直接基于問題的描述。例：計(jì)算例：計(jì)算an應(yīng)用舉例：是應(yīng)用舉例：

2、是RSA算法非對稱加密的重要組成部分算法非對稱加密的重要組成部分n次an=aaa算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社n 蠻力法所賴的基本技術(shù)蠻力法所賴的基本技術(shù)掃描技掃描技術(shù)術(shù)n 關(guān)鍵關(guān)鍵依次處理所有元素（避免依次處理所有元素（避免重復(fù)試探）重復(fù)試探）n 基本的掃描技術(shù)基本的掃描技術(shù)遍歷遍歷（1）集合的遍歷）集合的遍歷（2）線性表的遍歷）線性表的遍歷（3）樹的遍歷）樹的遍歷 （4）圖的遍歷）圖的遍歷 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 雖然巧妙和高效的算法很少來自于蠻力法，基于雖然巧妙和高效的算法很少來自于蠻力法，基于以下原因，蠻力法也是一種重要的算法

3、設(shè)計(jì)技術(shù)：以下原因，蠻力法也是一種重要的算法設(shè)計(jì)技術(shù)： （1）理論上，蠻力法可以解決可計(jì)算領(lǐng)域的各種問題。）理論上，蠻力法可以解決可計(jì)算領(lǐng)域的各種問題。 （2）蠻力法經(jīng)常用來解決一些較小規(guī)模的問題。）蠻力法經(jīng)常用來解決一些較小規(guī)模的問題。 （3）對于一些重要的問題蠻力法可以產(chǎn)生一些合理的算）對于一些重要的問題蠻力法可以產(chǎn)生一些合理的算法，他們具備一些實(shí)用價(jià)值，而且不受問題規(guī)模的限制。法，他們具備一些實(shí)用價(jià)值，而且不受問題規(guī)模的限制。 （4）蠻力法可以作為某類問題時(shí)間性能的底限，來衡量）蠻力法可以作為某類問題時(shí)間性能的底限，來衡量同樣問題的更高效算法。同樣問題的更高效算法。 算法設(shè)計(jì)與分析算法設(shè)

4、計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.2 查找問題中的蠻力法查找問題中的蠻力法 3.2.1 順序查找順序查找 3.2.2 串匹配問題串匹配問題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 順序查找從表的一端向另一端順序查找從表的一端向另一端逐個(gè)逐個(gè)將元素與給定值進(jìn)行將元素與給定值進(jìn)行比較，若相等，則查找成功，給出該元素在表中的位置；若比較，若相等，則查找成功，給出該元素在表中的位置；若整個(gè)表檢測完仍未找到與給定值相等的元素，則查找失敗，整個(gè)表檢測完仍未找到與給定值相等的元素，則查找失敗，給出失敗信息。給出失敗信息。3.2.1 順序查找順序查找 10 15 24 6 12 35 4

5、0 98 550 1 2 3 4 5 6 7 8 9 i查找方向查找方向算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法算法3.1順序查找順序查找 int SeqSearch1(int r , int n, int k) /數(shù)組r1 rn存放查找集合 i=n; while (i0 & ri!=k) i-; return i; 算法算法3.1的的基本語句基本語句是是i0和和ri!=k，其執(zhí)行次數(shù)為，其執(zhí)行次數(shù)為:ninininiiiiinOninninncpbp1111)(1) 1(1) 1(1基本語句基本語句 ？算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社將將待

6、查值待查值放在查找方向的放在查找方向的盡頭盡頭處，免去了在查找過處，免去了在查找過程中每一次比較后都要判斷查找位置是否程中每一次比較后都要判斷查找位置是否越界越界，從，從而提高了查找速度。而提高了查找速度。k 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i查找方向查找方向哨兵哨兵改進(jìn)的順序查找改進(jìn)的順序查找算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法3.2改進(jìn)的順序查找 int SeqSearch2(int r , int n, int k) /數(shù)組數(shù)組r1 rn存放查找集合存放查找集合 r0=k; i=n; while (ri!=

7、k) i -; return i;算法3.2的基本語句是ri!=k，其執(zhí)行次數(shù)為: niniiinOninncp11)(21) 1(1數(shù)量級相同，系數(shù)相差一半算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 用蠻力法設(shè)計(jì)的算法，一般來說，經(jīng)過適度的用蠻力法設(shè)計(jì)的算法，一般來說，經(jīng)過適度的努力后，都可以對算法的第一個(gè)版本進(jìn)行一定程度努力后，都可以對算法的第一個(gè)版本進(jìn)行一定程度的改良，改進(jìn)其時(shí)間性能，但只能減少系數(shù)，而數(shù)的改良，改進(jìn)其時(shí)間性能，但只能減少系數(shù)，而數(shù)量級不會改變。量級不會改變。v 一般觀點(diǎn)：一般觀點(diǎn)：算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.2.2 串匹配問

8、題串匹配問題 串匹配問題屬于易解問題。串匹配問題屬于易解問題。 串匹配問題的特征：串匹配問題的特征：（1）算法的一次執(zhí)行時(shí)間不容忽視：問題規(guī)模）算法的一次執(zhí)行時(shí)間不容忽視：問題規(guī)模 n 很大，很大，常常需要在大量信息中進(jìn)行匹配；常常需要在大量信息中進(jìn)行匹配；（2）算法改進(jìn)所取得的積累效益不容忽視：串匹配操作）算法改進(jìn)所取得的積累效益不容忽視：串匹配操作經(jīng)常被調(diào)用，執(zhí)行頻率高。經(jīng)常被調(diào)用，執(zhí)行頻率高。 串匹配問題串匹配問題給定兩個(gè)串給定兩個(gè)串S=“s1s2sn” 和和T=“t1t2tm”，在，在主串主串S中查找子串中查找子串T的過程稱為的過程稱為串匹配串匹配，也稱模式匹配。，也稱模式匹配。算法設(shè)

9、計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 基本思想：從主串基本思想：從主串S的第一個(gè)字符開始和模式的第一個(gè)字符開始和模式T的第一個(gè)的第一個(gè)字符進(jìn)行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；若不字符進(jìn)行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；若不相等，則從主串相等，則從主串S的第二個(gè)字符開始和模式的第二個(gè)字符開始和模式T的第一個(gè)字符的第一個(gè)字符進(jìn)行比較，重復(fù)上述過程，若進(jìn)行比較，重復(fù)上述過程，若T中的字符全部比較完畢，則中的字符全部比較完畢，則說明本趟匹配成功；若最后一輪匹配的起始位置是說明本趟匹配成功；若最后一輪匹配的起始位置是n-m，則，則主串主串S中剩下的字符不足夠匹配整個(gè)模式中剩

10、下的字符不足夠匹配整個(gè)模式T，匹配失敗。這，匹配失敗。這個(gè)算法稱為樸素的模式匹配算法，簡稱個(gè)算法稱為樸素的模式匹配算法，簡稱BF算法。算法。蠻力法解決串匹配問題蠻力法解決串匹配問題BF算法算法算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社本趟匹配開始位置本趟匹配開始位置 si 主串主串S模式模式T tjj 回溯回溯 回溯回溯i算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社設(shè)主串設(shè)主串s=“ababcabcacbab”，模式，模式t=“abcaca b a b c a b c a c b a ba b c i=3，j=3失敗；失?。籭回溯到回溯到2，j回溯到回溯到1第第1趟趟

11、ijijijij算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社a b a b c a b c a c b a baijij第第2趟趟i=2，j=1失敗失敗i回溯到回溯到3，j回溯到回溯到1第第3趟趟a b a b c a b c a c b a ba b c a ci=7，j=5失敗失敗i回溯到回溯到4，j回溯到回溯到1ijijijijijji算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社第第4趟趟a b a b c a b c a c b a baiji=4，j=1失敗失敗i回溯到回溯到5，j回溯到回溯到1ji第第5趟趟a b a b c a b c a c b a bi

12、jajii=5，j=1失敗失敗i回溯到回溯到6，j回溯到回溯到1 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社第第6趟趟a b a b c a b c a c b a b a b c a ci=11，j=6，t中全部中全部字符都比較完畢，匹字符都比較完畢，匹配成功。配成功。ijijijijijij算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社int BF( (char S , char T ) ) i=1; j=1; while ( (i=S0 & jT0) ) return ( (i- -j+1) ); else return 0;BF C+算法算法算法設(shè)計(jì)與分

13、析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 設(shè)串設(shè)串S長度為長度為n，串，串T長度為長度為m，在匹配成功的情況下，在匹配成功的情況下，考慮最壞情況，即每趟不成功的匹配都發(fā)生在串考慮最壞情況，即每趟不成功的匹配都發(fā)生在串T的最后一的最后一個(gè)字符。個(gè)字符。 例如：例如：S=aaaaaaaaaaab T=aaab 設(shè)匹配成功發(fā)生在設(shè)匹配成功發(fā)生在si處，則在處，則在i- -1趟不成功的匹配中共趟不成功的匹配中共比較了比較了( (i- -1) )m次，第次，第i趟成功的匹配共比較了趟成功的匹配共比較了m次，所次，所以總共比較了以總共比較了im次，因此平均比較次數(shù)是：次，因此平均比較次數(shù)是：11112

14、) 2()(11)(mnimniimnmmimnmip算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社改進(jìn)的串匹配算法改進(jìn)的串匹配算法KMP算法算法設(shè)計(jì)思想設(shè)計(jì)思想：盡量利用已經(jīng)盡量利用已經(jīng)部分匹配部分匹配的結(jié)果信息，的結(jié)果信息，盡量讓盡量讓 i 不回溯，加快模式串的滑動(dòng)速度。不回溯，加快模式串的滑動(dòng)速度。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 a b a b c a b c a c b a ba b c i=3，j=3失敗；失敗；第第1趟趟iiij a b a b c a b c a c b a baij第第2趟趟s2=t2;t1t2t1s2jj算法設(shè)計(jì)與分析算法設(shè)

15、計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社第第3趟趟a b a b c a b c a c b a ba b c a ci=7，j=5失敗失敗ijijijijij第第4趟趟a b a b c a b c a c b a baijs4=t2;t1t2t1s4算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社第第5趟趟a b a b c a b c a c b a bijas5=t3;t1t3t1s5第第6趟趟 a b a b c a b c a c b a b a b c a ci=11，j=6，t中全部字符中全部字符都比較完畢，匹配成功。都比較完畢，匹配成功。ijijijijij算法設(shè)計(jì)與分析

16、算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社需要討論兩個(gè)問題：需要討論兩個(gè)問題：如何由當(dāng)前部分匹配結(jié)果確定模式向右滑如何由當(dāng)前部分匹配結(jié)果確定模式向右滑動(dòng)的新比較起點(diǎn)動(dòng)的新比較起點(diǎn)k？模式應(yīng)該向右滑多遠(yuǎn)才是最高效率的模式應(yīng)該向右滑多遠(yuǎn)才是最高效率的?結(jié)論：結(jié)論： i可以不回溯，模式向右滑動(dòng)到的新可以不回溯，模式向右滑動(dòng)到的新比較起點(diǎn)比較起點(diǎn)k ，并且，并且k 僅與模式串僅與模式串T有關(guān)！有關(guān)！算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社請抓住部分匹配時(shí)的兩個(gè)特征：請抓住部分匹配時(shí)的兩個(gè)特征：兩式聯(lián)立可得：兩式聯(lián)立可得：S=a b a b c a b c a c b a bT= =a

17、b c a cik（1）設(shè)模式滑動(dòng)到第）設(shè)模式滑動(dòng)到第k個(gè)字符，則個(gè)字符，則 S （2）則）則Tj-(k-1) Tj-1 SjS=a b a b c a b c a c b a bT= =a b c a cikiS=a b a b c a b c a c b a bT= =a b c a cjk算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社（1） k 與與 j 具有函數(shù)關(guān)系，具有函數(shù)關(guān)系，由當(dāng)前失配位置由當(dāng)前失配位置 j ，可以計(jì)算出可以計(jì)算出滑動(dòng)位置滑動(dòng)位置 k（即比較的（即比較的新起點(diǎn)）新起點(diǎn)）；（2）滑動(dòng)位置滑動(dòng)位置k 僅與模式串僅與模式串T有關(guān)有關(guān)。從第從第1位往右位往右經(jīng)過

18、經(jīng)過k-1位位從從j-1位往左位往左經(jīng)過經(jīng)過k-1位位kmax k |1kj 且且T1Tk-1Tj-(k-1) Tj-1 模式應(yīng)該向右滑多遠(yuǎn)才是最高效率的模式應(yīng)該向右滑多遠(yuǎn)才是最高效率的?算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社next j 0 當(dāng)當(dāng)j1時(shí)時(shí) /不比較不比較max k | 1kj 且且T1Tk-1=Tj-(k-1) Tj-1 1 其他情況其他情況令令k = next j ，則：，則：t1 t2 t3 t4 t5 t6a b a b a c真前綴真前綴 真后綴真后綴t1=t5, t1t2t3=t3t4t5a和和aba都是都是ababa的真前綴和真后綴，的真前綴和真

19、后綴， 但但aba的長度最大的長度最大next6=3+1=4即當(dāng)即當(dāng)t6和和si匹配失敗后，將匹配失敗后，將t4和和si進(jìn)行比較進(jìn)行比較nextj函數(shù)表征著模式函數(shù)表征著模式T中最大相同首子串和尾子串（真中最大相同首子串和尾子串（真子串）的長度?？梢姡Ｊ街邢嗨撇糠衷蕉?，則子串）的長度?？梢?，模式中相似部分越多，則nextj函數(shù)越函數(shù)越大，模式串向右滑動(dòng)得越遠(yuǎn)，與主串進(jìn)行比較的次數(shù)越少，時(shí)大，模式串向右滑動(dòng)得越遠(yuǎn)，與主串進(jìn)行比較的次數(shù)越少，時(shí)間復(fù)雜度就越低。間復(fù)雜度就越低。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社此時(shí)，比較此時(shí)，比較tk和和tj，可能出現(xiàn)兩種情況：，可能出現(xiàn)兩種

20、情況：（1）tktj：說明：說明t1 tk-1tktj- -k+1 tj- -1tj，由前綴函數(shù)定義，由前綴函數(shù)定義，nextj+1=k1； 由模式由模式T的前綴函數(shù)定義易知，的前綴函數(shù)定義易知，next1=0，假設(shè)已經(jīng)，假設(shè)已經(jīng)計(jì)算出計(jì)算出next1，next2，nextj，如何計(jì)算，如何計(jì)算nextj1呢？設(shè)呢？設(shè)k=nextj，這意味著，這意味著t1 tk-1既是既是t1 tj-1的真后綴又的真后綴又是是t1 tj-1的真前綴，即：的真前綴，即： t1 tk-1tj- -k+1tj- -k+2 tj- -1計(jì)算計(jì)算nextj的方法：的方法： 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華

21、大學(xué)出版社t1 tnextk-1 tnextk tk-1 tk tj-nextk+1 tj-1 tj tj+1 t1 tnextk-1 tnextk tk-1 tk tj-nextk+1 tj-1 tj tj+1 最大真前綴最大真后綴最2大真前綴最2大真后綴（2）tktj：此時(shí)要找出：此時(shí)要找出t1 tj-1的后綴中第的后綴中第2大真前綴，顯然，大真前綴，顯然，這個(gè)第這個(gè)第2大的真前綴就是大的真前綴就是nextnextj=nextk。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社再比較再比較tnextk和和tj，此時(shí)仍會出現(xiàn)兩種情況，當(dāng)，此時(shí)仍會出現(xiàn)兩種情況，當(dāng)tnextktj時(shí)，與

22、時(shí)，與情況（情況（1）類似，）類似，nextj+1=nextk+1；當(dāng)；當(dāng)tnextktj時(shí)，與情況時(shí)，與情況（2）類似，再找）類似，再找t1 tj-1的后綴中第的后綴中第3大真前綴，重復(fù)（大真前綴，重復(fù)（2）的過程，直到找到的過程，直到找到t1 tj-1的后綴中的最大真前綴，或確定的后綴中的最大真前綴，或確定t1 tj-1的后綴中不存在真前綴，此時(shí)，的后綴中不存在真前綴，此時(shí)，nextj+1=1。t1 tnextk-1 tnextk tk-1 tk tj-nextk+1 tj-1 tj tj+1 最2大真前綴最2大真后綴算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社j=6時(shí)，時(shí)，t

23、2t5，next6=3；j=7時(shí)，時(shí)，t3t6，next7=4；j=8時(shí)，時(shí)，t4t7，k=next4=2，t2t7，next8=k+1=3。例如，模式例如，模式T=a b a a b a b c的的next值計(jì)算如下：值計(jì)算如下： j=1時(shí)，時(shí)，next1=0；j=2時(shí)，時(shí)，next2=1；j=3時(shí)，時(shí)，t1t2，next3=1；j=4時(shí)，時(shí)，t1t3，next4=2；j=5時(shí)，時(shí)，t2t4，令令k=next2=1，t1t4，next5=k+1=2；算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法3.4KMP算法中求next數(shù)組void GetNext(char T , int

24、next ) next1=0; j=1; k=0; while (jT0) if (k= =0)| |(Tj= =Tk) j+; k+; nextj=k; else k=nextk;算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社KMP算法用偽代碼描述如下： 算法3.5KMP算法 1. 在串S和串T中分別設(shè)比較的起始下標(biāo)i和j； 2. 循環(huán)直到S中所剩字符長度小于T的長度或T中所有字符均比較完畢 2.1 如果Si=Tj，則繼續(xù)比較S和T的下一個(gè)字符；否則 2.2 將j向右滑動(dòng)到nextj位置，即j=nextj； 2.3 如果j=0，則將i和j分別加1，準(zhǔn)備下一趟比較； 3. 如果T中所

25、有字符均比較完畢，則返回匹配的起始下標(biāo)；否則返回0； KMP算法的時(shí)間復(fù)雜性是O(n+m)，當(dāng)mn時(shí)，KMP算法的時(shí)間復(fù)雜性是O(n)。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.3 排序問題中的蠻力法排序問題中的蠻力法 3.3.1 選擇排序選擇排序 3.3.2 起泡排序起泡排序算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.3.1 選擇排序選擇排序 選擇排序第選擇排序第i趟排序從第趟排序從第i個(gè)記錄開始掃描序列，在個(gè)記錄開始掃描序列，在n-i+1（1in-1）個(gè)記錄中找到關(guān)鍵碼最小的記錄，并和第）個(gè)記錄中找到關(guān)鍵碼最小的記錄，并和第i個(gè)記個(gè)記錄交換作為有序序列的

26、第錄交換作為有序序列的第i個(gè)記錄。個(gè)記錄。 r1 r2 ri- -1 ri ri+1 rmin rn 有序區(qū)有序區(qū) 無序區(qū)無序區(qū) 已經(jīng)位于最終位置已經(jīng)位于最終位置 rmin為無序區(qū)的最小記錄為無序區(qū)的最小記錄 交換交換算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法算法3.6選擇排序選擇排序 void SelectSort( (int r , int n) ) /數(shù)組下標(biāo)從數(shù)組下標(biāo)從1 1開始開始 for ( (i=1; i=n- -1; i+) ) /對對n個(gè)記錄進(jìn)行個(gè)記錄進(jìn)行n- -1趟簡單選擇排序趟簡單選擇排序 index=i; for ( (j=i+1; j=n; j+)

27、) /在無序區(qū)中找最小記錄在無序區(qū)中找最小記錄 if ( (rjrindex) ) index=j; if ( (index!=i) ) ririndex; /若最小記錄不在最終位置則交換若最小記錄不在最終位置則交換 該算法的基本語句是內(nèi)層循環(huán)體中的比較語句該算法的基本語句是內(nèi)層循環(huán)體中的比較語句rjrindex，其執(zhí)行次數(shù)為：，其執(zhí)行次數(shù)為： 112111)(2) 1()(1nininijnOnnin算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社起泡排序在掃描過程中兩兩比較相鄰記錄，如果反序則交起泡排序在掃描過程中兩兩比較相鄰記錄，如果反序則交換，最終，最大記錄就被換，最終，最大記

28、錄就被“沉到沉到”了序列的最后一個(gè)位置，了序列的最后一個(gè)位置，第二遍掃描將第二大記錄第二遍掃描將第二大記錄“沉到沉到”了倒數(shù)第二個(gè)位置，重了倒數(shù)第二個(gè)位置，重復(fù)上述操作，直到復(fù)上述操作，直到n-1 遍掃描后，整個(gè)序列就排好序了。遍掃描后，整個(gè)序列就排好序了。 3.3.2 起泡排序起泡排序 rj rj+1 ri+1 rn- -1 rn 無序區(qū)無序區(qū) 有序區(qū)有序區(qū) 1ji- -1 位于最終位置位于最終位置反序則交換反序則交換算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法算法3.7起泡排序起泡排序 void BubbleSort( (int r , int n) ) /數(shù)組下標(biāo)從數(shù)組下

29、標(biāo)從1 1開始開始 for (i=1; i=n- -1; i+) for (j=1; jrj+1) rjrj+1；/如果反序，則交換元素如果反序，則交換元素 該算法的基本語句是內(nèi)層循環(huán)體中的比較語句該算法的基本語句是內(nèi)層循環(huán)體中的比較語句rjrj+1，其執(zhí)行次數(shù)為：，其執(zhí)行次數(shù)為： 112111)(2) 1()(1niniinjnOnnin算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社注意到，在一趟起泡排序過程中，如果有多個(gè)記錄交換到注意到，在一趟起泡排序過程中，如果有多個(gè)記錄交換到最終位置，則下一趟起泡排序?qū)⒉惶幚磉@些記錄；另外，最終位置，則下一趟起泡排序?qū)⒉惶幚磉@些記錄；另外，在

30、一趟起泡排序過程中，如果沒有記錄相交換，那么表明在一趟起泡排序過程中，如果沒有記錄相交換，那么表明這個(gè)數(shù)組已經(jīng)有序，算法將終止。這個(gè)數(shù)組已經(jīng)有序，算法將終止。算法算法3.8改進(jìn)的起泡排序改進(jìn)的起泡排序 void BubbleSort( (int r , int n) ) /數(shù)組下標(biāo)從數(shù)組下標(biāo)從1 1開始開始 exchange=n; /第一趟起泡排序的范圍是第一趟起泡排序的范圍是r1到到rn while ( (exchange) ) /僅當(dāng)上一趟排序有記錄交換才進(jìn)行本趟排序僅當(dāng)上一趟排序有記錄交換才進(jìn)行本趟排序 bound=exchange; exchange=0； for ( (j=1; jr

31、j+1) ) rjrj+1； exchange=j； /記錄每一次發(fā)生記錄交換的位置記錄每一次發(fā)生記錄交換的位置 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社在最好情況下，待排序記錄序列為正序，算法只執(zhí)行一趟，在最好情況下，待排序記錄序列為正序，算法只執(zhí)行一趟，進(jìn)行了進(jìn)行了n- -1次關(guān)鍵碼的比較，不需要移動(dòng)記錄，時(shí)間復(fù)雜性次關(guān)鍵碼的比較，不需要移動(dòng)記錄，時(shí)間復(fù)雜性為為O( (n) )；在最壞情況下，待排序記錄序列為反序，每趟排序在無序在最壞情況下，待排序記錄序列為反序，每趟排序在無序序列中只有一個(gè)最大的記錄被交換到最終位置，故算法執(zhí)序列中只有一個(gè)最大的記錄被交換到最終位置，故算法

32、執(zhí)行行n- -1趟，第趟，第i（1in）趟排序執(zhí)行了）趟排序執(zhí)行了n- -i次關(guān)鍵碼的比較次關(guān)鍵碼的比較和和n- -i次記錄的交換，這樣，關(guān)鍵碼的比較次數(shù)次記錄的交換，這樣，關(guān)鍵碼的比較次數(shù)為為 ，記錄的移動(dòng)次數(shù)為，記錄的移動(dòng)次數(shù)為 ，因此，時(shí)間復(fù)雜性為因此，時(shí)間復(fù)雜性為O( (n2) )；在平均情況下，其時(shí)間復(fù)雜性與最壞情況同數(shù)量級。在平均情況下，其時(shí)間復(fù)雜性與最壞情況同數(shù)量級。 2)1(11nninni）（2)1(3311nninni）（算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.4 3.4 組合問題中的蠻力法組合問題中的蠻力法 3.4.1 生成排列對象生成排列對象 3.4

33、.2 生成子集生成子集3.4.3 0/1背包問題背包問題3.4.4 任務(wù)分配問題任務(wù)分配問題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.4.1 生成排列對象生成排列對象 假設(shè)已經(jīng)生成了所有假設(shè)已經(jīng)生成了所有(n-1)!個(gè)排列，可以把個(gè)排列，可以把n插入到插入到n-1個(gè)元個(gè)元素的每一種排列中的素的每一種排列中的n個(gè)位置中去，來得到問題規(guī)模為個(gè)位置中去，來得到問題規(guī)模為n的的所有排列。按照這種方式生成的所有排列都是獨(dú)一無二的，所有排列。按照這種方式生成的所有排列都是獨(dú)一無二的，并且他們的總數(shù)應(yīng)該是并且他們的總數(shù)應(yīng)該是n(n-1)!=n!。開始開始 1插入插入2 12 21插入插入3

34、 123 132 312 213 231 321 生成排列的過程生成排列的過程算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社算法算法3.9生成排列對象生成排列對象 1生成初始排列生成初始排列1； 2for (i=2; i=n; i+) for (j=1; j=1; k-) 將將i插入到第插入到第j個(gè)排列中的第個(gè)排列中的第k個(gè)位置；個(gè)位置； 顯然，算法顯然，算法3.9的時(shí)間復(fù)雜性為的時(shí)間復(fù)雜性為O(n!)，也就是說和排，也就是說和排列對象的數(shù)量成正比。列對象的數(shù)量成正比。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.4.2 生成子集生成子集 n個(gè)元素的集合個(gè)元素的集合A

35、=a1, a2, an的所有的所有2n個(gè)子集和長度為個(gè)子集和長度為n的所有的所有2n個(gè)比特串之間的一一對應(yīng)關(guān)系。個(gè)比特串之間的一一對應(yīng)關(guān)系。建立對應(yīng)關(guān)系：為每一個(gè)子集指定一個(gè)比特串建立對應(yīng)關(guān)系：為每一個(gè)子集指定一個(gè)比特串b1b2bn，如，如果果ai屬于該子集，則屬于該子集，則bi1；如果；如果ai不屬于該子集，則不屬于該子集，則bi0（1in）。）。比特串比特串 000 001 010 011 100 101 110 111子集子集 a3 a2 a2,a3 a1 a1,a3 a1, a2 a1,a2,a2算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社生成n個(gè)元素子集的算法如下： 算法

36、算法3.10生成子集生成子集 1初始化一個(gè)長度為初始化一個(gè)長度為n的比特串的比特串s=000并將對應(yīng)的子集輸出；并將對應(yīng)的子集輸出； 2for (i=1; i2n; i+) 2.1 s+； 2.2 將將s對應(yīng)的子集輸出；對應(yīng)的子集輸出； 顯然，算法顯然，算法3.10的時(shí)間復(fù)雜性為的時(shí)間復(fù)雜性為O(2n)，也就是說和子，也就是說和子集的數(shù)量成正比。集的數(shù)量成正比。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.4.3 0/1背包問題背包問題 0/1背包問題是給定背包問題是給定n個(gè)重量為個(gè)重量為w1, w2, ,wn、價(jià)值為價(jià)值為v1, v2, ,vn的物品和一個(gè)容量為的物品和一個(gè)容

37、量為C的背包，的背包，求這些物品中的一個(gè)最有價(jià)值的子集，并且要能夠求這些物品中的一個(gè)最有價(jià)值的子集，并且要能夠裝到背包中。裝到背包中。 用蠻力法解決用蠻力法解決0/1背包問題，需要考慮給定背包問題，需要考慮給定n個(gè)個(gè)物品集合的所有子集，找出所有可能的子集（總重物品集合的所有子集，找出所有可能的子集（總重量不超過背包容量的子集），計(jì)算每個(gè)子集的總價(jià)量不超過背包容量的子集），計(jì)算每個(gè)子集的總價(jià)值，然后在他們中找到價(jià)值最大的子集。值，然后在他們中找到價(jià)值最大的子集。應(yīng)用實(shí)例：應(yīng)用實(shí)例：有有n個(gè)可投資的項(xiàng)目，每個(gè)項(xiàng)目需投成本個(gè)可投資的項(xiàng)目，每個(gè)項(xiàng)目需投成本si，可獲利潤，可獲利潤vi,現(xiàn)現(xiàn)有資金總數(shù)為

38、有資金總數(shù)為m,應(yīng)選擇哪些項(xiàng)目來投資，可獲得最大利潤。應(yīng)選擇哪些項(xiàng)目來投資，可獲得最大利潤。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社10w1=7v1=42w2=3v2=12w3=4v3=40w4=5v4=25背包背包 物品物品1 物品物品2 物品物品3 物品物品4 81,412161,2,3,419序號序號子集子集總重量總重量總價(jià)值總價(jià)值序號序號子集子集總重量總重量總價(jià)值總價(jià)值 100 92,3752 21742102,4837 32312113,4965 43440121,2,314不可行不可行 54525131,2,415 61,21054141,3,416 71,311不

39、可行不可行152,3,412不可行不可行不可行不可行不可行不可行不可行不可行不可行不可行例如：例如：算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 對于一個(gè)具有n個(gè)元素的集合，其子集數(shù)量是2n，所以，不論生成子集的算法效率有多高，蠻力法都會導(dǎo)致一個(gè)(2n)的算法。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.4.4 任務(wù)分配問題任務(wù)分配問題 假設(shè)有假設(shè)有n個(gè)任務(wù)需要分配給個(gè)任務(wù)需要分配給n個(gè)人執(zhí)行，個(gè)人執(zhí)行，每個(gè)任務(wù)只分配給一個(gè)人，每個(gè)人只分配一每個(gè)任務(wù)只分配給一個(gè)人，每個(gè)人只分配一個(gè)任務(wù)，且第個(gè)任務(wù)，且第j個(gè)任務(wù)分配給第個(gè)任務(wù)分配給第i個(gè)人的成本個(gè)人的成本是是Ci,

40、 j（1i , jn），任務(wù)分配問題要求），任務(wù)分配問題要求找出總成本最小的分配方案。找出總成本最小的分配方案。 應(yīng)用實(shí)例：有n個(gè)建筑物要建在n各地點(diǎn)，cij實(shí)在地點(diǎn)j建造建筑物i的成本，如何分配建筑任務(wù)，使得建設(shè)的總成本最少。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 下圖是一個(gè)任務(wù)分配問題的成本矩陣，矩陣元下圖是一個(gè)任務(wù)分配問題的成本矩陣，矩陣元素素Ci, j代表將任務(wù)代表將任務(wù)j分配給人員分配給人員i的成本。的成本。 C= 9 2 7 6 4 3 5 8 1任務(wù)任務(wù)1 任務(wù)任務(wù)2 任務(wù)任務(wù)3人員人員1人員人員2人員人員3 任務(wù)分配問題就是在分配成本矩陣中的每一行任務(wù)分配問題

41、就是在分配成本矩陣中的每一行選取一個(gè)元素，這些元素分別屬于不同的列，并且選取一個(gè)元素，這些元素分別屬于不同的列，并且元素之和最小。元素之和最小。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社可以用一個(gè)可以用一個(gè)n元組元組(j1, j2, , jn)來描述任務(wù)分配問題的一個(gè)可能來描述任務(wù)分配問題的一個(gè)可能解，其中第解，其中第i個(gè)分量個(gè)分量ji（1in）表示在第）表示在第i行中選擇的列號，行中選擇的列號，因此用蠻力法解決任務(wù)分配問題要求生成整數(shù)因此用蠻力法解決任務(wù)分配問題要求生成整數(shù)1n的全排列，的全排列，然后把成本矩陣中的相應(yīng)元素相加來求得每種分配方案的總?cè)缓蟀殉杀揪仃囍械南鄳?yīng)元素相加

42、來求得每種分配方案的總成本，最后選出具有最小和的方案。成本，最后選出具有最小和的方案。 序號序號分配方案分配方案 總成本總成本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算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 由于任務(wù)分配問題需要考慮的排列數(shù)由于任務(wù)分配問題需要考慮的排列數(shù)量是量是n!，所以，除了該問題的一些規(guī)模非，所以，除了該問題的一些規(guī)模非常小的實(shí)例，蠻力法幾乎是不實(shí)用的。常小的實(shí)例，蠻力法幾乎是不實(shí)用的。 算法設(shè)計(jì)與分析算法設(shè)

43、計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.5 圖問題中的蠻力法圖問題中的蠻力法 3.5.1 哈密頓回路問題哈密頓回路問題 3.5.2 TSP問題問題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.5.1 哈密頓回路問題哈密頓回路問題 著名的愛爾蘭數(shù)學(xué)家哈密頓（著名的愛爾蘭數(shù)學(xué)家哈密頓（William Hamilton，18051865）提出了著名的周游世界問題。他用正十二）提出了著名的周游世界問題。他用正十二面體的面體的20個(gè)頂點(diǎn)代表個(gè)頂點(diǎn)代表20個(gè)城市，要求從一個(gè)城市出發(fā)，個(gè)城市，要求從一個(gè)城市出發(fā)，經(jīng)過每個(gè)城市恰好一次，然后回到出發(fā)城市。經(jīng)過每個(gè)城市恰好一次，然后回到出發(fā)城市。1

44、983141202131545679101112161718正十二面體的展開圖，正十二面體的展開圖，按照圖中的頂點(diǎn)編號所按照圖中的頂點(diǎn)編號所構(gòu)成的回路，就是哈密構(gòu)成的回路，就是哈密頓回路的一個(gè)解。頓回路的一個(gè)解。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 使用蠻力法尋找哈密頓回路的基本思想是：對使用蠻力法尋找哈密頓回路的基本思想是：對于給定的無向圖于給定的無向圖G=(V, E)，首先生成圖中所有頂點(diǎn)，首先生成圖中所有頂點(diǎn)的排列對象的排列對象(vi1, vi2, , vin)，然后依次考察每個(gè)排列，然后依次考察每個(gè)排列對象是否滿足以下兩個(gè)條件：對象是否滿足以下兩個(gè)條件：（1）相鄰

45、頂點(diǎn)之間存在邊，即）相鄰頂點(diǎn)之間存在邊，即 (vij, vij+1)E（1jn-1）（2）最后一個(gè)頂點(diǎn)和第一個(gè)頂點(diǎn)之間存在邊，即）最后一個(gè)頂點(diǎn)和第一個(gè)頂點(diǎn)之間存在邊，即 (vin, vi1)E 滿足這兩個(gè)條件的回路就是哈密頓回路。滿足這兩個(gè)條件的回路就是哈密頓回路。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社12453路徑路徑(vij, vij+1)E1234512345（是）（是）12354123 54 （否）（否）1243512 43 5 （否）（否）否否否否1245312 45 3 （否）（否）12534125 34 （否）（否）1254312543（是）（是）(vin, v

46、i1)E是是是是是是是是(a) 一個(gè)無向圖一個(gè)無向圖 (b) 哈密頓回路求解過程哈密頓回路求解過程 顯然，蠻力法求解哈密頓回路在最壞情況下需要考察顯然，蠻力法求解哈密頓回路在最壞情況下需要考察所有頂點(diǎn)的排列對象，其時(shí)間復(fù)雜性為所有頂點(diǎn)的排列對象，其時(shí)間復(fù)雜性為O(n!)。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.5.2 TSP問題問題 TSP問題是指旅行家要旅行n個(gè)城市然后回到出發(fā)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。該問題又稱為貨郎擔(dān)問題、郵遞員問題、售貨員問題，是圖問題中最廣為人知的問題。 用蠻力法解決TSP問題，可以找出所有可能的旅行路線，從中選取

47、路徑長度最短的簡單回路。應(yīng)用實(shí)例：某生產(chǎn)汽車的工廠需要給汽車上顏色，每兩應(yīng)用實(shí)例：某生產(chǎn)汽車的工廠需要給汽車上顏色，每兩種顏色間的轉(zhuǎn)換開銷取決于轉(zhuǎn)換的兩種顏色以及他們的種顏色間的轉(zhuǎn)換開銷取決于轉(zhuǎn)換的兩種顏色以及他們的順序，如從順序，如從yellow到到black需要需要30個(gè)單位的開銷，從黑色個(gè)單位的開銷，從黑色到黃色需要到黃色需要90各單位。如何找一個(gè)最優(yōu)的生產(chǎn)調(diào)度，使各單位。如何找一個(gè)最優(yōu)的生產(chǎn)調(diào)度，使得顏色轉(zhuǎn)換的總開銷最少。得顏色轉(zhuǎn)換的總開銷最少。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社8abdc23571序號序號路徑路徑路徑長度路徑長度是否最短是否最短 1abcda 1

48、8 否否 2abdca 11 是是 3acbda 23 否否 4acdba 11 是是 5adbca 23 否否 6adcba 18 否否 注意到，在圖注意到，在圖3.16中有中有3對不同的路徑，對每對路徑來對不同的路徑，對每對路徑來說，不同的只是路徑的方向，因此，可以將這個(gè)數(shù)量減半，說，不同的只是路徑的方向，因此，可以將這個(gè)數(shù)量減半，則可能的解有則可能的解有( (n- -1) )!/ /2個(gè)。這是一個(gè)非常大的數(shù)，隨著個(gè)。這是一個(gè)非常大的數(shù)，隨著n的的增長，增長，TSP問題的可能解也在迅速地增長，例如：問題的可能解也在迅速地增長，例如：算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社l

49、 一個(gè)一個(gè)10城市的城市的TSP問題有大約有問題有大約有180,000個(gè)可能解。個(gè)可能解。l 一個(gè)一個(gè)20城市的城市的TSP問題有大約有問題有大約有 60,000,000,000,000,000個(gè)可能解。個(gè)可能解。l 一個(gè)一個(gè)50城市的城市的TSP問題有大約問題有大約1062個(gè)可能解，而一個(gè)個(gè)可能解，而一個(gè)行星上也只有行星上也只有1021升水。升水。v 用蠻力法求解用蠻力法求解TSP問題，只能解決問題規(guī)模很小的問題，只能解決問題規(guī)模很小的實(shí)例。實(shí)例。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.6 幾何問題中的蠻力法幾何問題中的蠻力法 3.6.1 最近對問題最近對問題3.6.2

50、凸包問題凸包問題算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社3.6.1 最近對問題最近對問題 最近對問題要求找出一個(gè)包含最近對問題要求找出一個(gè)包含n個(gè)點(diǎn)的集合中個(gè)點(diǎn)的集合中距離最近的兩個(gè)點(diǎn)。距離最近的兩個(gè)點(diǎn)。 簡單起見，只考慮二維的情況，并假設(shè)所討論簡單起見，只考慮二維的情況，并假設(shè)所討論的點(diǎn)是以標(biāo)準(zhǔn)笛卡兒坐標(biāo)形式（的點(diǎn)是以標(biāo)準(zhǔn)笛卡兒坐標(biāo)形式（x, y）給出的。因）給出的。因此，在兩個(gè)點(diǎn)此，在兩個(gè)點(diǎn)Pi=(xi, yi)和和Pj=(xj, yj)之間的距離是之間的距離是標(biāo)準(zhǔn)的歐幾里德距離：標(biāo)準(zhǔn)的歐幾里德距離： 22)()(jijiyyxxd算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析清華大學(xué)出版社清華大學(xué)出版社 蠻力法求解