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

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

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

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

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

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

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

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

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