np難問題求解綜述

《np難問題求解綜述》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

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

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

3、rministicPolynomial）問題。令Π是一個判定問題，如果對于NP類問題中的每一個問題Π'，都有Π'∝pΠ，則稱判定問題Π是一個NP難問題。什么是P類問題，如果對于某個判定問題Π，存在一個非負整數(shù)k，對于輸入規(guī)模為n的實例，能夠以O(shè)(nk)的時間運行一個確定性算法，得到y(tǒng)es或no的答案，則該判定問題Π是一個P類（Polynomial）問題。所有易解問題都是P類問題。P類問題和NP類問題的主要差別：P類問題可以用多項式時間的確定性算法來進行判定或求解；NP類問題可以用多項式時間的非確定性算法來進行判定或求解。二，常見的NP類問題上面介紹了

4、什么是NP問題，下面我將介紹我查閱到的一些常見的NP問題，他們同時也是著名的NP問題。①，圖著色問題：按圖中所示方式將16條邊著色，那么不管你從哪里出發(fā)，按照“藍紅紅藍紅紅藍紅紅”的路線走9步，你最后一定達到黃色頂點。路線著色定理就是說在滿足一定條件的有向圖中，這樣的著色方式一定存在。嚴(yán)格的數(shù)學(xué)描述如下。我們首先來定義同步著色。G是一個有限有向圖并且G的每個頂點的出度都是k。G的一個同步著色滿足以下兩個條件：1)G的每個頂點有且只有一條出邊被染成了1到k之間的某種顏色；2)G的每個頂點都對應(yīng)一種走法，不管你從哪里出發(fā)，按該走法走，最后都結(jié)束在該頂點。

5、有向圖G存在同步著第3頁共3頁色的必要條件是G是強連通而且是非周期的。一個有向圖是非周期的是指該圖中包含的所有環(huán)的長度沒有大于1的公約數(shù)。路線著色定理這兩個條件(強連通和是非周期)也是充分的。也就是說,有向圖G存在同步著色當(dāng)且僅當(dāng)G是強連通而且是非周期的。②，哈密頓回路問題：天文學(xué)家哈密頓(WilliamRowanHamilton)提出，在一個有多個城市的地圖網(wǎng)絡(luò)中，尋找一條從給定的起點到給定的終點沿途恰好經(jīng)過所有其他城市一次的路徑。這個問題和著名的過橋問題的不同之處在于，某些城市之間的旅行不一定是雙向的。比如A→B,但B→A是不允許的。換一種說法，

6、對于一個給定的網(wǎng)絡(luò)，確定起點和終點后，如果存在一條路徑，穿過這個網(wǎng)絡(luò)，我們就說這個網(wǎng)絡(luò)存在哈密頓路徑。哈密頓路徑問題在上世紀(jì)七十年代初，終于被證明是“NP完備”的。據(jù)說具有這樣性質(zhì)的問題，難于找到一個有效的算法。實際上對于某些頂點數(shù)不到100的網(wǎng)絡(luò)，利用現(xiàn)有最好的算法和計算機也需要很長的時間（可能要幾百年之久）才能確定其是否存在一條這樣的路徑。③，TSP問題：旅行商問題，即TSP問題（TravelingSalesmanProblem）是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個城市只能拜訪一次，

7、而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。TSP問題是一個組合優(yōu)化問題。該問題可以被證明具有NPC計算復(fù)雜性。上面三個即是非常著名的NP問題，也是比較常見的NP問題。它們的求解算法非常復(fù)雜，要尋找到一個最優(yōu)算法需要花費很長的時間，但正因為這些問題的復(fù)雜性，使得它們備受人們的關(guān)注。當(dāng)然NP問題本身也是世界七大數(shù)學(xué)難題之一。三，求解NP類問題的常見方法對于那些棘手的NP問題，我們也并非束手無策，有一些方法可供我們?nèi)ヌ骄縉P問題。①，近似算法：所有已知的解決NP難問題算法都有指數(shù)型運行時間。但是，如果我們要找一個

8、“好”解而非最優(yōu)解，有時候多項式算法是存在的。給定一個最小化問題和一個近似算法，我們按照如下方法評價算法：首