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