第3章 蠻力法 (1)

1、算法設(shè)計與分析算法設(shè)計與分析1第第3章章 蠻力法蠻力法 3.1 蠻力法的設(shè)計思想蠻力法的設(shè)計思想 3.2 查找問題中的蠻力法查找問題中的蠻力法3.3 排序問題中的蠻力法排序問題中的蠻力法3.4 組合問題中的蠻力法組合問題中的蠻力法3.5 圖問題中的蠻力法圖問題中的蠻力法3.6 幾何問題中的蠻力法幾何問題中的蠻力法算法設(shè)計與分析算法設(shè)計與分析23.1 蠻力法的設(shè)計思想蠻力法的設(shè)計思想 蠻力法蠻力法(窮舉法窮舉法）：是一種簡單而直接地解決問題）：是一種簡單而直接地解決問題的方法，常常直接基于問題的描述。的方法，常常直接基于問題的描述。例：計算例：計算ann次an=aaa算法設(shè)計與分析算法設(shè)計與分析

2、3n 蠻力法所賴的蠻力法所賴的基本技術(shù)基本技術(shù)掃描技術(shù)掃描技術(shù)n 關(guān)鍵關(guān)鍵依次處理所有元素依次處理所有元素n 基本的掃描技術(shù)基本的掃描技術(shù)遍歷遍歷（1）集合的遍歷：在集合中按照元素序號順序依次處理）集合的遍歷：在集合中按照元素序號順序依次處理每個元素。每個元素。（2）線性表的遍歷：在線性表中按照元素序號順序依次）線性表的遍歷：在線性表中按照元素序號順序依次處理每個元素。處理每個元素。（3）樹的遍歷）樹的遍歷 ：前序、后序和層序：前序、后序和層序3種，二叉樹有前序、種，二叉樹有前序、中序、后序和層序中序、后序和層序4種。種。（4）圖的遍歷）圖的遍歷 ：有深度優(yōu)先遍歷：有深度優(yōu)先遍歷 和廣度優(yōu)先遍

3、歷和廣度優(yōu)先遍歷 。算法設(shè)計與分析算法設(shè)計與分析4遍歷的結(jié)果：遍歷的結(jié)果：產(chǎn)生一個關(guān)于結(jié)點的線性序列。產(chǎn)生一個關(guān)于結(jié)點的線性序列。 設(shè)設(shè)訪問根結(jié)點訪問根結(jié)點記作記作 D 遍歷根的左子樹遍歷根的左子樹記作記作 L 遍歷根的右子樹遍歷根的右子樹記作記作 R 則可能的遍歷次序有則可能的遍歷次序有 先序先序 DLR DRL 逆先序逆先序 中序中序 LDR RDL 逆中序逆中序 后序后序 LRD RLD 逆后序逆后序 所謂遍歷二叉樹，就是遵從某種次序，訪所謂遍歷二叉樹，就是遵從某種次序，訪問二叉樹中的問二叉樹中的所有結(jié)點所有結(jié)點，使得每個結(jié)點，使得每個結(jié)點僅被僅被訪問一次訪問一次。遍歷二叉樹遍歷二叉樹算

4、法設(shè)計與分析算法設(shè)計與分析5先左后右的遍歷算法先左后右的遍歷算法先先（根）序的遍歷算法（根）序的遍歷算法中（根）序的遍歷算法中（根）序的遍歷算法后后（根）序的遍歷算法（根）序的遍歷算法根根左子樹右子樹根根根根根根根根根根算法設(shè)計與分析算法設(shè)計與分析6 若二叉樹為空樹，則空操作；否則，若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點；）訪問根結(jié)點；（2）先序遍歷左子樹；）先序遍歷左子樹；（3）先序遍歷右子樹。）先序遍歷右子樹。先（根）序的遍歷算法：先（根）序的遍歷算法：算法設(shè)計與分析算法設(shè)計與分析7 若二叉樹為空樹，則空操作；否則，若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；）中序遍歷

5、左子樹；（2）訪問根結(jié)點；）訪問根結(jié)點；（3）中序遍歷右子樹。）中序遍歷右子樹。中（根）序的遍歷算法：中（根）序的遍歷算法：算法設(shè)計與分析算法設(shè)計與分析8 若二叉樹為空樹，則空操作；否則，若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；）后序遍歷左子樹；（2）后序遍歷右子樹；）后序遍歷右子樹；（3）訪問根結(jié)點。）訪問根結(jié)點。后（根）序的遍歷算法：后（根）序的遍歷算法：算法設(shè)計與分析算法設(shè)計與分析9ABCDEFGHK例如：例如：先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A算

6、法設(shè)計與分析算法設(shè)計與分析10 雖然巧妙和高效的算法很少來自于蠻力法，基于雖然巧妙和高效的算法很少來自于蠻力法，基于以下原因，蠻力法也是一種重要的算法設(shè)計技術(shù)：以下原因，蠻力法也是一種重要的算法設(shè)計技術(shù)： （1）理論上，蠻力法可以解決可計算領(lǐng)域的各種問）理論上，蠻力法可以解決可計算領(lǐng)域的各種問題。題。 （2）蠻力法經(jīng)常用來解決一些較小規(guī)模的問題。）蠻力法經(jīng)常用來解決一些較小規(guī)模的問題。 （3）對于一些重要的問題蠻力法可以產(chǎn)生一些合理）對于一些重要的問題蠻力法可以產(chǎn)生一些合理的算法，他們具備一些實用價值，而且不受問題規(guī)模的算法，他們具備一些實用價值，而且不受問題規(guī)模的限制。的限制。 （4）蠻力法

7、可以作為某類問題時間性能的底限，來）蠻力法可以作為某類問題時間性能的底限，來衡量同樣問題的更高效算法。衡量同樣問題的更高效算法。 算法設(shè)計與分析算法設(shè)計與分析113.2 查找問題中的蠻力法查找問題中的蠻力法 3.2.1 順序查找順序查找 3.2.2 串匹配問題串匹配問題算法設(shè)計與分析算法設(shè)計與分析12 順序查找從表的一端向另一端順序查找從表的一端向另一端逐個逐個將元素與給定值將元素與給定值進行比較，若相等，則查找成功，給出該元素在表中的進行比較，若相等，則查找成功，給出該元素在表中的位置；若整個表檢測完仍未找到與給定值相等的元素，位置；若整個表檢測完仍未找到與給定值相等的元素，則查找失敗，給出

8、失敗信息。則查找失敗，給出失敗信息。3.2.1 順序查找順序查找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i查找方向查找方向算法設(shè)計與分析算法設(shè)計與分析13算法算法3.1順序查找順序查找 int SeqSearch1( (int r , int n, int k) ) /數(shù)組數(shù)組r1 rn存放查找存放查找集合集合 i=n; while ( (i0 & ri!=k) ) i-; return i; 算法算法3.1的的基本語句基本語句是是i0和和ri!=k，其執(zhí)行次數(shù)為，其執(zhí)行次數(shù)為:Pi為查找成功的概率，為查找成功的概率，ci和和bi為比較次數(shù)。

9、為比較次數(shù)。ninininiiiiinOninninncpbp1111)(1) 1(1) 1(1基本語句基本語句 ？算法設(shè)計與分析算法設(shè)計與分析14將將待查值待查值放在查找方向的放在查找方向的盡頭盡頭處，免去了在查找過處，免去了在查找過程中每一次比較后都要判斷查找位置是否程中每一次比較后都要判斷查找位置是否越界越界，從，從而提高了查找速度。而提高了查找速度。k 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i查找方向查找方向哨兵哨兵改進的順序查找改進的順序查找算法設(shè)計與分析算法設(shè)計與分析15算法算法3.2改進的順序查找改進的順序查找 int SeqS

10、earch2(int r , int n, int k) /數(shù)組數(shù)組r1 rn存放查找集合存放查找集合 r0=k; i=n; while (ri!=k) i -; return i;算法算法3.2的的基本語句基本語句是是ri!=k，其執(zhí)行次數(shù)為，其執(zhí)行次數(shù)為: niniiinOninncp11)(21) 1(1數(shù)量級相同，數(shù)量級相同，系數(shù)相差一半系數(shù)相差一半算法設(shè)計與分析算法設(shè)計與分析16 用蠻力法設(shè)計的算法，一般來說，經(jīng)過適度的用蠻力法設(shè)計的算法，一般來說，經(jīng)過適度的努力后，都可以對算法的第一個版本進行一定程度努力后，都可以對算法的第一個版本進行一定程度的改良，改進其時間性能，但的改良，改進

11、其時間性能，但只能減少系數(shù)，而數(shù)只能減少系數(shù)，而數(shù)量級不會改變。量級不會改變。v 一般觀點：一般觀點：算法設(shè)計與分析算法設(shè)計與分析173.2.2 串匹配問題串匹配問題 串匹配問題屬于易解問題。串匹配問題屬于易解問題。 串匹配問題的特征：串匹配問題的特征： （1）算法的一次執(zhí)行時間不容忽視：問題規(guī)模）算法的一次執(zhí)行時間不容忽視：問題規(guī)模 n 很大，常常需要在大量信息中進行匹配；很大，常常需要在大量信息中進行匹配； （2）算法改進所取得的積累效益不容忽視：串匹配）算法改進所取得的積累效益不容忽視：串匹配操作經(jīng)常被調(diào)用，執(zhí)行頻率高。操作經(jīng)常被調(diào)用，執(zhí)行頻率高。 串匹配問題串匹配問題給定兩個串給定兩個

12、串S=“s1s2sn” 和和T=“t1t2tm”，在主串，在主串S中查找子串中查找子串T的過程稱為的過程稱為串匹配串匹配，也稱也稱模式匹配模式匹配。算法設(shè)計與分析算法設(shè)計與分析18 基本思想：從主串基本思想：從主串S的第一個字符開始和模式的第一個字符開始和模式T的第的第一個字符進行比較，若相等，則繼續(xù)比較兩者的后續(xù)字一個字符進行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；若不相等，則從主串符；若不相等，則從主串S的第二個字符開始和模式的第二個字符開始和模式T的第一個字符進行比較，重復(fù)上述過程，若的第一個字符進行比較，重復(fù)上述過程，若T中的字符中的字符全部比較完畢，則說明本趟匹配成功；若最后一輪匹配

13、全部比較完畢，則說明本趟匹配成功；若最后一輪匹配的起始位置是的起始位置是n-m？，則主串則主串S中剩下的字符不足夠匹中剩下的字符不足夠匹配整個模式配整個模式T，匹配失敗。這個算法稱為，匹配失敗。這個算法稱為樸素的模式匹樸素的模式匹配算法配算法，簡稱，簡稱BF算法算法。蠻力法解決串匹配問題蠻力法解決串匹配問題BF算法算法算法設(shè)計與分析算法設(shè)計與分析19本趟匹配開始位置本趟匹配開始位置 si 主串主串S模式模式T tjj 回溯回溯 回溯回溯i算法設(shè)計與分析算法設(shè)計與分析20設(shè)主串設(shè)主串s=“ababcabcacbab”，模式，模式t=“abcaca b a b c a b c a c b a ba

14、 b c i=3，j=3失??；失?。籭回溯到回溯到2，j回溯到回溯到1第第1趟趟ijijijij算法設(shè)計與分析算法設(shè)計與分析21a 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è)計與分析算法設(shè)計與分析22第第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

15、a b c a c b a bijajii=5，j=1失敗失敗i回溯到回溯到6，j回溯到回溯到1 算法設(shè)計與分析算法設(shè)計與分析23第第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è)計與分析算法設(shè)計與分析24 設(shè)設(shè)S=s1,s2,sn(主串主串)T=t1,t2,tm(模式串模式串) i為指向為指向S中字符的指針，中字符的指針，j為指向為指向T中字中字符的指針符的指針 匹配失?。浩ヅ涫。簊itj時，時，(si-j+1 si-1)=(t1 tj-1) 回溯

16、：回溯： i=i-j+2 ; j=1算法設(shè)計與分析算法設(shè)計與分析25int BF( (char S , char T ) ) i=1; j=1; while ( (i=S0 & jT0) ) return ( (i- -j+1) ); / else return 0;BF C+算法算法算法設(shè)計與分析算法設(shè)計與分析26 設(shè)串設(shè)串S長度為長度為n，串，串T長度為長度為m，在匹配成功的情況下，在匹配成功的情況下，考慮最壞情況，即每趟不成功的匹配都發(fā)生在串考慮最壞情況，即每趟不成功的匹配都發(fā)生在串T的最后一的最后一個字符。個字符。 例如：例如：S=aaaaaaaaaaab T=aaab 設(shè)匹配成功發(fā)生

17、在設(shè)匹配成功發(fā)生在si處，則在處，則在i- -1趟不成功的匹配中共趟不成功的匹配中共比較了比較了( (i- -1) )m次，第次，第i趟成功的匹配共比較了趟成功的匹配共比較了m次，所次，所以總共比較了以總共比較了im次，因此平均比較次數(shù)是：次，因此平均比較次數(shù)是：11112) 2()(11)(mnimniimnmmimnmip一般情況下，一般情況下，mn，因此最壞情況下的時間復(fù)雜性是，因此最壞情況下的時間復(fù)雜性是O( (n*m) )。 BP算法簡單但效率低，主要原因是重復(fù)回溯太多。算法簡單但效率低，主要原因是重復(fù)回溯太多。算法設(shè)計與分析算法設(shè)計與分析27改進的串匹配算法改進的串匹配算法KMP算

18、法算法 由由D.E.Knuth, J.H.Morris D.E.Knuth, J.H.Morris ，V.R.PrattV.R.Pratt同時設(shè)同時設(shè)計計KMPKMP算法。算法。 設(shè)計思想設(shè)計思想：盡量利用已經(jīng)盡量利用已經(jīng)部分匹配部分匹配的結(jié)果信的結(jié)果信息，盡量讓息，盡量讓 i i 不回溯，加快模式串的滑動速度。不回溯，加快模式串的滑動速度。算法設(shè)計與分析算法設(shè)計與分析28 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è)計與分析算

19、法設(shè)計與分析293.3 3.3 排序問題中的蠻力法排序問題中的蠻力法 3.3.1 選擇排序選擇排序 3.3.2 起泡排序起泡排序算法設(shè)計與分析算法設(shè)計與分析303.3.1 選擇排序選擇排序 選擇排序第選擇排序第i趟排序從第趟排序從第i個記錄開始掃描序列，在個記錄開始掃描序列，在n-i+1（1in-1）個記錄中找到關(guān)鍵碼最小的記錄，并和第）個記錄中找到關(guān)鍵碼最小的記錄，并和第i個記個記錄交換作為有序序列的第錄交換作為有序序列的第i個記錄。個記錄。(第i趟選擇排序是指通過n-i次關(guān)鍵字的比較) r1 r2 ri- -1 ri ri+1 rmin rn 有序區(qū)有序區(qū) 無序區(qū)無序區(qū) 已經(jīng)位于最終位置已

20、經(jīng)位于最終位置 rmin為無序區(qū)的最小記錄為無序區(qū)的最小記錄例如：進行第例如：進行第i趟選擇時，從當(dāng)前候選記錄中趟選擇時，從當(dāng)前候選記錄中選出關(guān)鍵字最小的選出關(guān)鍵字最小的k號記錄，并與第號記錄，并與第i個記錄進個記錄進行交換。行交換。 交換交換算法設(shè)計與分析算法設(shè)計與分析31 圖 選擇排序示例 4862357755143598ik1462357755483598ik1435627755483598ik1435357755486298ik算法設(shè)計與分析算法設(shè)計與分析32算法算法3.6選擇排序選擇排序 void SelectSort( (int r , int n) ) /數(shù)組下標從數(shù)組下標從1

21、1開始開始 for ( (i=1; i=n- -1; i+) ) /對對n個記錄進行個記錄進行n- -1趟簡單選擇排序趟簡單選擇排序 index=i; for ( (j=i+1; j=n; j+) ) /在無序區(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()(1nininijnOnn

22、in算法設(shè)計與分析算法設(shè)計與分析33起泡排序在掃描過程中兩兩比較相鄰記錄，如果反序則交起泡排序在掃描過程中兩兩比較相鄰記錄，如果反序則交換，最終，最大記錄就被換，最終，最大記錄就被“沉到沉到”了序列的最后一個位置，了序列的最后一個位置，第二遍掃描將第二大記錄第二遍掃描將第二大記錄“沉到沉到”了倒數(shù)第二個位置，重了倒數(shù)第二個位置，重復(fù)上述操作，直到復(fù)上述操作，直到n-1 遍掃描后，整個序列就排好序了。遍掃描后，整個序列就排好序了。 3.3.2 起泡排序起泡排序 rj rj+1 ri+1 rn- -1 rn 無序區(qū)無序區(qū) 有序區(qū)有序區(qū) 1ji- -1 位于最終位置位于最終位置反序則交換反序則交換算

23、法設(shè)計與分析算法設(shè)計與分析34【例例】已知序列（已知序列（17，18，60，40，7，32，73，65，85），請給出采），請給出采用冒泡排序法對該序列作升序排序時的每一趟的結(jié)果。用冒泡排序法對該序列作升序排序時的每一趟的結(jié)果。解：解：初始初始 1趟趟 2趟趟 3趟趟 4趟趟 5趟趟 17 17 17 17 7 718 18 18 7 17 1760 40 7 18 18 1840 7 32 32 32 327 32 40 40 40 4032 60 60 60 60 6073 65 65 65 65 6565 73 73 73 73 7385 85 85 85 85 85 （ 紅色字表示有序

24、區(qū)）紅色字表示有序區(qū)）算法設(shè)計與分析算法設(shè)計與分析35算法算法3.7起泡排序起泡排序 void BubbleSort( (int r , int n) ) /數(shù)組下標從數(shù)組下標從1 1開始開始 for (i=1; i=n- -1; i+) /共共n-1趟趟 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è)計與分析算法設(shè)計與分析36注意到，在一趟起泡排序過程中，如果

25、有多個記錄交換到注意到，在一趟起泡排序過程中，如果有多個記錄交換到最終位置，則下一趟起泡排序?qū)⒉惶幚磉@些記錄；另外，最終位置，則下一趟起泡排序?qū)⒉惶幚磉@些記錄；另外，在一趟起泡排序過程中，如果沒有記錄相交換，那么表明在一趟起泡排序過程中，如果沒有記錄相交換，那么表明這個數(shù)組已經(jīng)有序，算法將終止。這個數(shù)組已經(jīng)有序，算法將終止。算法算法3.8改進的起泡排序改進的起泡排序 void BubbleSort( (int r , int n) ) /數(shù)組下標從數(shù)組下標從1 1開始開始 exchange=n; /第一趟起泡排序的范圍是第一趟起泡排序的范圍是r1到到rn while ( (exchange)

26、) /僅當(dāng)上一趟排序有記錄交換才進行本趟僅當(dāng)上一趟排序有記錄交換才進行本趟排序排序 bound=exchange; exchange=0； for ( (j=1; jrj+1) ) rjrj+1； exchange=j； /記錄每一次發(fā)生記錄交換的位置記錄每一次發(fā)生記錄交換的位置 算法設(shè)計與分析算法設(shè)計與分析37冒泡排序算法如下：冒泡排序算法如下：void BubbleSort(RecordType r, int length )/*對記錄數(shù)組對記錄數(shù)組r做冒泡排序，做冒泡排序， length為數(shù)組的長度為數(shù)組的長度*/ n=length; change=TRUE； for ( i=1 ; i

27、= n-1 & change ;+i ) change=FALSE； for ( j=1 ; j rj+1.key ) x= rj; rj= rj+1; rj+1= z; change=TRUE； /* BubbleSort */ 算法設(shè)計與分析算法設(shè)計與分析38 在最好情況下，在最好情況下，待排序記錄序列為正序，算法只執(zhí)行一趟，待排序記錄序列為正序，算法只執(zhí)行一趟，進行了進行了n- -1次關(guān)鍵碼的比較，不需要移動記錄，時間復(fù)雜性為次關(guān)鍵碼的比較，不需要移動記錄，時間復(fù)雜性為O( (n) )； 在最壞情況下，在最壞情況下，待排序記錄序列為反序，每趟排序在無序序待排序記錄序列為反序，每趟排序在無

28、序序列中只有一個最大的記錄被交換到最終位置，故算法執(zhí)行列中只有一個最大的記錄被交換到最終位置，故算法執(zhí)行n- -1趟，第趟，第i（1in）趟排序執(zhí)行了）趟排序執(zhí)行了n- -i次關(guān)鍵碼的比較和次關(guān)鍵碼的比較和n- -i次記次記錄的交換，這樣，關(guān)鍵碼的比較次數(shù)為錄的交換，這樣，關(guān)鍵碼的比較次數(shù)為 ，記錄，記錄的移動次數(shù)為的移動次數(shù)為 ，因此，時間復(fù)雜性為，因此，時間復(fù)雜性為O( (n2) )； 注意：注意：最壞情況下，待排序記錄按關(guān)鍵字的逆序進行排列，最壞情況下，待排序記錄按關(guān)鍵字的逆序進行排列，此時，每一趟冒泡排序需進行此時，每一趟冒泡排序需進行k 次比較，則有次比較，則有3k次移動。次移動。在

29、平均情況下在平均情況下，其時間復(fù)雜性與最壞情況同數(shù)量級。，其時間復(fù)雜性與最壞情況同數(shù)量級。 2)1(11nninni）（2)1(3311nninni）（算法設(shè)計與分析算法設(shè)計與分析393.4 3.4 組合問題中的蠻力法組合問題中的蠻力法 3.4.1 生成排列對象生成排列對象 3.4.2 生成子集生成子集3.4.3 0/1背包問題背包問題3.4.4 任務(wù)分配問題任務(wù)分配問題算法設(shè)計與分析算法設(shè)計與分析403.4.1 生成排列對象生成排列對象 假設(shè)已經(jīng)生成了所有假設(shè)已經(jīng)生成了所有(n-1)!個排列，可以把個排列，可以把n插入到插入到n-1個個元素的每一種排列中的元素的每一種排列中的n個位置中去，來

30、得到問題規(guī)模為個位置中去，來得到問題規(guī)模為n的所有排列。按照這種方式生成的所有排列都是獨一無二的所有排列。按照這種方式生成的所有排列都是獨一無二的，并且他們的總數(shù)應(yīng)該是的，并且他們的總數(shù)應(yīng)該是n(n-1)!=n!。開始開始 1插入插入2 12 21插入插入3 123 132 312 213 231 321 生成排列的過程生成排列的過程算法設(shè)計與分析算法設(shè)計與分析41算法算法3.9生成排列對象生成排列對象 1生成初始排列生成初始排列1； 2for (i=2; i=n; i+) /i為插入元素為插入元素 for (j=1; j=1; k-) /插入位置插入位置 將將i插入到第插入到第j個排列中的第

31、個排列中的第k個位置；個位置； 顯然，算法顯然，算法3.9的時間復(fù)雜性為的時間復(fù)雜性為O(n!)，也就是說和排，也就是說和排列對象的數(shù)量成正比。列對象的數(shù)量成正比。 算法設(shè)計與分析算法設(shè)計與分析423.4.2 生成子集生成子集 n個元素的集合個元素的集合A=a1, a2, an的所有的所有2n個子集和長度個子集和長度為為n的所有的所有2n個個比特串比特串之間的一一對應(yīng)關(guān)系。之間的一一對應(yīng)關(guān)系。 建立對應(yīng)關(guān)系：為每一個子集指定一個比特串建立對應(yīng)關(guān)系：為每一個子集指定一個比特串b1b2bn，如果如果ai屬于該子集，則屬于該子集，則bi1；如果；如果ai不屬于該子集，則不屬于該子集，則bi0（1in

32、）。）。比特串比特串 000 001 010 011 100 101 110 111子集子集 a3 a2 a2,a3 a1 a1,a3 a1, a2 a1,a2,a2算法設(shè)計與分析算法設(shè)計與分析43生成生成n個元素子集的算法如下：個元素子集的算法如下： 算法算法3.10生成子集生成子集 1初始化一個長度為初始化一個長度為n的比特串的比特串s=000并將對應(yīng)的子并將對應(yīng)的子集輸出；集輸出； 2for (i=1; i2n; i+) 2.1 s+； 2.2 將將s對應(yīng)的子集輸出；對應(yīng)的子集輸出； 顯然，算法顯然，算法3.10的時間復(fù)雜性為的時間復(fù)雜性為O(2n)，也就是說和子，也就是說和子集的數(shù)量成

33、正比。集的數(shù)量成正比。 算法設(shè)計與分析算法設(shè)計與分析443.4.3 0/1背包問題背包問題 0/1背包問題是給定背包問題是給定n個重量為個重量為w1, w2, ,wn、價值為價值為v1, v2, ,vn的物品和一個容量為的物品和一個容量為C的背包，的背包，求這些物品中的一個最有價值的子集，并且要能夠求這些物品中的一個最有價值的子集，并且要能夠裝到背包中。裝到背包中。 用蠻力法用蠻力法解決解決0/1背包問題，需要考慮給定背包問題，需要考慮給定n個個物品集合的所有子集，找出所有可能的子集（總重物品集合的所有子集，找出所有可能的子集（總重量不超過背包容量的子集），計算每個子集的總價量不超過背包容量的

34、子集），計算每個子集的總價值，然后在他們中找到價值最大的子集。值，然后在他們中找到價值最大的子集。算法設(shè)計與分析算法設(shè)計與分析4510w1=7v1=42w2=3v2=12w3=4v3=40w4=5v4=25背包背包 物品物品1 物品物品2 物品物品3 物品物品4 81,412161,2,3,419序號序號子集子集總重量總重量總價值總價值序號序號子集子集總重量總重量總價值總價值 100 92,3752 21742102,4837 32312113,4965 43440121,2,314不可行不可行 54525131,2,415 61,21054141,3,416 71,311不可行不可行152,

35、3,412不可行不可行不可行不可行不可行不可行不可行不可行不可行不可行算法設(shè)計與分析算法設(shè)計與分析46 對于一個具有對于一個具有n個元素的集合，其子集個元素的集合，其子集數(shù)量是數(shù)量是2n，所以，不論生成子集的算法，所以，不論生成子集的算法效率有多高，蠻力法都會導(dǎo)致一個效率有多高，蠻力法都會導(dǎo)致一個(2n)的算法。的算法。(描述增長率的下限）描述增長率的下限） 算法設(shè)計與分析算法設(shè)計與分析473.4.4 任務(wù)分配問題任務(wù)分配問題 假設(shè)有假設(shè)有n個任務(wù)需要分配給個任務(wù)需要分配給n個人執(zhí)行，個人執(zhí)行，每個任務(wù)只分配給一個人，每個人只分配一每個任務(wù)只分配給一個人，每個人只分配一個任務(wù)，且第個任務(wù)，且第

36、j個任務(wù)分配給第個任務(wù)分配給第i個人的成本個人的成本是是Ci, j（1i , jn），任務(wù)分配問題要求），任務(wù)分配問題要求找出總成本最小的分配方案。找出總成本最小的分配方案。 算法設(shè)計與分析算法設(shè)計與分析48 下圖是一個任務(wù)分配問題的成本矩陣，矩陣元下圖是一個任務(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ù)分配問題就是在分配成本矩陣中的每一行選取一個元素，這些元素分別屬于不同的列，并且選取

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

38、案分配方案 總成本總成本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è)計與分析算法設(shè)計與分析50 由于任務(wù)分配問題需要考慮的排列數(shù)由于任務(wù)分配問題需要考慮的排列數(shù)量是量是n!，所以，除了該問題的一些規(guī)模非，所以，除了該問題的一些規(guī)模非常小的實例，蠻力法幾乎是不實用的。常小的實例，蠻力法幾乎是不實用的。 算法設(shè)計與分析算法設(shè)計與分析513.5 圖問題中的蠻力法圖問題中的蠻力法 3.5.1 哈密頓回路問題哈密頓回路問題 3.5.2 TSP問題問題算法

39、設(shè)計與分析算法設(shè)計與分析523.5.1 哈密頓回路問題哈密頓回路問題 著名的愛爾蘭數(shù)學(xué)家著名的愛爾蘭數(shù)學(xué)家哈密頓哈密頓（William Hamilton，18051865）提出了著名的周游世界問題。他用正十二）提出了著名的周游世界問題。他用正十二面體的面體的20個頂點代表個頂點代表20個城市，要求從一個城市出發(fā)，個城市，要求從一個城市出發(fā)，經(jīng)過每個城市恰好一次，然后回到出發(fā)城市。經(jīng)過每個城市恰好一次，然后回到出發(fā)城市。1983141202131545679101112161718正十二面體的展開圖，正十二面體的展開圖，按照圖中的頂點編號所按照圖中的頂點編號所構(gòu)成的回路，就是哈密構(gòu)成的回路，就是

40、哈密頓回路的一個解。頓回路的一個解。 算法設(shè)計與分析算法設(shè)計與分析53 使用蠻力法尋找哈密頓回路的基本思想是：對使用蠻力法尋找哈密頓回路的基本思想是：對于給定的無向圖于給定的無向圖G=(V, E)，首先生成圖中所有頂點，首先生成圖中所有頂點的排列對象的排列對象(vi1, vi2, , vin)，然后依次考察每個排列，然后依次考察每個排列對象是否滿足以下對象是否滿足以下兩個條件：兩個條件：（1）相鄰頂點之間存在邊，即）相鄰頂點之間存在邊，即 (vij, vij+1)E（1jn-1）（2）最后一個頂點和第一個頂點之間存在邊，即）最后一個頂點和第一個頂點之間存在邊，即 (vin, vi1)E 滿足這

41、兩個條件的回路就是哈密頓回路。滿足這兩個條件的回路就是哈密頓回路。算法設(shè)計與分析算法設(shè)計與分析5412453路徑路徑(vij, vij+1)E1234512345（是）（是）12354123 54 （否）（否）1243512 43 5 （否）（否）否否否否1245312 45 3 （否）（否）12534125 34 （否）（否）1254312543（是）（是）(vin, vi1)E是是是是是是是是(a) 一個無向圖一個無向圖 (b) 哈密頓回路求解過程哈密頓回路求解過程 顯然，蠻力法求解哈密頓回路在最壞情況下需要考察顯然，蠻力法求解哈密頓回路在最壞情況下需要考察所有頂點的排列對象，其所有頂點的

42、排列對象，其時間復(fù)雜性為時間復(fù)雜性為O(n!)。 算法設(shè)計與分析算法設(shè)計與分析553.5.2 TSP問題問題 TSP(旅行商）旅行商）問題是問題是指旅行家要旅行指旅行家要旅行n個城市然后回個城市然后回到出發(fā)城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次，并要求到出發(fā)城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。該問題又稱為所走的路程最短。該問題又稱為貨郎擔(dān)問題貨郎擔(dān)問題、郵遞員問郵遞員問題、售貨員問題，題、售貨員問題，是圖問題中最廣為人知的問題。是圖問題中最廣為人知的問題。 用蠻力法解決用蠻力法解決TSP問題，可以找出所有可能的旅行問題，可以找出所有可能的旅行路線，從中選取路徑長度最短的簡單回

43、路。路線，從中選取路徑長度最短的簡單回路。 算法設(shè)計與分析算法設(shè)計與分析568abdc23571序號序號路徑路徑路徑長度路徑長度是否最短是否最短 1abcda 18 否否 2abdca 11 是是 3acbda 23 否否 4acdba 11 是是 5adbca 23 否否 6adcba 18 否否 注意到，在圖注意到，在圖3.16中有中有3對不同對不同的路徑，對每對路徑來的路徑，對每對路徑來說，不同的只是路徑的方向，因此，可以將這個數(shù)量減半，說，不同的只是路徑的方向，因此，可以將這個數(shù)量減半，則可能的解有則可能的解有( (n- -1) )!/ /2個。這是一個非常大的數(shù)，隨著個。這是一個非常

44、大的數(shù)，隨著n的的增長，增長，TSP問題的可能解也在迅速地增長，例如：問題的可能解也在迅速地增長，例如：算法設(shè)計與分析算法設(shè)計與分析57l 一個一個10城市的城市的TSP問題有大約有問題有大約有180,000個可能解。個可能解。l 一個一個20城市的城市的TSP問題有大約有問題有大約有 60,000,000,000,000,000個可能解。個可能解。l 一個一個50城市的城市的TSP問題有大約問題有大約1062個可能解，而一個個可能解，而一個行星上也只有行星上也只有1021升水。升水。v 用蠻力法求解用蠻力法求解TSP問題，只能解決問題規(guī)模很小的問題，只能解決問題規(guī)模很小的實例。實例。算法設(shè)計與分析算法設(shè)計與分析583.6 幾何問題中的蠻力法幾何問題中的蠻力法 3.6.1 最近對問題最近對問題3.6.2 凸包問題凸包問題算法設(shè)計與分析算法設(shè)計與分析593