一．貨郎擔問題

    貨郎擔問題屬于易于描述但難于解決的著名難題之一，至今世界上還有不少人在研究它。該問題的基本描述是：某售貨員要到若干個村莊售貨，各村莊之間的路程是已知的，為了提高效率，售貨員決定從所在商店出發，到每個村莊售一次貨然后返回商店，問他應選擇一條什么路線才能使所走的總路程最短?此問題可描述如下：設g=(v，e)是一個具有邊成本c_ij的有向圖，c_ij的定義如下，對于所有的i和j ,c_ij>0，若<i，j> e，則c_ij＝ 。令|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個結點，邊成本為c_ij圖的貨郎擔問題。

二．貨郎擔問題的分析

    貨郎擔問題要從圖g的所有周游路線中求取具有最小成本的周游路線，而由始點出發的周游路線一共有(n一1)!條，即等于除始結點外的n一1個結點的排列數，因此貨郎擔問題是一個排列問題。排列問題比子集合的選擇問題(例如0／1背包問題就是這類問題)通常要難于求解得多，這是因為n個物體有n1種排列，只有2ⁿ個子集合(n!>o(2n))。通過枚舉(n一1)1條周游路線，從中找出一條具有最小成本的周游路線的算法，其計算時間顯然為o(n1)。為了改善計算時間必須考慮新的設計策略來擬制更好的算法。動態規劃就是待選擇的設計策略之一。但貨郎擔問題是否能使用動態規劃設計求解呢?下面就來討論這個問題。

不失一般性，假設周游路線是開始于結點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的那些值。

三．例子

    例17 考慮圖4。13(a)，其邊長由圖4.13(b)中的矩陣c給出：

    g(2，∮)＝c_2l=5    g(3，∮)=c₃₁＝6    g(4，∮)=c₄₁＝8

由(4．20)式得

    g(2，{3})=c₂₃+g(3，∮)=15 g(2，{4})＝18

    g(4，{2}=13 g(4，{3})=15

接著，計算在 ＝2且i≠1，1 s，i s情況下的g(i，s)：

    g(2，{3，4})=min{c₂₃+g(3，{4})，c₂₄+g(4，{3})=25

g(3，{2，4})＝min{c₃₂2+g(2，{4})，c₃₄+g(4，{2})}＝25

g(4，{2，3})＝min{c₄₂2+g(2，{3})，c₄₂+g(3，{2})}＝23

 

                圖13                               （演示）

最后，由(19)式得

    g(1，{2，3，4})＝min{c₁₂-g(2，{3，4})，c₁₃+g(3，{2，4})，c₁₄+g(4，{2，3})}＝min{35，40，43}=35

    圖13(a)中的這個有向圖的最優周游路線長度為35。如果對每個g(i，s)，保留使(20)

式右邊取最小值的那個j值，那末就可構造出這一最優周游路線。令j(i，s)是這個值，則j(1，{2，3，4})=2。它表示這條周游路線由1開始并通到2。剩下的路徑可由g(2，{3，4})得到。因j(2，{3，4})＝4，故這下一條邊是(2，4)。以后的剩余段由g(4，{3})來獲得j(4，{3})=3。因此這條最優周游路線是1，2，4，3，l。

設n是用(4．19)式計算g(1，v一{1})以前需要計算的g(i，s)的數目。 的取值在不同的決策階段分別對應為0，1，…，n一2。對于 的每一種取值，i都有n一1種選擇。不包含1和i在內的大小為k的不同s的個數 是因此，

n=

又因為在 ＝k時，由(20)求g(i，s)的值要進行k一1次比較，所以用(19)和(20)求最優周游路線的算法要求的計算時間為⊙(n²,2ⁿ)。由此可知，用動態規劃設計的算法比枚舉法求最優周游路線在所用的時間上有所改進，但這種方法的嚴重缺點是空間要求要有o(n u)，這太大了，因而實際上是不可取的。在以后的章節里，將對貨郎擔問題作進一步的討論。