第3章 蠻力法

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

2、22-3-7算法設(shè)計(jì)與分析-蠻力法3應(yīng)用實(shí)例應(yīng)用實(shí)例: 計(jì)算計(jì)算an的值是的值是RSA算法的主要組成算法的主要組成部分。部分。 RSA算法的加密和解密過程都需要一算法的加密和解密過程都需要一個(gè)整數(shù)的整數(shù)次冪再取模。個(gè)整數(shù)的整數(shù)次冪再取模。n例如，設(shè)公鑰為例如，設(shè)公鑰為(5,119)，私鑰為，私鑰為(77,119)，明，明文文m=19，則加密得密文，則加密得密文c為：為：nc=195 mod 119=2 476 099 mod 119=66n解密得明文解密得明文m為：為：nm=6677 mod 119=19n計(jì)算計(jì)算an算法的效率直接影響到算法的效率直接影響到RSA算法的性能。算法的性能。202

3、2-3-7算法設(shè)計(jì)與分析-蠻力法4n 蠻力法所依賴的基本技術(shù)蠻力法所依賴的基本技術(shù)掃描技術(shù)掃描技術(shù)n 關(guān)鍵關(guān)鍵依次處理所有元素依次處理所有元素 n 基本的掃描技術(shù)基本的掃描技術(shù)遍歷遍歷（1）集合的遍歷）集合的遍歷（2）線性表的遍歷）線性表的遍歷（3）樹的遍歷）樹的遍歷 （4）圖的遍歷）圖的遍歷 2022-3-7算法設(shè)計(jì)與分析-蠻力法5蠻力法也是一種重要的算法設(shè)計(jì)技術(shù)，原因如下：蠻力法也是一種重要的算法設(shè)計(jì)技術(shù)，原因如下： （1）理論上，蠻力法可以解決可計(jì)算領(lǐng)域的）理論上，蠻力法可以解決可計(jì)算領(lǐng)域的各種問題。各種問題。 （2）蠻力法經(jīng)常用來解決一些較小規(guī)模的問）蠻力法經(jīng)常用來解決一些較小規(guī)模的問

4、題。題。 （3）對于一些重要的問題（如：排序、查找）對于一些重要的問題（如：排序、查找）蠻力法可以產(chǎn)生一些合理的算法。蠻力法可以產(chǎn)生一些合理的算法。 （4）蠻力法可以作為某類問題時(shí)間性能的底）蠻力法可以作為某類問題時(shí)間性能的底限，來衡量同樣問題的更高效算法。限，來衡量同樣問題的更高效算法。 2022-3-7算法設(shè)計(jì)與分析-蠻力法6舉例：百元買百雞問題舉例：百元買百雞問題 已知公雞已知公雞5元一只，母雞元一只，母雞3元一只，小元一只，小雞雞1元三只，用元三只，用100元錢買元錢買100只雞，問公雞、只雞，問公雞、母雞、小雞各多少只？母雞、小雞各多少只？2022-3-7算法設(shè)計(jì)與分析-蠻力法73.

5、2 查找問題中的蠻力法查找問題中的蠻力法 3.2.1 順序查找順序查找 3.2.2 串匹配問題串匹配問題2022-3-7算法設(shè)計(jì)與分析-蠻力法8 順序查找從表的一端向另一端順序查找從表的一端向另一端逐個(gè)逐個(gè)將元素與給將元素與給定值進(jìn)行比較，若相等，則查找成功，給出該元素定值進(jìn)行比較，若相等，則查找成功，給出該元素在表中的位置；若整個(gè)表檢測完仍未找到與給定值在表中的位置；若整個(gè)表檢測完仍未找到與給定值相等的元素，則查找失敗，給出失敗信息。相等的元素，則查找失敗，給出失敗信息。3.2.1 順序查找順序查找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i

6、查找方向查找方向2022-3-7算法設(shè)計(jì)與分析-蠻力法9算法算法3.1順序查找順序查找 int SeqSearch1(int r , int n, int k) /數(shù)組r1 rn存放查找集合 i=n; while (i0 & ri!=k) i-; return i; C+描述算法算法3.1的的基本語句基本語句是是i0和和ri!=k，其執(zhí)行次數(shù)為，其執(zhí)行次數(shù)為:ninininiiiiinOninninncpbp1111)(1) 1(1) 1(1基本語句基本語句 ？其中其中pi是第是第i個(gè)元素的查找概率，而個(gè)元素的查找概率，而bi和和ci分別是分別是基本語句基本語句i0和和ri!=k的執(zhí)行

7、次數(shù)的執(zhí)行次數(shù)2022-3-7算法設(shè)計(jì)與分析-蠻力法10將將待查值待查值放在查找方向的放在查找方向的盡頭盡頭處，免去了在查找過處，免去了在查找過程中每一次比較后都要判斷查找位置是否程中每一次比較后都要判斷查找位置是否越界越界，從，從而提高了查找速度。而提高了查找速度。k 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i查找方向查找方向哨兵哨兵改進(jìn)的順序查找改進(jìn)的順序查找2022-3-7算法設(shè)計(jì)與分析-蠻力法11算法3.2改進(jìn)的順序查找 int SeqSearch2(int r , int n, int k) /數(shù)組數(shù)組r1 rn存放查找集合存放查找集

8、合 r0=k; i=n; while (ri!=k) i -; return i;C+描述算法算法3.2的的基本語句基本語句是是ri!=k，其執(zhí)行次數(shù)為，其執(zhí)行次數(shù)為: niniiinOninncp11)(21) 1(1數(shù)量級相同，數(shù)量級相同，系數(shù)相差一半系數(shù)相差一半2022-3-7算法設(shè)計(jì)與分析-蠻力法12 用蠻力法設(shè)計(jì)的算法，都可以對算法的用蠻力法設(shè)計(jì)的算法，都可以對算法的第一個(gè)版本進(jìn)行一定程度的改良，改進(jìn)其時(shí)第一個(gè)版本進(jìn)行一定程度的改良，改進(jìn)其時(shí)間性能，但只能減少系數(shù)，而數(shù)量級不會改間性能，但只能減少系數(shù)，而數(shù)量級不會改變。變。v 一般觀點(diǎn)：一般觀點(diǎn)：2022-3-7算法設(shè)計(jì)與分析-蠻力

9、法133.2.2 串匹配問題串匹配問題 （略）（略） 串匹配問題屬于易解問題。串匹配問題屬于易解問題。 串匹配問題的特征：串匹配問題的特征：（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的過程稱為的過程稱為串匹配串匹

10、配，也稱模式匹配。，也稱模式匹配。2022-3-7算法設(shè)計(jì)與分析-蠻力法143.3 排序問題中的蠻力法排序問題中的蠻力法 3.3.1 選擇排序選擇排序 3.3.2 起泡排序起泡排序排序：給定一個(gè)記錄序列排序：給定一個(gè)記錄序列(r(r1 1,r,r2 2, ,r,rn n) )，其相應(yīng)的，其相應(yīng)的關(guān)鍵字分別為關(guān)鍵字分別為(k(k1 1,k,k2 2, ,k,kn n) ) ，排序是將這些記錄，排序是將這些記錄排列成順序?yàn)榕帕谐身樞驗(yàn)?r(rs1s1,r,rs2s2, ,r,rsnsn) )的一個(gè)序列，使得相的一個(gè)序列，使得相應(yīng)的關(guān)鍵字滿足應(yīng)的關(guān)鍵字滿足k ks1s1 k ks2 s2 k ksn

11、sn( (升序或非降序升序或非降序) )或或 k ks1s1 k ks2 s2 k ksn sn ( (降序或非升序降序或非升序) ) 。2022-3-7算法設(shè)計(jì)與分析-蠻力法153.3.1 選擇排序選擇排序 選擇排序第選擇排序第i趟排序從第趟排序從第i個(gè)記錄開始掃描序列，個(gè)記錄開始掃描序列，在在n-i+1（1in-1）個(gè)記錄中找到關(guān)鍵碼最小的記）個(gè)記錄中找到關(guān)鍵碼最小的記錄，并和第錄，并和第i個(gè)記錄交換作為有序序列的第個(gè)記錄交換作為有序序列的第i個(gè)記錄。個(gè)記錄。 r1 r2 ri- -1 ri ri+1 rmin rn 有序區(qū)有序區(qū) 無序區(qū)無序區(qū) 已經(jīng)位于最終位置已經(jīng)位于最終位置 rmin為

12、無序區(qū)的最小記錄為無序區(qū)的最小記錄 交換交換2022-3-7算法設(shè)計(jì)與分析-蠻力法16算法算法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+) ) /在無序區(qū)中找最小記錄在無序區(qū)中找最小記錄 if ( (rjrindex) ) index=j; if ( (index!=i) ) ririndex; /若最小記錄不在最終位置則交換

13、若最小記錄不在最終位置則交換 C+描述 該算法的基本語句是內(nèi)層循環(huán)體中的比較語句該算法的基本語句是內(nèi)層循環(huán)體中的比較語句rjrindex，其執(zhí)行次數(shù)為：，其執(zhí)行次數(shù)為： 112111)(2) 1()(1nininijnOnnin2022-3-7算法設(shè)計(jì)與分析-蠻力法17起泡排序在掃描過程中兩兩比較相鄰記錄，如果反起泡排序在掃描過程中兩兩比較相鄰記錄，如果反序則交換，最終，最大記錄就被序則交換，最終，最大記錄就被“沉到沉到”了序列的了序列的最后一個(gè)位置，第二遍掃描將第二大記錄最后一個(gè)位置，第二遍掃描將第二大記錄“沉到沉到”了倒數(shù)第二個(gè)位置，重復(fù)上述操作，直到了倒數(shù)第二個(gè)位置，重復(fù)上述操作，直到n

14、-1 遍掃遍掃描后，整個(gè)序列就排好序了。描后，整個(gè)序列就排好序了。 解釋冒泡的含義解釋冒泡的含義3.3.2 起泡排序起泡排序 rj rj+1 ri+1 rn- -1 rn 無序區(qū)無序區(qū) 有序區(qū)有序區(qū) 1ji- -1 位于最終位置位于最終位置反序則交換反序則交換2022-3-7算法設(shè)計(jì)與分析-蠻力法18算法算法3.7起泡排序起泡排序 void BubbleSort( (int r , int n) ) /數(shù)組下標(biāo)從數(shù)組下標(biāo)從1 1開始開始 for (i=1; i=n- -1; i+) for (j=1; jrj+1) rjrj+1；/如果反序，則交換元素如果反序，則交換元素 C+描述 該算法的基

15、本語句是內(nèi)層循環(huán)體中的比較語該算法的基本語句是內(nèi)層循環(huán)體中的比較語句句rjrj+1，其執(zhí)行次數(shù)為：，其執(zhí)行次數(shù)為： 112111)(2) 1()(1niniinjnOnnin2022-3-7算法設(shè)計(jì)與分析-蠻力法19基于起泡排序的特點(diǎn)，可對上述算法進(jìn)行改進(jìn)：基于起泡排序的特點(diǎn)，可對上述算法進(jìn)行改進(jìn)：算法算法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)上一趟排序有記錄

16、交換才進(jìn)行本趟排序僅當(dāng)上一趟排序有記錄交換才進(jìn)行本趟排序 bound=exchange; exchange=0； for ( (j=1; jrj+1) ) rjrj+1； exchange=j； /記錄每一次發(fā)生記錄交換的位置記錄每一次發(fā)生記錄交換的位置 C+描述2022-3-7算法設(shè)計(jì)與分析-蠻力法20在在最好情況最好情況下，待排序記錄序列為正序，算下，待排序記錄序列為正序，算法只執(zhí)行一趟，進(jìn)行了法只執(zhí)行一趟，進(jìn)行了n- -1次關(guān)鍵碼的比較，次關(guān)鍵碼的比較，不需要移動記錄，時(shí)間復(fù)雜性為不需要移動記錄，時(shí)間復(fù)雜性為O( (n) )例：正序例：正序 1 2 3 4 5 6 7 8 9 10例：反

17、序例：反序 10 9 8 7 6 5 4 3 2 12022-3-7算法設(shè)計(jì)與分析-蠻力法21最壞情況：最壞情況：記錄的比較次數(shù)為記錄的比較次數(shù)為 關(guān)鍵碼的移動次數(shù)為關(guān)鍵碼的移動次數(shù)為因此，時(shí)間復(fù)雜性為因此，時(shí)間復(fù)雜性為O( (n2) )；2)1(11nninni）（2)1(3311nninni）（平均情況：平均情況：時(shí)間復(fù)雜性與最壞情況同數(shù)量級。時(shí)間復(fù)雜性與最壞情況同數(shù)量級。2022-3-7算法設(shè)計(jì)與分析-蠻力法223.4 3.4 組合問題中的蠻力法組合問題中的蠻力法 3.4.1 0/1背包問題背包問題3.4.2 任務(wù)分配問題任務(wù)分配問題補(bǔ)充補(bǔ)充 生成排列對象生成排列對象 3.4.4 要求生

18、成并依次考察問題域中的每一個(gè)要求生成并依次考察問題域中的每一個(gè)元素，從中選出滿足問題的約束的元素。元素，從中選出滿足問題的約束的元素。易產(chǎn)生組合爆炸現(xiàn)象。易產(chǎn)生組合爆炸現(xiàn)象。2022-3-7算法設(shè)計(jì)與分析-蠻力法233.4.1 0/1背包問題背包問題 0/1背包問題是給定背包問題是給定n個(gè)重量為個(gè)重量為w1, w2, ,wn、價(jià)值為價(jià)值為v1, v2, ,vn的物品和一個(gè)容量為的物品和一個(gè)容量為C的背包，的背包，求這些物品中的一個(gè)最有價(jià)值的子集，并且要能夠求這些物品中的一個(gè)最有價(jià)值的子集，并且要能夠裝到背包中。裝到背包中。 用蠻力法解決用蠻力法解決0/1背包問題，需要考慮給定背包問題，需要考慮

19、給定n個(gè)個(gè)物品集合的所有子集，找出所有可能的子集（總重物品集合的所有子集，找出所有可能的子集（總重量不超過背包容量的子集），計(jì)算每個(gè)子集的總價(jià)量不超過背包容量的子集），計(jì)算每個(gè)子集的總價(jià)值，然后在他們中找到價(jià)值最大的子集。值，然后在他們中找到價(jià)值最大的子集。2022-3-7算法設(shè)計(jì)與分析-蠻力法2410w1=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

20、 32312113,4965 43440121,2,314不可行不可行 54525131,2,415 61,21054141,3,416 71,311不可行不可行152,3,412不可行不可行不可行不可行不可行不可行不可行不可行不可行不可行2022-3-7算法設(shè)計(jì)與分析-蠻力法25結(jié)論結(jié)論: 對于一個(gè)具有對于一個(gè)具有n個(gè)元素的集合，其子集個(gè)元素的集合，其子集數(shù)量是數(shù)量是2n，所以，不論生成子集的算法效率，所以，不論生成子集的算法效率有多高，蠻力法都會導(dǎo)致一個(gè)有多高，蠻力法都會導(dǎo)致一個(gè)(2n)的算法。的算法。2022-3-7算法設(shè)計(jì)與分析-蠻力法263.4.2 任務(wù)分配問題任務(wù)分配問題 假設(shè)有假

21、設(shè)有n個(gè)任務(wù)需要分配給個(gè)任務(wù)需要分配給n個(gè)人執(zhí)行，每個(gè)人執(zhí)行，每個(gè)任務(wù)只分配給一個(gè)人，每個(gè)人只分配一個(gè)任個(gè)任務(wù)只分配給一個(gè)人，每個(gè)人只分配一個(gè)任務(wù)，且第務(wù)，且第j個(gè)任務(wù)分配給第個(gè)任務(wù)分配給第i個(gè)人的成本是個(gè)人的成本是Ci, j（1i , jn），任務(wù)分配問題要求找出總成本），任務(wù)分配問題要求找出總成本最小的分配方案。最小的分配方案。 2022-3-7算法設(shè)計(jì)與分析-蠻力法27 下面是一個(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

22、任務(wù)任務(wù)3人員人員1人員人員2人員人員3 任務(wù)分配問題任務(wù)分配問題就是在分配成本矩陣中的每一行就是在分配成本矩陣中的每一行選取一個(gè)元素，這些元素分別屬于不同的列，并且選取一個(gè)元素，這些元素分別屬于不同的列，并且元素之和最小。元素之和最小。2022-3-7算法設(shè)計(jì)與分析-蠻力法28 用一個(gè)用一個(gè)n元組元組(j1, j2, , jn)來描述任務(wù)分配問題的來描述任務(wù)分配問題的一個(gè)可能解，其中第一個(gè)可能解，其中第i個(gè)分量個(gè)分量ji（1in）表示在第）表示在第i行中選擇的列號，因此用蠻力法解決任務(wù)分配問題行中選擇的列號，因此用蠻力法解決任務(wù)分配問題要求生成整數(shù)要求生成整數(shù)1n的全排列，然后把成本矩陣中的

23、相的全排列，然后把成本矩陣中的相應(yīng)元素相加來求得每種分配方案的總成本，最后選應(yīng)元素相加來求得每種分配方案的總成本，最后選出具有最小和的方案。出具有最小和的方案。 序號序號分配方案分配方案 總成本總成本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=162022-3-7算法設(shè)計(jì)與分析-蠻力法29結(jié)論 由于任務(wù)分配問題需要考慮的排列數(shù)量是由于任務(wù)分配問題需要考慮的排列數(shù)量是n!，所以，除了該問題的一些規(guī)模非常小的實(shí)例，所以，除了該問題的一些規(guī)模非常小的實(shí)例，蠻力

24、法幾乎是不實(shí)用的。蠻力法幾乎是不實(shí)用的。 2022-3-7算法設(shè)計(jì)與分析-蠻力法30補(bǔ)充：補(bǔ)充： 生成排列對象生成排列對象 假設(shè)已經(jīng)生成了所有假設(shè)已經(jīng)生成了所有(n-1)!個(gè)排列，可以把個(gè)排列，可以把n插入到插入到n-1個(gè)元素的每一種排列中的個(gè)元素的每一種排列中的n個(gè)位置中去，來得到個(gè)位置中去，來得到問題規(guī)模為問題規(guī)模為n的所有排列。按照這種方式生成的所的所有排列。按照這種方式生成的所有排列都是獨(dú)一無二的，并且他們的總數(shù)應(yīng)該是有排列都是獨(dú)一無二的，并且他們的總數(shù)應(yīng)該是n(n-1)!=n!。開始開始 1插入插入2 12 21插入插入3 123 132 312 213 231 321 生成排列的過

25、程生成排列的過程2022-3-7算法設(shè)計(jì)與分析-蠻力法31算法算法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ù)量成正比。 2022-3-7算法設(shè)計(jì)與分析-蠻力法32補(bǔ)充：補(bǔ)充： 生成子集生成子集 n個(gè)元素的集合個(gè)元素的集合A=a1, a2, an的所有的所有2n個(gè)子個(gè)子集和長度為集和長度為n的所有的所有2n個(gè)比

26、特串之間的一一對應(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,a22022-3-7算法設(shè)計(jì)與分析-蠻力法33生成生成n個(gè)元素子集的算法如下：個(gè)元素子集的算法如下： 算法算法3.10生成子集生成子集 1初始化一個(gè)長度為初始化一個(gè)長度為n的比特串

27、的比特串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ù)量成正比。 2022-3-7算法設(shè)計(jì)與分析-蠻力法343.5 圖問題中的蠻力法圖問題中的蠻力法 3.5.1 哈密頓回路問題哈密頓回路問題 3.5.2 TSP問題問題2022-3-7算法設(shè)計(jì)與分析-蠻力法353.5.1 哈密頓回路問題哈密頓回路問題 著名的愛爾蘭數(shù)學(xué)家哈密頓（著名的愛爾蘭數(shù)學(xué)家哈密頓（William Ha

28、milton，18051865）提出了著名的周游世界問題。他用正十二）提出了著名的周游世界問題。他用正十二面體的面體的20個(gè)頂點(diǎn)代表個(gè)頂點(diǎn)代表20個(gè)城市，要求從一個(gè)城市出發(fā)，個(gè)城市，要求從一個(gè)城市出發(fā)，經(jīng)過每個(gè)城市恰好一次，然后回到出發(fā)城市。經(jīng)過每個(gè)城市恰好一次，然后回到出發(fā)城市。1983141202131545679101112161718正十二面體的展開圖，正十二面體的展開圖，按照圖中的頂點(diǎn)編號所按照圖中的頂點(diǎn)編號所構(gòu)成的回路，就是哈密構(gòu)成的回路，就是哈密頓回路的一個(gè)解。頓回路的一個(gè)解。 2022-3-7算法設(shè)計(jì)與分析-蠻力法36 使用蠻力法尋找哈密頓回路的基本思想是：對于使用蠻力法尋找哈

29、密頓回路的基本思想是：對于給定的無向圖給定的無向圖G=(V, E)，首先生成圖中所有頂點(diǎn)的，首先生成圖中所有頂點(diǎn)的排列對象排列對象(vi1, vi2, , vin)，然后依次考察每個(gè)排列對，然后依次考察每個(gè)排列對象是否滿足以下兩個(gè)條件：象是否滿足以下兩個(gè)條件：（1）相鄰頂點(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è)條件的回路就是哈密頓回路。目前沒有有效的算法求解哈密頓回路問題目前沒有有效的算法求解哈密頓

30、回路問題2022-3-7算法設(shè)計(jì)與分析-蠻力法3712453路徑路徑(vij, vij+1)E1234512345（是）（是）12354123 54 （否）（否）1243512 43 5 （否）（否）否否否否1245312 45 3 （否）（否）12534125 34 （否）（否）1254312543（是）（是）(vin, vi1)E是是是是是是是是(a) 一個(gè)無向圖一個(gè)無向圖 顯然，蠻力法求解哈密頓回路在最壞情況下需要考察顯然，蠻力法求解哈密頓回路在最壞情況下需要考察所有頂點(diǎn)的排列對象，其時(shí)間復(fù)雜性為所有頂點(diǎn)的排列對象，其時(shí)間復(fù)雜性為O(n!)。 例:蠻力法求解哈密頓回路(b) 哈密頓回路求

31、解過程哈密頓回路求解過程2022-3-7算法設(shè)計(jì)與分析-蠻力法383.5.2 TSP問題問題 TSP問題是指旅行家要旅行問題是指旅行家要旅行n個(gè)城市然后回到個(gè)城市然后回到出發(fā)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并出發(fā)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。該問題又稱為貨郎擔(dān)問題、要求所走的路程最短。該問題又稱為貨郎擔(dān)問題、郵遞員問題、售貨員問題，是圖問題中最廣為人郵遞員問題、售貨員問題，是圖問題中最廣為人知的問題。知的問題。 用蠻力法解決用蠻力法解決TSPTSP問題，可以找出所有可能問題，可以找出所有可能的旅行路線，從中選取路徑長度最短的簡單回路。的旅行路線，從中選取路徑長度

32、最短的簡單回路。 2022-3-7算法設(shè)計(jì)與分析-蠻力法398abdc23571序號序號路徑路徑路徑長度路徑長度是否最短是否最短 1abcda 18 否否 2abdca 11 是是 3acbda 23 否否 4acdba 11 是是 5adbca 23 否否 6adcba 18 否否 若有若有n n個(gè)城市，則可能的解有個(gè)城市，則可能的解有( (n- -1) )!/ /2個(gè)。隨著個(gè)。隨著n的增長，的增長，TSP問題的可能解也在迅速地增長。問題的可能解也在迅速地增長。2022-3-7算法設(shè)計(jì)與分析-蠻力法40l 一個(gè)一個(gè)10城市的城市的TSP問題有大約有問題有大約有180,000個(gè)可能解。個(gè)可能解

33、。l 一個(gè)一個(gè)20城市的城市的TSP問題有大約有問題有大約有 60,000,000,000,000,000個(gè)可能解。個(gè)可能解。l 一個(gè)一個(gè)50城市的城市的TSP問題有大約問題有大約1062個(gè)可能解，而一個(gè)個(gè)可能解，而一個(gè)行星上也只有行星上也只有1021升水。升水。 例如：例如：u用蠻力法求解用蠻力法求解TSP問題，只能解決問題問題，只能解決問題規(guī)模很小的實(shí)例。規(guī)模很小的實(shí)例。2022-3-7算法設(shè)計(jì)與分析-蠻力法413.6 幾何問題中的蠻力法幾何問題中的蠻力法 3.6.1 最近對問題最近對問題3.6.2 凸包問題凸包問題2022-3-7算法設(shè)計(jì)與分析-蠻力法423.6.1 最近對問題最近對問題 最近對問題要求找出一個(gè)包含最近對問題要求找出一個(gè)包含n個(gè)點(diǎn)的集合個(gè)點(diǎn)的集合中距離最近的兩個(gè)點(diǎn)。中距離最近的兩個(gè)點(diǎn)。 22)()(jijiyyxxd 考慮二維情況，并假設(shè)兩個(gè)點(diǎn)考慮二維情況，并假設(shè)兩個(gè)點(diǎn)Pi=(xi, yi)和和Pj=(xj, yj)之間的距離是標(biāo)準(zhǔn)的歐幾里德距離：之間的距離是標(biāo)準(zhǔn)的歐幾里德距離：2022-3-7算法設(shè)計(jì)與分析-蠻力法43分別計(jì)算每一對點(diǎn)之間的距離，然后找分別計(jì)算每一對點(diǎn)之間的距離，然后找出距離最小的那一對，為了避免對同一出距離最小的那一對，為了避免對同一對點(diǎn)計(jì)算兩次距離，只考慮對點(diǎn)計(jì)算兩次距離，只考慮ij的那些的那些點(diǎn)對點(diǎn)對(Pi, Pj