1、1,第9章 NP完全性理論與近似算法,2,學(xué)習(xí)要點(diǎn) 理解RAM，RASP和圖靈機(jī)計(jì)算模型 理解非確定性圖靈機(jī)的概念 理解P類與NP類語言的概念 理解NP完全問題的概念 理解近似算法的性能比及多項(xiàng)式時間近似格式的概念 通過范例學(xué)習(xí)NP完全問題的近似算法 （1）頂點(diǎn)覆蓋問題； （2）旅行售貨員問題； （3）集合覆蓋問題； （4）子集和問題。,3,在計(jì)算機(jī)算法理論中，最深刻的問題之一是： 從計(jì)算的觀點(diǎn)來看，要解決的問題的內(nèi)在復(fù)雜性如何，它是“易”計(jì)算的還是“難”計(jì)算的。,若知道了一個問題的計(jì)算時間下界，就可以較正確地評價解決該問題的各種算法的效率，進(jìn)而確定對已有算法還有多少改進(jìn)的余地。,在許多情況下

2、，要確定一個問題的內(nèi)在復(fù)雜性是相當(dāng)困難的。但問題的計(jì)算復(fù)雜性可以通過解決該問題所需計(jì)算量的多少來度量。,4,如何區(qū)分一個問題是“難”還是“易”？,人們通常將在多項(xiàng)式時間內(nèi)解決的問題看作是“易”解決的問題，而將需要指數(shù)時間解決的問題看作是“難”問題。（這里是針對問題的規(guī)模而言）,對于實(shí)際遇到的很多問題，人們至今未確切地了解其內(nèi)在的計(jì)算復(fù)雜性。,只能用分類的方法, 將計(jì)算復(fù)雜性大致相同的問題, 歸類研究。,5,計(jì)算模型,在進(jìn)行問題的計(jì)算復(fù)雜性分析之前，首先必須建立求解問題所用的計(jì)算模型，包括定義該計(jì)算模型中所用的基本運(yùn)算。 建立計(jì)算模型的目的, 是為了使問題的計(jì)算復(fù)雜性分析, 有一個共同的客觀尺度

3、。 3個基本計(jì)算模型： 隨機(jī)存取機(jī)RAM(Random Access Machine)； 隨機(jī)存取存儲程序機(jī)RASP(Random Access Stored Program Machine) 圖靈機(jī)(Turing Machine)。 這3個計(jì)算模型在計(jì)算能力上是等價的，但在計(jì)算速度上是不同的。,6,NP完全問題,7,新千年的七個數(shù)學(xué)問題,1900年在巴黎召開的“國際數(shù)學(xué)家大會”上, Hilbert提出著名的23個數(shù)學(xué)問題, 深刻影響(和推動)了20世紀(jì)的數(shù)學(xué)發(fā)展. 在新千年來臨之際, 2000年5月24日，就在希爾伯特提出23個世紀(jì)難題之后的整整一百年后, 在巴黎又宣布了新的7個數(shù)學(xué)問題.

4、這次是由“柯萊數(shù)學(xué)研究所” (/,Clay Math. Inst., Cambridge, MA, USA,)宣布, 為7個問題中的任一個解答設(shè)立一百萬美元獎金.,8,在這7個問題中，排在第一位的是P與NP問題。即 P問題即是可被“運(yùn)行多項(xiàng)式時間的”一個算法解決的問題 (多項(xiàng)式時間: 運(yùn)行時間最多是輸入量的多項(xiàng)式函數(shù)). NP問題即是有一個“可用多項(xiàng)式時間檢驗(yàn)的”解答的問題. P = NP ?,9,2黎曼假設(shè)(RiemannHypothesis):黎曼Zeta函數(shù)的非平凡零點(diǎn)的實(shí)部都是1/2.3龐加萊猜想(PoincareConjecture):任意

5、閉單連通3-流型同胚于3-球.4霍奇猜想(HodgeConjecture):在非奇異復(fù)射影代數(shù)簇上,任一霍奇類是代數(shù)閉鏈類的有理線性組合.5BSD猜想(BirchandSwinnerton-DyerConjecture) 6奈維爾斯托克斯方程(Navier-StokesEquatoins) 7楊米爾斯理論(Yang-MillsTheory):證明諸量子楊米爾斯場存在而且有一個大缺口.,10,背 景,計(jì)算機(jī)處理能力受限于內(nèi)存大小與中央處理器速度等，導(dǎo)致算法本身的數(shù)據(jù)結(jié)構(gòu)對于其執(zhí)行效率有很大的影響。 在分析算法時，主要以時間復(fù)雜度與空間復(fù)雜度兩者為分析依據(jù)。 隨著計(jì)算器發(fā)展迅速，算法的空間復(fù)雜度已

6、經(jīng)不是那么重要的一件事，目前分析主要是在時間復(fù)雜度方面。,P問題：線性時間或者多項(xiàng)式時間內(nèi)能夠解決的問題。如能夠在O(n)、O(nlog2n)、O(nk)數(shù)量級內(nèi)解決的問題。它們都是以多項(xiàng)式時間為上界。 NP問題：不能在多項(xiàng)式時間內(nèi)解決的問題。如計(jì)算時間數(shù)量級為O(n!)、O(2n)。 不可解問題：“圖靈停機(jī)問題” 任何計(jì)算機(jī)耗費(fèi)任意時間不能解決。邏輯學(xué)家阿朗索丘奇證明了所謂的判定問題也是不可解的：判定一個已知的語句是否表達(dá)一個算術(shù)的真值，決不可能有一般的過程。換句話說，能夠輸出所有算術(shù)真值的計(jì)算機(jī)是不存在的 。,P與NP問題,圖靈、圖靈獎及圖靈獎獲得者簡介,1912年6月23日，出生于英國倫

7、敦。 1931年-1934年，在英國劍橋大學(xué)國王學(xué)院學(xué)習(xí)。 1932年-1935年，研究量子力學(xué)、概率論和邏輯學(xué)。 1935年，由于獨(dú)立發(fā)現(xiàn)中心極限定理，獲Smith獎，年僅23歲被選為劍橋大學(xué)國王學(xué)院院士。 1936年，研究可計(jì)算理論，提出“圖靈機(jī)”的構(gòu)想。,1936年-1938年，主要在美國普林斯頓大學(xué)做博士研究，涉及邏輯學(xué)、代數(shù)和數(shù)論等領(lǐng)域。 1938年-1939年，返回劍橋從事研究工作，并應(yīng)邀加入英國政府破譯二戰(zhàn)德軍密碼的工作。 1940年-1942年，作為主要參與者和貢獻(xiàn)者之一，在破譯納粹德國通訊密碼的工作上成就杰出，并成功破譯了德軍U-潛艇密碼，為扭轉(zhuǎn)二戰(zhàn)盟軍的大西洋戰(zhàn)場戰(zhàn)局立下汗

8、馬功勞。,1943年-1945年，擔(dān)任英美密碼破譯部門的總顧問。 1945年,應(yīng)邀在英國國家物理實(shí)驗(yàn)室從事計(jì)算機(jī)理論研究工作。 1946年，圖靈在計(jì)算機(jī)和程序設(shè)計(jì)原始理論上的構(gòu)思和成果，已經(jīng)確定了他的理論開創(chuàng)者的地位。由于圖靈的杰出貢獻(xiàn)，他被英國皇室授予OBE爵士勛銜。 1947年-1948年，主要從事計(jì)算機(jī)程序理論的研究，并同時在神經(jīng)網(wǎng)絡(luò)和人工智能領(lǐng)域做出開創(chuàng)性的理論研究。,1948年，應(yīng)邀加入英國曼徹斯特大學(xué)從事研究工作，擔(dān)任曼徹斯特大學(xué)計(jì)算實(shí)驗(yàn)室副主任。 1949年，成為世上第一位把計(jì)算機(jī)實(shí)際用于數(shù)學(xué)研究的科學(xué)家。 1950年，發(fā)表論文“計(jì)算機(jī)器與智能”，為后來的人工智能科學(xué)提供了開創(chuàng)性

9、的構(gòu)思。提出著名的“圖靈測試”理論。,1951年，提出生物增長的非線性理論研究。年僅39歲即被選為英國皇家學(xué)會會員。 1953年-1954年，繼續(xù)在生物和物理學(xué)等方面的研究。 1954年6月7日，42歲，圖靈死于家中的床上，床頭有一個咬了一半的、在氰化物溶液中浸泡過的蘋果，警方調(diào)查結(jié)論是自殺。 一代英靈，就此過早離去，成為人類科學(xué)史上的一大遺憾。,Turing Award,被公認(rèn)為是計(jì)算機(jī)科學(xué)界的諾貝爾獎最高獎項(xiàng).獎勵在計(jì)算機(jī)科學(xué)技術(shù)研究中做出了創(chuàng)造性貢獻(xiàn)的杰出科學(xué)家. 1966年開始由ACM設(shè)立（美國計(jì)算機(jī)協(xié)會，1947年成立，與IEEE Computer Society并列為計(jì)算機(jī)界最著名

10、的兩大國際學(xué)術(shù)組織），用Turing的名字來命名該獎，以紀(jì)念這位偉人對于計(jì)算機(jī)科學(xué)技術(shù)發(fā)展的功績。 通常每年1名獲獎?wù)? 偶爾2名(同方向)，02年3名(RSA,Rivest,Shamir,Adelman). 雖未明確規(guī)定, 但授獎較偏重于計(jì)算機(jī)科學(xué)理論和軟件技術(shù)方面作出貢獻(xiàn)的科學(xué)家. 唯一華人獲獎?wù)呤且ζ谥?Andrew Yao, 美籍, 2000年),1972，E.W.Dijkstra（美Burroughs公司）：求最短路徑的Dijkstra算法，PV操作，結(jié)構(gòu)化程序設(shè)計(jì)，“goto有害”等 1974，D.E.Knuth（stanford）：算法最早的奠基人之一，現(xiàn)代“算法”與“數(shù)據(jù)結(jié)構(gòu)”

11、等名詞及內(nèi)涵的提出，KMP算法，多卷算法巨著的作者，LR(k)文法，Tex編輯器等。 1976，M.O.Rabin（以色列人）x1,x2,xk)，當(dāng)它屬于的定義域時，Q(TL，R，S)k中有惟一子集(q;x1,x2,xk)與之對應(yīng)?？梢栽?q;x1,x2,xk)中隨意選定一個值作為它的函數(shù)值。,非確定性圖靈機(jī),45,P類與NP類語言,P=L|L是一個能在多項(xiàng)式時間內(nèi)被一臺DTM所接受的語言 NP=L|L是一個能在多項(xiàng)式時間內(nèi)被一臺NDTM所接受的語言,由于一臺確定性圖靈機(jī),可看作是非確定性圖靈機(jī)的特例，所以可在多項(xiàng)式時間內(nèi)被確定性圖靈機(jī)接受的語言,也可在多項(xiàng)式時間內(nèi)被非確定性圖靈機(jī)接受。故P

12、NP。,46,多項(xiàng)式時間變換,設(shè) ， 是2個語言。所謂語言 能在多項(xiàng)式時間內(nèi)變換為語言 (簡記為 p )是指存在映身f: ，且f滿足： (1)有一個計(jì)算f的多項(xiàng)式時間確定性圖靈機(jī)； (2)對于所有x ，x ，當(dāng)且僅當(dāng)f(x) 。,47,語言L是NP完全的當(dāng)且僅當(dāng) (1)LNP； (2)對于所有LNP有L p L。 如果有一個語言L滿足上述性質(zhì)(2)，但不一定滿足性質(zhì)(1)，則稱該語言是NP難的。 所有NP完全語言構(gòu)成的語言類, 稱為NP完全語言類，記為NPC。,48,PNP？ P屬于NP，NP屬于P？ NPC性質(zhì)：任意一個NPC能在多項(xiàng)式時間解決，則所有的NP問題都多項(xiàng)式可解。即PNP。,49,Cook定理（第一個NP完全問題）,(Cook定理)：布爾表達(dá)式的可滿足性問題是NP完全的。,0/1 knapsack Traveling salesperson (TSP) Graph coloring Sum of subsets Multicasting (多播) Hamiltonian cycle Maximum clique Multiple sequence alignment (MS