算法設(shè)計(jì)與分析NP完全問(wèn)題一些重要的概念PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析NP完全問(wèn)題一些重要的完全問(wèn)題一些重要的概念概念2021-7-202第1頁(yè)/共19頁(yè)2021-7-203 不過(guò)，有些指數(shù)時(shí)間算法在實(shí)際中可能十分有用。作為定義，時(shí)間復(fù)雜性是一種最壞情況的度量時(shí)間復(fù)雜性是一種最壞情況的度量。時(shí)間復(fù)雜性為2n的算法僅僅表示至少有一個(gè)規(guī)模為n的問(wèn)題實(shí)例需要這么多的運(yùn)算時(shí)間，而大多數(shù)問(wèn)題實(shí)例可能實(shí)際上需要遠(yuǎn)比這個(gè)少得多的時(shí)間。有幾個(gè)著名的算法就是這種情況。已經(jīng)證明線性規(guī)劃的單純形算法單純形算法具有指數(shù)時(shí)間復(fù)雜性Klee and Minty，1972，但是在實(shí)際中它計(jì)算得很好，給人留下了深刻印象。同樣，背包問(wèn)題背包問(wèn)題的分支界限算法分

2、支界限算法雖然也具有指數(shù)時(shí)間復(fù)雜性，但是它是一種非常成功的算法，使得許多人認(rèn)為背包問(wèn)題已經(jīng)很好地解決了。第2頁(yè)/共19頁(yè)2021-7-204 遺憾的是，像這樣的例子太少了。雖然對(duì)于很多問(wèn)題都知道指數(shù)時(shí)間算法，但是只有少數(shù)幾個(gè)被認(rèn)為在實(shí)際中是很有用的。甚至上面提到的那幾個(gè)成功的指數(shù)時(shí)間算法也沒(méi)有使研究人員停止繼續(xù)尋找這些問(wèn)題的多項(xiàng)式時(shí)間算法的努力。實(shí)際上，這些算法的真正成功產(chǎn)生了一種猜疑，認(rèn)為它們不知怎么地抓住了這些問(wèn)題的關(guān)鍵性的性質(zhì)，對(duì)這些性質(zhì)的仔細(xì)研究可能給出更好的方法，至今在解釋這種成功方面幾乎毫無(wú)進(jìn)展，也沒(méi)有一種方法能夠事先預(yù)言給定的指數(shù)時(shí)間算法在實(shí)際中能否快速運(yùn)算。第3頁(yè)/共19頁(yè)20

3、21-7-205 另一方面，如果多項(xiàng)式時(shí)間算法滿足對(duì)運(yùn)算時(shí)間更嚴(yán)格得多的限制，就往往可以作出這種預(yù)言。雖然可以認(rèn)為時(shí)間復(fù)雜性為n100或1099n2的算法在實(shí)際中不大可能快速運(yùn)算，但是自然提出的多項(xiàng)式可解的問(wèn)題大多數(shù)可用2次，或者在最壞的情況下用3次多項(xiàng)式時(shí)間算法求解，而且在多項(xiàng)式中不包含特別大的系數(shù)，可以認(rèn)為滿足這些限制的算法是“可可證地有效證地有效”算法。正是這種特別需要的性質(zhì)使我們優(yōu)先考慮用多項(xiàng)式時(shí)間算法解決問(wèn)題。第4頁(yè)/共19頁(yè)2021-7-206 關(guān)于計(jì)算機(jī)模型計(jì)算機(jī)模型的選擇可以作類似的注釋。至今研究過(guò)的所有實(shí)際的計(jì)算機(jī)模型，例如單帶圖靈機(jī)單帶圖靈機(jī)，多帶圖靈機(jī)多帶圖靈機(jī)以及隨機(jī)存

4、取機(jī)隨機(jī)存取機(jī)（RAM）都是相對(duì)于多項(xiàng)式時(shí)間復(fù)雜性等價(jià)的，人們可以指望任何其它“合理的”模型都享有這種等價(jià)性。這里所說(shuō)的“合理的”概念在本質(zhì)上是指在單位時(shí)間內(nèi)可以完成的工作量有一個(gè)多項(xiàng)式界限。例如，不能認(rèn)為具有完成任意多道并行運(yùn)算能力的模型是“合理的“，而且也確實(shí)不存在一合計(jì)算機(jī)具有這種能力。無(wú)論如何，只要我們規(guī)只要我們規(guī)定只采用實(shí)際的計(jì)算機(jī)標(biāo)準(zhǔn)模型，難解的問(wèn)題類就不定只采用實(shí)際的計(jì)算機(jī)標(biāo)準(zhǔn)模型，難解的問(wèn)題類就不受使用的具體模型的影響受使用的具體模型的影響。因而我們可以根據(jù)方便與否來(lái)選擇計(jì)算機(jī)模型，而不會(huì)妨礙結(jié)果的使用。 “合理的”計(jì)算機(jī)模型也稱為是“確定型確定型”（deterministic

5、)的計(jì)算機(jī)模型。第5頁(yè)/共19頁(yè)2021-7-207 這樣一來(lái)，“難解的”定義在理論上給出了重要的一般原則。即問(wèn)題的難度在本質(zhì)上不依賴于用來(lái)決定時(shí)間復(fù)雜性的具體編碼方案和計(jì)算機(jī)模型。 能夠用實(shí)際的計(jì)算機(jī)標(biāo)準(zhǔn)模型在多項(xiàng)式時(shí)間算法（Polynomial time algorithm)內(nèi)求解的問(wèn)題稱為P P類類問(wèn)題。第6頁(yè)/共19頁(yè)2021-7-208第7頁(yè)/共19頁(yè)2021-7-209 第一個(gè)難解的“可判定”問(wèn)題是在六十年代初獲得的，它是Hartmanis和Stearns1965的復(fù)雜性“譜系”工作的一部分，但是，這些結(jié)果只包括一些“人工制造的”問(wèn)題，它們被專門構(gòu)造成具有所需要的性質(zhì)。直到七十年代

6、初，Meyer和Stockmeyer1972，F(xiàn)ischer和Rabin1974以及其他人終于成功地證明某些“自然的”可判定問(wèn)題是難解的，這些問(wèn)題包括自動(dòng)機(jī)理論、形式語(yǔ)言理論以及數(shù)理邏輯中以前研究過(guò)的各種問(wèn)題。實(shí)際上，他們的證明表明甚至用“非確定型非確定型”（nondeterministic)計(jì)算機(jī)模型也不可能在多項(xiàng)式時(shí)間內(nèi)解這些問(wèn)題，這種“非確定型”計(jì)算機(jī)模型具有執(zhí)行無(wú)限多個(gè)獨(dú)立的并行計(jì)算序列的能力。這種“不合理的”計(jì)算機(jī)模型在NP完全性理論中起著重要的作用。第8頁(yè)/共19頁(yè)2021-7-2010 迄今為止我們已經(jīng)知道的所有可證的難解問(wèn)題分成剛才敘述的兩種類型，它們或者是“不可判定的不可判定

7、的”，或者是“非確定型非確定型”難解的。但是，大多數(shù)在實(shí)際中遇到的在表面上看來(lái)難解的問(wèn)題是可判定的，并且可以用非確定型計(jì)算機(jī)在多項(xiàng)式時(shí)間內(nèi)求解。因此，要證明這些問(wèn)題的表面上的難解性，至今所研究過(guò)的證明方法都還不夠有力。第9頁(yè)/共19頁(yè)2021-7-2011第10頁(yè)/共19頁(yè)2021-7-2012 早期就找到了許多這種簡(jiǎn)單的歸約。例如，Dantzig1960把一些組合最優(yōu)化問(wèn)題歸約為一般的0-l整數(shù)線性規(guī)劃問(wèn)題，Edmonds1962把圖論問(wèn)題“用最少的頂點(diǎn)覆蓋所有邊”和“尋找最大的頂點(diǎn)獨(dú)立集”歸約為一般的“集合覆蓋問(wèn)題”。Gimple1965把一般的集合覆蓋問(wèn)題歸約為邏輯設(shè)計(jì)的“素蘊(yùn)涵覆蓋問(wèn)題

8、”，Dantzig，Blattner和Rao1966描述了一個(gè)“著名的”歸約，把巡回推銷員問(wèn)題歸約為帶非負(fù)邊長(zhǎng)的“最短路徑問(wèn)題”。第11頁(yè)/共19頁(yè)2021-7-2013 Stephen Cook于1971年發(fā)表的題為“定理證明過(guò)程的復(fù)雜性”一文奠定了NP完全性理論的基礎(chǔ)。在這篇簡(jiǎn)潔而又精致的文章中Cook做了幾件重要的事情。 第一，他強(qiáng)調(diào)了“多項(xiàng)式時(shí)間可歸約性”的重要意義，所謂多項(xiàng)式時(shí)間歸約是指可以用多項(xiàng)式時(shí)間算法實(shí)現(xiàn)所需要的變換的歸約。如果我們有從第一個(gè)問(wèn)題到第二個(gè)問(wèn)題的多項(xiàng)式時(shí)間歸約，那末就一定能把第二個(gè)問(wèn)題的任何多項(xiàng)式時(shí)間算法轉(zhuǎn)換成第一個(gè)問(wèn)題的多項(xiàng)式時(shí)間算法。 第二，他把注意力集中在判

9、定向題的NP類上，這類問(wèn)題可以用非確定型計(jì)算機(jī)在多項(xiàng)式時(shí)間內(nèi)解決。（如果問(wèn)題的解不是“是”就是“否”，則稱這個(gè)問(wèn)題是判定向題。）在實(shí)際中遇到的表面上看來(lái)難解的問(wèn)題，當(dāng)把它們表成判定問(wèn)題時(shí)，大多數(shù)屬于這一類。第12頁(yè)/共19頁(yè)2021-7-2014 第三，他證明了NP中的一個(gè)名叫“可滿足性”問(wèn)題的具體問(wèn)題具有這樣的性質(zhì)：NP類中的所有其它問(wèn)題都可以多項(xiàng)式歸約為這個(gè)問(wèn)題。如果可滿足性問(wèn)題如果可滿足性問(wèn)題可以用多項(xiàng)式時(shí)間算法解決，那末可以用多項(xiàng)式時(shí)間算法解決，那末NPNP類中的所有問(wèn)題類中的所有問(wèn)題也都可以用多項(xiàng)式時(shí)間算法解決也都可以用多項(xiàng)式時(shí)間算法解決。如果如果NPNP中的某個(gè)問(wèn)中的某個(gè)問(wèn)題是難解

10、的，那末可滿足性問(wèn)題也一定是難解的題是難解的，那末可滿足性問(wèn)題也一定是難解的。因此，在某種意義下，可滿足性問(wèn)題是可滿足性問(wèn)題是NPNP類中類中“最難的最難的”問(wèn)題問(wèn)題。 最后，Cook認(rèn)為NP類中的一些其它問(wèn)題可能和可滿足性問(wèn)題一樣，具有這種成為NP類中“最難的”問(wèn)題的性質(zhì)。他證明對(duì)于問(wèn)題“給定的圖G是否包含k個(gè)頂點(diǎn)上的完全子圖？其中k 是給定的自然數(shù)”就是這種清況。第13頁(yè)/共19頁(yè)2021-7-2015 隨后，Richard Karp給出了一組結(jié)果1972，證明許多著名的組合問(wèn)題,包括巡回推銷員問(wèn)題在內(nèi)的判定問(wèn)題形式確實(shí)恰好與可滿足性問(wèn)題一樣難。從那以后證明了各種各樣的其它問(wèn)題在難度上等價(jià)

11、于這些問(wèn)題，這些問(wèn)題構(gòu)成了一個(gè)NPNP等價(jià)問(wèn)題等價(jià)問(wèn)題(NP equivalent problem)類 ，并給這個(gè)等價(jià)類起了一個(gè)名字，叫做NPNP完全問(wèn)題完全問(wèn)題(NP complete problem)類，它是由NP中所有“最難的”問(wèn)題組成。 已經(jīng)證明Cook的原始思想是相當(dāng)有力的。它提供了一些方法把許多個(gè)別的復(fù)雜性問(wèn)題聯(lián)合成一個(gè)問(wèn)題：NP完全問(wèn)題是難解的嗎？由于越來(lái)越多的具有獨(dú)立意義的問(wèn)題被證明屬于這個(gè)等價(jià)類，所以它的重要性還在繼續(xù)增長(zhǎng)。第14頁(yè)/共19頁(yè)2021-7-2016 現(xiàn)在認(rèn)為NP完全問(wèn)題是否是難解的這一向題是當(dāng)代數(shù)學(xué)和計(jì)算機(jī)科學(xué)中尚未解決的最重要問(wèn)題之一。盡管大多數(shù)研究工作者猜想NP完全問(wèn)題是難解的，然而在證明或否定這個(gè)廣泛的猜想方面幾乎沒(méi)有取得什么進(jìn)展。但是，即使沒(méi)有證明NP完全性蘊(yùn)涵難解性，知道一個(gè)問(wèn)題是NP完全的至少暗示著要想用多項(xiàng)式時(shí)間算法解這個(gè)問(wèn)題必須有重大的突破。第15頁(yè)/共19頁(yè)2021-7-2017 實(shí)用中，知道一個(gè)問(wèn)題是NP完全的就給我們提供了有價(jià)值的信息，告訴我們采用什么樣的途徑可以是最富有成效的。一定不要去優(yōu)先尋找有效的、精確的算法?，F(xiàn)在比較適當(dāng)?shù)耐緩绞羌芯χ铝τ谄渌^低目標(biāo)的方法。例如，你可以尋找解決這個(gè)問(wèn)題的各種特殊情況的有效算