NP問題的通用多項式算法

王海東

(天津市北方調(diào)查策劃事務(wù)所 300050)

不管擁有多么強大的計算能力和多么先進的計算工具，人類面臨的所有計算問題都可以分為兩類.這兩類計算問題就是P類問題和E類問題.P類問題就是給出計算結(jié)果的時間為多項式時間的計算問題.多項式時間就是用多項式時間函數(shù)表示的計算時間.多項式時間函數(shù)就是將計算步驟視為多項式變量的時間函數(shù).E類問題就是給出計算結(jié)果的時間為指數(shù)時間的計算問題.指數(shù)時間就是用指數(shù)時間函數(shù)表示的計算時間.指數(shù)時間函數(shù)就是將計算步驟視為指數(shù)變量的時間函數(shù).

令t代表計算時間，s代表計算步驟，C代表重復(fù)計算次數(shù)，N代表計算數(shù)據(jù)位數(shù)，k代表任意正整數(shù)，P代表多項式時間，E代表指數(shù)時間，我們可以用以下公式表示多項式時間和指數(shù)時間：

從這個公式來看，在計算數(shù)據(jù)位數(shù)較小的情況下，P類問題和E類問題在理論上都是人類可以有效解決的計算問題.但是，在計算數(shù)據(jù)位數(shù)較大的情況下，P類問題在理論上仍然是人類可以有效解決的計算問題，E類問題在理論上則不是人類可以有效解決的計算問題了.因為，E類問題計算時間的增長速度不僅遠遠超過了P類問題計算時間的增長速度，而且有可能遠遠超過幾代甚至十幾代或幾十代人類的生存時間.

那么，怎樣才能使E類問題像P類問題一樣，不管計算數(shù)據(jù)位數(shù)如何發(fā)生變化，都能在理論上成為人類可以有效解決的計算問題呢？顯然，回答這個問題的關(guān)鍵在于是否存在NP問題.NP問題就是具有非確定性多項式時間的計算問題.非確定性多項式時間就是可以采取非確定性方法有效解決各種E類問題的多項式時間.非確定性方法就是通過一次計算就能從可供選擇的眾多答案中找到正確答案的計算方法.

假定不存在NP問題，人類就只能采取計算近似值或特征值的替代方法，來解決那些在理論上不能有效解決的E類問題了.假定存在NP問題，另一個問題就會隨之而來：NP問題到底是不是一種P類問題？如果NP問題是一種P類問題，NP問題就肯定具有NP完全性.如果NP問題不是一種P類問題，NP問題就肯定不具有NP完全性.NP完全性是指：存在著一種具有特殊性質(zhì)的NP問題.只要這種NP問題存在著一種多項式算法，這種多項式算法就可以被推廣到其他任何一種NP問題之中.因為，所有NP問題在理論上都存在著某種相同的多項式時間.多項式算法就是適用于多項式時間的計算方法.由于NP完全性意味著NP問題可能存在通用多項式算法，所以能否找到這種通用多項式算法就變成了回答上述所有問題的關(guān)鍵.

下面，我們就以流動推銷員問題為例來尋找NP問題的通用多項式算法.

流動推銷員問題是奧地利數(shù)學(xué)家門格提出的一個計算問題.這個計算問題在各種計算領(lǐng)域之中具有廣泛的代表性.我們可以用一個n階方陣來表述這個計算問題：

其中，主對角線元素為零元素，非主對角線元素為非零元素.第一組行列元素代表第一座城市與其他城市之間的往返距離，第二組行列元素代表第二座城市與其他城市之間的往返距離，第三組行列元素代表第三座城市與其他城市之間的往返距離，以此類推直至第n組行列元素.

假定流動推銷員居住在第一座城市，其他城市都是流動推銷員從事推銷工作的城市.所謂流動推銷員問題，就是從第一座城市與其他城市之間的所有往返路線中選出一條最短路線的計算問題.

那么，第一座城市與其他城市之間到底有多少往返路線呢？顯然，第一座城市與其他城市之間的往返路線數(shù)等于(n-1)的階乘數(shù).從這個階乘數(shù)來看，當(dāng)n的位數(shù)達到兩位數(shù)之后，流動推銷員問題就會變成流動推銷員本人無法有效解決的E類問題了.因此，流動推銷員問題是一個與NP問題有關(guān)的計算問題.由于流動推銷員問題是一個與NP問題有關(guān)的計算問題，所以流動推銷員問題也是一個與NP完全性有關(guān)的計算問題.

問題是和解決問題的方法一起產(chǎn)生的.既然流動推銷員問題可以用一個n階方陣表述出來，這個n階方陣就肯定包含著有效解決這個問題的某種方法.這種方法來自于這個n階方陣為我們提供的兩個重要信息.

第一個重要信息是：主對角線左右兩側(cè)的非零行列元素都屬于對稱元素.如果將穿越主對角線的往返路線視為無效路線，主對角線左右兩側(cè)就存在著兩套相互對稱的往返路線.只要從主對角線一側(cè)找出一條往返路線，就可以從主對角線另一側(cè)找出另一條往返距離相同的往返路線.雖然第一座城市與其他城市之間的往返路線數(shù)等于(n-1)的階乘數(shù)，但是可供選擇的往返路線數(shù)僅僅等于這個階乘數(shù)的二分之一.

第二個重要信息是：主對角線左右兩側(cè)的非零行列元素都包含最短距離.如果將包含最短距離的非零行列元素集中排列在主對角線的左上角或右下角，就可以利用這些非零行列元素的相鄰關(guān)系構(gòu)造出一條最短距離最多的往返路線.由于每條往返路線的往返距離既有可能來自最短距離又有可能來自非最短距離，又由于最短距離的增加意味著非最短距離的減少和往返距離的縮短，所以最短距離最多的往返路線就是一條最短路線.

根據(jù)以上分析，我們可以推出兩個十分重要的計算定理.這兩個計算定理就是最短路線選擇定理和最短路線構(gòu)造定理.

最短路線選擇定理是指：某條往返路線為最短路線當(dāng)且僅當(dāng)最短距離數(shù)超過其他任何一條往返路線.

令u代表一組最短距離，v代表一組非最短距離，L代表一組往返路線，minL代表最短路線，我們可以用以下方法來證明最短路線選擇定理：

已知

u=(u1,u2,u3,…,un)

v=(v1,v2,v3,…,vn)

L=(L1,L2,L3,…,Ln)

又知

u1

L1=u1+v2+v3+v4+…+vn

L2=u1+u2+v3+v4+…+vn

L3=u1+u2+u3+v4+…+vn

……

Ln=u1+u2+u3+u4+…+un

因此

minL=Ln

證畢.

最短路線構(gòu)造定理是指：在一個主對角線元素為零元素、非主對角線元素為非零元素的n階方陣中，只有將包含最短距離的非零行列元素集中排列在主對角線的左上角或右下角，才能用最短時間構(gòu)造出一條最短距離最多的往返路線.

我們可以用一個流動推銷員問題的具體案例來證明最短路線構(gòu)造定理：

已知

又知

x13=x31

x23=x32

x14=x41

x24=x42

因此

minL=x13+x23+x24+x14+…+x31+x32+x42+x41

證畢

由此可見，最短路線選擇定理和最短路線構(gòu)造定理就是流動推銷員問題的多項式算法.流動推銷員問題的多項式算法就是NP問題的通用多項式算法.因為，流動推銷員問題就是一種具有特殊性質(zhì)的NP問題.任何一種可以化為流動推銷員問題的NP問題，都可以用最短路線選擇定理和最短路線構(gòu)造定理來解決.

在找到了NP問題的通用多項式算法之后，我們就可以對上述所有問題做出回答了：由于NP問題存在通用多項式算法，所以NP問題就是一種P類問題.這種P類問題不僅大量存在于各種計算領(lǐng)域，而且確實有可能用非確定性方法一次給出正確答案.這種非確定性方法就是符合最短路線選擇定理和最短路線構(gòu)造定理的計算方法.