第6章分支限界法(存儲版)
【正文】 27 最大團(tuán)問題 3. 算法思想 子集樹的根結(jié)點(diǎn)是初始擴(kuò)展結(jié)點(diǎn)，對于這個(gè)特殊的擴(kuò)展結(jié)點(diǎn)，其 cliqueSize的值為 0。 此時(shí)活結(jié)點(diǎn)優(yōu)先隊(duì)列中剩余結(jié)點(diǎn)的 upperSize值均不超過當(dāng)前擴(kuò)展結(jié)點(diǎn)的 upperSize值，從而進(jìn)一步搜索不可能得到更大的團(tuán)，此時(shí)算法已找到一個(gè)最優(yōu)解。旅行售貨員問題要在圖 G中找出費(fèi)用最小的周游路線。如果該葉結(jié)點(diǎn)相應(yīng)一條可行回路且費(fèi)用小于當(dāng)前最小費(fèi)用，則將該葉結(jié)點(diǎn)插入到優(yōu)先隊(duì)列中，否則舍去該葉結(jié)點(diǎn)。此時(shí)該葉結(jié)點(diǎn)所相應(yīng)的回路的費(fèi)用等于 cc和 lcost的值。 x表示相應(yīng)于該葉結(jié)點(diǎn)的電路板排列。 j++) ld += board [[n]][j]。 j = m。 = (ld, )。 } } } 算法描述 計(jì)算出每一個(gè)兒子結(jié)點(diǎn)的密度與 bestd進(jìn)行比較大于 bestd時(shí)加入隊(duì)列 37 批處理作業(yè)問題 1. 問題的描述 給定 n個(gè)作業(yè)的集合 J={J1,J2,… ,Jn}。 同理如果選擇 Pk使 t2pk依非減序排列，則 S2取得極小值。對于當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子結(jié)點(diǎn) node， 計(jì)算出其相應(yīng)的完成時(shí)間和的下界 bb。 i n。 } (, ,i)。 i++) bestx[i] = [i]。當(dāng) bestc時(shí)更新當(dāng)前最優(yōu)值 bestc和相應(yīng)的當(dāng)前最優(yōu)解 bestx。批處理作業(yè)調(diào)度問題要求對于給定的 n個(gè)作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。 [i] = []。amp。 i++) { HeapNode node = new HeapNode(0, new int [m + 1], 0, new int [n + 1])。 // 最后一塊電路板的密度 for (int j = 1。在 dowhile循環(huán)體內(nèi)算法依次從活結(jié)點(diǎn)優(yōu)先隊(duì)列中取出具有最小 cd值的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并加以擴(kuò)展。當(dāng) s=n1時(shí)，已找到的回路前綴是 x[0:n1]， 它已包含圖 G的所有 n個(gè)頂點(diǎn)。 算法的 while循環(huán)體完成對排列樹內(nèi)部結(jié)點(diǎn)的擴(kuò)展。周游路線的費(fèi)用是這條路線上所有邊的費(fèi)用之和。 28 最大團(tuán)問題 算法的 while循環(huán)的終止條件是遇到子集樹中的一個(gè)葉結(jié)點(diǎn)(即 n+1層結(jié)點(diǎn) )成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。 在此優(yōu)先隊(duì)列式分支限界法中， upperSize實(shí)際上也是優(yōu)先隊(duì)列中元素的優(yōu)先級。 如果 U?V， 且對任意 u， v?U有 (u，v)?E， 則稱 U是 G的完全子圖。 } if (i = n) b += p[i] / w[i] * cleft。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將它加入到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。 if (( == ) amp。 i = size + 1。 這個(gè)過程一直繼續(xù)到算法搜索到目標(biāo)方格b或活結(jié)點(diǎn)隊(duì)列為空時(shí)為止 。 優(yōu)先隊(duì)列中優(yōu)先級最大的活結(jié)點(diǎn)成為下一個(gè)擴(kuò)展結(jié)點(diǎn)。 // 左兒子標(biāo)志 int weight。 } 提前更新bestw // 檢查右兒子結(jié)點(diǎn) if (ew + r bestw amp。 // 取下一擴(kuò)展結(jié)點(diǎn) i++。 當(dāng)取出的元素是 1時(shí) ， 再判斷當(dāng)前隊(duì)列是否為空 。如果有，找出一種裝載方案。amp。這個(gè)結(jié)點(diǎn)的擴(kuò)展過程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時(shí)為止。 7 單源最短路徑問題 下圖是用優(yōu)先隊(duì)列式分支限界法解有向圖 G的單源最短路徑問題產(chǎn)生的解空間樹。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。 在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展結(jié)點(diǎn)。要求圖 G的從源頂點(diǎn) s到目標(biāo)頂點(diǎn) t之間的最短路徑。如果從當(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)先隊(duì)列中。j++) if(a[][j] amp。 } 頂點(diǎn) I和 j間有邊，且此路徑長小于原先從原點(diǎn)到 j的路徑長 11 裝載問題 1. 問題描述 有一批共個(gè)集裝箱要裝上 2艘載重量分別為 C1和 C2的輪船 ， 其中集 裝箱 i的重量為 Wi， 且 211ccwnii ????裝載問題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上這 2艘輪船。 活結(jié)點(diǎn)隊(duì)列中的隊(duì)首元素被取出作為當(dāng)前擴(kuò)展結(jié)點(diǎn) ， 由于隊(duì)列中每一層結(jié)點(diǎn)之后都有一個(gè)尾部標(biāo)記 1， 故在取隊(duì)首元素時(shí) ， 活結(jié)點(diǎn)隊(duì)列一定不空 。 // 同層結(jié)點(diǎn)尾部標(biāo)志 ew = ((Integer) ()).intValue()。 // 加入活結(jié)點(diǎn)隊(duì)列 if (i n) (new Integer(wt))。 // 父結(jié)點(diǎn)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1