| |
旅行業務員問題既是個難題，我們只得退而求其次找一個近似解，這種解法係從直觀而來，稱為最近鄰居法 (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.
|
|
|
![\begin{displaymath}\frac{d}{d_{0}}\leq \frac{1}{2} [
\log 2n] +\frac{1}{2}\end{displaymath}](img44.gif){kind=small}