礦大算法第6章 分支限界法

1、學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn)理解分支限界法的剪枝搜索策略。理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架掌握分支限界法的算法框架 （1）隊(duì)列式）隊(duì)列式(FIFO)分支限界法分支限界法 （2）優(yōu)先隊(duì)列式分支限界法）優(yōu)先隊(duì)列式分支限界法 第第6 6章章 分支限界法分支限界法通過(guò)應(yīng)用范例學(xué)習(xí)分支限界法的設(shè)計(jì)策略。通過(guò)應(yīng)用范例學(xué)習(xí)分支限界法的設(shè)計(jì)策略。 （1）單源最短路徑問(wèn)題）單源最短路徑問(wèn)題 （2）裝載問(wèn)題；）裝載問(wèn)題； （3）布線問(wèn)題）布線問(wèn)題 （4）0-1背包問(wèn)題；背包問(wèn)題；（5）最大團(tuán)問(wèn)題；）最大團(tuán)問(wèn)題；（6）旅行售貨員問(wèn)題）旅行售貨員問(wèn)題（7）電路板排列問(wèn)題）電路板排列問(wèn)題（8）批處理作業(yè)調(diào)度問(wèn)

2、題）批處理作業(yè)調(diào)度問(wèn)題2021年10月26日星期二第6章 分支限界分支限界法法22021年10月26日星期二第6章 分支限界分支限界法法32021年10月26日星期二第6章 分支限界分支限界法法42021年10月26日星期二第6章 分支限界分支限界法法52021年10月26日星期二第6章 分支限界分支限界法法6W=(16,15,15)P=(45,25,25)C=30101116/45 30/5000112021年10月26日星期二第6章 分支限界分支限界法法72021年10月26日星期二第6章 分支限界分支限界法法82021年10月26日星期二第6章 分支限界分支限界法法92021年10月26

3、日星期二第6章 分支限界分支限界法法102021年10月26日星期二第6章 分支限界分支限界法法112021年10月26日星期二第6章 分支限界分支限界法法1232(n-1)!個(gè)葉結(jié)點(diǎn)個(gè)葉結(jié)點(diǎn) TSP問(wèn)題的解空間樹問(wèn)題的解空間樹143230201065443413ABEDCKJIHGFQPONML2434242559662632最優(yōu)解：最優(yōu)解：1 3 2 4 1 (結(jié)點(diǎn)結(jié)點(diǎn)N) 1 4 2 3 1 (結(jié)點(diǎn)結(jié)點(diǎn)K)E結(jié)點(diǎn)：結(jié)點(diǎn)： B C D E F G H I J K2021年10月26日星期二第6章 分支限界分支限界法法132021年10月26日星期二第6章 分支限界分支限界法法142021年

4、10月26日星期二第6章 分支限界分支限界法法156.3 6.3 裝載問(wèn)題裝載問(wèn)題問(wèn)題描述問(wèn)題描述: :n n個(gè)集裝箱裝到個(gè)集裝箱裝到2 2艘載重量分別為艘載重量分別為c1,c2c1,c2的的貨輪貨輪, ,其中集裝箱其中集裝箱i i的重量為的重量為wiwi且且 問(wèn)題要求找到一個(gè)合理的裝載方案可將這問(wèn)題要求找到一個(gè)合理的裝載方案可將這n個(gè)個(gè)貨貨箱箱裝上這裝上這2艘輪船。艘輪船。211ccwnii當(dāng)當(dāng) 時(shí)問(wèn)題等價(jià)于子集和問(wèn)題時(shí)問(wèn)題等價(jià)于子集和問(wèn)題; ; 當(dāng)當(dāng)c1=c2c1=c2且且 時(shí)時(shí)問(wèn)題等價(jià)于劃分問(wèn)題問(wèn)題等價(jià)于劃分問(wèn)題. .211ccwnii112cwnii若裝載問(wèn)題有解若裝載問(wèn)題有解, 采用

5、如下策略可得一個(gè)最優(yōu)裝載方案采用如下策略可得一個(gè)最優(yōu)裝載方案:(1)將第一艘輪船盡可能裝滿將第一艘輪船盡可能裝滿; (2)將剩余的將剩余的貨貨箱裝到第二艘輪船上。箱裝到第二艘輪船上。將第一艘船盡可能裝滿等價(jià)于如下將第一艘船盡可能裝滿等價(jià)于如下0-l背包問(wèn)題背包問(wèn)題:niiixw1m axm ax12cxwniii2021年10月26日星期二第6章 分支限界分支限界法法162021年10月26日星期二第6章 分支限界分支限界法法172021年10月26日星期二第6章 分支限界分支限界法法182021年10月26日星期二第6章 分支限界分支限界法法192021年10月26日星期二第6章 分支限界分

6、支限界法法202021年10月26日星期二第6章 分支限界分支限界法法212021年10月26日星期二第6章 分支限界分支限界法法222021年10月26日星期二第6章 分支限界分支限界法法232021年10月26日星期二第6章 分支限界分支限界法法242021年10月26日星期二第6章 分支限界分支限界法法252021年10月26日星期二第6章 分支限界分支限界法法26ACB 1 30 0 15ABC2021年10月26日星期二第6章 分支限界分支限界法法272021年10月26日星期二第6章 分支限界分支限界法法282021年10月26日星期二第6章 分支限界分支限界法法292021年10

7、月26日星期二第6章 分支限界分支限界法法302021年10月26日星期二第6章 分支限界分支限界法法312021年10月26日星期二第6章 分支限界分支限界法法322021年10月26日星期二第6章 分支限界分支限界法法332021年10月26日星期二第6章 分支限界分支限界法法342021年10月26日星期二第6章 分支限界分支限界法法352021年10月26日星期二第6章 分支限界分支限界法法362021年10月26日星期二第6章 分支限界分支限界法法372021年10月26日星期二第6章 分支限界分支限界法法382021年10月26日星期二第6章 分支限界分支限界法法392021年10

8、月26日星期二第6章 分支限界分支限界法法402021年10月26日星期二第6章 分支限界分支限界法法412021年10月26日星期二第6章 分支限界分支限界法法422021年10月26日星期二第6章 分支限界分支限界法法432021年10月26日星期二第6章 分支限界分支限界法法442021年10月26日星期二第6章 分支限界分支限界法法452021年10月26日星期二第6章 分支限界分支限界法法462021年10月26日星期二第6章 分支限界分支限界法法472021年10月26日星期二第6章 分支限界分支限界法法482021年10月26日星期二第6章 分支限界分支限界法法492021年10月26日星期二第6章 分支限界分支限界法法502021年10月26日星期二第6章 分支限界分支限界法法512021年10月26日星期二第6章 分支