1、2020/7/12,計算機算法設(shè)計與分析,1,第六章分支限界法,2020/7/12,計算機算法設(shè)計與分析,2,分支限界法是最佳優(yōu)先搜索法,分支限界法就是最佳優(yōu)先(包括廣度優(yōu)先在內(nèi))的搜索法。 分支限界法將要搜索的結(jié)點按評價函數(shù)的優(yōu)劣排序，讓好的結(jié)點優(yōu)先搜索，將壞的結(jié)點剪去。所以準確說，此方法應稱為界限剪支法。 分支限界法中有兩個要點：,(1)評價函數(shù)的構(gòu)造； (2)搜索路徑的構(gòu)造。,2020/7/12,計算機算法設(shè)計與分析,3,評價函數(shù)的構(gòu)造,評價函數(shù)要能夠提供一個評定候選擴展結(jié)點的方法，以便確定哪個結(jié)點最有可能在通往目標的最佳路徑上。 一個評價函數(shù)f(d)通?？梢杂蓛蓚€部分構(gòu)成：從開始結(jié)點到

2、結(jié)點d的已有耗損值g(d)，和再從結(jié)點d到達目標的期望耗損值h(d)。即：,f(d) = g(d) + h(d),通常g(d)的構(gòu)造較易，h(d)的構(gòu)造較難。,2020/7/12,計算機算法設(shè)計與分析,4,搜索路徑的構(gòu)造,在回溯法中，每次僅考察一條路徑，因而只需要構(gòu)造這一條路徑即可：前進時記下相應結(jié)點，回溯時刪去最末尾結(jié)點的記錄。這比較容易實現(xiàn)。 在分支限界法中，是同時考察若干條路徑，那么又該如何構(gòu)造搜索的路徑呢？,對每一個擴展的結(jié)點，建立三個信息：,(1)該結(jié)點的名稱； (2)它的評價函數(shù)值； (3)指向其前驅(qū)的指針；,這樣一旦找到目標，即可逆向構(gòu)造其路徑。 用一個表保存準備擴展的結(jié)點，稱為

3、Open表。 用一個表保存已搜索過的結(jié)點，稱為Closed表。,2020/7/12,計算機算法設(shè)計與分析,5,分支限界法的一般算法,計算初始結(jié)點s的f(s); s, f(s), nil放入Open; while (Open ) 從Open中取出p, f(p), x(f(p)為最小); 將p, f(p), x放入Closed; 若p是目標，則成功返回；否則 產(chǎn)生p的后繼d并計算f(d) ；對每個后繼d,有二種情況：,dClosed | d Open； dOpen s, f(s), nil放入Open; while (Open ) 從Open中取出p, f(p), L; /L是路徑已有結(jié)點 若f(

4、p)U，則拋棄該路徑； 若p是目標，則考慮修改上界函數(shù)值；否則 將p, f(p), L放入Closed; 在該路徑上擴展結(jié)點p；對每個后繼d 計算f(d)； 若f(d)U, 則L = L p; 將d, f(d),L依序放入Open。 ,2020/7/12,計算機算法設(shè)計與分析,11,分支限界法求TSP舉例,設(shè)有向圖G = (V, E)的邊的代價矩陣為C = cij。若不存在有向邊E，則定義cij=且規(guī)定cii=。不失一般性，設(shè)周游路線均以頂點1為起點。左下為一個有向圖G的代價矩陣C。, 25 40 31 27 5 17 30 25 19 15 6 1 9 50 24 6 22 8 7 10 ,

5、評價函數(shù)f(d)為1到d的代價減去已經(jīng)過的邊數(shù)。 初始時f(1) = 0; f(d) = f(p) + cpd 1，這里p是d的前驅(qū)。,2020/7/12,計算機算法設(shè)計與分析,12,分支限界法求TSP的搜索, 25 40 31 27 5 17 30 25 19 15 6 1 9 50 24 6 22 8 7 10 ,1,0,2,24,3,39,4,30,5,26,2,3,40,4,53,5,48,5,2,33,3,32,4,35,4,2,79,3,53,5,45,3,2,46,4,37,2,3,49,4,62,4,2,84,3,58,4,2,86,找到了第一條周游路線153421，其長度為9

6、5。,這不是最短周游路線，需要修改上界后繼續(xù)搜索。,2020/7/12,計算機算法設(shè)計與分析,13,歸約矩陣以及約數(shù),前面的搜索的效率不高，幾乎要搜索全部的狀態(tài)空間。其原因是評價函數(shù)以及上下界的估計太低。為了設(shè)計求解TSP問題的更好的評價函數(shù)，先定義其代價矩陣的歸約矩陣和約數(shù)。,給定代價矩陣C，從C的任何行i(或列i)的各元素中減去此行(或此列)的最小元素的值r(i)(或r(i)，稱為對i行(或i列)的歸約。將C的各行和各列都歸約后的矩陣稱為C的歸約矩陣。和數(shù) r = in r(i) + in r(i) 稱為C的約數(shù)。,2020/7/12,計算機算法設(shè)計與分析,14,例子中的歸約矩陣和約數(shù),計

7、算前面例子中的歸約矩陣及其約數(shù)如下：, 25 40 31 27 5 17 30 25 19 15 6 1 9 50 24 6 22 8 7 10 ,先做行歸約：,r(1)=25, 0 15 6 2,r(2)=5,0 12 25 20,r(3)=1,18 14 5 0,r(4)=6,3 44 21 0,r(5)=7,15 1 0 3 ,再做列歸約：,r(1)=r(2)=r(3)=r(5)=0 r(4)=3,3 22 2 0,約數(shù) r = 47。,2020/7/12,計算機算法設(shè)計與分析,15,約數(shù)是周游路線長度的下界,定理：設(shè)C是圖G的代價矩陣，P是周游路線，則P的代價，即P cij = r +

8、 P cij ， 式中C = cij是C的歸約矩陣，r為約數(shù)。,證明：由歸約矩陣的構(gòu)造可知： cij = cij r(i) r(j) 即cij = cij + r(i) + r(j)。,任何周游路線包含n條邊并且對應在C中的每行每列有且僅有一條邊。于是 P cij = P(cij + r(i) + r(j)。,r + P cij 。,2020/7/12,計算機算法設(shè)計與分析,16,定義期望函數(shù)h(d),對開始結(jié)點1，令g(1) = 0，h(1) = r，f(1) = r。 若從結(jié)點1選擇了一條邊，不妨設(shè)邊，則令g(2) = f(1)+從1到2的距離l ，顯然l應該是c12，而不應該再是c12了

9、。 那么h(2) = ？ 自然可以想到h(2)可以是從2開始的路線的下界r2。是否也可用類似求r一樣去求新的約數(shù)r2呢？ 可以，但在此之前應將邊和所有邊和邊都刪去，即置c12、c1k和ck2為。,設(shè)Cp為某路線上結(jié)點p的歸約矩陣。從p選擇邊所得到結(jié)點d的歸約矩陣Cd和約數(shù)rd為： (1)將Cp中的cpd，cpk和ckd置為，1kn； (2)依照求歸約矩陣C的方法對Cp進行行歸約和列歸約，便得到了Cd和rd 。,令f(1) = g(1) + h(1)，其中g(shù)(1) = 0，h(1) = r。 對任意路線上的結(jié)點d，設(shè)p是其前驅(qū)結(jié)點，則 f(d) = g(d) + h(d)， 其中，g(d) =

10、f(p) + Cppd， h(d) = rd。,2020/7/12,計算機算法設(shè)計與分析,17,用新的評價函數(shù)求TSP,下面用新的評價函數(shù)求前面的例子，我們已經(jīng)求得了它的歸約矩陣C和約數(shù)r = 47。, 0 15 3 2 0 12 22 20 18 14 2 0 3 44 18 0 15 1 0 0 ,1,47,2,g(2) = 47 + 0 = 47,0,10,8,0,15,12,h(2) = 12 + 3 = 15,f(2) = 47 +15 = 62,62,3, 0 15 3 2 0 12 22 20 18 14 2 0 3 44 18 0 15 1 0 0 ,g(3) = 47 + 1

11、5 = 62,0,43,13,h(3) = 1,f(3) = 63,63,4,類似地可求出 f(4) = 51。,51,5,類似地可求出 f(5) = 50。,50,下面優(yōu)先擴展的是結(jié)點5。,2,此時C2是在C5的基礎(chǔ)上進行。右邊就是C5。, 0 12 22 18 14 2 3 44 18 0 0 0 ,g(2) = 50 + 0 = 50,0,16,0,15,0,3,h(2) = 17,f(2) = 67,67,3,類似地計算出f(3) = 68,68,4,類似地計算出f(4) = 81,81,下面擴展f(4) = 51的結(jié)點4。并用同樣方法計算它們的評價函數(shù)值。,2,121,3,69,4,

12、64,1,5,4,下面要擴展的結(jié)點 是f(2)= 62的結(jié)點2。 右邊是其對應的歸 約矩陣C2。,2, 0 10 8 15 2 0 0 18 0 12 0 0 ,3,g(3) = 62 + 0 = 62； 對C2進行歸約，,得 h(3) = 0；于是 f(3) = 62。,62,對結(jié)點2的另外兩個兒子進行同樣的計算，得： f(4) = 84，f(5) = 72。,4,84,5,72,下面對f(3) = 62的結(jié)點3進行擴展。它有兩個后繼結(jié)點。,3,4,5,對結(jié)點4， g(4) = 62 + 2 = 64。,0,h(4) = 12 ，于是 f(4) = 64 + 12 = 76,76,對結(jié)點5，

13、 g(5) = 62 + 0 = 62。, 15 2 0 0 0 12 0 ,h(5) = 0，于是 f(5) = 62 + 0 = 62,62,對結(jié)點5(f(5) = 62)再進行擴展。,5,4,g(4) = 62 + 0 = 62，,h(4) = 0，f(4) = 62。,62,結(jié)點4是目標結(jié)點，找到了第一條路線。,4,這條路線的長度為62，以其為上界。,其余未擴展的結(jié)點的評價函數(shù)值均超過上界，因而不再需要擴展了。,于是找到了一條最短的周游路線： 123541。,2020/7/12,計算機算法設(shè)計與分析,18,分支邊與二叉樹,在構(gòu)造求TSP的搜索樹時，還有另外一種算法稍有點不同，就是將搜索

14、樹構(gòu)造成二叉樹。 給定一條最短周游路線P，對于任一條邊只有兩種情況，即P或者P。 這就可以表示成右邊的二叉樹：,k,m,n,_ ,其中,_ 表示P。,這樣的邊稱為分支邊。,2020/7/12,計算機算法設(shè)計與分析,19,用二叉樹求TSP,1,2,50,_ ,3,62,2,4,53,_ ,5,68,4,6,64,_ ,7,65,3,8,62,_ ,9,74,8,10,62,_ ,11,70,10,12,62,_ ,13,66,12,14,62,_ ,15,66,14,16,62,_ ,17,結(jié)點16給出了一條最短周游路線： 123541,2020/7/12,計算機算法設(shè)計與分析,20,分支限界法

15、的效率,從TSP問題的計算可看出，分支限界法搜索的狀態(tài)空間為O(2n)。 對每個結(jié)點的計算時間為O(n2)。 因此在最壞情況下，分支限界法計算TSP的時間復雜性為O(n22n)。 顯然，用分支限界法計算TSP的空間復雜性為O(n22n)。因為對每個結(jié)點需要n2的空間。,2020/7/12,計算機算法設(shè)計與分析,21,對評價函數(shù)的討論,分支限界法總耗時為O(n22n)，它與回溯法、動態(tài)規(guī)劃法等在時間復雜性上沒有本質(zhì)的區(qū)別。 然而，如果評價函數(shù)選擇得好，采用分支限界法可能有一個小得多的常數(shù)因子。 好的評價函數(shù)應該有一個盡可能高的下界估計和一個盡可能低的上界估計，從而使得搜索空間能夠得到有效的壓縮，

16、從而提高效率。 在理論上可以證明好的評價函數(shù)所搜索的結(jié)點不會多于壞的評價函數(shù)所搜索的結(jié)點。,2020/7/12,計算機算法設(shè)計與分析,22,關(guān)系、傳遞閉包與搜索,定義在集合S上關(guān)系R是笛卡兒直積SS的一個子集，RSS。 關(guān)系R的傳遞閉包是包含R的最小的具有傳遞性質(zhì)的關(guān)系。 若S是有限的，|S| = n，則R可表示為一個nn的關(guān)系矩陣M或n個結(jié)點的有向圖G。 求關(guān)系R的傳遞閉包實際上也就是在有向圖G上的搜索。而反過來，在有向圖G上的搜索也就是求某種關(guān)系的傳遞閉包。,2020/7/12,計算機算法設(shè)計與分析,23,傳遞閉包的集合算法,給定關(guān)系R以及S中的元素a，求R*(a)。 初始化：U = A

17、= a; q = true; while (q) for (pA) U = U d | dS 且 pRd； if (U = A) q = false; else A = U 這個算法稍加修改即可變成求R*(a)中滿足某性質(zhì)的元素的算法。 不難看出此算法實際也就是分支限界法。,2020/7/12,計算機算法設(shè)計與分析,24,傳遞閉包的矩陣算法,若|S| = n，則R可表示為一個矩陣M。于是R的傳遞閉包R*的矩陣M*為：,i=n M* = Mi = M0M1 Mn i=0 其中M0為單位矩陣E，Mi為M的i次冪。,M* = E; for (i=1; i=n; i+) M* = M* M*M,不難看出此算法的時間復雜性為O(n4)。,2020/7/12,計算機算法設(shè)計與分析,25,傳遞閉包的Warshall算法,下面給出求傳遞閉包的Warshall算法： for (i = 1; i = n; i+) for (j = 1; j = n; j+) if (Mji =