1、第3章 蠻力法,3.1 蠻力法的設(shè)計思想,3.2 查找問題中的蠻力法,3.3 排序問題中的蠻力法,3.4 組合問題中的蠻力法,3.5 圖問題中的蠻力法,3.6 幾何問題中的蠻力法,3.7 實驗項目串匹配問題,3.1 蠻力法的設(shè)計思想,蠻力法的設(shè)計思想：直接基于問題的描述。 例：計算an,蠻力法所賴的基本技術(shù)掃描技術(shù) 關(guān)鍵依次處理所有元素 基本的掃描技術(shù)遍歷 （1）集合的遍歷 （2）線性表的遍歷 （3）樹的遍歷 （4）圖的遍歷,雖然巧妙和高效的算法很少來自于蠻力法，基于以下原因，蠻力法也是一種重要的算法設(shè)計技術(shù)：,（1）理論上，蠻力法可以解決可計算領(lǐng)域的各種問題。 （2）蠻力法經(jīng)常用來解決一些較

2、小規(guī)模的問題。 （3）對于一些重要的問題蠻力法可以產(chǎn)生一些合理的算法，他們具備一些實用價值，而且不受問題規(guī)模的限制。 （4）蠻力法可以作為某類問題時間性能的底限，來衡量同樣問題的更高效算法。,3.2 查找問題中的蠻力法,3.2.1 順序查找,3.2.2 串匹配問題,順序查找從表的一端向另一端逐個將元素與給定值進行比較，若相等，則查找成功，給出該元素在表中的位置；若整個表檢測完仍未找到與給定值相等的元素，則查找失敗，給出失敗信息。,3.2.1 順序查找,算法3.1的基本語句是i0和ri!=k，其執(zhí)行次數(shù)為:,基本語句 ？,將待查值放在查找方向的盡頭處，免去了在查找過程中每一次比較后都要判斷查找位

3、置是否越界，從而提高了查找速度。,改進的順序查找,算法3.2的基本語句是ri!=k，其執(zhí)行次數(shù)為:,數(shù)量級相同， 系數(shù)相差一半,用蠻力法設(shè)計的算法，一般來說，經(jīng)過適度的努力后，都可以對算法的第一個版本進行一定程度的改良，改進其時間性能，但只能減少系數(shù)，而數(shù)量級不會改變。,一般觀點：,3.2.2 串匹配問題,串匹配問題屬于易解問題。 串匹配問題的特征： （1）算法的一次執(zhí)行時間不容忽視：問題規(guī)模 n 很大，常常需要在大量信息中進行匹配； （2）算法改進所取得的積累效益不容忽視：串匹配操作經(jīng)常被調(diào)用，執(zhí)行頻率高。,串匹配問題給定兩個串S=“s1s2sn” 和T=“t1t2tm”，在主串S中查找子串

4、T的過程稱為串匹配，也稱模式匹配。,基本思想：從主串S的第一個字符開始和模式T的第一個字符進行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；若不相等，則從主串S的第二個字符開始和模式T的第一個字符進行比較，重復(fù)上述過程，若T中的字符全部比較完畢，則說明本趟匹配成功；若最后一輪匹配的起始位置是n-m，則主串S中剩下的字符不足夠匹配整個模式T，匹配失敗。這個算法稱為樸素的模式匹配算法，簡稱BF算法。,蠻力法解決串匹配問題BF算法,本趟匹配開始位置,設(shè)主串s=“ababcabcacbab”，模式t=“abcac,a b c,i=3，j=3失??； i回溯到2，j回溯到1,第1趟,a,第2趟,i=2，j=1失

5、敗 i回溯到3，j回溯到1,第3趟,a b c a c,i=7，j=5失敗 i回溯到4，j回溯到1,第4趟,a,i=4，j=1失敗 i回溯到5，j回溯到1,第5趟,a,i=5，j=1失敗 i回溯到6，j回溯到1,第6趟,i=11，j=6，t中全部字符都比較完畢，匹配成功。,int BF(char S , char T ) i=1; j=1; while (iT0) return (i-j+1); else return 0; ,BF C+算法,設(shè)串S長度為n，串T長度為m，在匹配成功的情況下，考慮最壞情況，即每趟不成功的匹配都發(fā)生在串T的最后一個字符。,例如：S=aaaaaaaaaaab T=

6、aaab 設(shè)匹配成功發(fā)生在si處，則在i-1趟不成功的匹配中共比較了(i-1)m次，第i趟成功的匹配共比較了m次，所以總共比較了im次，因此平均比較次數(shù)是：,改進的串匹配算法KMP算法,設(shè)計思想：盡量利用已經(jīng)部分匹配的結(jié)果信息，盡量讓主串 i 不回溯，加快模式串的滑動速度。,a b c,i=3，j=3失??；,第1趟,a,第2趟,s2=t2;t1t2 t1s2,第3趟,a b c a c,i=7，j=5失敗,第4趟,a,s4=t2;t1t2 t1s4,第5趟,a,s5=t3;t1t3 t1s5,第6趟,i=11，j=6，t中全部字符都比較完畢，匹配成功。,需要討論兩個問題： 如何由當(dāng)前部分匹配結(jié)

7、果確定模式向右滑動的新比較起點k？ 模式應(yīng)該向右滑多遠(yuǎn)才是最高效率的?,結(jié)論： i可以不回溯，模式向右滑動到的新比較起點k ，并且k 僅與模式串T有關(guān)！,請抓住部分匹配時的兩個特征：,兩式聯(lián)立可得：T1Tk-1Tj-(k-1) Tj-1,S=a b a b c a b c a c b a b,T=a b c a c,（1）設(shè)模式滑動到第k個字符，則T1Tk-1 Si-(k-1) Si-1,（2）則Tj-(k-1) Tj-1 Si-(k-1) Si-1,T1Tk-1Tj-(k-1) Tj-1說明了什么？ （1） k 與 j 具有函數(shù)關(guān)系，由當(dāng)前失配位置 j ，可以計算出滑動位置 k（即比較的新起

8、點）； （2）滑動位置k 僅與模式串T有關(guān)。,從第1位往右 經(jīng)過k-1位,從j-1位往左 經(jīng)過k-1位,kmax k |1kj 且T1Tk-1Tj-(k-1) Tj-1 ,T1Tk-1Tj-(k-1) Tj-1的物理意義是什么？,模式應(yīng)該向右滑多遠(yuǎn)才是最高效率的?,next j ,0 當(dāng)j1時 /不比較 max k | 1kj 且T1Tk-1=Tj-(k-1) Tj-1 1 其他情況,令k = next j ，則：,nextj函數(shù)表征著模式T中最大相同首子串和尾子串（真子串）的長度。可見，模式中相似部分越多，則nextj函數(shù)越大，模式串向右滑動得越遠(yuǎn)，與主串進行比較的次數(shù)越少，時間復(fù)雜度就越低

9、。,此時，比較tk和tj，可能出現(xiàn)兩種情況： （1）tktj：說明t1 tk-1tktj-k+1 tj-1tj，由前綴函數(shù)定義，nextj=k1；,由模式T的前綴函數(shù)定義易知，next1=0，假設(shè)已經(jīng)計算出next1，next2，nextj，如何計算nextj1呢？設(shè)k=nextj，這意味著t1 tk-1既是t1 tj-1的真后綴又是t1 tj-1的真前綴，即： t1 tk-1tj-k+1tj-k+2 tj-1,計算nextj的方法：,（2）tktj：此時要找出t1 tj-1的后綴中第2大真前綴，顯然，這個第2大的真前綴就是nextnextj=nextk。,再比較tnextk和tj，此時仍會出

10、現(xiàn)兩種情況，當(dāng)tnextktj時，與情況（1）類似，nextj=nextk+1；當(dāng)tnextktj時，與情況（2）類似，再找t1 tj-1的后綴中第3大真前綴，重復(fù)（2）的過程，直到找到t1 tj-1的后綴中的最大真前綴，或確定t1 tj-1的后綴中不存在真前綴，此時，nextj+1=1。,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；

11、j=4時，t1t3，next4=2；j=5時，t2t4， 令k=next2=1，t1t4，next5=k+1=2；,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算法用偽代碼描述如下：,KMP算法的時間復(fù)雜性是O(n+m)，當(dāng)mn時，KMP算法的時間復(fù)雜性是O(n)。,3.3 排序問題中的蠻力法,3.3.1 選擇排序,3.3.2 起泡排序,3.3.1 選擇排序,選擇排序第i趟排序從第i個記錄開始掃描

12、序列，在n-i+1（1in-1）個記錄中找到關(guān)鍵碼最小的記錄，并和第i個記錄交換作為有序序列的第i個記錄。,該算法的基本語句是內(nèi)層循環(huán)體中的比較語句rjrindex，其執(zhí)行次數(shù)為：,起泡排序在掃描過程中兩兩比較相鄰記錄，如果反序則交換，最終，最大記錄就被“沉到”了序列的最后一個位置，第二遍掃描將第二大記錄“沉到”了倒數(shù)第二個位置，重復(fù)上述操作，直到n-1遍掃描后，整個序列就排好序了。,3.3.2 起泡排序,該算法的基本語句是內(nèi)層循環(huán)體中的比較語句rjrj+1，其執(zhí)行次數(shù)為：,注意到，在一趟起泡排序過程中，如果有多個記錄交換到最終位置，則下一趟起泡排序?qū)⒉惶幚磉@些記錄；另外，在一趟起泡排序過程中

13、，如果沒有記錄相交換，那么表明這個數(shù)組已經(jīng)有序，算法將終止。,在最好情況下，待排序記錄序列為正序，算法只執(zhí)行一趟，進行了n-1次關(guān)鍵碼的比較，不需要移動記錄，時間復(fù)雜性為O(n)； 在最壞情況下，待排序記錄序列為反序，每趟排序在無序序列中只有一個最大的記錄被交換到最終位置，故算法執(zhí)行n-1趟，第i（1in）趟排序執(zhí)行了n-i次關(guān)鍵碼的比較和n-i次記錄的交換，這樣，關(guān)鍵碼的比較次數(shù)為 ，記錄的移動次數(shù)為 ，因此，時間復(fù)雜性為O(n2)； 在平均情況下，其時間復(fù)雜性與最壞情況同數(shù)量級。,3.4 組合問題中的蠻力法,3.4.1 生成排列對象,3.4.2 生成子集,3.4.3 0/1背包問題,3.4

14、.4 任務(wù)分配問題,3.4.1 生成排列對象,假設(shè)已經(jīng)生成了所有(n-1)!個排列，可以把n插入到n-1個元素的每一種排列中的n個位置中去，來得到問題規(guī)模為n的所有排列。按照這種方式生成的所有排列都是獨一無二的，并且他們的總數(shù)應(yīng)該是n(n-1)!=n!。,開始 1 插入2 12 21 插入3 123 132 312 213 231 321 生成排列的過程,顯然，算法3.9的時間復(fù)雜性為O(n!)，也就是說和排列對象的數(shù)量成正比。,3.4.2 生成子集,n個元素的集合A=a1, a2, an的所有2n個子集和長度為n的所有2n個比特串之間的一一對應(yīng)關(guān)系。 建立對應(yīng)關(guān)系：為每一個子集指定一個比特串

15、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,生成n個元素子集的算法如下：,顯然，算法3.10的時間復(fù)雜性為O(2n)，也就是說和子集的數(shù)量成正比。,3.4.3 0/1背包問題,0/1背包問題是給定n個重量為w1, w2, ,wn、價值為v1, v2, ,vn的物品和一個容量為C的背包，求這些物品中的一個最有價值的子集，并且要能夠裝到背包中。 用蠻力法解決0/1背包問題，需要考慮給定n個物品集合的所有子

16、集，找出所有可能的子集（總重量不超過背包容量的子集），計算每個子集的總價值，然后在他們中找到價值最大的子集。,對于一個具有n個元素的集合，其子集數(shù)量是2n，所以，不論生成子集的算法效率有多高，蠻力法都會導(dǎo)致一個(2n)的算法。,3.4.4 任務(wù)分配問題,假設(shè)有n個任務(wù)需要分配給n個人執(zhí)行，每個任務(wù)只分配給一個人，每個人只分配一個任務(wù)，且第j個任務(wù)分配給第i個人的成本是Ci, j（1i , jn），任務(wù)分配問題要求找出總成本最小的分配方案。,下圖是一個任務(wù)分配問題的成本矩陣，矩陣元素Ci, j代表將任務(wù)j分配給人員i的成本。,任務(wù)分配問題就是在分配成本矩陣中的每一行選取一個元素，這些元素分別屬于

17、不同的列，并且元素之和最小。,可以用一個n元組(j1, j2, , jn)來描述任務(wù)分配問題的一個可能解，其中第i個分量ji（1in）表示在第i行中選擇的列號，因此用蠻力法解決任務(wù)分配問題要求生成整數(shù)1n的全排列，然后把成本矩陣中的相應(yīng)元素相加來求得每種分配方案的總成本，最后選出具有最小和的方案。,由于任務(wù)分配問題需要考慮的排列數(shù)量是n!，所以，除了該問題的一些規(guī)模非常小的實例，蠻力法幾乎是不實用的。,3.5 圖問題中的蠻力法,3.5.1 哈密頓回路問題,3.5.2 TSP問題,3.5.1 哈密頓回路問題,著名的愛爾蘭數(shù)學(xué)家哈密頓（William Hamilton，18051865）提出了著名

18、的周游世界問題。他用正十二面體的20個頂點代表20個城市，要求從一個城市出發(fā)，經(jīng)過每個城市恰好一次，然后回到出發(fā)城市。,使用蠻力法尋找哈密頓回路的基本思想是：對于給定的無向圖G=(V, E)，首先生成圖中所有頂點的排列對象(vi1, vi2, , vin)，然后依次考察每個排列對象是否滿足以下兩個條件： （1）相鄰頂點之間存在邊，即 (vij, vij+1)E（1jn-1） （2）最后一個頂點和第一個頂點之間存在邊，即 (vin, vi1)E 滿足這兩個條件的回路就是哈密頓回路。,(a) 一個無向圖 (b) 哈密頓回路求解過程,顯然，蠻力法求解哈密頓回路在最壞情況下需要考察所有頂點的排列對象，

19、其時間復(fù)雜性為O(n!)。,3.5.2 TSP問題,TSP問題是指旅行家要旅行n個城市然后回到出發(fā)城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。該問題又稱為貨郎擔(dān)問題、郵遞員問題、售貨員問題，是圖問題中最廣為人知的問題。 用蠻力法解決TSP問題，可以找出所有可能的旅行路線，從中選取路徑長度最短的簡單回路。,注意到，在圖3.16中有3對不同的路徑，對每對路徑來說，不同的只是路徑的方向，因此，可以將這個數(shù)量減半，則可能的解有(n-1)!/2個。這是一個非常大的數(shù)，隨著n的增長，TSP問題的可能解也在迅速地增長，例如：,一個10城市的TSP問題有大約有180,000個可能解。 一個20城

20、市的TSP問題有大約有 60,000,000,000,000,000個可能解。 一個50城市的TSP問題有大約1062個可能解，而一個行星上也只有1021升水。 用蠻力法求解TSP問題，只能解決問題規(guī)模很小的實例。,3.6 幾何問題中的蠻力法,3.6.1 最近對問題,3.6.2 凸包問題,3.6.1 最近對問題,最近對問題要求找出一個包含n個點的集合中距離最近的兩個點。 簡單起見，只考慮二維的情況，并假設(shè)所討論的點是以標(biāo)準(zhǔn)笛卡兒坐標(biāo)形式（x, y）給出的。因此，在兩個點Pi=(xi, yi)和Pj=(xj, yj)之間的距離是標(biāo)準(zhǔn)的歐幾里德距離：,蠻力法求解最近對問題的過程是：分別計算每一對點

21、之間的距離，然后找出距離最小的那一對，為了避免對同一對點計算兩次距離，只考慮ij的那些點對(Pi, Pj)。,int ClosestPoints(int n, int x , int y , int ,算法3.11的基本操作是計算兩個點的歐幾里德距離。注意到在求歐幾里德距離時，避免了求平方根操作，其原因是：如果被開方的數(shù)越小，則它的平方根也越小。所以，算法3.11的基本操作就是求平方，其執(zhí)行次數(shù)為：,3.6.2 凸包問題,定義3.1 對于平面上的一個點的有限集合，如果以集合中任意兩點P和Q為端點的線段上的點都屬于該集合，則稱該集合是凸集合。 顯然，任意凸多邊形都是凸集合。,定義3.2 一個點集S的凸包是包含S的最小凸集合，其中，最小是指S的凸包一定是所有包含S的凸集合的子集。,對于平面上n個點的集合S，它的凸包就是包含所有這些點（或者在內(nèi)部，或者在邊界上）的最小凸多邊形。,凸包問題是為一個具有n個點的集合構(gòu)造凸多邊形的問題。為了解決凸包問題，需要找出凸多邊形的頂點，這樣的點稱為極點。 一個凸集合的極點應(yīng)該具有這樣性質(zhì)：對于任何以凸集合中的點為端點的線段來說，它不是這種線段中的點。,定