旅行商問題(1)

1、. 貨郎擔(dān)問題在運籌學(xué)里是一個著名的命題。有一個串村貨郎擔(dān)問題在運籌學(xué)里是一個著名的命題。有一個串村走戶賣貨郎，他從某個村莊出發(fā)，通過若干個村莊一次且走戶賣貨郎，他從某個村莊出發(fā)，通過若干個村莊一次且僅一次，最后仍回到原出發(fā)的村莊。問應(yīng)如何選擇行走路僅一次，最后仍回到原出發(fā)的村莊。問應(yīng)如何選擇行走路線，能使總的行程最短。類似的問題有旅行路線問題，應(yīng)線，能使總的行程最短。類似的問題有旅行路線問題，應(yīng)如何選擇行走路線，使總路程最短或費用最少等。如何選擇行走路線，使總路程最短或費用最少等?，F(xiàn)在把問題一般化。設(shè)有現(xiàn)在把問題一般化。設(shè)有n個城市，以個城市，以v1，v2，vn表表示之。示之。dij表示從表

2、示從vi城到城到vj城的距離。一個推銷員從城市城的距離。一個推銷員從城市v1出發(fā)到其他每個城市去一次且僅僅是一次，然后回到城出發(fā)到其他每個城市去一次且僅僅是一次，然后回到城市市v1。問他如何選擇行走的路線，使總的路程最短。這。問他如何選擇行走的路線，使總的路程最短。這個問題屬于組合最優(yōu)化問題，當(dāng)個問題屬于組合最優(yōu)化問題，當(dāng)n不太大時，利用動態(tài)規(guī)不太大時，利用動態(tài)規(guī)劃方法求解是很方便的。劃方法求解是很方便的。. 設(shè)設(shè)S表示從表示從V1到到Vi中間所有可能經(jīng)過的城市集合，中間所有可能經(jīng)過的城市集合，S S實際上是包實際上是包含除含除V1與與Vi兩個點之外其余點的集合，但兩個點之外其余點的集合，但S

3、中的點的個數(shù)要隨階中的點的個數(shù)要隨階段數(shù)改變。段數(shù)改變。狀態(tài)變量（狀態(tài)變量（i，S）表示：）表示：從從V1點出發(fā)，經(jīng)過點出發(fā)，經(jīng)過S集合中所有點一次集合中所有點一次最后到達最后到達到到Vi最有指標(biāo)函數(shù)最有指標(biāo)函數(shù)fk(i, S)為為從從V1出發(fā)經(jīng)由出發(fā)經(jīng)由k個城鎮(zhèn)的個城鎮(zhèn)的S到到Vi的最短距的最短距離離決策變量決策變量Pk(i, S)表示：從表示：從V1經(jīng)由經(jīng)由k個中間城鎮(zhèn)的個中間城鎮(zhèn)的S到到Vi城鎮(zhèn)的最城鎮(zhèn)的最短路線上鄰接短路線上鄰接Vi的前一個城鎮(zhèn)，則動態(tài)規(guī)劃的順序遞推關(guān)系為的前一個城鎮(zhèn)，則動態(tài)規(guī)劃的順序遞推關(guān)系為 1 01( , )min( ,)( ,) (1,2,12,3, )kkj

4、ij sif i Sfj Sjdf idknin 為空集，.例：例： 求解四個城市旅行推銷員問題，其距離矩陣求解四個城市旅行推銷員問題，其距離矩陣如表所示。當(dāng)推銷員從如表所示。當(dāng)推銷員從v1城出發(fā)，經(jīng)過每個城市一城出發(fā)，經(jīng)過每個城市一次且僅一次，最后回到次且僅一次，最后回到v1城，問按怎樣的路線走，城，問按怎樣的路線走，使總的行程距離最短。使總的行程距離最短。vivj123410679280973580846550.解解: 由邊界條件可知：由邊界條件可知：012013014(2,)6,(3,)7,(4,)9fdfdfd當(dāng)當(dāng)k=1時，即從時，即從v1城開始，中間經(jīng)過一個城市到達城開始，中間經(jīng)過一

5、個城市到達vi城的最城的最短距離是：短距離是： 103210421111(2, 3 )(3,)7815(2, 4 )(4,)9514(3, 2 )6915 (3, 4 )9514(4, 2 )6713 (4, 3 )7815ffdffdffff.當(dāng)當(dāng)k=2時，即從時，即從v1城開始，中間經(jīng)過二個城市城開始，中間經(jīng)過二個城市(它們的順序隨它們的順序隨便便)到達到達vi城的最短距離是：城的最短距離是： 213214222222(2,3,4)min (3, 4 ), (4, 3 )min 148,15520 (2, 3,4 )4(3, 2,4 )min 149,13518 (3, 2,4 )4(4,

6、 2,3 )min 157,15822 (4, 2,3 )2ffdfdpfpfp.當(dāng)當(dāng)k=3時，即從時，即從v1城開始，中間經(jīng)過三個城市城開始，中間經(jīng)過三個城市(順序隨便順序隨便)回回到到v1城的最短距離是：城的最短距離是：3221231241(1, 234 )min (2, 3,4 ),(3, 2,4 ),(4, 2,3 )min 20 8,18 5,22623ffdfdfd， ，3 (1, 2,3,4 )2p由此可知，推銷員的最短旅行路線是由此可知，推銷員的最短旅行路線是12431，最短，最短總距離為總距離為23。. 物資運輸路線問題物資運輸路線問題 自動焊機割咀路線問題自動焊機割咀路線問題 管道鋪設(shè)路線問題管道鋪設(shè)路線問題. 求解四個城市的旅行商問題。問應(yīng)如何選擇行進路線，求解四個城市的旅行商問題。問應(yīng)如何選擇行進路線，使從使從v1的出發(fā)到其他城市一次且僅一次，再回到的出發(fā)到其他城市一次且僅一次，再回到v1的總的總路程最短？路程最短？vivj123410367250233640243750. 求解求解5個城