上頁 1234567 次頁

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

楊照崑;楊重駿

 

首頁 | 搜尋

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

註釋
對外搜尋關鍵字
 
五、NP-complete 問題之近似解

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

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

證明
今令 n 個物品之重為 w1,w2,…,wn 公斤,因每個盒子只可以裝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年證明這並不是一個很理想的走法,他們證出若各城間的距離滿足三角不等式 7 ,則「先訪近城」法所走之總程 D1 與最短路徑 D0 之關係為

\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 大時可以很大,故 D1 可與 D0 相差非常之大,但在同一篇論文之中,Rosenkrantz 等證明另一種複雜的「直觀」走法可以達到 $D_1\leq 2D_0$ 之地步。

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

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

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

   

上頁 1234567 次頁

回頁首
 
(若有指正、疑問……,可以在此 留言寫信 給我們。)
EpisteMath

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


編輯:王昱昇 / 校對:陳文是 / 繪圖:簡立欣 最後修改日期:6/29/2002