|
旅行業務員問題既是個難題,我們只得退而求其次找一個近似解,這種解法係從直觀而來,稱為最近鄰居法 (nearest-neighbor method )。
從城市 1 開始,先找最近 1 的城市 x1,次找最接近 x1 的城市 x2,再找最接近 x2 的城市 x3, ,直至找出所有的城市,將最後一個城市與 1 連接,即得所求的路徑,例如圖4(a),從 1 開始,
根據最近鄰居法,過程如圖4(b)至圖4(f),此路徑成本為 40,而最小成本路徑如圖4(g)所示,成本為 37。
圖4
|
若圖形含 n 個頂點,令 d 表根據最近鄰居法所求之路徑成本,d0 表最佳路徑成本,當三角不等式成立時,
亦即
恆成立,則可證明
其中 [x] 表示大於或等於 x 的最小整數,
證明參閱 [3] 第160頁或 [1] 第129頁,[1] 第130到132頁另介紹兩種近似法,其中最小生成樹法 (minimum spanning tree method) 可以保證
,另外最小配對法 (minimum matching method) 則保證
。
- 1. Garey, M. and Johnson D.:《Computers and Intractability》,1979.
- 2. Horowitz, E. and Sahni, S.:《Fundamentals of Computer
Algorithms》, Computer Science Press,1978.
- 3. Liu, C.L.:《Elements of Discrete Mathematics》,
2nd.ed. McGraw-Hill,1985.
- 4. Tucker, A.:《Applied Combinatorics》, 2nd.ed.,John Wiley & Sons,1984.
- 5. 劉涵初:《離散數學》,華泰書局,1987.
|
|
|