分支限界法作業(yè)答案

1、分支限界法作業(yè)分支限界法作業(yè)1.旅行商問(wèn)題旅行商問(wèn)題設(shè)有n個(gè)城市，城市之間道路的長(zhǎng)度均大于或等于0，還可能是∞（對(duì)應(yīng)城市之間無(wú)交通線路）。一個(gè)旅行商從某個(gè)城市出發(fā)，要經(jīng)過(guò)每個(gè)城市一次且僅一次，最后回到出發(fā)的城市，問(wèn)他如何走才能使他走的路線最短？要求：使用矩陣歸約確定限界函數(shù)的方法，或者其他方法實(shí)現(xiàn)。分析：旅行商問(wèn)題對(duì)應(yīng)的解的元組為n元組，其中假設(shè)第一個(gè)城市為1，則n元組中未確定的為剩下n1個(gè)城市，元組為（1x2…xn）每個(gè)xi的取值為2

2、…n；約束條件為已經(jīng)經(jīng)過(guò)的城市不能再走，最后回到出發(fā)城市。目標(biāo)函數(shù)是巡回旅行路線長(zhǎng)度。利用矩陣歸約的方法確定限界函數(shù)：限界函數(shù)：限界函數(shù)：對(duì)任意路線上的結(jié)點(diǎn)d，設(shè)p是其前驅(qū)結(jié)點(diǎn)，則f(d)=g(d)h(d)，其中，g(d)=f(p)C’p[p][d]，h(d)=rd。C’p[p][d]是在p點(diǎn)規(guī)約后得到的矩陣中p點(diǎn)到d點(diǎn)的長(zhǎng)度值，rd為d點(diǎn)可以歸約掉的值。算法1：(葉子結(jié)點(diǎn)進(jìn)堆葉子結(jié)點(diǎn)進(jìn)堆)Input：圖：圖G；Output：從源點(diǎn)：從

3、源點(diǎn)1出發(fā)再回到出發(fā)再回到1頂點(diǎn)的最短巡回旅行路線。頂點(diǎn)的最短巡回旅行路線。1.設(shè)定目標(biāo)函數(shù)的限界設(shè)定目標(biāo)函數(shù)的限界down=r1，up=∞2.計(jì)算初始結(jié)點(diǎn)計(jì)算初始結(jié)點(diǎn)1的f(1)=r1，將初始結(jié)點(diǎn)插入最小堆，將初始結(jié)點(diǎn)插入最小堆H3.while(H≠Φ≠Φ)4.5.從H中做中做MIN的操作，用的操作，用p帶回相應(yīng)結(jié)點(diǎn)帶回相應(yīng)結(jié)點(diǎn)6.Ifp是葉子結(jié)點(diǎn)是葉子結(jié)點(diǎn)then7.輸出當(dāng)前最優(yōu)值，并從葉子結(jié)點(diǎn)沿輸出當(dāng)前最優(yōu)值，并從葉子結(jié)點(diǎn)沿par

4、ent指針輸出解，退出；指針輸出解，退出；8.Else9.產(chǎn)生產(chǎn)生p的所有滿足約束條件的后繼結(jié)點(diǎn)的所有滿足約束條件的后繼結(jié)點(diǎn)d(建樹(shù)，建立指向建樹(shù)，建立指向parent的指針的指針)并計(jì)算并計(jì)算f(d)；10.iff(d)upthen11.將d結(jié)點(diǎn)插入最小堆結(jié)點(diǎn)插入最小堆H中；中；12.ifd是葉子結(jié)點(diǎn)是葉子結(jié)點(diǎn)then13.up=f(p)14.刪除活結(jié)點(diǎn)表刪除活結(jié)點(diǎn)表(最小堆最小堆H)中函數(shù)值大于中函數(shù)值大于up值的結(jié)點(diǎn)；值的結(jié)點(diǎn)；1

5、5.16.17.18.2.批處理作業(yè)問(wèn)題批處理作業(yè)問(wèn)題設(shè)J1J2J3J4是四項(xiàng)待處理的作業(yè)，它們的工序一樣，即先在m1上處理，然后在m2上處理，最后在m3上處理，第i項(xiàng)作業(yè)在第j臺(tái)機(jī)器上的處理時(shí)間為tij。找一種最佳處理順序，使完成作業(yè)的總時(shí)間達(dá)到最短。分析：將問(wèn)題推廣到一般的n個(gè)作業(yè)，該問(wèn)題對(duì)應(yīng)的解的元組為n元組（x1x2…xn）每個(gè)xi的取值為1…n；約束條件為xi≠xj。目標(biāo)函數(shù)是sum3=maxsum2[n]sum3[n1]tn

6、3其中sum2[n]=maxsum1[n]sum2[n1]tn2Sum1[n]=sum1[n1]tn1。限界函數(shù)：設(shè)限界函數(shù)：設(shè)M是已經(jīng)安排好的作業(yè)集合，是已經(jīng)安排好的作業(yè)集合，M?12...n|M|=k?，F(xiàn)在要處理作業(yè)。現(xiàn)在要處理作業(yè)k1，有：，有：minsum2[k]1]sum1[kmax132MjkjjMiittdb?????????其中其中sum1[k1]=sum1[k]tk11sum2[k1]=maxsum1[k1]sum2[

7、k]tk12目標(biāo)函數(shù)的下限界目標(biāo)函數(shù)的下限界down=ikknjjinittt???????minmin31211Input：n個(gè)作業(yè)，及其在個(gè)作業(yè)，及其在3臺(tái)機(jī)器上的處理時(shí)間臺(tái)機(jī)器上的處理時(shí)間tij；Output：n個(gè)作業(yè)的最佳處理順序及其處理時(shí)間。個(gè)作業(yè)的最佳處理順序及其處理時(shí)間。1.設(shè)定目標(biāo)函數(shù)的限界設(shè)定目標(biāo)函數(shù)的限界down=，up=∞ikknjjinittt???????minmin312112.計(jì)算初始結(jié)點(diǎn)計(jì)算初始結(jié)點(diǎn)1的s

8、um1=0，sum2=0，db(1)=0，將初始結(jié)點(diǎn)插入最小堆，將初始結(jié)點(diǎn)插入最小堆H3.while(H≠Φ≠Φ)4.5.從H中做中做MIN的操作，用的操作，用p帶回相應(yīng)結(jié)點(diǎn)帶回相應(yīng)結(jié)點(diǎn)6.產(chǎn)生產(chǎn)生p的所有滿足約束條件的后繼結(jié)點(diǎn)的所有滿足約束條件的后繼結(jié)點(diǎn)d(建樹(shù)，建立指向建樹(shù)，建立指向parent的指針的指針)并計(jì)算并計(jì)算db(d)；7.while對(duì)每個(gè)結(jié)點(diǎn)對(duì)每個(gè)結(jié)點(diǎn)d8.ifdb(d)upthen9.ifd是葉子結(jié)點(diǎn)是葉子結(jié)點(diǎn)the