上頁 1234 次頁

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

劉涵初

 

首頁 | 搜尋

.原載於數學傳播第十一卷第三期
.作者當時任教於逢甲大學統計系
對外搜尋關鍵字
 
(三)動態規劃(Dynamic Programming)

V={1,2,,n}n 個城市,$S\subseteq V$g(i,S) 表由頂點 i 出發,可經由 S 中所有頂點而抵達 1 的最佳路徑成本,故旅行業務員問題的解為 g(1,V-{1}),在最佳路徑中,若由 1 出發,下一個城市為 k,則最佳路徑成本必為 C1k 加上由 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|=1S 只含一個元素);接著再求所有 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| 之值,in-1 種選擇,若 |S|=k, 則不含 1 及 iS${{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)2n-1,這當然比蠻力法需計算 (n-1)!條路徑成本要好得多, 例如,n=20,則 $(19)2^{18}\cong 5\times 10^{6}$,而 $19!\cong
10^{12}$,雖然如此,以動態規劃求解,其計算複雜度 (computational complexity) 仍然呈指數上升,對目前及未來的計算機而言,一個計算複雜度呈指數上升的問題, 在 n 相當大時仍無法解決,因此旅行業務員問題是個難題。(事實上這是個 NP-Hard 問題)

   

上頁 1234 次頁

回頁首
 
(若有指正、疑問……,可以在此 留言寫信 給我們。)
EpisteMath

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


編輯:吳明和 / 校對:陳文是 / 繪圖:簡立欣 最後修改日期:5/2/2002