旅行業務員問題(Traveling Salesman Problem)是個有名的難題，旅行業務員要到$n$個城市推展業務，$n$個城市已$1，2，...，n$表示，從1出發， 經過每個城市洽指一次，再回到1，令$C_{ij}$表城市$i$到城市$j$的旅行成本，問題為找出一個最小成本的路徑。在工廠的組合線上， 以機器人上緊螺絲帽，機器人從起始的位置出發，做連續的移動，上緊每一個螺絲帽，再回到起始的位置，如何找一個最短的路徑? 這亦是旅行業務員問題。這個問題難在那裏?我們看以下的四種解法。

我們以最直覺的方法一一計數來解，亦即找出所有可能的路徑，計算每條路徑的成本後，找出最小者。那麼共有幾條路徑? 因每一條路徑必形如$1→…→１$，中間需經過$n-1$個城市，故有$(n-1)!$路徑，若$n=26$，則有$25!$條不同路徑，$25!$這個數字寫來輕鬆，究竟有多大? 25!≌1.55×10⁷秒，故一年可計算3.15×10¹³條路徑，求出所有路徑的成本需時$$\frac{1.55×10^{25}}{3.15×10^{13}}≌5×10^{11}(年)$$ 即使對不太大的$n=26$，就需時五千億年，顯然這種方法毫無用處。

旅行業務員問題的解可以樹形(tree)表示，例如$n=4$，則圖1的樹形表示所有可能的3!=6條路徑，例如，最右邊一條路徑為1→4→3→2→1。

在這問題中我們需找出最小成本路徑，分支界定法搜尋此最佳解的觀念為，將樹形不斷分支，但隨時以問題的條件限制分支的持續， 亦即若知最佳解不會出現在經由此點的路徑，則不必繼續分支，因此所需搜尋的路徑將大為減少。

考慮以下的例子，表1為城市間的成本矩陣，例如$C_{12}=3$表示城市1到城市2的旅行成本為3，注意$C_{ij}$不一定等於$C_{ji}$， 在主對角線上的$C_{ii}=∞$，表示我們不需這些值，一個可能的路徑需矩陣中的4個表值，每一行且每一列恰有一個，又且，若選$C_{ij}$， 則不能選$C_{ji}$；若選$C_{ij}$、$C_{jk}$，則不能選$C_{ik}$(為什麼?)，例如，表1中所圈的4個值表示路徑1→2→3→4→1， 成本為$C_{12}$+$C_{23}$+$C_{34}$+$C_{41}$=3+6+6+9=24

首先，我們找此問題的一個下限，在成本矩陣中，若每一行(每一列)減去相同的值，顯然，最低成本的路徑不會改變，故在第一列每項減3 (該列中最小值為3)，第二列減3，第三列減5，第四列減4，得表2之成本矩陣，但現在成本比原來成本少3+3+5+4=15。

第四行可減1，故表3之成本矩陣較原問題少15+1=16，因此這問題的解至少16，16為下限。

現在我們開始分支，首先考慮第一列，因$C_{12}$=0為最小，故考慮$C_{12}$，我們選$C_{12}$或不選$C_{12}$。若不選$C_{12}$， 則令$C_{12}$=∞，得表4。

表4中，第一列可減3，第二行可減1，故得表5，下限則為16+(3+1)=20

若選$C_{12}$，則表3中第一列第二行不能再被使用，可刪去，$C_{21}$亦不得被使用，故令$C_{21}$=∞，得表6。

第一列可減去1，故下限為16+1=17，如表7

目前樹形分支過程如圖2

所以二元決策數(binary decision tree)的每一內點表示:選$C_{ij}$或不選$C_{ij}$。現在因選$C_{12}$下限17小於不選$C_{12}$下限20， 故接著對選$C_{12}$分支，新選的表值不一定需與$C_{12}$連接，亦即不一定需為$C_{ij}$或$C_{zj}$，但為簡單起見，我們選$C_{zj}$， 表7中因$C_{24}$=0，故接著的分支為選$C_{24}$或不選$C_{24}$。若不選$C_{24}$，則表7中令$C_{24}$=∞，第一列減2，故下限為17+2=19。 若選$C_{24}$，則表7中移去對應的行與列，又令$C_{41}$=∞(否則得廻路1→2→4→1)，故得表8下限仍為17。

現在我們繼續分支，由表8可知，接著必得選$C_{43}$，$C_{31}$(否則得∞)，因$C_{43}$=$C_{31}$=0，故下限為17， 而這條路徑1→2→4→3→1成本為3+5+4+5=17正為下限，故為最佳解。以上全部的分支界定過程如圖3。

令$V={1，2，......，n}$表$n$個城市，$S⊆V，g(i,s)$表由頂點$i$出發，可經由$S$中所有頂點而抵達1的最佳路徑成本，故旅行業務員問題的解為 $g(1，V-{1})$，在最佳路徑中，若由1出發，下一個城市為$k$，則最佳路徑成本必為$C_{1k}$加上由$k$到1的最佳路徑成本，故我們可得下式: $$g(1，V-\{1\})=\min_{2\le k\le n}{C_{1k}+g(k,V-\{1,k\})}$$ 將(1)式一般化可得 $$g(i.s)=\min_{j∈s}\{C_{ij}+g(j,S-\{j\})\}$$ 顯然$g(i,ø)=C_{i1}$，$1\le i\le n$，利用(2)式，可先求得所有$g(i,s)$，而$|S|=2$；......；最後求得$g(1,V-{1})$。 當$|S|\lt n-1$時，只需計算$i≠１，1∉S，i∉S$的$g(i,S)$，這種動態規劃的求解方法為建立遞廻關係(recurrence relation)，亦即(2)式， 再以起始條件(initial conditions)g(i,ø)=$C_{i1}$，逐步代入求解，我們考慮前面表1的成本矩陣，求解過程如下:

首先g(2,ø)=$C_{21}$=3，g(3,ø)=$C_{31}$=5，g(4,ø)=$C_{41}$=9，利用(2)式可得 $$g(2,\{3\})=C_{23}+g(3,ø)=6+5=11$$ $$g(2,\{4\})=C_{24}+g(4,ø)=5+9=14$$ $$g(3,\{2\})=C_{32}+g(2,ø)=6+3=9$$ $$g(3,\{4\})=C_{34}+g(4,ø)=6+9=15$$ $$g(4,\{2\})=C_{42}+g(2,ø)=7+3=10$$ $$g(4,\{3\})=C_{43}+g(3,ø)=4+5=9$$ 接著計算$g(i,s)$而$|S|=2$，$i≠1$,且$1∉S,i∉S$ $$g(2,\{3,4\})=min\{C_{23}+g(3,\{4\}),C_{24}+g(4,\{3\})\}$$$$=min\{6+15,5+9\}=14$$ $$g(3,\{2,4\})=min\{C_{32}+g(2,\{4\}),C_{34}+g(4,\{2\})\}$$$$=min\{6+14,6+10\}=16$$ $$g(4,\{2,3\})=min\{C_{42}+g(2,\{3\}),C_{43}+g(3,\{2\})\}$$$$=min\{7+11,4+9\}=13$$ 最後可得 $$g(1,\{2,3,4\})=min\{C_{12}+g(2,\{3,4\}),C_{13}+g(3,\{2,4\}),C_{14}+g(4,\{2,3\})\}$$$$=min\{3+14,9+16,7+13\}$$$$=17$$ 故最佳路徑成本為17，令$J(i,s)$表(2)式中令$g(i,s)$最小的$j$值，由$g(1,{2,3,4})$可得$J(1,{2,3,4})=2$，故最佳路徑為1→2→...， 接著由$g(2,{3,4})$可得$J(2,{3,4})=4$，故最佳路徑為1→2→4→...，最後可得$J(4,{3})=3$，故最佳路徑為1→2→4→3→1。

令$N$表求$g(1,V-{1})$之前所需計算$g(i,S)$的個數，對每一個$|S|$之值，$i$有$n-1$種選擇，若$|S|=k$, 則不含$1$及$i$的$S$有$(^{n-2}_k)$種，故 $$N=\sum_{k=0}^{n-2} (n-1)(^{n-2}_k)=\sum_{k=0}^{n-2} (k+1)(^{n-1}_{k+1})$$ $$=\sum_{j=1}^{n-1} j(^{n-1}_j)=(n-1)2^{n-2}$$ 為求解所需計算$g(i,S)$的個數為$(n-1)2^{n-2}$，這當然比蠻力法需計算$(n-1)!$條路徑成本要好得多，例如，$n=20$，雖然如此， 以動態規劃求解，其計算複雜度(computational complexity)仍然呈指數上升，對目前及未來的計算機而言，一個計算複雜指數上升的問題， 在$n$相當大時仍無法解決，因此旅行業務員問題是個難題。(事實上這是個NP-Hard問題)

旅行業務員問題既是個難題，我們只得退而求其次找一個近似解，這種解法係從直觀而來，稱為最近鄰居法(nearest-neighbor method)。 從城市1開始，先找最接近1的城市$x1$，次找最接近$x1$的城市$x2$，再找最接近$x2$的城市$x3$，......，直至找出所有的城市， 將最後的一個城市與1連接，即得所求的路徑，例如圖4(a)，從1開始，根據最近鄰居法，過程如圖4(b)至圖4(f)，此路徑成本為40， 而最小成本路徑如圖4(g)所示，成本為37。

若圖形含$n$個頂點，令$d$表根據最近鄰居法所求之路徑成本，當三角不等式成立時，亦即$C_{ij}+C{jk}≥C{ik}$恆成立，則可證明 $$\frac d{d_0}≤\frac 1{2}[log2n]+\frac 1{2}$$ 其中[x]表示大於或等於$x$的最小整數，證明參閱第160頁或 第129頁， 第130到132頁另介紹兩種近似法，其中最小生成樹法(minimun spanning tree method)可以保證$\frac d{d_0}\lt 2$， 另外最小配對法(minimum matching method)則保證$d/d_0\lt 1.5$。

(本文作者任教於逢甲大學統計系)