第6章分支限界法-全文預(yù)覽
【正文】 //b為上界函數(shù) 24 01背包問題 while (i != n + 1) {// 非葉結(jié)點 double wt = cw + w[i]。 //w[i]表示 i所占空間 b += p[i]。當(dāng)擴展到葉節(jié)點時為問題的最優(yōu)值。 在下面描述的優(yōu)先隊列分支限界法中，節(jié)點的優(yōu)先級由已裝袋的物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。 ( == )) break。 = + offset[i].col。 // 頂部和底部 grid[i][0] = grid[i][size + 1] = 1。 // 左 offset[3] = new Position(1, 0)。 20 布線問題 Position [] offset = new Position [4]。 與該擴展結(jié)點相鄰并且可達的方格成為可行結(jié)點被加入到活結(jié)點隊列中 ， 并且將這些方格標記為 1， 即從起始方格 a到這些方格的距離為 1。子集樹中葉結(jié)點所相應(yīng)的載重量與其優(yōu)先級相同。 } 18 裝載問題 5. 優(yōu)先隊列式分支限界法 解裝載問題的優(yōu)先隊列式分支限界法用最大優(yōu)先隊列存儲活結(jié)點表。 // 構(gòu)造當(dāng)前最優(yōu)解 for (int j = n。 private static class QNode { QNode parent。 i n) // 可能含最優(yōu)解 (new Integer(ew))。 if (wt = c) { // 可行結(jié)點 if (wt bestw) bestw = wt。設(shè) bestw是當(dāng)前最優(yōu)解； ew是當(dāng)前擴展結(jié)點所相應(yīng)的重量； r是剩余集裝箱的重量。 (new Integer(1))。 13 裝載問題 2. 隊列式分支限界法 while (true) { if (ew + w[i] = c) enQueue(ew + w[i], i)。 2個兒子結(jié)點都產(chǎn)生后 ， 當(dāng)前擴展結(jié)點被舍棄 。 (1)首先將第一艘輪船盡可能裝滿； (2)將剩余的集裝箱裝上第二艘輪船 。 else enode = (HeapNode) ()。 p[j]=。j=n。 在算法中 ， 利用結(jié)點間的控制關(guān)系進行剪枝 。此后，算法從堆中取出具有最小當(dāng)前路長的結(jié)點作為當(dāng)前擴展結(jié)點，并依次檢查與當(dāng)前擴展結(jié)點相鄰的所有頂點。 8 單源最短路徑問題 2. 算法思想 解單源最短路徑問題的優(yōu)先隊列式分支限界法用一極小堆來存儲活結(jié)點表。 6 單源最短路徑問題 1. 問題描述 下面以一個例子來說明單源最短路徑問題： 在下圖所給的有向圖 G中，每一邊都有一個非負邊權(quán)。 此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴展結(jié)點，并重復(fù)上述結(jié)點擴展過程。 4 分支限界法的基本思想 2. 分支限界法基本思想 分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。 （ 2）搜索方式的不同： 回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。在這些兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。 （ 2）優(yōu)先隊列式分支限界法 按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當(dāng)前擴展節(jié)點。其中，每一個結(jié)點旁邊的數(shù)字表示該結(jié)點所對應(yīng)的當(dāng)前路長。結(jié)點 s被擴展后，它的兒子結(jié)點被依次插入堆中。 9 單源最短路徑問題 3. 剪枝策略 在算法擴展結(jié)點的過程中 ， 一旦發(fā)現(xiàn)一個結(jié)點的下界不小于當(dāng)前找到的最短路長 ， 則算法剪去以該結(jié)點為根的子樹 。 10 單源最短路徑問題 while (true) { // 搜索問題的解空間 for (int j=1。 +a[][j] dist[j]) { // 頂點 i到頂點 j可達 ， 且滿足控制約束 dist[j]=+a[][j]。 // 加入活結(jié)點優(yōu)先隊列 } if (()) break。 容易證明：如果一個給定裝載問題有解 ， 則采用下面的策略可得到最優(yōu)裝載方案 。 然后將其右兒子結(jié)點加入到活結(jié)點隊列中 (右兒子結(jié)點一定是可行結(jié)點 )。 如果隊列非空 ， 則將尾部標記 1加入活結(jié)點隊列 ， 算法開始處理下一層的活結(jié)點 。 // 取下一擴展結(jié)點 if (ew == 1) {
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1