NP問(wèn)題的通用多項(xiàng)式算法

王海東

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

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

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

從這個(gè)公式來(lái)看，在計(jì)算數(shù)據(jù)位數(shù)較小的情況下，P類問(wèn)題和E類問(wèn)題在理論上都是人類可以有效解決的計(jì)算問(wèn)題.但是，在計(jì)算數(shù)據(jù)位數(shù)較大的情況下，P類問(wèn)題在理論上仍然是人類可以有效解決的計(jì)算問(wèn)題，E類問(wèn)題在理論上則不是人類可以有效解決的計(jì)算問(wèn)題了.因?yàn)椋珽類問(wèn)題計(jì)算時(shí)間的增長(zhǎng)速度不僅遠(yuǎn)遠(yuǎn)超過(guò)了P類問(wèn)題計(jì)算時(shí)間的增長(zhǎng)速度，而且有可能遠(yuǎn)遠(yuǎn)超過(guò)幾代甚至十幾代或幾十代人類的生存時(shí)間.

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

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

下面，我們就以流動(dòng)推銷員問(wèn)題為例來(lái)尋找NP問(wèn)題的通用多項(xiàng)式算法.

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

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

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

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

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

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

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

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

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

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

已知

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

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

已知

又知

x13=x31

x23=x32

x14=x41

x24=x42

因此

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

證畢

由此可見(jiàn)，最短路線選擇定理和最短路線構(gòu)造定理就是流動(dòng)推銷員問(wèn)題的多項(xiàng)式算法.流動(dòng)推銷員問(wèn)題的多項(xiàng)式算法就是NP問(wèn)題的通用多項(xiàng)式算法.因?yàn)椋鲃?dòng)推銷員問(wèn)題就是一種具有特殊性質(zhì)的NP問(wèn)題.任何一種可以化為流動(dòng)推銷員問(wèn)題的NP問(wèn)題，都可以用最短路線選擇定理和最短路線構(gòu)造定理來(lái)解決.

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