未來數學家的挑戰【五、NP-complete 問題之近似解】

http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/page5.html
五、NP-complete 問題之近似解

NP-complete 問題既找不到可行的解法，而很大部分的 NP-complete 問題都在計算機語言，程式，電路設計，統計學，程式作業上有大用，因此只好退而求其次找一個可行的近似解。很可惜的是，所有的 NP-complete 問題雖在 NP 的層次上相聯，在近似解上往往各需不同的解法，這些解法多從直觀而來，我們在此舉二個例子。

例1

在第三節問題5，包裝問題中，若採取「能裝就裝」法，即現有的盒子若可以裝得下，就不用新盒子，則此法所需用之盒子數 k₁ 與最可能少的盒子數 k₀ 滿足 。

證明

今令 n 個物品之重為 w₁,w₂,…,w_n 公斤，因每個盒子只可以裝1公斤，故

另一方面，「能裝就裝」法不可能有兩個以上的盒子同時少於 公斤，故

本例得證。

這個問題的結果是說，我們大約可以用「能裝就裝」法做得最好情形的一半好。 經過較複雜的證明，Johnson 在1974年證得，當 n 很大時，

(i)

，且存在一種情形能產生。

(ii)

也就是用「能裝就裝」法不會壞到 70% 以上，但可以壞到多用了 70% 的盒子。

售貨員旅行問題的一個直觀走法是先訪問最近那個尚未訪問過的城，稱為「先訪近城」法，以圖1為例，其走法為

Rosenkrantz 等在1977年證明這並不是一個很理想的走法，他們證出若各城間的距離滿足三角不等式 ⁷ ，則「先訪近城」法所走之總程 D₁ 與最短路徑 D₀ 之關係為

且當 n 很大時，可以有一種情形使得

上式中之 [x] 表示大於 x 之最小整數，例如 [5]=5, [2.5]=3。 因 當 n 大時可以很大，故 D₁ 可與 D₀ 相差非常之大，但在同一篇論文之中，Rosenkrantz 等證明另一種複雜的「直觀」走法可以達到 之地步。

在上面的定理中，三角不等式的條件很重要，若城之距離無此關係存在時，Sahni 與Gonzalez 在1976年證得：若 NP，則不可能存在一個有限的 m，及一個 O(n^k) 計算量的走法，能使其全程長 D₁ 在任何 n 時滿足

即上式中 m 非等於無限大不可，亦即所有 O(n^k) 的做法都不很好。