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

《分支限界法作業(yè)答案》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、分支限界法作業(yè)1.旅行商問(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元組中未確定的為剩下n-1個(gè)城市，元組為（1,x2,…,xn）,每個(gè)xi的取值為{2,…,n}；約束條件為已經(jīng)經(jīng)過(guò)的城市不能再走，最后回到出發(fā)城市。目標(biāo)函數(shù)是巡回旅行路

2、線長(zhǎng)度。利用矩陣歸約的方法確定限界函數(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)堆)Input：圖G；Output：從源點(diǎn)1出發(fā)再回到1頂點(diǎn)的最短巡回旅行路線。1.設(shè)定目標(biāo)函數(shù)的限界down=r1，up=∞2.計(jì)算初始結(jié)點(diǎn)1的f(1)=r1，將初始結(jié)點(diǎn)插入最小堆H;3.while(H≠Φ)4.{5

3、.從H中做DELETEMIN的操作，用p帶回相應(yīng)結(jié)點(diǎn);6.Ifp是葉子結(jié)點(diǎn)then7.輸出當(dāng)前最優(yōu)值，并從葉子結(jié)點(diǎn)沿parent指針輸出解，退出；8.Else9.{產(chǎn)生p的所有滿足約束條件的后繼結(jié)點(diǎn)d(建樹(shù)，建立指向parent的指針)并計(jì)算f(d)；10.iff(d)

4、t：從源點(diǎn)1出發(fā)再回到1頂點(diǎn)的最短巡回旅行路線。1.設(shè)定目標(biāo)函數(shù)的限界down=r1，up=∞2.計(jì)算初始結(jié)點(diǎn)1的f(1)=r1，將初始結(jié)點(diǎn)插入最小堆H;3.while(H≠Φ)4.{5.從H中做DELETEMIN的操作，用p帶回相應(yīng)結(jié)點(diǎn);6.產(chǎn)生p的所有滿足約束條件的后繼結(jié)點(diǎn)d(建樹(shù)，建立指向parent的指針)并計(jì)算f(d)；7.while對(duì)每個(gè)結(jié)點(diǎn)d8.{iff(d)

5、H=Φ)then13.從葉子結(jié)點(diǎn)沿parent指針輸出解，退出；14.}15.else將d結(jié)點(diǎn)插入最小堆H中；16.}17.}18.}2.批處理作業(yè)問(wèn)題設(shè)J1,J2,J3,J4是四項(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元組（x1,x2,…,xn）,每個(gè)xi的取值為{1,…,n}；約束條件為xi≠xj。目標(biāo)函數(shù)是s

6、um3=max{sum2[n],sum3[n-1]}+tn3,其中sum2[n]=max{sum1[n],sum2[n-1]}+tn2,Sum1[n]=sum1[n-1]+tn1。限界函數(shù)：設(shè)M是已經(jīng)安排好的作業(yè)集合，Mì{1,2,...,n},

7、M

8、=k?，F(xiàn)在要處理作業(yè)k+1，有：其中sum1[k+1]=sum1[k]+tk+1,1sum2[k+1]=max{sum1[k+1],sum2[k]}+tk+1,2目標(biāo)函數(shù)的下限界down=Input：n個(gè)作業(yè)，及其在3臺(tái)機(jī)器上的處理時(shí)間tij；Output：n

9、個(gè)作業(yè)的最佳處理順序及其處理時(shí)間。1.設(shè)定目標(biāo)函數(shù)的限界down=，up=∞2.計(jì)算初始結(jié)點(diǎn)1的sum1=0，sum2=0，db(1)=0，將初始結(jié)點(diǎn)插入最小堆H;3.while(H≠Φ)4.{5.從H中做DELETEMIN的操作，用p帶回相應(yīng)結(jié)點(diǎn);6.產(chǎn)生p的所有滿足約束條件的后繼結(jié)點(diǎn)d(建樹(shù)，建立指向parent的指針)并計(jì)算db(d)；7.while對(duì)每個(gè)結(jié)點(diǎn)d8.{ifdb(d)

10、點(diǎn)；12.if(H=Φ)then13.從葉子結(jié)點(diǎn)沿parent指針輸出解，退出；14.}15.else將d結(jié)點(diǎn)插入最小堆H中；16.}17.}18.}3.裝載問(wèn)題有一批共n個(gè)集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為Wi，且裝載問(wèn)題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。分析：該問(wèn)題的解決可以簡(jiǎn)化為盡量裝滿第一艘輪船，再將剩余集裝箱裝入第二艘