六章分支限界法-ppt課件

1、第六章第六章 分支限界法分支限界法 算法設(shè)計(jì)與算法設(shè)計(jì)與分析分析Design and Design and Analysis of Analysis of Computer Computer Algorithm Algorithm 信息工程學(xué)院信息工程學(xué)院張永梅張永梅學(xué)時(shí)分配學(xué)時(shí)分配 章章 節(jié)節(jié)內(nèi)容內(nèi)容講授課時(shí)講授課時(shí)上機(jī)課時(shí)上機(jī)課時(shí)考試考試第一第一章章緒論緒論4第二第二章章分治與遞歸分治與遞歸42第三第三章章貪心算法貪心算法42第四第四章章動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃42第五第五章章回溯法回溯法42第六第六章章分支限界法分支限界法2合計(jì)合計(jì)2282 本課程成果由平常作業(yè)、上機(jī)實(shí)驗(yàn)和期末考試進(jìn)展評(píng)定：考核

2、方法及成果評(píng)定規(guī)范考核方法及成果評(píng)定規(guī)范 平常作業(yè)：平常作業(yè)：10% 上機(jī)實(shí)驗(yàn)：上機(jī)實(shí)驗(yàn)：30% 期末考試：期末考試：60%，考試方式為開卷，考試方式為開卷第六章第六章 分支限界法分支限界法Branch-and-Bound1、根本要求、根本要求要求掌握分治限界法的根本思想，要求掌握分治限界法的根本思想，算法設(shè)計(jì)步驟，及常見問題的算法。算法設(shè)計(jì)步驟，及常見問題的算法。要求了解分支限界法的剪枝搜索戰(zhàn)要求了解分支限界法的剪枝搜索戰(zhàn)略。略。 2、教學(xué)內(nèi)容、教學(xué)內(nèi)容根本思想根本思想 0-1背包問題背包問題 第六章第六章 分支限界法分支限界法Branch-and-Bound6.1 分支限界法的根本思想分支

3、限界法的根本思想分支限界法與回溯法1求解目的：回溯法的求解目的是找出解空間樹中求解目的：回溯法的求解目的是找出解空間樹中滿足約束條件的一切解，而分支限界法的求解目的那么滿足約束條件的一切解，而分支限界法的求解目的那么是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。解中找出在某種意義下的最優(yōu)解。 2搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法那么以廣度優(yōu)先或以最小耗費(fèi)優(yōu)空間樹，而分支限界法那么以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。先的方式搜索解空間

4、樹。 回溯與分支限界是對(duì)窮舉法的改良?；厮菖c分支限界是對(duì)窮舉法的改良。 它們每次只構(gòu)造候選解的一個(gè)分量，然后評(píng)價(jià)這個(gè)部分它們每次只構(gòu)造候選解的一個(gè)分量，然后評(píng)價(jià)這個(gè)部分解：解： 假設(shè)加上剩下的分量也不能夠求得一個(gè)解，就不再生成假設(shè)加上剩下的分量也不能夠求得一個(gè)解，就不再生成剩下的分量。剩下的分量。 回溯法和分支限界都是以構(gòu)造一棵形狀空間樹為根底，回溯法和分支限界都是以構(gòu)造一棵形狀空間樹為根底，樹的節(jié)點(diǎn)反映了對(duì)一個(gè)部分解所做的特定的選擇。樹的節(jié)點(diǎn)反映了對(duì)一個(gè)部分解所做的特定的選擇。6.1 分支限界法的根本思想分支限界法的根本思想分支限界法與回溯法 有兩種生成問題形狀的根本方法。它們都是從根結(jié)點(diǎn)有

5、兩種生成問題形狀的根本方法。它們都是從根結(jié)點(diǎn)開場(chǎng)然后生成形狀空間樹上的其它結(jié)點(diǎn)。開場(chǎng)然后生成形狀空間樹上的其它結(jié)點(diǎn)。 6.1 分支限界法的根本思想分支限界法的根本思想 假設(shè)已生成一個(gè)結(jié)點(diǎn)而它的一切兒子結(jié)點(diǎn)還沒有全部假設(shè)已生成一個(gè)結(jié)點(diǎn)而它的一切兒子結(jié)點(diǎn)還沒有全部生成，那么這個(gè)結(jié)點(diǎn)叫做活結(jié)點(diǎn)生成，那么這個(gè)結(jié)點(diǎn)叫做活結(jié)點(diǎn)Live node。當(dāng)前正。當(dāng)前正在生成其兒子結(jié)點(diǎn)的活結(jié)點(diǎn)叫在生成其兒子結(jié)點(diǎn)的活結(jié)點(diǎn)叫E-結(jié)點(diǎn)正在擴(kuò)展的結(jié)結(jié)點(diǎn)正在擴(kuò)展的結(jié)點(diǎn)點(diǎn),Expanded node。不再進(jìn)一步擴(kuò)展或者其兒子結(jié)點(diǎn)已。不再進(jìn)一步擴(kuò)展或者其兒子結(jié)點(diǎn)已全部生成的結(jié)點(diǎn)就是死結(jié)點(diǎn)全部生成的結(jié)點(diǎn)就是死結(jié)點(diǎn)Dead node

6、。n在生成問題形狀的兩種方法中，都要有一張活結(jié)點(diǎn)表。問在生成問題形狀的兩種方法中，都要有一張活結(jié)點(diǎn)表。問題形狀的生成可以采用兩種不同的方法：題形狀的生成可以采用兩種不同的方法：n假設(shè)對(duì)一個(gè)假設(shè)對(duì)一個(gè)E-結(jié)點(diǎn)結(jié)點(diǎn)R一旦生成了它的一個(gè)新的兒子一旦生成了它的一個(gè)新的兒子C，就，就把把C當(dāng)作新的擴(kuò)展結(jié)點(diǎn)，在完成對(duì)子樹當(dāng)作新的擴(kuò)展結(jié)點(diǎn)，在完成對(duì)子樹C以以C為根的子為根的子樹的窮盡搜索之后。將樹的窮盡搜索之后。將R結(jié)點(diǎn)重新變成結(jié)點(diǎn)重新變成 E-結(jié)點(diǎn)，繼續(xù)生結(jié)點(diǎn)，繼續(xù)生成成R的下一個(gè)兒子假設(shè)存在。這稱做深度優(yōu)先的問題的下一個(gè)兒子假設(shè)存在。這稱做深度優(yōu)先的問題形狀生成法。形狀生成法。n在另一種形狀生成方法中，

7、一個(gè)在另一種形狀生成方法中，一個(gè)E-結(jié)點(diǎn)不斷堅(jiān)持到變成死結(jié)點(diǎn)不斷堅(jiān)持到變成死結(jié)點(diǎn)為止。即在一個(gè)結(jié)點(diǎn)為止。即在一個(gè)E-結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它不斷是擴(kuò)結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它不斷是擴(kuò)展結(jié)點(diǎn)。這實(shí)踐上是一種寬度優(yōu)先的問題形狀生成法。展結(jié)點(diǎn)。這實(shí)踐上是一種寬度優(yōu)先的問題形狀生成法。6.1 分支限界法的根本思想分支限界法的根本思想 廣度優(yōu)先遍歷廣度優(yōu)先遍歷(BFS) 方法：從圖的某一頂點(diǎn)方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)后，依出發(fā)，訪問此頂點(diǎn)后，依次訪問次訪問V0的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中一切這些鄰接點(diǎn)出發(fā)，廣度優(yōu)

8、先遍歷圖，直至圖中一切已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；假設(shè)此時(shí)圖已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；假設(shè)此時(shí)圖中尚有頂點(diǎn)未被訪問，那么另選圖中一個(gè)未被訪問中尚有頂點(diǎn)未被訪問，那么另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，反復(fù)上述過程，直至圖中一切頂點(diǎn)的頂點(diǎn)作起點(diǎn)，反復(fù)上述過程，直至圖中一切頂點(diǎn)都被訪問為止。都被訪問為止。V1V2V4V5V3V7V6V8例例廣度遍歷：廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V86.1 分支限界法的根本思想分支限界法的根本思想在這兩種方法中，為了防止生成那些不能夠產(chǎn)生最正確解或所需解的問題形狀，將用限界函數(shù)去殺死那些實(shí)踐上不能夠產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問題的

9、計(jì)算任務(wù)量。這樣做要非常小心，以使得在處置終了時(shí)至少能生成一個(gè)答案結(jié)點(diǎn)；假設(shè)這個(gè)問題要求找出全部解，那么要能生成一切的答案結(jié)點(diǎn)。運(yùn)用限界函數(shù)的深度優(yōu)先結(jié)點(diǎn)生成方法稱為回溯法backtracking。E-結(jié)點(diǎn)不斷堅(jiān)持到死為止的形狀生成方法導(dǎo)致分枝-限界方法branch-and-bound。6.1 分支限界法的根本思想分支限界法的根本思想6.1 分支限界法的根本思想分支限界法的根本思想 分支限界法常以廣度優(yōu)先或以最小耗費(fèi)最大效益優(yōu)先的方式搜索問題的解空間樹。對(duì)已處置的各結(jié)點(diǎn)根據(jù)限界函數(shù)估算目的函數(shù)的能夠取值，從中選取使目的函數(shù)獲得極值極大/極小的結(jié)點(diǎn)優(yōu)先進(jìn)展廣度優(yōu)先搜索不斷調(diào)整搜索方向，盡快找到解

10、。 特點(diǎn)：限界函數(shù)?；趩栴}的目的函數(shù)，適用特點(diǎn)：限界函數(shù)?；趩栴}的目的函數(shù)，適用于求解最優(yōu)化問題。于求解最優(yōu)化問題。6.1 分支限界法的根本思想分支限界法的根本思想 分支限界法常以廣度優(yōu)先或以最小耗費(fèi)最大效益優(yōu)先的方式搜索問題的解空間樹。 以后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并以后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并反復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程不斷繼續(xù)到找到所需的解反復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程不斷繼續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止?；蚧罱Y(jié)點(diǎn)表為空時(shí)為止。 在分支限界法中，每一個(gè)活結(jié)點(diǎn)只需一次時(shí)機(jī)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其一切兒子結(jié)點(diǎn)。在這

11、些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其他兒子結(jié)點(diǎn)被參與活結(jié)點(diǎn)表中。分支限界法是最正確優(yōu)先搜索分支限界法是最正確優(yōu)先搜索法法 分支限界法就是最正確優(yōu)先包括廣度優(yōu)先在分支限界法就是最正確優(yōu)先包括廣度優(yōu)先在內(nèi)的搜索法。內(nèi)的搜索法。 分支限界法將要搜索的結(jié)點(diǎn)按評(píng)價(jià)函數(shù)的優(yōu)劣分支限界法將要搜索的結(jié)點(diǎn)按評(píng)價(jià)函數(shù)的優(yōu)劣排序，讓好的結(jié)點(diǎn)優(yōu)先搜索，將壞的結(jié)點(diǎn)剪去。排序，讓好的結(jié)點(diǎn)優(yōu)先搜索，將壞的結(jié)點(diǎn)剪去。所以準(zhǔn)確說，此方法應(yīng)稱為界限剪支法。所以準(zhǔn)確說，此方法應(yīng)稱為界限剪支法。 分支限界法中有兩個(gè)要點(diǎn)：分支限界法中有兩個(gè)要點(diǎn)：n評(píng)價(jià)函數(shù)的構(gòu)造；評(píng)價(jià)函數(shù)的構(gòu)造；n搜索途徑的構(gòu)造。搜索途徑的構(gòu)造

12、。6.1 分支限界法的根本思想分支限界法的根本思想評(píng)價(jià)函數(shù)的構(gòu)造評(píng)價(jià)函數(shù)的構(gòu)造 評(píng)價(jià)函數(shù)要可以提供一個(gè)評(píng)定候選擴(kuò)展結(jié)點(diǎn)的評(píng)價(jià)函數(shù)要可以提供一個(gè)評(píng)定候選擴(kuò)展結(jié)點(diǎn)的方法，以便確定哪個(gè)結(jié)點(diǎn)最有能夠在通往目的方法，以便確定哪個(gè)結(jié)點(diǎn)最有能夠在通往目的的最正確途徑上。的最正確途徑上。6.1 分支限界法的根本思想分支限界法的根本思想搜索途徑的構(gòu)造搜索途徑的構(gòu)造 在回溯法中，每次僅調(diào)查一條途徑，因在回溯法中，每次僅調(diào)查一條途徑，因此只需求構(gòu)造這一條途徑即可：前進(jìn)時(shí)此只需求構(gòu)造這一條途徑即可：前進(jìn)時(shí)記下相應(yīng)結(jié)點(diǎn)，回溯時(shí)刪去最末尾結(jié)點(diǎn)記下相應(yīng)結(jié)點(diǎn)，回溯時(shí)刪去最末尾結(jié)點(diǎn)的記錄。這比較容易實(shí)現(xiàn)。的記錄。這比較容易實(shí)現(xiàn)

13、。 在分支限界法中，是同時(shí)調(diào)查假設(shè)干條在分支限界法中，是同時(shí)調(diào)查假設(shè)干條途徑，那么又該如何構(gòu)造搜索的途徑呢？途徑，那么又該如何構(gòu)造搜索的途徑呢？n對(duì)每一個(gè)擴(kuò)展的結(jié)點(diǎn)，建立三個(gè)信息：對(duì)每一個(gè)擴(kuò)展的結(jié)點(diǎn)，建立三個(gè)信息：n(1)該結(jié)點(diǎn)的稱號(hào)；該結(jié)點(diǎn)的稱號(hào)；n(2)它的評(píng)價(jià)函數(shù)值；它的評(píng)價(jià)函數(shù)值；n(3)指向其前驅(qū)的指針；指向其前驅(qū)的指針；n這樣一旦找到目的，即可逆向構(gòu)造其途徑。這樣一旦找到目的，即可逆向構(gòu)造其途徑。6.1 分支限界法的根本思想分支限界法的根本思想界限界限(Bounding) 評(píng)價(jià)函數(shù)評(píng)價(jià)函數(shù)f(d)關(guān)系著算法的效率乃至成敗。關(guān)系著算法的效率乃至成敗。 由于在大多數(shù)問題中由于在大多數(shù)問

14、題中f(d)只是個(gè)估計(jì)值，所以單只是個(gè)估計(jì)值，所以單靠靠f(d)是不夠的。通常還要設(shè)計(jì)它的上、下界函是不夠的。通常還要設(shè)計(jì)它的上、下界函數(shù)數(shù)U(d)和和L(d)。 L(d)f(d)U(d)。 所謂分支限界法就是經(jīng)過評(píng)價(jià)函數(shù)及其上、下所謂分支限界法就是經(jīng)過評(píng)價(jià)函數(shù)及其上、下界函數(shù)的計(jì)算，將形狀空間中不能夠產(chǎn)生最正界函數(shù)的計(jì)算，將形狀空間中不能夠產(chǎn)生最正確解的子樹剪去，減少搜索的范圍，提高效率。確解的子樹剪去，減少搜索的范圍，提高效率。因此更準(zhǔn)確的稱謂應(yīng)是因此更準(zhǔn)確的稱謂應(yīng)是“界限剪支法。界限剪支法。6.1 分支限界法的根本思想分支限界法的根本思想對(duì)評(píng)價(jià)函數(shù)的討論對(duì)評(píng)價(jià)函數(shù)的討論 分支限界法總耗時(shí)

15、為分支限界法總耗時(shí)為O(n22n)，它與回溯法、動(dòng)態(tài)，它與回溯法、動(dòng)態(tài)規(guī)劃法等在時(shí)間復(fù)雜性上沒有本質(zhì)的區(qū)別。規(guī)劃法等在時(shí)間復(fù)雜性上沒有本質(zhì)的區(qū)別。 然而，假設(shè)評(píng)價(jià)函數(shù)選擇得好，采用分支限界法能然而，假設(shè)評(píng)價(jià)函數(shù)選擇得好，采用分支限界法能夠有一個(gè)小得多的常數(shù)因子。夠有一個(gè)小得多的常數(shù)因子。 好的評(píng)價(jià)函數(shù)應(yīng)該有一個(gè)盡能夠高的下界估計(jì)和一好的評(píng)價(jià)函數(shù)應(yīng)該有一個(gè)盡能夠高的下界估計(jì)和一個(gè)盡能夠低的上界估計(jì)，從而使得搜索空間可以得個(gè)盡能夠低的上界估計(jì)，從而使得搜索空間可以得到有效的緊縮，從而提高效率。到有效的緊縮，從而提高效率。 在實(shí)際上可以證明好的評(píng)價(jià)函數(shù)所搜索的結(jié)點(diǎn)不會(huì)在實(shí)際上可以證明好的評(píng)價(jià)函數(shù)所搜

16、索的結(jié)點(diǎn)不會(huì)多于壞的評(píng)價(jià)函數(shù)所搜索的結(jié)點(diǎn)。多于壞的評(píng)價(jià)函數(shù)所搜索的結(jié)點(diǎn)。6.1 分支限界法的根本思想分支限界法的根本思想6.1 分支限界法的根本思想分支限界法的根本思想常見的兩種分支限界法1隊(duì)列式隊(duì)列式(FIFO)分支限界法分支限界法 按照隊(duì)列先進(jìn)先出按照隊(duì)列先進(jìn)先出FIFO原那么選取下原那么選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。 2優(yōu)先隊(duì)列式分支限界法優(yōu)先隊(duì)列式分支限界法 按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。最大優(yōu)先隊(duì)列：運(yùn)用最大堆，表達(dá)最大效益優(yōu)先最大優(yōu)先隊(duì)列：運(yùn)用最大堆，表達(dá)最大效益優(yōu)先最

17、小優(yōu)先隊(duì)列：運(yùn)用最小堆，表達(dá)最小費(fèi)用優(yōu)先最小優(yōu)先隊(duì)列：運(yùn)用最小堆，表達(dá)最小費(fèi)用優(yōu)先解空間樹的動(dòng)態(tài)搜索 利用回溯法求解問題，雖然剪枝減少了搜索空利用回溯法求解問題，雖然剪枝減少了搜索空間，但整個(gè)搜索按深度優(yōu)先機(jī)械進(jìn)展，是盲目搜索間，但整個(gè)搜索按深度優(yōu)先機(jī)械進(jìn)展，是盲目搜索不可預(yù)測(cè)本結(jié)點(diǎn)以下的結(jié)點(diǎn)進(jìn)展得如何。不可預(yù)測(cè)本結(jié)點(diǎn)以下的結(jié)點(diǎn)進(jìn)展得如何。6.1 分支限界法的根本思想分支限界法的根本思想解空間樹的動(dòng)態(tài)搜索 分支限界法首先確定一個(gè)合理的限界函數(shù)，并根分支限界法首先確定一個(gè)合理的限界函數(shù)，并根據(jù)限界函數(shù)確定目的函數(shù)的界據(jù)限界函數(shù)確定目的函數(shù)的界down, up； 然后按照廣度優(yōu)先戰(zhàn)略遍歷問題的解空

18、間樹，在然后按照廣度優(yōu)先戰(zhàn)略遍歷問題的解空間樹，在某一分支上，依次搜索該結(jié)點(diǎn)的一切孩子結(jié)點(diǎn)，分別某一分支上，依次搜索該結(jié)點(diǎn)的一切孩子結(jié)點(diǎn)，分別估算這些孩子結(jié)點(diǎn)的目的函數(shù)的能夠取值對(duì)最小化估算這些孩子結(jié)點(diǎn)的目的函數(shù)的能夠取值對(duì)最小化問題，估算結(jié)點(diǎn)的問題，估算結(jié)點(diǎn)的down，對(duì)最大化問題，估算結(jié)點(diǎn)的，對(duì)最大化問題，估算結(jié)點(diǎn)的up。 假設(shè)某孩子結(jié)點(diǎn)的目的函數(shù)值超出目的函數(shù)的界，假設(shè)某孩子結(jié)點(diǎn)的目的函數(shù)值超出目的函數(shù)的界，那么將其丟棄從此結(jié)點(diǎn)生成的解不會(huì)比目前已得到那么將其丟棄從此結(jié)點(diǎn)生成的解不會(huì)比目前已得到的更好，否那么入待處置表。的更好，否那么入待處置表。6.1 分支限界法的根本思想分支限界法的根

19、本思想 途徑查找終止條件途徑查找終止條件 該節(jié)點(diǎn)的邊境值超越目前目的函數(shù)的界。該節(jié)點(diǎn)的邊境值超越目前目的函數(shù)的界。 該節(jié)點(diǎn)無法代表任何可行解，由于它已違反該節(jié)點(diǎn)無法代表任何可行解，由于它已違反了問題的約束。了問題的約束。226.1 分支限界法的根本思想分支限界法的根本思想6.1 分支限界法的根本思想分支限界法的根本思想 在問題的邊帶權(quán)解空間樹中進(jìn)展廣度優(yōu)先搜索。找一個(gè)答在問題的邊帶權(quán)解空間樹中進(jìn)展廣度優(yōu)先搜索。找一個(gè)答案結(jié)點(diǎn)使對(duì)應(yīng)途徑權(quán)最小。當(dāng)搜索到一個(gè)擴(kuò)展結(jié)點(diǎn)時(shí)，一次性案結(jié)點(diǎn)使對(duì)應(yīng)途徑權(quán)最小。當(dāng)搜索到一個(gè)擴(kuò)展結(jié)點(diǎn)時(shí)，一次性擴(kuò)展它的一切兒子，將滿足約束條件且最小耗費(fèi)函數(shù)擴(kuò)展它的一切兒子，將滿足

20、約束條件且最小耗費(fèi)函數(shù)目的函目的函數(shù)限界的兒子，插入活結(jié)點(diǎn)表中，再?gòu)幕罱Y(jié)點(diǎn)表中取下一結(jié)點(diǎn)數(shù)限界的兒子，插入活結(jié)點(diǎn)表中，再?gòu)幕罱Y(jié)點(diǎn)表中取下一結(jié)點(diǎn)同樣擴(kuò)展，同樣擴(kuò)展， 直到找到所需的解或活動(dòng)結(jié)點(diǎn)表為空。直到找到所需的解或活動(dòng)結(jié)點(diǎn)表為空。用于求解最優(yōu)化問題用于求解最優(yōu)化問題 結(jié)點(diǎn)結(jié)點(diǎn)x的最小耗費(fèi)函數(shù)的最小耗費(fèi)函數(shù)c(x):以以x為根的子樹所包含的答案結(jié)為根的子樹所包含的答案結(jié)點(diǎn)中，途徑權(quán)最小者的權(quán)值。假設(shè)點(diǎn)中，途徑權(quán)最小者的權(quán)值。假設(shè)x是答案結(jié)點(diǎn)是答案結(jié)點(diǎn), 那么那么c(x)為該為該點(diǎn)的目的函數(shù)值點(diǎn)的目的函數(shù)值; 假設(shè)假設(shè)x是根結(jié)點(diǎn)是根結(jié)點(diǎn), 那么那么c(x)為最優(yōu)解值。為最優(yōu)解值。c(x)為為單調(diào)

21、遞增函數(shù)。單調(diào)遞增函數(shù)。通常采用優(yōu)先隊(duì)列方式組織，通常采用優(yōu)先隊(duì)列方式組織， c(x)小者優(yōu)先。小者優(yōu)先。目的函數(shù)限界目的函數(shù)限界U: 初始初始U可取可取，假設(shè)，假設(shè)x*是任一答案結(jié)點(diǎn)，且是任一答案結(jié)點(diǎn)，且c(x*)U時(shí)，時(shí)， x將不用擴(kuò)展剪枝。將不用擴(kuò)展剪枝。活動(dòng)結(jié)點(diǎn)表活動(dòng)結(jié)點(diǎn)表: :6.1 分支限界法的根本思想分支限界法的根本思想用于求解最優(yōu)化問題用于求解最優(yōu)化問題1.確定解空間構(gòu)造；確定解空間構(gòu)造；2.確定約束條件和目的函數(shù)；確定約束條件和目的函數(shù)；3.取取U=U(T)；4.擴(kuò)展根結(jié)點(diǎn)的一切兒子，對(duì)每一子結(jié)點(diǎn)擴(kuò)展根結(jié)點(diǎn)的一切兒子，對(duì)每一子結(jié)點(diǎn)x斷定其能否滿足約束斷定其能否滿足約束 條件，

22、對(duì)滿足約束條件的條件，對(duì)滿足約束條件的 x 計(jì)算計(jì)算 , 將將 U的的x 參與活參與活 結(jié)點(diǎn)表；結(jié)點(diǎn)表；5. x為葉結(jié)點(diǎn)時(shí)，檢查能否為葉結(jié)點(diǎn)時(shí)，檢查能否c(x)U， 是，那么用是，那么用c(x)更新更新U；6. 取活結(jié)點(diǎn)表中的第一個(gè)結(jié)點(diǎn)為根取活結(jié)點(diǎn)表中的第一個(gè)結(jié)點(diǎn)為根, 反復(fù)反復(fù)4。 解題步驟解題步驟 最小耗費(fèi)函數(shù)最小耗費(fèi)函數(shù)c(x)的估算的估算: c(x)不能即時(shí)求得不能即時(shí)求得, 為此取能即時(shí)為此取能即時(shí)計(jì)算的下界函數(shù)計(jì)算的下界函數(shù) 替代替代, 應(yīng)具有單調(diào)性應(yīng)具有單調(diào)性, 且在答案結(jié)點(diǎn)且在答案結(jié)點(diǎn)上上 =c(x) )( (xc) )( (xc) )( (xc) )( (xc) )( (xc

23、6.1 分支限界法的根本思想分支限界法的根本思想6.2 0-1背包問題背包問題 (0-1 Knapsack Problem) 問題描畫問題描畫 背包問題中的背包問題中的xj限定只能取限定只能取0或或1值，用值，用KNAP(1,j,X)來表示這個(gè)問題來表示這個(gè)問題效益值效益值背包容量背包容量那么那么0/1背包問題就是背包問題就是KNAP(1,n,M)6.2 0-1背包問題背包問題 (0-1 Knapsack Problem) 首先把物品按照P(i)/W(i)P(i+1)/W(i+1)的衡量規(guī)范排序，以此順序讀入物品。并且定義一個(gè)大小為物品多少的解向量X，X的一個(gè)分量就代表某個(gè)物品的裝入情況。背包

24、問題的貪婪算法及闡明背包問題的貪婪算法及闡明 問題描畫問題描畫 設(shè)有設(shè)有n n個(gè)物體和一個(gè)背包，物體個(gè)物體和一個(gè)背包，物體i i的分量為的分量為wi wi ， 價(jià)值為價(jià)值為pi pi ，背包的載荷為，背包的載荷為M M，找一個(gè)裝載方案，使得能放入，找一個(gè)裝載方案，使得能放入背包的物體總價(jià)值最高。背包的物體總價(jià)值最高。 算法思緒算法思緒 將問題的解表示為將問題的解表示為n n元向量元向量:x1, . xn , :x1, . xn , xixi0,1 0,1 用排序樹表示解空間用排序樹表示解空間, , 在樹中做廣度優(yōu)先搜索在樹中做廣度優(yōu)先搜索, ,約束條件約束條件: M ;: M ;目的函數(shù)目的函

25、數(shù): ; : ; 目的函數(shù)限界初值目的函數(shù)限界初值:U=0:U=0；c(x):c(x):以以x x為根的子樹所包含的葉子中，途徑權(quán)值最大者；為根的子樹所包含的葉子中，途徑權(quán)值最大者； : :以以x x為根的子樹的部分途徑的權(quán)值。為根的子樹的部分途徑的權(quán)值。iinixp1iniixw16.2 0-1背包問題背包問題 (0-1 Knapsack Problem) )( (xc算法的思想 首先，要對(duì)輸入數(shù)據(jù)進(jìn)展預(yù)處置，將各物品依其單位分量?jī)r(jià)值從大到小進(jìn)展陳列。 對(duì)于優(yōu)先隊(duì)列分支限界法，結(jié)點(diǎn)的優(yōu)先級(jí)由已裝袋的物品價(jià)值加上剩下的最大單位分量?jī)r(jià)值的物品裝滿剩余容量的價(jià)值和。 算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒

26、子結(jié)點(diǎn)的可行性。假設(shè)該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，那么將它參與到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才將它參與子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列。當(dāng)擴(kuò)展到葉結(jié)點(diǎn)時(shí)為問題的最優(yōu)值。6.2 0-1背包問題背包問題 (0-1 Knapsack Problem)算法的思想 算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。假設(shè)該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，那么將它參與到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才將它參與子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列。當(dāng)擴(kuò)展到葉結(jié)點(diǎn)時(shí)為問題的最優(yōu)值。6.2 0-1背包問題背包問題 (0-1 Knapsack Problem) 為了便于計(jì)算上界函數(shù)，可以先將物品按照其單位分量?jī)r(jià)值從大到小排序，以后只需順序