1、第8章 分支與限界,1. 由部分解估計(jì)整體解的界 2. 分支與限界法的基本思想 3. 分支與限界法示例 4. 分支與限界法總結(jié) 5. 分支與限界法界估算預(yù)處理示例 6.分支與限界法的雙限界示例,1. 由部分解估計(jì)整體解的界,1.1 0/1背包問題解的上界估計(jì) 1.2 多段圖最短路徑問題解的下界估計(jì) 1.3 任務(wù)分配問題解的下界估計(jì),1.1 0/1背包問題解的上界估計(jì),假設(shè)0/1背包問題背包承重為M，有n個(gè)物品，其中的物品已按照價(jià)/重比由大到小的順序排列。序號(hào)集合是0,1,n-1，第i個(gè)物品的價(jià)/重比是pi/wi。目前背包中已經(jīng)有物品的集合是S1，被拋棄不用的物品集合是S2，待選物品集合是S3

2、（其中物品的價(jià)/重比是所有物品中最小的。假定S3中的物品全部加入背包后超重）。 此時(shí)，如果背包超重，上界估計(jì)為0；如果背包剛好放滿，上界即為S1中價(jià)值總和；如果背包中尚有空間N， S3中的序號(hào)為m, m+1, , n-1。則必定存在一個(gè)序號(hào)k滿足m=k=n-1，使得 此時(shí)，令 則Pe是對(duì)整體解的一個(gè)上界估計(jì),例如，5個(gè)物品要裝入載重為37的背包，物品重量和價(jià)值分別為（已按價(jià)/重比由大到小排列） 8，16，21，17，12（重） 8，14，16，11，7（價(jià)） 現(xiàn)在背包中只有一個(gè)元素0，估算解的上界。 S1=0， S2=， S3=1，2，3，4背包的剩余空間為37-8=29。它能裝下S3中的物品

3、1和物品2的一部分。因此，解的估計(jì)為：,1.2 多段圖最短路徑問題解的下界估計(jì),0,1,2,3,4,5,6,7,8,9,4,2,3,9,8,8,8,7,4,7,5,6,8,6,6,5,7,3,如果當(dāng)前路徑為(0)(2)，則這個(gè)部分解估計(jì)整體解不會(huì)小于如下估計(jì)值，哪個(gè)好？,1.3 任務(wù)分配問題解的下界估計(jì),任務(wù)1,任務(wù)2,任務(wù)3,任務(wù)4,人員a,人員b,人員c,人員d,9,2,7,8,6,4,3,7,5,8,1,8,7,6,9,4,n個(gè)任務(wù)、n個(gè)人構(gòu)成的任務(wù)分配問題在沒有任何選擇的情況下，解的下界是： 當(dāng)確定了某個(gè)任務(wù)分配給哪個(gè)人后，剩余的問題與原問題等價(jià)，下界估計(jì)是已選費(fèi)用加子問題下界,任務(wù)1

4、,任務(wù)2,任務(wù)3,任務(wù)4,人員a,人員b,人員c,人員d,9,2,7,8,6,4,3,7,5,8,1,8,7,6,9,4,這個(gè)問題的下界估計(jì)是：5+2+1+4 = 12。第一個(gè)任務(wù)分配給第一個(gè)人后，得到子問題,任務(wù)2,任務(wù)3,任務(wù)4,人員b,人員c,人員d,4,3,7,8,1,8,6,9,4,這個(gè)子問題的下界估計(jì)是：4+1+4=9。部分解對(duì)應(yīng)的原問題下界估計(jì)是：9+9=18,2. 分支與限界法的基本思想,分支與限界法從一個(gè)空的解向量開始，逐漸擴(kuò)展這個(gè)解向量，直至擴(kuò)展至完整的解向量（這與回溯法相同） 分支與限界法在解向量的擴(kuò)展過程中，遇到不滿足約束的情況，把當(dāng)前解和它的分支全部刪除（這也與回溯法

5、相同） 分支與限界法在選擇當(dāng)前解時(shí)，并不是按照解向量的固有先后順序進(jìn)行，而是對(duì)那些最有可能成為最優(yōu)解的解向量或部分向量擴(kuò)展 分支與限界法通常以一個(gè)最大或最小堆作為數(shù)據(jù)結(jié)構(gòu)支持,3. 分支與限界法示例,3.1 分支限界法解決0/1背包問題 3.2 分支限界法解決多段圖最短路徑問題 3.3 分支限界法解決任務(wù)分配問題,3.1 分支限界法解決0/1背包問題,對(duì)M容量的背包和n個(gè)物品，如果物品i的價(jià)/重比是pi/wi，則把物品按照價(jià)/重比排序。排序后各個(gè)物品的序號(hào)是0, 1, 2, , n-1 一個(gè)完整的解要進(jìn)行n次擴(kuò)展才能完成。第i次擴(kuò)展有兩個(gè)分支：要物品i和不要物品i 當(dāng)前解如果不滿足背包重量約束

6、，則刪除它；否則，估計(jì)該解的上界，按照估計(jì)值插入最大堆。如果是對(duì)當(dāng)前部分解擴(kuò)展，則要把它的所有子女估值插入最大堆，同時(shí)刪除當(dāng)前部分解 直至某個(gè)解擴(kuò)展完成，并且它處于最大堆堆頂，則問題結(jié)束,8，16，21，17，12（重）背包載重37 8，14，16，11，17（價(jià)）,包中 包外0,1,2,3,4 上界31.9,包中 包外1,2,3,4 上界30,包中0 包外1,2,3,4 上界31.9,3.2 分支限界法解決多段圖最短路徑問題,假設(shè)多段圖共有n段，每段上的路徑條數(shù)的最大值是m 一個(gè)完整的解要進(jìn)行n次擴(kuò)展才能完成。第i次擴(kuò)展的分支數(shù)是當(dāng)前節(jié)點(diǎn)到下一階段的節(jié)點(diǎn)中連線的條數(shù)，最多有m個(gè)分支 用一個(gè)最

7、小堆存放待處理的解，最小堆的關(guān)鍵字是對(duì)部分解下界的估計(jì)（下確界大于或等于這個(gè)關(guān)鍵字）。每次取堆頂、刪除，并估算它的所有子女，并把它們插入到最小堆中，以便繼續(xù)對(duì)解進(jìn)行擴(kuò)展 如果處于最小堆堆頂?shù)慕庖呀?jīng)擴(kuò)展完成，則它就是問題的解,0,1,2,3,4,5,6,7,8,9,4,2,3,9,8,8,8,7,4,7,5,6,8,6,6,5,7,3,路徑0 下界2+4+5+3=14,路徑0-1 下界4+8+5+3=20,路徑0-2 下界2+7+5+3=17,路徑0-3 下界3+4+5+3=15,3.3 分支限界法解決任務(wù)分配問題,假設(shè)n個(gè)任務(wù)分配給n個(gè)人，每個(gè)人完成不同任務(wù)的耗費(fèi)由一個(gè)矩陣給出 初始時(shí)，任何任

8、務(wù)都沒分配給任何人，一個(gè)完整的解要進(jìn)行n次擴(kuò)展才能完成。第i次擴(kuò)展的分支數(shù)是剩余的任務(wù)數(shù)（等于剩余的人數(shù)） 用一個(gè)最小堆存放待處理的解，最小堆的關(guān)鍵字是對(duì)部分解下界的估計(jì)。每次取堆頂、刪除，并估算它的所有子女，并把它們插入到最小堆中，以便繼續(xù)對(duì)解進(jìn)行擴(kuò)展 直至某個(gè)解擴(kuò)展完成，并且它處于最小堆堆頂，則問題結(jié)束,解的下界： 5+2+1+4=12,解的下界： 9+4+1+4=18,解的下界： 6+2+1+4=18,解的下界： 5+2+3+4=14,解的下界： 7+2+1+7=17,4. 分支與限界法總結(jié)(待續(xù)),分支與限界法與回溯法的求解方式是一致的，都是對(duì)部分解進(jìn)行擴(kuò)展直至得到最佳的整體解 分支與

9、限界法與回溯法都可以在求解過程中刪除不可能的解 但分支限界法能夠改變回溯法處理部分解的順序，使得最可能發(fā)展成為最優(yōu)解的部分解優(yōu)先處理。可以認(rèn)為回溯法是“世襲制”，分支限界法是“競(jìng)爭(zhēng)制” 當(dāng)問題只有約束條件而沒有最優(yōu)目標(biāo)時(shí)，分支限界法退化為回溯法,4. 分支與限界法總結(jié)(續(xù)),回溯法的空間一般由問題的深度決定，問題同一深度上的空間可以重復(fù)利用；而分支限界法需要大量的空間?？梢杂靡恍┮騿栴}而異的方法簡(jiǎn)化每一個(gè)節(jié)點(diǎn)的空間大小 分支限界法的時(shí)間消耗一般比回溯法少得多，但估計(jì)上/下界時(shí)，需要花費(fèi)額外的時(shí)間?？梢杂妙A(yù)處理的辦法減少上/下界估算的時(shí)間復(fù)雜度 最小問題在估算下界的同時(shí)，可以同時(shí)估算上界，以便有一個(gè)參考，使得高于上界的那些部分解的節(jié)點(diǎn)提前刪除，減小堆的規(guī)模，提高運(yùn)算效率,5. 分支與限界法界估算預(yù)處理示例,0,1,2,3,4,5,6,7,8,9,4,2,3,9,8,8,8,7,4,7,5,6,8,6,6,5,7,3,下界序列：14，12，8，3 當(dāng)部分解是0-3時(shí)，下界估計(jì)是3+4+