NP難問題求解綜述

1、第 頁共16頁NP難問題求解綜述摘要：定義NP問題及P類問題，并介紹一些常見的NP問題，以及NP問題的一些求解方法，最后最NP問題求解的發(fā)展方向做一些展望。關(guān)鍵詞：NP難問題P類問題算法最優(yōu)化問題正文：一，NP難問題及P類問題為了解釋NP難問題及P類問題，先介紹確定性算法和非確定性算法這兩個概念，設(shè)A是求解問題n的一個算法，如果在算法的整個執(zhí)行過程中，每一步只有一個確定的選擇，則稱算法A是確定性(Determinism)算法。設(shè)A是求解問題n的一個算法，如果算法A以如下猜測并驗證的方式工作，就稱算法A是非確定性(Nondeterminism)算法：(1)猜測階段：在這個階段，對問題的輸入實例產(chǎn)

2、生一個任意字符串y,在算法的每一次運行時，串y的值可能不同，因此，猜測以一種非確定的形式工作。(2)驗證階段：在這個階段，用一個確定性算法驗證：檢查在猜測階段產(chǎn)生的串y是否是合適的形式，如果不是，則算法停下來并得到no；如果串y是合適的形式，則驗證它是否是問題的解，如果是，則算法停下來并得到y(tǒng)es,否則算法停下來并得到no。什么是np難問題，如果對于某個判定問題n，存在一個非負整數(shù)k,對于輸入規(guī)模為n的實例，能夠以O(shè)(nk)的時間運行一個非確定性算法，得到y(tǒng)es或no的答案，則該判定問題n是一個NP類(NondeterministicPolynomial)問題。令n是一個判定問題，如果對于np

3、類問題中的每一個問題n，都有npn，則稱判定問題n是一個np難問題。什么是p類問題，如果對于某個判定問題n，存在一個非負整數(shù)k,對于輸入規(guī)模為n的實例，能夠以O(shè)(nk)的時間運行一個確定性算法，得到y(tǒng)es或no的答案，則該判定問題口是一個P類(Polynomial)問題。所有易解問題都是P類問題。P類問題和NP類問題的主要差別：P類問題可以用多項式時間的確定性算法來進行判定或求解；NP類問題可以用多項式時間的非確定性算法來進行判定或求解。二，常見的NP類問題上面介紹了什么是NP問題，下面我將介紹我查閱到的一些常見的NP問題，他們同時也是著名的NP問題。，圖著色問題：按圖中所示方式將16條邊著色

4、，那么不管你從哪里出發(fā)，按照“藍紅紅藍紅紅藍紅紅”的路線走9步，你最后一定達到黃色頂點。路線著色定理就是說在滿足一定條件的有向圖中，這樣的著色方式一定存在。嚴格的數(shù)學描述如下。我們首先來定義同步著色。G是一個有限有向圖并且G的每個頂點的出度都是k。G的一個同步著色滿足以下兩個條件：1)G的每個頂點有且只有一條出邊被染成了1到k之間的某種顏色；2)G的每個頂點都對應(yīng)一種走法，不管你從哪里出發(fā)，按該走法走，最后都結(jié)束在該頂點。有向圖G存在同步著色的必要條件是G是強連通而且是非周期的。一個有向圖是非周期的是指該圖中包含的所有環(huán)的長度沒有大于1的公約數(shù)。路線著色定理這兩個條件(強連通和是非周期)也是充

5、分的。也就是說,有向圖G存在同步著色當且僅當G是強連通而且是非周期的。，哈密頓回路問題：天文學家哈密頓(WilliamRowanHamilton)提出，在一個有多個城市的地圖網(wǎng)絡(luò)中，尋找一條從給定的起點到給定的終點沿途恰好經(jīng)過所有其他城市一次的路徑。這個問題和著名的過橋問題的不同之處在于，某些城市之間的旅行不一定是雙向的。比如AB,但BA是不允許的。換一種說法，對于一個給定的網(wǎng)絡(luò)，確定起點和終點后，如果存在一條路徑，穿過這個網(wǎng)絡(luò)，我們就說這個網(wǎng)絡(luò)存在哈密頓路徑。哈密頓路徑問題在上世紀七十年代初，終于被證明是“NP完備”的。據(jù)說具有這樣性質(zhì)的問題，難于找到一個有效的算法。實際上對于某些頂點數(shù)不到

6、100的網(wǎng)絡(luò)，利用現(xiàn)有最好的算法和計算機也需要很長的時間(可能要幾百年之久)才能確定其是否存在一條這樣的路徑。，TSP問題：旅行商問題，即TSP問題(TravelingSalesmanProblem)是數(shù)學領(lǐng)域中著名問題之一。假設(shè)有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。TSP問題是一個組合優(yōu)化問題。該問題可以被證明具有NPC計算復(fù)雜性。上面三個即是非常著名的NP問題，也是比較常見的NP問題。它們的求解算法非常復(fù)雜，要尋找到一個最優(yōu)算法需要花費很長的時間，但正因為

7、這些問題的復(fù)雜性，使得它們備受人們的關(guān)注。當然NP問題本身也是世界七大數(shù)學難題之一。三，求解NP類問題的常見方法對于那些棘手的NP問題，我們也并非束手無策，有一些方法可供我們?nèi)ヌ骄縉P問題。，近似算法：所有已知的解決NP難問題算法都有指數(shù)型運行時間。但是，如果我們要找一個“好”解而非最優(yōu)解，有時候多項式算法是存在的。給定一個最小化問題和一個近似算法，我們按照如下方法評價算法：首先給出最優(yōu)解的一個下界，然后把算法的運行結(jié)果與這個下界進行比較。對于最大化問題，先給出一個上界然后把算法的運行結(jié)果與這個上界比較。近似算法比較經(jīng)典的問題包括：最小頂點覆蓋、旅行售貨員問題、集合覆蓋等。，概率算法：很多算法

8、的每一個計算步驟都是固定的，而概率算法允許算法在執(zhí)行的過程中隨機選擇下一個計算步驟。許多情況下，當算法在執(zhí)行過程中面臨一個選擇時，隨機性選擇常比最優(yōu)選擇省時。因此概率算法可在很大程度上降低算法的復(fù)雜度。概率算法的一個基本特征是對所求解問題的同一實例用同一概率算法求解兩次可能得到完全不同的效果。這兩次求解問題所需的時間甚至所得到的結(jié)果可能會有相當大的差別。一般情況下，可將概率算法大致分為四類:數(shù)值概率算法，蒙特卡羅(MonteCarlo)算法，拉斯維加斯(LasVegas)算法和舍伍德(Sherwood)算法。，并行計算：并行計算或稱平行計算是相對于串行計算來說的。所謂并行計算可分為時間上的并行

9、和空間上的并行。時間上的并行就是指流水線技術(shù)，而空間上的并行則是指用多個處理器并發(fā)的執(zhí)行計算。并行計算(ParallelComputing)是指同時使用多種計算資源解決計算問題的過程。為執(zhí)行并行計算，計算資源應(yīng)包括一臺配有多處理機(并行處理)的計算機、一個與網(wǎng)絡(luò)相連的計算機專有編號，或者兩者結(jié)合使用。并行計算的主要目的是快速解決大型且復(fù)雜的計算問題。此外還包括：利用非本地資源，節(jié)約成本一使用多個“廉價”計算資源取代大型計算機，同時克服單個計算機上存在的存儲器限制。包含以下三個特征：1，將工作分離成離散部分，有助于同時解決；2，隨時并及時地執(zhí)行多個程序指令；,3，多計算資源下解決問題的耗時要少于

10、單個計算資源下的耗時。，智能算法：在工程實踐中，經(jīng)常會接觸到一些比較“新穎”的算法或理論，比如模擬退火，遺傳算法，禁忌搜索，神經(jīng)網(wǎng)絡(luò)等。這些算法或理論都有一些共同的特性(比如模擬自然過程)，通稱為“智能算法”。智能優(yōu)化算法要解決的一般是最優(yōu)化問題。最優(yōu)化問題可以分為(1)求解一個函數(shù)中，使得函數(shù)值最小的自變量取值的函數(shù)優(yōu)化問題和(2)在一個解空間里面，尋找最優(yōu)解，使目標函數(shù)值最小的組合優(yōu)化問題。典型的組合優(yōu)化問題有：旅行商問題(TravelingSalesmanProblem，TSP)，加工調(diào)度問題(SchedulingProblem)，01背包問題(KnapsackProblem),以及裝箱

11、問題(BinPackingProblem)等。優(yōu)化算法有很多，經(jīng)典算法包括：有線性規(guī)劃，動態(tài)規(guī)劃等；改進型局部搜索算法包括爬山法，最速下降法等，本文介紹的模擬退火、遺傳算法以及禁忌搜索稱作指導(dǎo)性搜索法。而神經(jīng)網(wǎng)絡(luò)，混沌搜索則屬于系統(tǒng)動態(tài)演化方法。四，NP問題求解未來發(fā)展方向NP問題是世界七大數(shù)學難題之一，在名稱上就有別于其它六個問題，也是其中唯一一個不是用人名來命名的數(shù)學難題。因為它不是某個數(shù)學家火花一閃、靈機一動所提出的理論或是猜測，而是一個非常古老的問題，涉及到了最基礎(chǔ)的數(shù)學理論，并且經(jīng)過了幾百年來無數(shù)數(shù)學家們持之以恒的努力，直到現(xiàn)在仍然是一個沒有得到解決的公開問題。NP問題排在世界七大數(shù)學難題之首，七個問題都是經(jīng)過美國克雷數(shù)學研究所的科學顧問委員會精心挑選出來的，這些問題的獲解上哪怕是獲得了些許的進展，就將對數(shù)學理論的發(fā)展和應(yīng)用產(chǎn)生極其巨大的推動作用。研究這些“千年大獎問題”已經(jīng)成為世界數(shù)學界的熱點，不少國家的數(shù)學家正在組織聯(lián)合攻關(guān)，同時它們也是任何一個數(shù)學工作者都夢寐以求予以摘取的數(shù)學皇冠上的耀眼明珠?？梢灶A(yù)期，這些“千年大獎問題”將會改變新世紀數(shù)學發(fā)展