5-分支限界法

1、1,5 分支限界法,2,學(xué)習(xí)要點(diǎn)α-β剪枝技術(shù)分支限界法的剪枝搜索策略應(yīng)用范例（1）流動(dòng)推銷員問(wèn)題（2）單源最短路徑問(wèn)題（3）裝載問(wèn)題；（4）布線問(wèn)題；（5）0-1背包問(wèn)題；（6）同順序加工任務(wù)安排問(wèn)題（7）八數(shù)碼問(wèn)題,3,5.1 圖的廣度優(yōu)先遍歷 對(duì)于圖G=(V,E), 從任意一點(diǎn)r開始，依次檢查所有與r有關(guān)聯(lián)的邊(r,a1),(r, a2),…,(r,ak),當(dāng)上面k條邊檢查完畢后，再依次檢查所

2、有與a1,a2,…,ak相關(guān)聯(lián)的(a1,a11),(a1,a12),…,(a1,a1m),(a2,a21),(a2,a22),…,(a2,a2m)，……，(ak,ak1),(ak,ak2),…,(ak,akm)。依次類推，直到所有的邊被檢查，即所有頂點(diǎn)均被訪問(wèn)為止。,4,廣度優(yōu)先搜索的示例,廣度優(yōu)先搜索過(guò)程 廣度優(yōu)先生成樹,廣度優(yōu)先遍歷序列：ABCDEFGHI,5,廣度優(yōu)先搜索是一種分層的搜索過(guò)

3、程，每向前走一步可能訪問(wèn)一批頂點(diǎn)。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過(guò)程，其算法也不是遞歸的。為了實(shí)現(xiàn)逐層訪問(wèn)，算法中使用了一個(gè)隊(duì)列，以記憶正在訪問(wèn)的這一層和上一層的頂點(diǎn)，以便于向下一層訪問(wèn)。為避免重復(fù)訪問(wèn)，需要一個(gè)輔助數(shù)組 visited [ ]，給被訪問(wèn)過(guò)的頂點(diǎn)加標(biāo)記。,6,圖的廣度優(yōu)先搜索算法:templatevoid Graph ::BFS ( int v ) { int * visited = new

4、int[NumVertices]; for ( int i = 0; i q; q.EnQueue (v); //訪問(wèn) v, 進(jìn)隊(duì)列,7,while ( !q.IsEmpty ( ) ) { //隊(duì)空搜索結(jié)束 v = q.DeQueue ( ); //不空, 出隊(duì)列 int w = GetFirstNeighbor (v)

5、; //取頂點(diǎn) v 的第一個(gè)鄰接頂點(diǎn) w while ( w != -1 ) { //若鄰接頂點(diǎn) w 存在 if ( !visited[w] ) { //若該鄰接頂點(diǎn)未訪問(wèn)過(guò) cout << GetValue (w) << ‘ ’; //訪問(wèn) visited[w] = 1; q.EnQueue (w);

6、 //進(jìn)隊(duì) } w = GetNextNeighbor (v, w); //取頂點(diǎn) v 的排在 w 后面的下一鄰接頂點(diǎn) } //重復(fù)檢測(cè) v 的所有鄰接頂點(diǎn) } //外層循環(huán)，判隊(duì)列空否},如果使用鄰接表表示圖，則循環(huán)的總時(shí)間代價(jià)為 d0 + d1 + … + dn-1 = O(e)，其中的 di 是頂點(diǎn) i 的度。,如

7、果使用鄰接矩陣，則對(duì)于每一個(gè)被訪問(wèn)過(guò)的頂點(diǎn)，循環(huán)要檢測(cè)矩陣中的 n 個(gè)元素，總的時(shí)間代價(jià)為O(n2)。,8,5.2α-β剪枝技術(shù) α-β剪枝技術(shù)是一種技巧。比如，7根火柴，A、B兩人依次從中取出 1根 或 2根 ，但不能不取，最后一個(gè)將取盡的便是贏家。,9,5.3 分支限界法 通常

8、以廣度優(yōu)先或最小耗費(fèi)（最大效益）優(yōu)先的方式，搜索問(wèn)題的解空間樹。 可以這樣理解：分支定界法與廣度優(yōu)先方法的不同在于，往往不用遍歷整個(gè)圖，而是將不可能得到解 或 不可能得到最優(yōu)解的樹枝剪掉（即下界估計(jì)），從而提高搜索效率。 關(guān)鍵：下界估計(jì),10,5.3.1 分支限界法的基本思想,（1）求解目標(biāo)： 分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最

9、優(yōu)解。,（2）搜索方式： 以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。,11,分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹。,此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。,在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)

10、解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。,12,,5.3.2 分支限界法示例,（1）單源最短路徑問(wèn)題（2）布線問(wèn)題（3）八數(shù)碼問(wèn)題（4）對(duì)稱流動(dòng)推銷員問(wèn)題（5）非對(duì)稱流動(dòng)推銷員問(wèn)題,13,例1：?jiǎn)卧醋疃搪窂絾?wèn)題,1. 問(wèn)題描述,在下圖所給的有向圖G中，每一邊都有一個(gè)非負(fù)邊權(quán)。要求圖G的從源頂點(diǎn)s到目標(biāo)頂點(diǎn)t之間的最短路徑。,a=2b=3c=4d=7e=2f=9g=2h=2i=6j=7k=3l=5

11、m=1n=50=8p=2q=1r=2u=3,14,用優(yōu)先隊(duì)列式分支限界法解有向圖G的單源最短路徑問(wèn)題產(chǎn)生的解空間樹。其中，每一個(gè)結(jié)點(diǎn)旁邊的數(shù)字表示該結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。,,15,2. 算法思想,解單源最短路徑問(wèn)題的優(yōu)先隊(duì)列式分支限界法用一小頂堆來(lái)存儲(chǔ)活結(jié)點(diǎn)表。其優(yōu)先級(jí)是結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。,算法從圖G的源頂點(diǎn)s和空優(yōu)先隊(duì)列開始。結(jié)點(diǎn)s被擴(kuò)展后，它的兒子結(jié)點(diǎn)被依次插入堆中。此后，算法從堆中取出具有最小當(dāng)前路長(zhǎng)的結(jié)點(diǎn)作為當(dāng)前

12、擴(kuò)展結(jié)點(diǎn)，并依次檢查與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰的所有頂點(diǎn)。如果從當(dāng)前擴(kuò)展結(jié)點(diǎn)i到頂點(diǎn)j有邊可達(dá)，且從源出發(fā)，途經(jīng)頂點(diǎn)i再到頂點(diǎn)j的所相應(yīng)的路徑的長(zhǎng)度小于當(dāng)前最優(yōu)路徑長(zhǎng)度，則將該頂點(diǎn)作為活結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。這個(gè)結(jié)點(diǎn)的擴(kuò)展過(guò)程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時(shí)為止。,16,,a=2b=3c=4d=7e=2f=9g=2h=2i=6j=7k=3l=5m=1n=50=8p=2q=1r=2u=3,17,,,3. 剪

13、枝策略,在算法擴(kuò)展結(jié)點(diǎn)的過(guò)程中，一旦發(fā)現(xiàn)一個(gè)結(jié)點(diǎn)的下界不小于當(dāng)前找到的最短路長(zhǎng)，則算法剪去以該結(jié)點(diǎn)為根的子樹。 在算法中，利用結(jié)點(diǎn)間的控制關(guān)系進(jìn)行剪枝。從源頂點(diǎn)s出發(fā)，2條不同路徑到達(dá)圖G的同一頂點(diǎn)。由于兩條路徑的路長(zhǎng)不同，因此可以將路長(zhǎng)長(zhǎng)的路徑所對(duì)應(yīng)的樹中的結(jié)點(diǎn)為根的子樹剪去。,18,例2 布線問(wèn)題,1. 算法思想,解此問(wèn)題的隊(duì)列式分支限界法從起始位置a開始將它作為第一個(gè)擴(kuò)展結(jié)點(diǎn)。與該擴(kuò)展結(jié)點(diǎn)相鄰并且可達(dá)的方格成為可行結(jié)點(diǎn)被

14、加入到活結(jié)點(diǎn)隊(duì)列中，并且將這些方格標(biāo)記為1，即從起始方格a到這些方格的距離為1。,接著，算法從活結(jié)點(diǎn)隊(duì)列中取出隊(duì)首結(jié)點(diǎn)作為下一個(gè)擴(kuò)展結(jié)點(diǎn)，并將與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰且未標(biāo)記過(guò)的方格標(biāo)記為2，并存入活結(jié)點(diǎn)隊(duì)列。這個(gè)過(guò)程一直繼續(xù)到算法搜索到目標(biāo)方格b或活結(jié)點(diǎn)隊(duì)列為空時(shí)為止。即加入剪枝的廣度優(yōu)先搜索。,19,2. 示例,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

15、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,20,bool findpath(position start, Position finish, int &pathlen,position *&path) { //計(jì)算從起點(diǎn)位置start到目標(biāo)位置finish的最短布線路徑 // 找到最短路徑返回true,否則返回false if

16、((start.row==finish.row)&& (start.col==finish.col)) { pathlen=0; trturn true; },for (int i = 0; i <= m+1; i++) grid[0][i] = grid[n+1][i] = 1; // 頂部和底部 for (int i = 0; i <= n+1; i++) grid[

17、i][0] = grid[i][m+1] = 1; // 左翼和右翼,設(shè)置邊界的圍墻,21,position offset[4]; offset[0].row = 0; offset[0].col = 1; // 右 offset[1].row = 1; offset[1].col = 0; // 下 offset[2].row = 0; offset[2].col = -1; // 左 offset[3].ro

18、w = -1; offset[3].col = 0; // 上,定義移動(dòng)方向的相對(duì)位移,int numofnbrs=4; here.row=start.row; here.col=start.col; grid[start.row][start.col] = 2; //標(biāo)記可達(dá)方格位置 linkedqueue Q;,22,do { // 標(biāo)記可達(dá)相鄰方格 for (int i = 0; i

19、< NumOfNbrs; i++) { nbr.row = here.row + offset[i].row; nbr.col = here.col + offset[i].col; if (grid[nbr.row][nbr.col] == 0) { // 該方格未標(biāo)記 grid[nbr.r

20、ow][nbr.col] = grid[here.row][here.col] + 1; if ((nbr.row == finish.row) && (nbr.col == finish.col)) break; // 完成布線 Q.Add(nbr);

21、 } },,找到目標(biāo)位置后，可以通過(guò)回溯方法找到這條最短路徑。,23,// 是否達(dá)到目標(biāo)位置 if ((nbr.row == finish.row) && (nbr.col == finish.col)) break; // 完成布線 // 隊(duì)列 為空？ if (Q.Isempty()) return

22、 false; // 無(wú)解 Q.delete(here); //取下一個(gè)擴(kuò)展結(jié)點(diǎn)} while (true);,,找到目標(biāo)位置后，可以通過(guò)回溯方法找到這條最短路徑。,24,在 3*3 的方格棋盤上，分別放置了標(biāo)有數(shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)S0，目標(biāo)狀態(tài)Sg。 可以使用的操作有： 空格左移，空格上移，空相右移，空格下移 即只允許把位于空格左、上、右、下方的牌移入空格。

23、 尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解路徑。,2 8 347 6 5,S0,1 2 38 47 6 5,Sg,,例3 八數(shù)碼難題,25,Sg,由圖可以看出，解的路徑是： S0 →3 → 8 → 16 → 26(Sg),,,,,26,設(shè)估價(jià)函數(shù)為: f（n）=d（n）＋W（n）其中，d（n）表示節(jié)點(diǎn) n在搜索樹中的深度； w（n）表示節(jié)點(diǎn) n中“不在位”的數(shù)碼個(gè)數(shù)。

24、 取g（n）=d（n），h（n）=W（n）。它說(shuō)明是用從S0到n的路徑上的單位代價(jià)表示實(shí)際代價(jià)，用n中“不在位”的數(shù)碼個(gè)數(shù)作為啟發(fā)信息。一般來(lái)說(shuō)，某節(jié)點(diǎn)中的“不在位”的數(shù)碼個(gè)數(shù)越多，說(shuō)明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn)。 對(duì)初始節(jié)點(diǎn) S0，由于 d（S0）= 0， W（S0）= 3，因此有 f（S0）=0＋3=3  這個(gè)例子僅是為了說(shuō)明估價(jià)函數(shù)的

25、含義及估價(jià)函數(shù)值的計(jì)算。在問(wèn)題搜索過(guò)程中，除了需要計(jì)算初始節(jié)點(diǎn)的估價(jià)函數(shù)之外，更多的是要計(jì)算新生成節(jié)點(diǎn)的估價(jià)函數(shù)值。,,27,1．全局擇優(yōu)搜索,二. A算法,2.3 狀態(tài)空間的啟發(fā)式搜索,每個(gè)節(jié)點(diǎn)旁邊的數(shù)字是該節(jié)點(diǎn)的估價(jià)函數(shù)值。例如，對(duì)節(jié)點(diǎn)S2，其估價(jià)函數(shù)值的計(jì)算為 f（S2）=d（S2）＋W（S2）=1＋3=4 從該圖還可以看出，該問(wèn)題的解為： S0→S2 →

26、 S7 → S9 → Sg,,S9 4,28,例4 對(duì)稱流動(dòng)推銷員問(wèn)題 ∞ 14 1 16 2 14 ∞ 25 2 3 1 25 ∞ 9 9

27、 16 1 9 ∞ 6 2 3 9 6 ∞,,,,,,Dmn=,,,問(wèn)題：從某一城市出發(fā)，遍歷各城市一次且僅一次，最后返 回原地，求最短路徑。（1）取5個(gè)最小邊，求和。 d13+d15+d24+d25+

28、d45=14（2）用34替換15，求和。 d13+d34+d24+d25+d45=21（3）用34替換25，求和。 d13+d15+d24+d34+d45=20（4）用34替換45，求和。 d13+d15+d24+d25+d34=17,29,,（13，15，24，25，45）,14,（13，34，24，25，45）,21,（13，15，24，34，45）,20,選擇45,,,,,,,（13，15，24，25，34）,17,,,,選

29、擇15,選擇25,不選25,不選45,不選15,∞ 14 1 16 2 14 ∞ 25 2 3 1 25 ∞ 9 9

30、16 1 9 ∞ 6 2 3 9 6 ∞,,,Dmn=,,,,,30,∞ 14 30 5 6 10 ∞ 11 4 3 4

31、6 ∞ 5 6 15 10 13 ∞ 2 13 3 4 11 ∞,,,,,Dmn =,,,問(wèn)題：從某一城市出發(fā)，遍歷各城市一次且僅一次，最后返回原地，求最短路徑。,,,,例5 非對(duì)稱流動(dòng)推銷員問(wèn)題,31,,,,方法：對(duì)D的每行減去該行的最小元，或每列

32、減去該列的最小元，的一新矩陣，使每行每列至少有一個(gè)0元素。比如：第1行減5,第2行減3,……,32,,,,由于D[1][4]=0, 所以選取v1?v4的路徑。排除v1?其他頂點(diǎn)，封鎖v4?v1。,33,,,,與取v1?v4相反，選取v4?v1的路徑。排除v4?其他頂點(diǎn)，封鎖v1?v4。,34,,,,因?yàn)镈[4][5]=0, 所以選取v4?v5的路徑。,35,,,,取v4?v5相反，排除D[4][5] 。取v5?v4。,36,,,,因?yàn)?/p>