第6章分支限界法(編輯修改稿)
2024-10-22 19:17 本頁面
【文章內(nèi)容簡介】 相鄰且未標記過的方格標記為 2，并存入活結(jié)點隊列 。 這個過程一直繼續(xù)到算法搜索到目標方格b或活結(jié)點隊列為空時為止 。 即加入剪枝的廣度優(yōu)先搜索 。 20 布線問題 Position [] offset = new Position [4]。 offset[0] = new Position(0, 1)。 // 右 offset[1] = new Position(1, 0)。 // 下 offset[2] = new Position(0, 1)。 // 左 offset[3] = new Position(1, 0)。 // 上 定義移動方向的相對位移 for (int i = 0。 i = size + 1。 i++) { grid[0][i] = grid[size + 1][i] = 1。 // 頂部和底部 grid[i][0] = grid[i][size + 1] = 1。 // 左翼和右翼 } 設置邊界的圍墻 21 布線問題 for (int i = 0。 i numOfNbrs。 i++) { = + offset[i].row。 = + offset[i].col。 if (grid[][] == 0) { // 該方格未標記 grid[][] = grid[][] + 1。 if (( == ) amp。amp。 ( == )) break。 (new Position(, ))。 } } 找到目標位置后，可以通過回溯方法找到這條最短路徑。 22 01背包問題 ? 算法的思想 首先，要對輸入數(shù)據(jù)進行預處理，將各物品依其單位重量價值從大到小進行排列。 在下面描述的優(yōu)先隊列分支限界法中，節(jié)點的優(yōu)先級由已裝袋的物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。 算法首先檢查當前擴展結(jié)點的左兒子結(jié)點的可行性。如果該左兒子結(jié)點是可行結(jié)點，則將它加入到子集樹和活結(jié)點優(yōu)先隊列中。當前擴展結(jié)點的右兒子結(jié)點一定是可行結(jié)點，僅當右兒子結(jié)點滿足上界約束時才將它加入子集樹和活結(jié)點優(yōu)先隊列。當擴展到葉節(jié)點時為問題的最優(yōu)值。 23 01背包問題 上界函數(shù) while (i = n amp。amp。 w[i] = cleft) // n表示物品總數(shù) ， cleft為剩余空間 { cleft = w[i]。 //w[i]表示 i所占空間 b += p[i]。 //p[i]表示 i的價值 i++。 } if (i = n) b += p[i] / w[i] * cleft。 // 裝填剩余容量裝滿背包 return b。 //b為上界函數(shù) 24 01背包問題 while (i != n + 1) {// 非葉結(jié)點 double wt = cw + w[i]。 if (wt = c) {// 左兒子結(jié)點為可行結(jié)點 if (cp + p[i] bestp) bestp = cp + p[i]。 addLiveNode(up,cp + p[i],cw + w[i],i + 1, enode, true)。 } up = bound(i + 1)。 if (up = bestp) //檢查右兒子節(jié)點 addLiveNode(up,cp,cw,i + 1, enode, false)。 // 取下一個擴展節(jié)點 （ 略 ） } 分支限界搜索過程 25 最大團問題 1. 問題描述 給定無向圖 G=(V， E)。 如果 U?V， 且對任意 u， v?U有 (u，v)?E， 則稱 U是 G的完全子圖。 G的完全子圖 U是 G的團當且僅當 U不包含在 G的更大的完全子圖中。 G的最大團是指 G中所含頂點數(shù)最多的團。 下圖 G中，子集 {1， 2}是 G的大小為 2的完全子圖。這個完全子圖不是團，因為它被 G的更大的完全子圖 {1， 2， 5}包含。 {1， 2，5}是 G的最大團。 {1， 4， 5}和 {2， 3， 5}也是 G的最大團。 26 最大團問題 2. 上界函數(shù) 用變量 cliqueSize表示與該結(jié)點相應的團的頂點數(shù)； level表示結(jié)點在子集空間樹中所處的層次；用 cliqueSize +nlevel+1作為頂點數(shù)上界 upperSize的值。 在此優(yōu)先隊列式分支限界法中，
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1