已在第一頁 1234 次頁

 


首頁 | 搜尋

.原載於數學傳播第十一卷第三期
.作者當時任教於逢甲大學統計系
 

旅行業務員問題

劉涵初

 
 

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


(一)蠻力法(brute force method)

我們以最直覺的方法一一計數來解,亦即找出所有可能的路徑,計算每條路徑的成本後,找出其最小者。 那麼共有幾條路徑?因每一條路徑必形如 $1\rightarrow \cdots \rightarrow 1$,中間需經過 n-1 個城市,故有 (n-1)! 路徑, 若 n=26,則有 25! 條不同路徑,25! 這個數字寫來輕鬆,究竟有多大? $25!\cong 1.55\times 10^{25}$, 假設電腦每秒可計算 106 條路徑的成本(目前也許還做不到),一年有 3.15 x 107秒, 故一年可計算 3.15 x 1013條路徑,求出所有路徑的成本需時

\begin{displaymath}
\frac{1.55\times 10^{25}}{3.15\times 10^{13}}\cong 5\times 1...
...\mbox{({\fontfamily{cwM1}\fontseries{m}\selectfont \char 20})}
\end{displaymath}

即使對不太大的 n=26,就需時五千億年,顯然這種方法毫無用處。

 
對外搜尋關鍵字:
旅行業務員問題
NP-Hard

已在第一頁 1234 次頁

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

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


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