旅行業務員問題 (第 3 頁)

　1│2│3│4　

旅行業務員問題（第 3 頁）

劉涵初

首頁 | 搜尋

．原載於數學傳播第十一卷第三期
．作者當時任教於逢甲大學統計系
‧對外搜尋關鍵字

(三)動態規劃(Dynamic Programming)

令 V={1,2, … ,n} 表 n 個城市， $S\subseteq V$ ，g(i,S) 表由頂點 i 出發，可經由 S 中所有頂點而抵達 1 的最佳路徑成本，故旅行業務員問題的解為 g(1,V-{1})，在最佳路徑中，若由 1 出發，下一個城市為 k，則最佳路徑成本必為 C_1k 加上由 k 到 1 的最佳路徑成本，故我們可得下式：

$\begin{displaymath} g(1,V-\{1\})=\min_{2\leq k\leq n}\{C_{1k}+g(k,V-\{1,k\})\} \eqno{(1)} \end{displaymath}$

將(1)式一般化，可得

$\begin{displaymath} g(i,S)=\min_{j\in S}\{C_{ij}+g(j,S-\{j\})\} \eqno{(2)} \end{displaymath}$

顯然 $g(i,\phi)=C_{i1}$ ， $1\leq i\leq n$ ，利用(2)式，可先求得所有 g(i,S)，而 |S|=1（S 只含一個元素）；接著再求所有 g(i,S)，而 |S|=2； $\cdots\cdots$ ；最後求得 g(1,V-{1})。當 |S|<n-1 時，只需計算 $i\neq 1$ ， $1\not \in S$ ， $i\not \in S$ 的 g(i,S)，這種動態規劃的求解方法為建立遞迴關係 (recurrence relation)，亦即(2)式，再以起始條件 (initial conditions) $g(i,\phi)=C_{i1}$ ，逐步代入求解，我們先考慮前面表 1 的成本矩陣，求解過程如下：

首先 $g(2,\phi)=C_{21}=3$ ， $g(3,\phi)=C_{31}=5$ ， $g(4,\phi)=C_{41}=9$ ，利用(2)式可得

$\begin{eqnarray*} g(2,\{3\})&=&C_{23}+g(3,\phi) = 5+6=11,\\ g(2,\{4\})&=&C_{24}... ...2}+g(2,\phi) = 7+3=10,\\ g(4,\{3\})&=&C_{43}+g(3,\phi) = 4+5=9, \end{eqnarray*}$

接著計算 g(i,S) 而 |S|=2， $i\neq 1$ ，且 $1\not \in S$ ， $i\not \in S$

$\begin{eqnarray*} g(2,\{3,4\})&=&\min\{C_{23}+g(3,\{4\}),C_{24}+g(4,\{3\})\}\\ ... ...C_{42}+g(2,\{3\}),C_{43}+g(3,\{2\})\}\\ &=&\min\{7+11,4+9\}=13 \end{eqnarray*}$

最後可得

$\begin{eqnarray*} \lefteqn{ g(1,\{2,3,4\}) } \\ &=& \min\{C_{12}+g(2,\{3,4\}),... ...),C_{14}+g(4,\{2,3\})\}\\ &=& \min\{3+14,9+16,7+13\}\\ &=&17 \end{eqnarray*}$

故最佳路徑成本為 17，令 J(i,S) 表(2)式中令 g(i,S) 最小的 j 值，由 g(1,{2,3,4}) 可得 J(1,{2,3,4})=2，故最佳路徑為 $1\rightarrow 2\rightarrow \cdots$ ，接著由 g(2,{3,4}) 可得 J(2,{3,4})=4，故最佳路徑為 $1\rightarrow 2\rightarrow 4\rightarrow \cdots$ ，最後可得 J(4,{3})=3，故最佳路徑為 $1\rightarrow 2\rightarrow 4\rightarrow 3\rightarrow 1$ 。

令 N 表示 g(1,V-{1}) 之前所需計算 g(i,S) 的個數，對每一個 |S| 之值，i 有 n-1 種選擇，若 |S|=k，則不含 1 及 i 的 S 有 ${{n-2}\choose{k}}$ 種，故

$\begin{eqnarray*} N&=&\sum_{k=0}^{n-2}(n-1){n-2 \choose k}\\ &=&\sum_{k=0}^{n-... ... k+1}\\ &=&\sum_{j=1}^{n-1}j{n-1\choose j}\\ &=&(n-1)2^{n-2} \end{eqnarray*}$

為求解所需計算 g(i,S) 的個數為 (n-1)2^n-1，這當然比蠻力法需計算 (n-1)!條路徑成本要好得多，例如，n=20，則 $(19)2^{18}\cong 5\times 10^{6}$ ，而 $19!\cong 10^{12}$ ，雖然如此，以動態規劃求解，其計算複雜度 (computational complexity) 仍然呈指數上升，對目前及未來的計算機而言，一個計算複雜度呈指數上升的問題，在 n 相當大時仍無法解決，因此旅行業務員問題是個難題。（事實上這是個 NP-Hard 問題）

　1│2│3│4　


	（若有指正、疑問……，可以在此留言或寫信給我們。）

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有

編輯：吳明和 ∕ 校對：陳文是 ∕ 繪圖：簡立欣

最後修改日期：5/2/2002