第6章分支限界法-預(yù)覽頁(yè)
【正文】 if (()) return bestw。 // 進(jìn)入下一層 } } 14 裝載問(wèn)題 3. 算法的改進(jìn) 節(jié)點(diǎn)的左子樹表示將此集裝箱裝上船，右子樹表示不將此集裝箱裝上船。 15 裝載問(wèn)題 3. 算法的改進(jìn) // 檢查左兒子結(jié)點(diǎn) int wt = ew + w[i]。amp。為此目的，可在每個(gè)結(jié)點(diǎn)處設(shè)置指向其父結(jié)點(diǎn)的指針，并設(shè)置左、右兒子標(biāo)志。 // 結(jié)點(diǎn)所相應(yīng)的載重量 17 裝載問(wèn)題 找到最優(yōu)值后，可以根據(jù) parent回溯到根節(jié)點(diǎn)，找到最優(yōu)解。 e = 。以結(jié)點(diǎn) x為根的子樹中所有結(jié)點(diǎn)相應(yīng)的路徑的載重量不超過(guò)它的優(yōu)先級(jí)。 19 布線問(wèn)題 算法的思想 解此問(wèn)題的隊(duì)列式分支限界法從起始位置 a開始將它作為第一個(gè)擴(kuò)展結(jié)點(diǎn) 。 即加入剪枝的廣度優(yōu)先搜索 。 // 下 offset[2] = new Position(0, 1)。 i++) { grid[0][i] = grid[size + 1][i] = 1。 i++) { = + offset[i].row。amp。 22 01背包問(wèn)題 ? 算法的思想 首先，要對(duì)輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量?jī)r(jià)值從大到小進(jìn)行排列。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才將它加入子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列。 w[i] = cleft) // n表示物品總數(shù) ， cleft為剩余空間 { cleft = w[i]。 // 裝填剩余容量裝滿背包 return b。 } up = bound(i + 1)。 G的完全子圖 U是 G的團(tuán)當(dāng)且僅當(dāng) U不包含在 G的更大的完全子圖中。 {1， 2，5}是 G的最大團(tuán)。算法總是從活結(jié)點(diǎn)優(yōu)先隊(duì)列中抽取具有最大 upperSize值的元素作為下一個(gè)擴(kuò)展元素。 當(dāng)頂點(diǎn) i與當(dāng)前團(tuán)中所有頂點(diǎn)之間都有邊相連 ， 則相應(yīng)的左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn) ， 將它加入到子集樹中并插入活結(jié)點(diǎn)優(yōu)先隊(duì)列 ， 否則就不是可行結(jié)點(diǎn) 。 對(duì)于子集樹中的葉結(jié)點(diǎn)，有 upperSize＝ cliqueSize。 路線是一個(gè)帶權(quán)圖。 旅行售貨員問(wèn)題的解空間可以組織成一棵樹，從樹的根結(jié)點(diǎn)到任一葉結(jié)點(diǎn)的路徑定義了圖的一條周游路線。接著算法計(jì)算出圖中每個(gè)頂點(diǎn)的最小費(fèi)用出邊并用 minout記錄。對(duì)于當(dāng)前擴(kuò)展結(jié)點(diǎn)，算法分 2種情況進(jìn)行處理： 31 旅行售貨員問(wèn)題 首先考慮 s=n2的情形，此時(shí)當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列樹中某個(gè)葉結(jié)點(diǎn)的父結(jié)點(diǎn)。對(duì)于當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)可行兒子結(jié)點(diǎn)，計(jì)算出其前綴 (x[0:s]， x[i])的費(fèi)用 cc和相應(yīng)的下界 lcost。因此，當(dāng) s=n1時(shí)，相應(yīng)的擴(kuò)展結(jié)點(diǎn)表示一個(gè)葉結(jié)點(diǎn)。因此已找到的葉結(jié)點(diǎn)所相應(yīng)的回路是一個(gè)最小費(fèi)用旅行售貨員回路，算法可以結(jié)束。 首先考慮 s=n1的情形，當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列樹中的一個(gè)葉結(jié)點(diǎn)的父結(jié)點(diǎn)。對(duì)于當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子結(jié)點(diǎn) node， 計(jì)算出其相應(yīng)的密度。 j = m。 } } S=n1的情況，計(jì)算出此時(shí)的密度和 bestd進(jìn)行比較。 for (int j = 1。 // 新插入電路板的密度 for (int j = 1。 total[j] != [j]) ld++。 j = n。 (node)。作業(yè) Ji需要機(jī)器 j的處理時(shí)間為 tji， i=1,2,… ,n；j=1,2。 38 批處理作業(yè)問(wèn)題 2. 限界函數(shù) 在結(jié)點(diǎn) E處相應(yīng)子樹中葉結(jié)點(diǎn)完成時(shí)間和的下界是： },m a x { 212 SSFfMii ?? ??注意到如果選擇 Pk， 使 t1pk在 k=r+1時(shí)依非減序排列， S1則取得極小值 。在 while循環(huán)體內(nèi)算法依次從活結(jié)點(diǎn)優(yōu)先隊(duì)列中取出具有最小 bb值（完成時(shí)間和下界）的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并加以擴(kuò)展。 當(dāng) n時(shí)，算法依次產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn) enode的所有兒子結(jié)點(diǎn)。 40 批處理作業(yè)問(wèn)題 do { if ( == n ) {// 葉結(jié)點(diǎn) if ( bestc) { bestc = 。 } } 3. 算法描述 當(dāng) bestc時(shí)，更新當(dāng)前最優(yōu)值 beste和相應(yīng)的最優(yōu)解 bestx 41 批處理作業(yè)問(wèn)題 3. 算法描述 else // 產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的兒子結(jié)點(diǎn) for (int i = 。 int bb=bound(enode,f)。 } // 完成結(jié)點(diǎn)擴(kuò)展 當(dāng) bbbestc時(shí)，將兒子結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1