計(jì)算理論與算法分析設(shè)計(jì)總復(fù)習(xí)2016年上

1、計(jì)算理論與算法總復(fù)習(xí)2022-6-92 of 158成績計(jì)算方法n平時(shí)成績平時(shí)成績 30%n上機(jī)題目n平時(shí)作業(yè)n平時(shí)考勤n期末成績期末成績 70%n算法題中，嚴(yán)格按照題目要求給出算法代碼、算法思想、測(cè)試用例的求解過程。n如果題目沒有明確要求給出算法代碼，那么不需要給出。2022-6-93 of 158考題類型n判斷題：判斷題：10分分. 5個(gè)個(gè)n填空題：填空題：30分分. 10個(gè)個(gè)n大題：大題：60分分. 5道道n其中算法：其中算法：60分，計(jì)算理論：分，計(jì)算理論：40分分CH1 算法概述2022-6-95 of 158n算法的五個(gè)特征算法的五個(gè)特征1）有窮性）有窮性 2）確定性）確定性3）輸

2、入）輸入 4）輸出）輸出 5）可行性）可行性n算法的定義算法的定義:Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the outp

3、ut. 2022-6-96 of 158O、o、第一種理解方法設(shè)設(shè)f和和g是定義域?yàn)樽匀粩?shù)是定義域?yàn)樽匀粩?shù)N上的函數(shù)上的函數(shù)nf(n)=O(g(n).（上界）（上界） 若存在正數(shù)若存在正數(shù)c和和n0使得對(duì)一切使得對(duì)一切n n0 有有 0 f(n) cg(n)nf(n) = (g(n).（下界）（下界） 若存在正數(shù)若存在正數(shù)c和和n0使得對(duì)一切使得對(duì)一切n n0有有 0 cg(n) f(n)nf(n) = (g(n) f(n) =O(g(n) 且且 f(n) = (g(n)2022-6-97 of 158n標(biāo)準(zhǔn)復(fù)雜性函數(shù)的比較標(biāo)準(zhǔn)復(fù)雜性函數(shù)的比較O(1)O(logn)O(n)O(nlogn)O(

4、n2)O(n3)O(2n)O(n!)O(nn)多項(xiàng)式時(shí)間階多項(xiàng)式時(shí)間階指數(shù)時(shí)間階指數(shù)時(shí)間階一個(gè)算法的時(shí)間復(fù)雜性如果是一個(gè)算法的時(shí)間復(fù)雜性如果是O(nk)(k為有為有理數(shù)），則稱此算法需要多項(xiàng)式時(shí)間。理數(shù)），則稱此算法需要多項(xiàng)式時(shí)間。有效算法有效算法以多項(xiàng)式時(shí)間為限界的算法稱為有效算法以多項(xiàng)式時(shí)間為限界的算法稱為有效算法2022-6-98 of 158n標(biāo)準(zhǔn)復(fù)雜性函數(shù)的比較標(biāo)準(zhǔn)復(fù)雜性函數(shù)的比較O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)O(nn)注意：注意：1）不能劃等號(hào)）不能劃等號(hào) 2）以下若無特殊聲明，）以下若無特殊聲明，log是以是以2為底的對(duì)數(shù)為

5、底的對(duì)數(shù) 3）上式只有在）上式只有在n較大的時(shí)候成立較大的時(shí)候成立O(1)的含義？的含義？計(jì)算時(shí)間由一個(gè)常數(shù)（零次多項(xiàng)式）來限界計(jì)算時(shí)間由一個(gè)常數(shù)（零次多項(xiàng)式）來限界多項(xiàng)式時(shí)間階多項(xiàng)式時(shí)間階指數(shù)時(shí)間階指數(shù)時(shí)間階2022-6-99 of 158例n例：算法例：算法A1,A2的時(shí)間復(fù)雜性分別是的時(shí)間復(fù)雜性分別是n,2n,設(shè)設(shè)100s是一個(gè)單位時(shí)間，求是一個(gè)單位時(shí)間，求A1,A2在在1s內(nèi)能處理的問題規(guī)模。內(nèi)能處理的問題規(guī)模。n已知已知lg2=0.301T(n) = nT(n)*10- -4 = 1即即 n*10- -4 = 1所以所以 n = 104 2022-6-910 of 158例n假設(shè)某算

6、法在輸入規(guī)模為n的時(shí)間復(fù)雜性為T(n)=3*2n。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為t秒?，F(xiàn)在另一計(jì)算機(jī)，其運(yùn)行速度為第一臺(tái)的64倍，那么在這臺(tái)新機(jī)器上用同一算法在t秒內(nèi)能解輸入規(guī)模為多大的問題？2022-6-911 of 158例解：設(shè)新機(jī)器用同一算法內(nèi)能解輸入規(guī)模解：設(shè)新機(jī)器用同一算法內(nèi)能解輸入規(guī)模為為n1的問題，那么有的問題，那么有3 *2n=3 * 2n1 /64，解得解得n1=n+6.CH2 分治法 2022-6-913 of 158例例1 用分治法求用分治法求n個(gè)元素集個(gè)元素集合合S中的最大、最小元素。中的最大、最小元素。假設(shè)假設(shè)n=2m。要求每次平分成。要求每次平分成2個(gè)子集

7、。個(gè)子集。void maxmin(int A,int &e_max,int &e_min,int low,int high) 2. 3. int mid,x1,y1,x2,y2; 4. if (high-low Alow) 6. e_max = Ahigh;7. e_min = Alow;8. 9. else 10. e_max = Alow;11. e_min = Ahigh; 12. 13.2022-6-914 of 15814. else 15. mid = (low + high) / 2;16. maxmin(A,&x1,&y1,low,mid);17. maxmin(A,&x2,&

8、y2,mid+1,high);18. e_max = max(x1,x2);19. e_min = min(y1,y2);20. 21. T(n)=1n=2n22T(n/2)+22022-6-915 of 158 用分治法求用分治法求n個(gè)元素集合個(gè)元素集合S中的最大、最中的最大、最小元素。小元素。寫出算法，并分析時(shí)間復(fù)雜寫出算法，并分析時(shí)間復(fù)雜性（比較次數(shù)）。性（比較次數(shù)）。 假設(shè)假設(shè)n=3m。要求每次平分成。要求每次平分成3個(gè)子集。個(gè)子集。T(n)=n=3n33T(n/3)+43T(n)=5n/3- -2平分成平分成2個(gè)子集個(gè)子集 T(n) = 3n/2- -22022-6-916 of 1

9、58歸并排序（Merge Sort)void MergeSort(int A, int B, int l, int h)if(l = h)return;int m = (l+h)/2;MergeSort(A, B, l, m);MergeSort(A, B, m+1, h);Merge(A, B, l, m, h); T(n)=n=2n22T(n/2) +cn12022-6-917 of 158主定理：其中主定理：其中n= ck, k為某個(gè)非負(fù)常數(shù)為某個(gè)非負(fù)常數(shù)T(n) =n=2n2aT(n/c) +bnxdT(n) =acx)(log acnT(n)=n=2n22T(n/2) +cn1n歸并

10、排序歸并排序 (nlogn)T(n) =1n=2n22T(n/2) +22022-6-918 of 158快排序-劃分過程2022-6-919 of 158大整數(shù)乘法由由X=A2n/2+B, Y=C2n/2+D 則則XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+BC) 2n/2+BD = AC2n+(A-B)(D-C)+AC+BD)2n/2+BD計(jì)算成本：計(jì)算成本：3次次n/2位乘法，位乘法，6次不超過次不超過n位加減法，位加減法，2次移位，所有加法和移位共計(jì)次移位，所有加法和移位共計(jì)O(n)次運(yùn)算。由此可得，次運(yùn)算。由此可得，T(n)=O(nlog3)=O(n1.59)這種思

11、想同樣可以用于十進(jìn)制數(shù)的乘法中。這種思想同樣可以用于十進(jìn)制數(shù)的乘法中。2022-6-920 of 158求第k小的元素long Select(k,S) if (|S| 38) 將將S中的元素排成非遞減序；中的元素排成非遞減序； return (S中的第中的第k小元素小元素); else 將將S中的元素劃分成長度等于中的元素劃分成長度等于5的的 |S|/5 個(gè)子序列；個(gè)子序列；2022-6-921 of 158 由各子序列的中值元素組成非遞減序列由各子序列的中值元素組成非遞減序列M； m Select( |M|/2 ，M); 按按m將將S中的元素劃分成小于中的元素劃分成小于m、等于、等于 m和大

12、于和大于m的三個(gè)子序列的三個(gè)子序列S1，S2和和S3; if (|S1|k) return(Select(k,S1); else if (|S1| +|S2|k) return(m); else return(Select(k- |S1| -|S2|, S3); 2022-6-922 of 158線性時(shí)間選擇問題:l定理：算法定理：算法Select 在在O(n)時(shí)間內(nèi)找時(shí)間內(nèi)找出出n個(gè)元素序列中的第個(gè)元素序列中的第k小的元素。小的元素。 c n 38 T( n/5 )+T( 3n/4 )+cn n38T(n) T(n) =20cnl用線性時(shí)間從n個(gè)元素中選擇出第k個(gè)小的元素2022-6-923

13、 of 158線性時(shí)間選擇: 中位數(shù)應(yīng)用n中位數(shù)原理中位數(shù)原理X軸上有軸上有n個(gè)點(diǎn)，由左至右依次排列為個(gè)點(diǎn)，由左至右依次排列為找一個(gè)點(diǎn)找一個(gè)點(diǎn)xp(不一定是不一定是n個(gè)點(diǎn)之一個(gè)點(diǎn)之一)，使，使xp到各到各點(diǎn)距離和最小，解為：點(diǎn)距離和最小，解為：x1x2xpxnx為偶數(shù)時(shí)當(dāng)為奇數(shù)時(shí)當(dāng)nxxnxxnnnp2/ )(12/2/2/ )1(即解為中位數(shù)或中位數(shù)的平均值。即解為中位數(shù)或中位數(shù)的平均值。2022-6-924 of 158【例】殘缺棋盤殘缺棋盤是一個(gè)有2k2k （k1）個(gè)方格的棋盤，其中恰有一個(gè)方格殘缺。圖中給出k=1時(shí)各種可能的殘缺棋盤，其中殘缺的方格用陰影表示。 稱作“三格板”，殘缺棋盤

14、問題就是要用這四種三格板覆蓋更大的殘缺棋盤。號(hào)號(hào) 號(hào)號(hào) 號(hào)號(hào) 號(hào)號(hào)CH3 動(dòng)歸 2022-6-926 of 158方法概述: 基本思想 n動(dòng)態(tài)規(guī)劃的思想實(shí)質(zhì)是動(dòng)態(tài)規(guī)劃的思想實(shí)質(zhì)是分治思想和和解決冗余。 n與分治法類似的是，將原問題分解成若干個(gè)子與分治法類似的是，將原問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解問題，先求解子問題，然后從這些子問題的解得到原問題的解。得到原問題的解。n與分治法不同的是，經(jīng)分解的子問題往往不是與分治法不同的是，經(jīng)分解的子問題往往不是互相獨(dú)立的。若用分治法來解，有些共同部分互相獨(dú)立的。若用分治法來解，有些共同部分（子問題或子子問題）被重復(fù)計(jì)算了很多次。（

15、子問題或子子問題）被重復(fù)計(jì)算了很多次。2022-6-927 of 158方法概述: 適用條件 動(dòng)態(tài)規(guī)劃法的有效性依賴于問題本身所具有的動(dòng)態(tài)規(guī)劃法的有效性依賴于問題本身所具有的兩個(gè)重要性質(zhì)兩個(gè)重要性質(zhì)n最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問題：當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。的最優(yōu)解時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。n重疊子問題重疊子問題：在用遞歸算法自頂向下解問題時(shí)，：在用遞歸算法自頂向下解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是

16、利用了這種子問題的重疊性質(zhì)，對(duì)每一個(gè)子問題只解這種子問題的重疊性質(zhì)，對(duì)每一個(gè)子問題只解一次，而后將其解保存在一個(gè)表格中，在以后一次，而后將其解保存在一個(gè)表格中，在以后盡可能多地利用這些子問題的解。盡可能多地利用這些子問題的解。自底向上的動(dòng)規(guī)與備忘錄區(qū)別自底向上的動(dòng)規(guī)自底向上的動(dòng)規(guī)每個(gè)子問題至少求解一次每個(gè)子問題至少求解一次.備忘錄備忘錄某些子問題根本沒有必要求解某些子問題根本沒有必要求解.2022-6-929 of 158矩陣鏈乘法矩陣鏈乘問題滿足最優(yōu)性原理 記Ai:j為AiAi+1Aj鏈乘的一個(gè)最優(yōu)括號(hào)方案，設(shè)Ai:j的最優(yōu)次序中含有二個(gè)子鏈Ai:k和Ak+1:n，則Ai:k和Ak+1:n也

17、是最優(yōu)的。（反證可得）2022-6-930 of 158l遞歸求解最優(yōu)解的值 記mij為計(jì)算Ai:j的最少乘法數(shù)，則原問題的最優(yōu)值為 m1njipppjkmkimminjijimjkijki110(AiAi+1Ak)pi-1pk(Ak+1Ak+2Aj)pkpj2022-6-931 of 158見習(xí)題答案見習(xí)題答案2022-6-932 of 1580-1背包問題0 0 0 00 pi1(j wi) pi1(j)0 pi(j)0 目標(biāo)目標(biāo) 0i 1i n 0 j wi j M2022-6-933 of 158設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,zk ，

18、則(1)若xm=yn，則zk=xm=yn， 且z1,z2, zk-1是否為x1,x2,xm-1和y1,y2, yn-1的最長公共子序列。(2)若xmyn且zkxm， 則Z是x1,x2,xm-1和Y的最長公共子序列(3)若xmyn且zkyn， 則Z是X和y1,y2, yn-1的最長公共子序列2022-6-934 of 158由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用cij記錄序列和的最長公共子序列的長度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長公共子序列。故此時(shí)Cij=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)

19、系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110最長遞增子序列最長遞增子序列(LIS) 輸入輸入: 實(shí)數(shù)序列實(shí)數(shù)序列(x1,x2,xn) 輸出輸出: xi1 xi2 xik, 其中其中k最大且最大且i1 i2 ik. 樣例樣例: ( 2,8,9,4,6,1,3,7,5,10 ) : ( 2,4,6,7,10 ) O(n2)算法算法 O(nlogn)算法算法CH4 貪心法2022-6-937 of 158部分(或者小數(shù))背包問題 已知一個(gè)容量大小為已知一個(gè)容量大小為M重量的背包和重量的背包和n種種物品，物品物品，物品i的重量為的重量為wi

20、,假定物品假定物品i的一部的一部分分xi放入背包會(huì)得到放入背包會(huì)得到vixi這么大的收益，這么大的收益，這里，這里，0 xi1，vi0。采用怎樣的裝包方采用怎樣的裝包方法才會(huì)使裝入背包的物品總效益最大？法才會(huì)使裝入背包的物品總效益最大？例：考慮以下情況下的背包問題例：考慮以下情況下的背包問題n=3, M=20 , (v1, v2, v3)=(25,24,15)(w1 , w2 , w3)=(18,15,10)2022-6-938 of 158n=3, M=20 , (v1, v2, v3) =(25,24,15)(w1 , w2 , w3)=(18,15,10)n按按vi/wi的非增次序?qū)⑽锲?/p>

21、依次放入背的非增次序?qū)⑽锲芬来畏湃氡嘲?(x1,x2,x3) wixi vixi(0,1,1/2)2031.52022-6-939 of 158活動(dòng)安排: 問題描述有有n個(gè)活動(dòng)集個(gè)活動(dòng)集E=1,2,n使用同一資使用同一資源，而同一時(shí)間內(nèi)同一資源只能由一源，而同一時(shí)間內(nèi)同一資源只能由一個(gè)活動(dòng)使用。每個(gè)活動(dòng)的使用時(shí)間為個(gè)活動(dòng)使用。每個(gè)活動(dòng)的使用時(shí)間為si, fi) i=1,n，si為開始時(shí)間，為開始時(shí)間，fi為為結(jié)束時(shí)間，若結(jié)束時(shí)間，若si, fi) 與與sj, fj)不相交不相交稱活動(dòng)稱活動(dòng)i和活動(dòng)和活動(dòng)j是相容的。是相容的。問題：選出最大的相容活動(dòng)子集合。問題：選出最大的相容活動(dòng)子集合。20

22、22-6-940 of 158l貪貪 心心 策策 略略 將各活動(dòng)按結(jié)束時(shí)將各活動(dòng)按結(jié)束時(shí)間排序間排序f1f2fn，先選出活動(dòng)，先選出活動(dòng)1，然后按活動(dòng)編好從小到大的次序，然后按活動(dòng)編好從小到大的次序依次選擇與當(dāng)前活動(dòng)相容的活動(dòng)。依次選擇與當(dāng)前活動(dòng)相容的活動(dòng)。2022-6-941 of 158活動(dòng)安排: 計(jì)算示例11 11個(gè)活動(dòng)已按結(jié)束時(shí)間排序，用貪心算法求解：個(gè)活動(dòng)已按結(jié)束時(shí)間排序，用貪心算法求解： i 1 2 3 4 5 6 7 8 9 10 11start_timei 1 3 0 5 3 5 6 8 8 2 12finish_timei 4 5 6 7 8 9 10 11 12 13 14

23、01234567891011121314time a1a2a3a4a5a6a7a8a9a10a11相容活動(dòng)：相容活動(dòng)：a3, a9, a11, a1,a4,a8,a11, a2,a4,a9,a1101234567891011121314timea1a2a3a4a5a6a7a8a9a10a112022-6-942 of 158最優(yōu)裝載nixwcxwtsxmaxniwciiniiiniii,.,2 , 11 , 00. .,.,2 , 1,11問題的形式化定義：上輪船。盡可能多的集裝箱裝況下，裝載體積不受限制的情在）（集裝箱重量為輪船載重為2022-6-943 of 158假設(shè)假設(shè)n =8, w1

24、, . ,w8=100,200,50,90,150,50,20,80, c=400。從剩下的貨箱中，選擇重量最小的貨箱。從剩下的貨箱中，選擇重量最小的貨箱。2022-6-944 of 158排序之車間作業(yè)計(jì)劃模型一臺(tái)機(jī)器、一臺(tái)機(jī)器、n個(gè)零件的排序個(gè)零件的排序目的：使得各加工零件在車間里停留的平均目的：使得各加工零件在車間里停留的平均時(shí)間最短。時(shí)間最短。零件零件加工時(shí)間加工時(shí)間11.822.030.540.951.361.5最短：最短：3, 4, 5, 6, 1, 2(0.5+1.4+2.7+4.2+6+8)/6=3.8最短路問題最短路問題 輸入輸入: 帶權(quán)有向圖或無向圖帶權(quán)有向圖或無向圖 G

25、= (V,E,w), 權(quán)代表距離權(quán)代表距離 輸出輸出: 節(jié)點(diǎn)之間的最短距離節(jié)點(diǎn)之間的最短距離(路徑路徑) 例例: 找下圖中找下圖中V1到到V2的最短距離的最短距離, 最短路徑最短路徑 OSP: 一條最短路徑一條最短路徑, 其任意子段都是最短路徑其任意子段都是最短路徑 全點(diǎn)對(duì)全點(diǎn)對(duì)(all-pair)最短路最短路,Floyd-Warshall,O(|V|3), 單源單源(single source)最短路最短路, Dijkstra, O(|E|log|V|), 帶負(fù)權(quán)帶負(fù)權(quán), Bellman-Ford, O(|V|E|) (u,v): u,v之間最短路徑的距離之間最短路徑的距離 V1V5V4V2

26、V3V610101002050205030510最小生成樹最小生成樹(minimum spanning tree) 無向連通帶權(quán)圖無向連通帶權(quán)圖G=(V,E,w). G的的生成樹生成樹是是G的的包含所有頂點(diǎn)的一顆子包含所有頂點(diǎn)的一顆子樹樹 若若G的生成樹的生成樹T在所有在所有G的生成樹中各邊權(quán)總和最小的生成樹中各邊權(quán)總和最小, 則則T稱為稱為G的最小生成樹的最小生成樹(MST) 144187125818410909461121234212351464337139180218642704621740849867MIAPVDJFKBWIDFWLAXSFOORDBOS1441871258184109

27、09461121234212351464337139180218642704621740849867MIAPVDJFKBWIDFWLAXSFOORDBOSPrim算法算法O(|V|2), O(|E|log|V|) 輸入輸入: G=(V,E,w)無向連通無向連通; 輸出輸出: G的的MST 維護(hù)維護(hù)S V, 初始任取初始任取V中一點(diǎn)中一點(diǎn)r 當(dāng)當(dāng)S!=V, 取取S到到V-S的最小權(quán)邊的最小權(quán)邊(u,v), 將將v加入加入S. keyu記記u到到S的最小距離的最小距離, Gu記記u與與S最小距離對(duì)應(yīng)點(diǎn)最小距離對(duì)應(yīng)點(diǎn) 1. 初始初始Gu=NIL, keyr=0, 其它其它keyu=INF, Q=V,

28、 S空空 2. 當(dāng)當(dāng)Q非空非空 3. 取出取出Q中中u使得使得keyu最小最小, 加入加入S 4. 對(duì)對(duì)u的每個(gè)鄰居的每個(gè)鄰居v, 5. 若若 v Q 且且 wu,v ranky2 則則 py=x3 否則否則 px=y4 若若 rankx=ranky5 則則 ranky=ranky+1 Find(x)1 若若 x px, 則則2 px = Find(px) 3 返回返回 px 路徑壓縮路徑壓縮(pc)技術(shù)技術(shù) px: x的父親的父親; rankx: x的階的階; Find(x): 找找x的根的根 n個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn), m次操作次操作. 不計(jì)不計(jì)pc: O(mlogn); 計(jì)計(jì)pc: O(m (n)

29、 樹根階樹根階r 節(jié)點(diǎn)數(shù)節(jié)點(diǎn)數(shù) 2r. 加入并查集結(jié)構(gòu)的加入并查集結(jié)構(gòu)的Kruskal算法算法1. A為空為空, Q=E按邊權(quán)升序排列按邊權(quán)升序排列, 每個(gè)點(diǎn)是一顆樹每個(gè)點(diǎn)是一顆樹 2. 當(dāng)當(dāng)Q非空非空 3. 順序取順序取Q中邊中邊(u,v) 4. 若若u,v在不同樹中在不同樹中, 則添則添(u,v)到到A, 合并合并u,v所在樹所在樹, 5. 輸出輸出A 1. A為空為空, Q=E按邊權(quán)升序排列按邊權(quán)升序排列, x Make(x) 2. 當(dāng)當(dāng)Q非空非空 3. 順序取順序取Q中邊中邊(u,v) 4. 若若Find(u) Find(v), 則添則添(u,v)到到A, Union(u,v), 5.

30、 輸出輸出A 2022-6-950CH5 回溯法 2022-6-951 of 1582022-6-951 of 158子集樹與排列樹遍歷子集樹需O(2n)計(jì)算時(shí)間 void backtrack (int t) if (tn) output(x); else for (int i=0;in) output(x); else for (int i=t;i n) / 到達(dá)葉結(jié)點(diǎn) /更新最優(yōu)解bestx,bestw;return; if(cwbestw) for(j=1; j=n; j+) bestxj=xj; bestw = cw; return; r -= wi; if (cw + wi best

31、w) xi = 0; / 搜索右子樹 backtrack(i + 1); r += wi; 2022-6-960 of 158給定無向圖G=(V，E)。如果UV，且對(duì)任意u，vU有(u，v)E，則稱U是G的完全子圖。G的完全子圖U是G的團(tuán)。G的最大團(tuán)是指G中所含頂點(diǎn)數(shù)最多的團(tuán)。如果UV且對(duì)任意u，vU有(u，v)E，則稱U是G的空子圖。G的空子圖U是G的獨(dú)立集當(dāng)且僅當(dāng)U不包含在G的更大的空子圖中。G的最大獨(dú)立集是G中所含頂點(diǎn)數(shù)最多的獨(dú)立集。對(duì)于任一無向圖G=(V，E)其補(bǔ)圖G=(V1，E1)定義為：V1=V，且(u，v)E1當(dāng)且僅當(dāng)(u，v)E。U U是是G G的最大團(tuán)當(dāng)且僅當(dāng)?shù)淖畲髨F(tuán)當(dāng)且僅當(dāng)

32、U U是是G G的最大獨(dú)立集。的最大獨(dú)立集。12453124532022-6-961 of 158解空間：子集樹可行性約束函數(shù)：頂點(diǎn)i到已選入的頂點(diǎn)集中每一個(gè)頂點(diǎn)都有邊相連。 上界函數(shù)：有足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹中找到更大的團(tuán)。 private static void backtrack(int i) if (i n) / 到達(dá)葉結(jié)點(diǎn) for (int j = 1; j = n; j+) bestxj = xj; bestn = cn; return; / 檢查頂點(diǎn) i 與當(dāng)前團(tuán)的連接 boolean ok = true; for (int j = 1; j bestn) /

33、進(jìn)入右子樹 xi = 0; backtrack(i + 1); 124532022-6-962 of 1582022-6-962 of 158子集和問題n問題問題n給定由n個(gè)不同正數(shù)組成的集合W=wi，和正數(shù)M，求W中所有和等于M的子集的集合；n例如n = 6, M = 30, W=10, 13, 5, 18, 12, 152022-6-963 of 1582022-6-963 of 158子集和問題n按照回溯法思想，從狀態(tài)樹的根結(jié)點(diǎn)按照回溯法思想，從狀態(tài)樹的根結(jié)點(diǎn)出發(fā)，做深度優(yōu)先搜索；出發(fā)，做深度優(yōu)先搜索；n當(dāng)在某一狀態(tài)當(dāng)在某一狀態(tài)A下，依次嘗試加入和下，依次嘗試加入和不加入正數(shù)不加入正數(shù)w

34、i，若，若A+wiM，則可，則可停止對(duì)該結(jié)點(diǎn)的搜索；若停止對(duì)該結(jié)點(diǎn)的搜索；若A+ (wiwn)M，則也可停止對(duì)該結(jié)點(diǎn)，則也可停止對(duì)該結(jié)點(diǎn)的搜索；的搜索；2022-6-964 of 1582022-6-964 of 1580/1背包問題背包問題Mwwximkkiikii110Mwwwxmkimkkiikii110且且 mkmkimkkiiikiiimkkiiikiiwpwxwxMpxpx/)(11101102022-6-965 of 1582022-6-965 of 158有載重量有載重量M50的背包，物體重量分別為的背包，物體重量分別為5, 15, 25, 27,30，物體價(jià)值分別為，物體價(jià)值

35、分別為12,30,44,46,50。求最優(yōu)裝入背包的物體及價(jià)值。求最優(yōu)裝入背包的物體及價(jià)值。 2022-6-966 of 1582022-6-966 of 158回溯過程的效率用回溯法去處理一實(shí)例所要生用回溯法去處理一實(shí)例所要生成的結(jié)點(diǎn)數(shù)，一般是采用在狀成的結(jié)點(diǎn)數(shù)，一般是采用在狀態(tài)空間樹中生成一條隨機(jī)路徑態(tài)空間樹中生成一條隨機(jī)路徑的方法估計(jì)。的方法估計(jì)。2022-6-967CH6 分支限界法 2022-6-968 of 1582022-6-968 of 158方法概述: 與回溯法的區(qū)別n求解目標(biāo)不同求解目標(biāo)不同 ： 一般而言，回溯法的求解目標(biāo)是找出解空間樹一般而言，回溯法的求解目標(biāo)是找出解空間

36、樹中滿足約束條件的所有解，而分支限界法的求解中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解；目標(biāo)則是找出滿足約束條件的一個(gè)解； n搜索方法不同：搜索方法不同： 回溯算法使用深度優(yōu)先方法搜索，而分枝限界回溯算法使用深度優(yōu)先方法搜索，而分枝限界一般用寬度優(yōu)先或最小耗費(fèi)方法來搜索；一般用寬度優(yōu)先或最小耗費(fèi)方法來搜索； 2022-6-969 of 1582022-6-969 of 158方法概述: 與回溯法的區(qū)別n對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同：對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同： 分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)

37、展結(jié)點(diǎn)，就一次為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)；性產(chǎn)生其所有兒子結(jié)點(diǎn)；n存儲(chǔ)空間的要求不同：存儲(chǔ)空間的要求不同： 相對(duì)而言，分枝限界法的存儲(chǔ)空間比回溯法大相對(duì)而言，分枝限界法的存儲(chǔ)空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可得多，因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大；能性更大； 2022-6-970 of 1582022-6-970 of 158方法概述: 示例1n示例示例1（FIFO隊(duì)列分枝限界法）隊(duì)列分枝限界法）n問題：問題： 0-1背包問題背包問題:物品數(shù)物品數(shù)n=3, 重量重量w=(20,15,15), 價(jià)值價(jià)值v=(40,25,25)

38、, 背包容量背包容量c=30, 試裝入最大價(jià)值之和的物品試裝入最大價(jià)值之和的物品?n求解：求解： 解空間解空間:(0,0,0), (0,0,1), , (1,1,1) 解空間樹解空間樹:DBHAIEJKFCLMGNO111111100000002022-6-971 of 1582022-6-971 of 158方法概述: 示例1BFS搜索（FIFO隊(duì)列） 擴(kuò)展結(jié)點(diǎn) 活結(jié)點(diǎn) 隊(duì)列(可行結(jié)點(diǎn)) 可行解(葉結(jié)點(diǎn)) 解值 A B,C BC B D,E(D死結(jié)點(diǎn)) CE C F,G EFG E J,K(J死結(jié)點(diǎn)) FG K 40 F L,M G L,M 50,25 G N,O N,O 25,0 最優(yōu)解為

39、L, 即(0,1,1); 解值為50 DBHAIEJKFCLMGN O11111110000000w=(20,15,15), v=(40,25,25), c=302022-6-972 of 1582022-6-972 of 158方法概述: 示例2n示例示例2（優(yōu)先隊(duì)列分枝限界法）（優(yōu)先隊(duì)列分枝限界法）n問題：問題： 0-1背包問題背包問題:物品數(shù)物品數(shù)n=3, 重量重量w=(20,15,15), 價(jià)值價(jià)值v=(40,25,25), 背包容量背包容量c=30, 試裝入最大價(jià)值之和的物品試裝入最大價(jià)值之和的物品?n求解：求解： 解空間解空間:(0,0,0), (0,0,1), , (1,1,1) 解空間樹解空間樹:DBHAIEJKF