![]() ![]() |
.原載於數學傳播第十一卷第三期 .作者當時任教於逢甲大學統計系 | ||
旅行業務員問題
劉涵初 |
旅行業務員問題 (Traveling Salesman Problem) 是個有名的難題,旅行業務員要到 n 個城市推展業務,n 個城市以 1,2,…,n 表示, 從 1 出發,經過每個城市恰只一次,再回到 1,令 Cij 表城市 i 到城市 j 的旅行成本, 問題為找出一個最小成本的路徑。在工廠的組合線上,以機器人上緊螺絲帽,機器人從起始的位置出發, 做連續的移動,上緊每一個螺絲帽,再回到起始的位置,如何找到一個最短的路徑?這亦是旅行業務員問題。這個問題難在哪裏?我們看以下的四種解法。
我們以最直覺的方法一一計數來解,亦即找出所有可能的路徑,計算每條路徑的成本後,找出其最小者。
那麼共有幾條路徑?因每一條路徑必形如
![]() 即使對不太大的 n=26,就需時五千億年,顯然這種方法毫無用處。
|
對外搜尋關鍵字: .旅行業務員問題 .NP-Hard |
|
![]() |
(若有指正、疑問……,可以在此 留言 或 寫信 給我們。) |
![]() |
EpisteMath (c) 2000 中央研究院數學所、台大數學系 各網頁文章內容之著作權為原著作人所有 |
編輯:吳明和 ∕ 校對:陳文是 ∕ 繪圖:簡立欣 | 最後修改日期:5/2/2002 |