十動態(tài)規(guī)劃的應(yīng)用---knapsack,TSP問題

1、 背包問題背包問題例例1 (背包問題背包問題) 設(shè)有一輛背包可以裝入的物品情況如下表設(shè)有一輛背包可以裝入的物品情況如下表:問問: 如何安排裝入如何安排裝入方案方案, 使背包一次使背包一次裝入的貨物總價裝入的貨物總價值最大值最大?解解: 設(shè)設(shè) x i為背包為背包裝入第裝入第 i 種貨物種貨物的件數(shù)。的件數(shù)。貨物（件）貨物（件） 1 2 n 最大裝入量最大裝入量 單位重量單位重量 w1 w2 wn a 單位價值單位價值 c1 c2 cn11max. .0 1,2, .niiiniiiiifc xw xas txxin ，取取整整數(shù)數(shù)，注：若每種物品的最大件數(shù)為注：若每種物品的最大件數(shù)為1，則，則x

2、i取值為取值為0或或1，稱為，稱為0-1背包背包問題問題階段階段：按照物品的種類將裝入背包的過程分為：按照物品的種類將裝入背包的過程分為n個階段，每個階段個階段，每個階段裝入一種物品；裝入一種物品；狀態(tài)變量狀態(tài)變量sk: 裝前裝前k-1種的物品的可用背包容量；種的物品的可用背包容量；決策變量決策變量xk :裝入第裝入第k種物品的數(shù)量；種物品的數(shù)量；狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程: sk= sk+1-wkxk最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù) fk(sk+1)：若只裝入：若只裝入k種物品，背包容量為種物品，背包容量為sk+1時裝入物時裝入物品的最大價值品的最大價值動態(tài)規(guī)劃的順序遞推方程（順序解法）動態(tài)規(guī)劃的順序

3、遞推方程（順序解法）111001()max (),1,.,()0kkkkkkkkkw xsfsw xfsknfs 顯然，我們要求的是顯然，我們要求的是 fn(a)例例1：有一艘貨船的最大載重量為有一艘貨船的最大載重量為5噸，用以裝載三種貨物，每種貨噸，用以裝載三種貨物，每種貨物的單位重量及單價如表所示。應(yīng)如何裝載使總重量最大？物的單位重量及單價如表所示。應(yīng)如何裝載使總重量最大？貨物（件）貨物（件） 1 2 3 最大裝入量最大裝入量 單位重量單位重量 3 2 5 5 單位價值單位價值 8 5 12解：按順序裝入三種貨物，裝入過程分為三個階段，解：按順序裝入三種貨物，裝入過程分為三個階段，k=1，

4、2，3。采用動態(tài)規(guī)劃的順序解法求解。采用動態(tài)規(guī)劃的順序解法求解。111001()max (),1,.,()0kkkkkkkkkw xsfsw xfsknfs 當(dāng)當(dāng)k=2時時當(dāng)當(dāng)k=1時時12121210110 30 3()max 8()max 8xsxsf sxfsx 23232321221320 20 2()max 5()max 5(2)xsxsfsxf sxf sx 343432430 5()max 12(5)xsfsxfsx當(dāng)當(dāng)k=3時時45s 由由33323220 55(5)max 12(55)max0(5),12(0)xfxfxff 22(0)0,(5)?ff 2222122120

5、250 25111(5)max 5()max 5(52)max0(5),5(3),10(1)xxfxf sxfxfff1110 35(5)max88xfx1110 33(3)max88xfx1110 31(1)max80 xfx所以所以2111(5)max0(5),5(3),10(1)5813ffff 3(5)max013,12013f 0*3x1*2x1*1x0*3x5055343xss1*2x3252232xss1*1x0333121xss所裝入的最大物品總價值為所裝入的最大物品總價值為13。 旅行商（旅行商（TSPTSP）問題）問題設(shè)有一個由設(shè)有一個由n個城市構(gòu)成的交通網(wǎng)絡(luò)，各個城市之間

6、個城市構(gòu)成的交通網(wǎng)絡(luò)，各個城市之間的路徑長度已知。一個推銷員從城市的路徑長度已知。一個推銷員從城市1出發(fā)到其他城出發(fā)到其他城市，每個城市必須經(jīng)過且只經(jīng)過一次然后返回城市市，每個城市必須經(jīng)過且只經(jīng)過一次然后返回城市1。問：該推銷員該如何選擇行走路線使得總的路程最短。問：該推銷員該如何選擇行走路線使得總的路程最短。記所有城市的集合為記所有城市的集合為V=v1,v2,vn； 城市城市i到城市到城市j的距離為的距離為dij；遞推公式遞推公式(動態(tài)規(guī)劃的基本方程動態(tài)規(guī)劃的基本方程)：iijkjkijVvkikdvfnkvVvfdVvfkj101),(,.,3 , 2 , 1,(min),(很顯然，我們最

7、后需要求的是很顯然，我們最后需要求的是 ，其中，其中),(11 -Vvfn,32nvvvV將推銷員的旅行過程分為將推銷員的旅行過程分為n個階段；個階段；第第k階段的狀態(tài)為階段的狀態(tài)為： (所在的城市所在的城市vi，所經(jīng)過的城市集合，所經(jīng)過的城市集合Vk )最優(yōu)值函數(shù)最優(yōu)值函數(shù)fk (vi,Vk):從城市從城市 1 出發(fā)，經(jīng)過出發(fā)，經(jīng)過k個城市（經(jīng)個城市（經(jīng)過城市集合為過城市集合為Vk）到達(dá)城市）到達(dá)城市vi 的最短路徑長度的最短路徑長度采用順序解法進(jìn)行求解采用順序解法進(jìn)行求解例例2：求解求解4個城市的旅行商問題，其個城市的旅行商問題，其4個城市之間的距離個城市之間的距離如矩陣所示。求推銷員從城

8、市如矩陣所示。求推銷員從城市1出發(fā)經(jīng)過所有城市一次并出發(fā)經(jīng)過所有城市一次并回到城市回到城市1的最短路徑及路徑長度。的最短路徑及路徑長度。0879509758066580D解：由邊界條件可知解：由邊界條件可知; 8),(1220dvf; 5),(1330dvf; 6),(1440dvf21vv 31vv 41vv k=1：從：從v1出發(fā)，經(jīng)過一個城市后到達(dá)城市出發(fā)，經(jīng)過一個城市后到達(dá)城市vi;1495),() v,(3230321dvfvf;1376),() v,(4240421dvfvf;1688),() v,(2320231dvfvf;1486),() v,(4340431dvfvf;135

9、8),() v,(2420241dvfvf;1055),() v,(3430341dvfvf23vv 24vv 32vv 34vv 42vv 43vv k=2：從：從v1出發(fā)，經(jīng)過兩個城市后到達(dá)城市出發(fā)，經(jīng)過兩個城市后到達(dá)城市vi;17710, 914min) v,(,) v,(min) v,v,(42341324314322dvfdvfvf21813, 813min) ,(,) ,(min) v,v,(43241234214232dvvfdvvfvf2431vvvv34213241vvvvorvvvv4231vvvv19516, 514min) ,(,) ,(min) v,v,(34231243213242dvvf