計算機算法分析與設計第9章.ppt

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

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

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

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

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

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

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

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

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

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

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

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