摘要：綜合論述了組合最優(yōu)化理論與計(jì)算復(fù)雜性理論，尤其是NP-完備理論之間的密切關(guān)系，揭示出NP-完備理論研究的重大理論和現(xiàn)實(shí)意義。

關(guān)鍵詞：組合最優(yōu)化；計(jì)算復(fù)雜性；NP-完備；近似算法

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）13-3140-02

1 組合最優(yōu)化

經(jīng)典數(shù)學(xué)主要研究問(wèn)題的存在性，唯一性和穩(wěn)定性等，很少涉及組合最優(yōu)化問(wèn)題，一個(gè)主要原因就是人們不具備有效的數(shù)值計(jì)算能力。科學(xué)技術(shù)的發(fā)展使得組合最優(yōu)化的重要性日益顯現(xiàn)出來(lái)，而計(jì)算機(jī)的產(chǎn)生與發(fā)展則使得人們的計(jì)算能力大大增強(qiáng)，從而為解決組合最優(yōu)化問(wèn)題提供了可能；同時(shí)，在計(jì)算機(jī)的發(fā)展過(guò)程中，人們又提出了不少亟待解決的組合最優(yōu)化問(wèn)題。由此可見(jiàn)，組合最優(yōu)化與計(jì)算機(jī)科學(xué)是相輔相成，緊密聯(lián)系的。

2 計(jì)算復(fù)雜性

如上所述，組合最優(yōu)化就是要找到適用于計(jì)算機(jī)的計(jì)算方法。這一方法應(yīng)普遍適用于問(wèn)題包含的所有實(shí)例（instance），求出實(shí)例的解。這樣的計(jì)算方法就是算法。算法是計(jì)算機(jī)科學(xué)的核心概念，被譽(yù)為計(jì)算機(jī)科學(xué)的“靈魂”。算法的優(yōu)劣直接關(guān)系到軟件乃至整個(gè)計(jì)算機(jī)系統(tǒng)的性能.。著名的方正排版軟件系統(tǒng)就是基于新的更有效的算法設(shè)計(jì)的。

那么，評(píng)價(jià)一個(gè)算法是否有效的標(biāo)準(zhǔn)是什么呢？一般而言，理論計(jì)算機(jī)科學(xué)界普遍以算法的計(jì)算復(fù)雜性，即算法在最壞情形（worst case）下的運(yùn)行時(shí)間作為評(píng)價(jià)其有效與否的標(biāo)準(zhǔn)。然而，算法的運(yùn)行時(shí)間與很多因素有關(guān)，如計(jì)算機(jī)的速度，問(wèn)題的規(guī)模等。首先，我們假定算法是在“理想計(jì)算機(jī)”上運(yùn)行的。理想計(jì)算機(jī)只能執(zhí)行最基本的加、減、乘、除、大小比較等基本運(yùn)算，且耗費(fèi)的時(shí)間都是一個(gè)時(shí)間單位。因此，算法的運(yùn)行時(shí)間常用算法所執(zhí)行的基本運(yùn)算的次數(shù)來(lái)表示。其次，一個(gè)待解決的問(wèn)題的實(shí)例總是以一定的規(guī)模（size）輸入計(jì)算機(jī)中的，如圖和網(wǎng)絡(luò)的頂點(diǎn)數(shù)和邊數(shù)。因此，可設(shè)法估計(jì)出算法對(duì)規(guī)模為[n]的實(shí)例需執(zhí)行的基本運(yùn)算的次數(shù)的一個(gè)上界[f（n）]，將函數(shù)[f（n）]作為該算法的計(jì)算復(fù)雜性[1-3]。

顯然，即使對(duì)于同一個(gè)問(wèn)題的實(shí)例，不同的算法的計(jì)算復(fù)雜性也是不同的。以下面的旅行售貨員問(wèn)題[1]為例：有[n]個(gè)城市，任兩城市之間都有路相通。一售貨員擬從他所在的城市到其它[n-1]個(gè)城市去售貨。問(wèn)：這個(gè)售貨員應(yīng)如何選擇路線，才能經(jīng)過(guò)每個(gè)城市恰好一次，再回到原地，且總路程最短？

由數(shù)值計(jì)算理論知，當(dāng)變量的個(gè)數(shù)增加時(shí)，多項(xiàng)式函數(shù)比指數(shù)函數(shù)增加的速度慢很多?；谶@一事實(shí)，人們通常認(rèn)為只有計(jì)算復(fù)雜性是多項(xiàng)式函數(shù)的（精確的）算法才是有效的算法。在上例中，由Stirling公式知，枚舉法的計(jì)算復(fù)雜性是[n ！≈2nπ×（ne）n]，顯然不是一個(gè)有效算法。

3 NP-完備理論

在NP類問(wèn)題中有這樣一些問(wèn)題，如果其中有一個(gè)存在（不存在）有效算法，那么所有其它問(wèn)題也都存在（不存在）有效算法，這些問(wèn)題被稱為NP-完備問(wèn)題或NPC問(wèn)題。絕大多數(shù)組合最優(yōu)化問(wèn)題都是NP-完備的。

NP問(wèn)題的研究始于20世紀(jì)70年代。1971年，圖靈獎(jiǎng)得主Cook[4]證明了第一個(gè)NP-完備問(wèn)題-適應(yīng)性（satisfiability）問(wèn)題。1972年，另一個(gè)圖靈獎(jiǎng)得主Karp[5]證明了24個(gè)NP-完備問(wèn)題。到目前為止，大約有兩千多個(gè)問(wèn)題被證明是NP-完備的；然而，遺憾的是，人們尚未找到任何一個(gè)NP-完備問(wèn)題的有效算法。但是鑒于NP-完備問(wèn)題在理論和應(yīng)用上的重要性，人們又不能回避它們。幸運(yùn)的是，在很多實(shí)際應(yīng)用中，人們只需找到NP-完備問(wèn)題的“不錯(cuò)的”解，而不必是最優(yōu)解。因而，近似算法成為求解NP-完備問(wèn)題的方法之一。

4 結(jié)束語(yǔ)

生命科學(xué)和生物工程被稱為當(dāng)今科學(xué)技術(shù)的又一次革命。在這一偉大工程的研究過(guò)程中，許許多多包括NP-完備的組合最優(yōu)化問(wèn)題在內(nèi)的困難問(wèn)題被提出來(lái)，計(jì)算生物學(xué)（computational biology）或生物信息學(xué)（bioinformatics）也隨之應(yīng)運(yùn)而生。近似算法技術(shù)在這一新興學(xué)科的諸多研究領(lǐng)域都得到了成功地應(yīng)用，如基因組的排序（genome sorting），進(jìn)化樹（phylogenetic tree）的構(gòu)建，蛋白質(zhì)結(jié)構(gòu)的測(cè)定等。我們相信：伴隨NP理論的深入研究和NP完備問(wèn)題的最終解決，組合最優(yōu)化的理論和方法必將為人類文明作出更大的貢獻(xiàn)。

參考文獻(xiàn)：

[1] 劉家壯，徐源.網(wǎng)絡(luò)最優(yōu)化[M].北京：高等教育出版社，1991.

[2] 顧小豐，孫世新，盧光輝.計(jì)算復(fù)雜性[M].北京：機(jī)械工業(yè)出版社，2005.

[3] 蘇德富，鐘誠(chéng).計(jì)算機(jī)算法與分析[M]. 2版.北京：電子工業(yè)出版社，2005

[4] S. A. Cook. The complexity of theorem proving procedures[J]. Proc. 3rd ACM Symp. On the Theory of Computing， ACM， 1971， 1514-158.

[5] R. M. Karp. On the complexity of combinatorial problems[J]. Networks， 1975， 45-68.

[6] N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem[R]. Technical Report， Graduate School of Industrial Administration， Carnegie-Melon University， Pittsburgh， PA 1976.

[7] L. G. Khachiyan. A polynomial algorithm in linear programming[J]. Soviet Math. Dokl.，1979，191-194.