第6章分支限界法(文件)
【正文】 perSize實際上也是優(yōu)先隊列中元素的優(yōu)先級。 在左兒子結(jié)點處 ， 將頂點 i加入到當(dāng)前團(tuán)中 ， 并檢查該頂點與當(dāng)前團(tuán)中其他頂點之間是否有邊相連 。 28 最大團(tuán)問題 算法的 while循環(huán)的終止條件是遇到子集樹中的一個葉結(jié)點(即 n+1層結(jié)點 )成為當(dāng)前擴(kuò)展結(jié)點。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一次，最后回到駐地的路線，使總的路程 (或總旅費 )最小。周游路線的費用是這條路線上所有邊的費用之和。堆中每個結(jié)點的子樹費用的下界 lcost值是優(yōu)先隊列的優(yōu)先級。 算法的 while循環(huán)體完成對排列樹內(nèi)部結(jié)點的擴(kuò)展。由于當(dāng)前擴(kuò)展結(jié)點所相應(yīng)的路徑是 x[0:s]， 其可行兒子結(jié)點是從剩余頂點 x[s+1:n1]中選取的頂點 x[i]， 且 (x[s]， x[i])是所給有向圖 G中的一條邊。當(dāng) s=n1時，已找到的回路前綴是 x[0:n1]， 它已包含圖 G的所有 n個頂點。它們都不可能導(dǎo)致費用更小的回路。在 dowhile循環(huán)體內(nèi)算法依次從活結(jié)點優(yōu)先隊列中取出具有最小 cd值的結(jié)點作為當(dāng)前擴(kuò)展結(jié)點，并加以擴(kuò)展。 當(dāng) sn1時，算法依次產(chǎn)生當(dāng)前擴(kuò)展結(jié)點的所有兒子結(jié)點。 // 最后一塊電路板的密度 for (int j = 1。 bestd = (ld, )。 i++) { HeapNode node = new HeapNode(0, new int [m + 1], 0, new int [n + 1])。 36 電路板排列問題 int ld = 0。amp。 for (int j = 1。 [i] = []。每一個作業(yè)必須先由機(jī)器 1處理，然后再由機(jī)器 2處理。批處理作業(yè)調(diào)度問題要求對于給定的 n個作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時間和達(dá)到最小。 39 批處理作業(yè)問題 3. 算法描述 算法的 while循環(huán)完成對排列樹內(nèi)部結(jié)點的有序擴(kuò)展。當(dāng) bestc時更新當(dāng)前最優(yōu)值 bestc和相應(yīng)的當(dāng)前最優(yōu)解 bestx。而當(dāng) bb? bestc時，可將結(jié)點 node舍去。 i++) bestx[i] = [i]。 int [] f= new int [3]。 } (, ,i)。 if (bb bestc ) { HeapNode node=new HeapNode(enode,f,bb,n)。 i n。 for (int i = 0。對于當(dāng)前擴(kuò)展結(jié)點的每一個兒子結(jié)點 node， 計算出其相應(yīng)的完成時間和的下界 bb。 首先考慮 =n的情形，當(dāng)前擴(kuò)展結(jié)點 enode是排列樹中的葉結(jié)點。 同理如果選擇 Pk使 t2pk依非減序排列，則 S2取得極小值。 對于一個確定的作業(yè)調(diào)度，設(shè)是 Fji是作業(yè) i在機(jī)器 j上完成處理的時間。 } } } 算法描述 計算出每一個兒子結(jié)點的密度與 bestd進(jìn)行比較大于 bestd時加入隊列 37 批處理作業(yè)問題 1. 問題的描述 給定 n個作業(yè)的集合 J={J1,J2,… ,Jn}。 j++) [j] = [j]。 = (ld, )。 j = m。 j = m。 35 電路板排列問題 算法描述 else {// 產(chǎn)生當(dāng)前擴(kuò)展結(jié)點的所有兒子結(jié)點 for (int i = + 1。 j++) ld += board [[n]][j]。 當(dāng) bestd時，將該兒子結(jié)點 N插入到活結(jié)點優(yōu)先隊列中。 x表示相應(yīng)于該葉結(jié)點的電路板排列。 算法結(jié)束時返回找到的最小費用，相應(yīng)的最優(yōu)解由數(shù)組 v給出。此時該葉結(jié)點所相應(yīng)的回路的費用等于 cc和 lcost的值。 當(dāng)lcostbestc時，將這個可行兒子結(jié)點插入到活結(jié)點優(yōu)先隊列中。如果該葉結(jié)點相應(yīng)一條可行回路且費用小于當(dāng)前最小費用，則將該葉結(jié)點插入到優(yōu)先隊列中，否則舍去該葉結(jié)點。如果所給的有向圖中某個頂點沒有出邊，則該圖不可能有回路，算法即告結(jié)束。旅行售貨員問題要在圖 G中找出費用最小的周游路線。圖中各邊的費用（權(quán)）為正數(shù)。 此時活結(jié)點優(yōu)先隊列中剩余結(jié)點的 upperSize值均不超過當(dāng)前擴(kuò)展結(jié)點的 upperSize值，從而進(jìn)一步搜索不可能得到更大的團(tuán)，此時算法已找到一個最優(yōu)解。 接 著 繼 續(xù) 考 察 當(dāng) 前 擴(kuò) 展 結(jié) 點 的 右 兒 子 結(jié) 點 。 27 最大團(tuán)問題 3. 算法思想 子集樹的根結(jié)點是初始擴(kuò)展結(jié)點，對于這個特殊的擴(kuò)展結(jié)點，其 cliqueSize的值為 0。 {1， 4， 5}和 {2， 3， 5}也是 G的最大團(tuán)。 G的最大團(tuán)是指 G中所含頂點數(shù)最多的團(tuán)。 if (up = bestp) //檢查右兒子節(jié)點 addLiveNode(up,cp,cw,i + 1, enode, false)。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1