5-分支限界法

1、1,5 分支限界法,2,學(xué)習(xí)要點(diǎn)α-β剪枝技術(shù)分支限界法的剪枝搜索策略應(yīng)用范例（1）流動推銷員問題（2）單源最短路徑問題（3）裝載問題；（4）布線問題；（5）0-1背包問題；（6）同順序加工任務(wù)安排問題（7）八數(shù)碼問題,3,5.1 圖的廣度優(yōu)先遍歷 對于圖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)均被訪問為止。,4,廣度優(yōu)先搜索的示例,廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹,廣度優(yōu)先遍歷序列：ABCDEFGHI,5,廣度優(yōu)先搜索是一種分層的搜索過

3、程，每向前走一步可能訪問一批頂點(diǎn)。因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。為了實現(xiàn)逐層訪問，算法中使用了一個隊列，以記憶正在訪問的這一層和上一層的頂點(diǎn)，以便于向下一層訪問。為避免重復(fù)訪問，需要一個輔助數(shù)組 visited [ ]，給被訪問過的頂點(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); //訪問 v, 進(jìn)隊列,7,while ( !q.IsEmpty ( ) ) { //隊空搜索結(jié)束 v = q.DeQueue ( ); //不空, 出隊列 int w = GetFirstNeighbor (v)

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

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

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

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

9、優(yōu)解。,（2）搜索方式： 以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。,11,分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。,此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時為止。,在分支限界法中，每一個活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展結(jié)點(diǎn)?；罱Y(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）單源最短路徑問題（2）布線問題（3）八數(shù)碼問題（4）對稱流動推銷員問題（5）非對稱流動推銷員問題,13,例1：單源最短路徑問題,1. 問題描述,在下圖所給的有向圖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)先隊列式分支限界法解有向圖G的單源最短路徑問題產(chǎn)生的解空間樹。其中，每一個結(jié)點(diǎn)旁邊的數(shù)字表示該結(jié)點(diǎn)所對應(yīng)的當(dāng)前路長。,,15,2. 算法思想,解單源最短路徑問題的優(yōu)先隊列式分支限界法用一小頂堆來存儲活結(jié)點(diǎn)表。其優(yōu)先級是結(jié)點(diǎn)所對應(yīng)的當(dāng)前路長。,算法從圖G的源頂點(diǎn)s和空優(yōu)先隊列開始。結(jié)點(diǎn)s被擴(kuò)展后，它的兒子結(jié)點(diǎn)被依次插入堆中。此后，算法從堆中取出具有最小當(dā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)的路徑的長度小于當(dāng)前最優(yōu)路徑長度，則將該頂點(diǎn)作為活結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊列中。這個結(jié)點(diǎn)的擴(kuò)展過程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊列為空時為止。,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)的過程中，一旦發(fā)現(xiàn)一個結(jié)點(diǎn)的下界不小于當(dāng)前找到的最短路長，則算法剪去以該結(jié)點(diǎn)為根的子樹。 在算法中，利用結(jié)點(diǎn)間的控制關(guān)系進(jìn)行剪枝。從源頂點(diǎn)s出發(fā)，2條不同路徑到達(dá)圖G的同一頂點(diǎn)。由于兩條路徑的路長不同，因此可以將路長長的路徑所對應(yīng)的樹中的結(jié)點(diǎn)為根的子樹剪去。,18,例2 布線問題,1. 算法思想,解此問題的隊列式分支限界法從起始位置a開始將它作為第一個擴(kuò)展結(jié)點(diǎn)。與該擴(kuò)展結(jié)點(diǎn)相鄰并且可達(dá)的方格成為可行結(jié)點(diǎn)被

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

15、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,20,bool findpath(position start, Position finish, int &pathlen,position *&path) { //計算從起點(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; // 上,定義移動方向的相對位移,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)位置后，可以通過回溯方法找到這條最短路徑。,23,// 是否達(dá)到目標(biāo)位置 if ((nbr.row == finish.row) && (nbr.col == finish.col)) break; // 完成布線 // 隊列 為空？ if (Q.Isempty()) return

22、 false; // 無解 Q.delete(here); //取下一個擴(kuò)展結(jié)點(diǎn)} while (true);,,找到目標(biāo)位置后，可以通過回溯方法找到這條最短路徑。,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è)估價函數(shù)為: f（n）=d（n）＋W（n）其中，d（n）表示節(jié)點(diǎn) n在搜索樹中的深度； w（n）表示節(jié)點(diǎn) n中“不在位”的數(shù)碼個數(shù)。

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

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

26、 S7 → S9 → Sg,,S9 4,28,例4 對稱流動推銷員問題 ∞ 14 1 16 2 14 ∞ 25 2 3 1 25 ∞ 9 9

27、 16 1 9 ∞ 6 2 3 9 6 ∞,,,,,,Dmn=,,,問題：從某一城市出發(fā)，遍歷各城市一次且僅一次，最后返 回原地，求最短路徑。（1）取5個最小邊，求和。 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 =,,,問題：從某一城市出發(fā)，遍歷各城市一次且僅一次，最后返回原地，求最短路徑。,,,,例5 非對稱流動推銷員問題,31,,,,方法：對D的每行減去該行的最小元，或每列

32、減去該列的最小元，的一新矩陣，使每行每列至少有一個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,,,,因為D[4][5]=0, 所以選取v4?v5的路徑。,35,,,,取v4?v5相反，排除D[4][5] 。取v5?v4。,36,,,,因為