貨郎擔問題也叫旅行商問題，即TSP問題（Traveling Salesman Problem），是數學領域中著名問題之一。
其一般提法為：有n個城市，用1，2，…，n表示，城i,j之間的距離為dij，有一個貨郎從城1出發到其他城市一次且僅一次，最後回到城市1，怎樣選擇行走路線使總路程最短？
旅行商問題的提法為：假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路經的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。
貨郎擔問題（TSP問題）是一個組合最佳化問題。該問題可以被證明具有NPC計算複雜性。因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關注。
基本介紹
- 中文名：貨郎擔問題
- 外文名：Traveling Salesman Problem
- 別名：旅行商問題
- 簡稱：TSP
動態規劃,郵路問題,螺帽問題,生產安排,問題分析,
動態規劃
階段變數k：按所經過的城市個數劃分階段k,k=1,2，…，n-1.
狀態變數Sk：設第k階段到達城市i時途中所經過的k個城市集合為S
=====================================================================
貨郎擔問題屬於易於描述但難於解決的著名難題之一，世界上還有不少人在研究它。該問題的基本描述是：某售貨員要到若干個村莊售貨，各村莊之間的路程是已知的，為了提高效率，售貨員決定從所在商店出發，到每個村莊售一次貨然後返回商店，問他應選擇一條什麼路線才能使所走的總路程最短?此問題可描述如下：設g=(v，e）是一個具有邊成本cij的有向圖，cij的定義如下，對於所有的i和j,cij>0，若<i，j> e，則cij=。令|v1|=n，並假定n>l。g的一條週遊路線是包含v中每個結點的一個有向環。週遊路線的成本是此路線上所有邊的成本和。貨郎擔問題(traveling sales person problem）是求取具有最小成本的週遊路線問題。 有很多實際問題可歸結為貨郎擔問題·。
郵路問題
例如郵路問題就是一個貨郎擔問題。假定有一輛郵車要到n個不同的地點收集郵件，這種情況可以用n十1個結點的圖來表示。一個結點表示此郵車出發並要返回的那個郵局，其餘的n個結點表示要收集郵件的n個地點。由地點i到地點j的距離則由邊<i，j>；上所賦予的成本來表示。郵車所行經的路線是一條週遊路線，希望求出具有最小長度的週遊路線。
螺帽問題
第二個例子是在一條裝配線上用一個機械手去緊固待裝配部件上的螺帽問題。機械手由其初始位置（該位置在第一個要緊固的螺帽的上方）開始，依次移動到其餘的每一個螺帽，最後返回到初始位置。機械手移動的路線就是以螺帽為結點的一個圖中的一條週遊路線。一條最小成本週遊路線將使這機械手完成其工作所用的時間取最小值。
注意只有機械手移動的時間總量是可變化的。
生產安排
第三個例子是產品的生產安排問題。假設要在同一組機器上製造n種不同的產品，生產是周期性進行的，即在每一個生產周期這n種產品都要被製造。要生產這些產品有兩種開銷，一種是製造第i種產品時所耗費的資金（1≤i≤n），稱為生產成本，另一種是這些機器由製造第i種產品變到製造第j種產品時所耗費的開支cij稱為轉換成本。顯然，生產成本與生產順序無關。於是，我們希望找到一種製造這些產品的順序，使得製造這n種產品的轉換成本和為最小。由於生產是周期進行的，因此在開始下一周期生產時也要開支轉換成本，它等於由最後一種產品變到製造第一種產品的轉換成本。於是，可以把這個問題看成是一個具有n個結點，邊成本為cij圖的貨郎擔問題。
問題分析
貨郎擔問題要從圖g的所有週遊路線中求取具有最小成本的週遊路線，而由始點出發的週遊路線一共有（n一1）！條，即等於除始結點外的n一1個結點的排列數，因此貨郎擔問題是一個排列問題。排列問題比子集合的選擇問題（例如0/1背包問題就是這類問題）通常要難於求解得多，這是因為n個物體有n!種排列，只有2n個子集合（n!>o（2n））。通過枚舉（n一1）！條週遊路線，從中找出一條具有最小成本的週遊路線的算法，其計算時間顯然為o(n！）。為了改善計算時間必須考慮新的設計策略來擬制更好的算法。動態規劃就是待選擇的設計策略之一。但貨郎擔問題是否能使用動態規劃設計求解呢?下面就來討論這個問題。
不失一般性，假設週遊路線是開始於結點1並終止於結點l的了條簡單路徑。每一條週遊路線都由一條邊（1，k）和一條由結點k到結點1的路徑所組成，其中k∈v一（1）；而這條由結點k到結點1的路徑通過v一{1，k}的每個結點各一次。容易看出，如果這條週遊路線是最優的，那么這條由k到1的路徑必定是通過v-{1,k}中所有結點的由k到1的最短路徑，因此最優性原理成立。設g(i，s）是由結點i開始，通過s中的所有結點，在結點1終止的一條最短路徑長度.
g（1，v一{1})是一條最優的週遊路線長度。於是可以得出
g（1，v一{1））= {clk十g(k，v一{1,k}))
將（4．19）式一般化可得
g(i，s）— {cij+g(j，s—{j})} （4．20）
如果對於k的所有選擇，知道了g(k，v一<1，k））的值，由（4。19）式就可求解出g（1，v一{1})。而這些g值則可通過（20）式得到。顯然，g（1，∮）=cil，l<i≤n。於是，可套用（20）式去獲得元素個數為1的所有s的g(i,s）。然後，可對 =2的s得到g(i，s）等等。當 <n一1時，g(i，s）所需要的i和s的值是i≠1，1 s且i各s的那些值。
