旅行業務員問題

　1│2│3│4　

首頁 | 搜尋

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

旅行業務員問題

劉涵初

(一)蠻力法(brute force method)
(二)分支界定法(branch-and-bound method)
(三)動態規劃(Dynamic Programming)
(四)近似法

旅行業務員問題 (Traveling Salesman Problem) 是個有名的難題，旅行業務員要到 n 個城市推展業務，n 個城市以 1,2,…,n 表示，從 1 出發，經過每個城市恰只一次，再回到 1，令 C_ij 表城市 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}$ ，假設電腦每秒可計算 10⁶ 條路徑的成本(目前也許還做不到)，一年有 3.15 x 10⁷秒，故一年可計算 3.15 x 10¹³條路徑，求出所有路徑的成本需時

$\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

　1│2│3│4　


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

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

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

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