未來數學家的挑戰 (第 5 頁)

　1│2│3│4│5│6│7　

未來數學家的挑戰
計算量問題（第 5 頁）

楊照崑;楊重駿

首頁 | 搜尋

．原載於數學傳播十卷二期
．作者當時任教於美國佛羅里大學統計系;美國海軍研究實驗所

‧註釋
‧對外搜尋關鍵字

五、NP-complete 問題之近似解

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

例1

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

證明

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

$\begin{displaymath} k_0\geq \sum_{i=1}^{n}{w_i} \end{displaymath}$

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

$\begin{displaymath} k_1\leq 2\sum_{i=1}^{n}{w_i}+1 \end{displaymath}$

本例得證。

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

(i): $k_1\leq \frac{17}{10} k_0+2$ ，且存在一種情形能產生。
(ii): $k_1\geq \frac{17}{10} (k_0-1)$

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

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

$\begin{displaymath} A\rightarrow G\rightarrow C\rightarrow B\rightarrow D\rightarrow F\rightarrow E\rightarrow A \end{displaymath}$

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

$\begin{displaymath} D_1\leq \frac{1}{2}([\log_2n]+1)D_0 \end{displaymath}$

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

$\begin{displaymath} D_1\geq \frac{1}{3}(\log_2n+\frac{4}{3})D_0 \end{displaymath}$

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

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

$\begin{displaymath} D_1\leq mD_0 \end{displaymath}$

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

　1│2│3│4│5│6│7　


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

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

編輯：王昱昇 ∕ 校對：陳文是 ∕ 繪圖：簡立欣

最後修改日期：6/29/2002