算法設(shè)計(jì)與分析_05NP完全問(wèn)題-一些重要的概念

1、2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)1算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析NP完全問(wèn)題完全問(wèn)題2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)2一、一些重要的概念一、一些重要的概念1 1、多項(xiàng)式時(shí)間算法和難解問(wèn)題、多項(xiàng)式時(shí)間算法和難解問(wèn)題不同的算法具有很不相同的時(shí)間復(fù)雜性函數(shù)，什么樣的算法算作“效率高效率高”，什么樣的算法算作“效率低效率低”，計(jì)算機(jī)科學(xué)家們公認(rèn)一種簡(jiǎn)單的區(qū)別，這就是多頂式時(shí)間算法多頂式時(shí)間算法（polynomial time algorithm)和指數(shù)時(shí)間算法指數(shù)時(shí)間算法（exponential time algorithm)之間的區(qū)別。Cobham1

2、964和Edmonds1965首先討論了這種區(qū)別的基本性質(zhì)。特別是Edmonds把多項(xiàng)式時(shí)間算法與“好的”算法等同看待，并且猜想某些整數(shù)規(guī)劃問(wèn)題可能不能用這種“好的”算法求解。這反映了一種觀點(diǎn)，認(rèn)為指數(shù)時(shí)間算法不應(yīng)該算作“好的”算法。通常也的確是這樣的。大多數(shù)指數(shù)時(shí)間算法只是窮舉搜索法窮舉搜索法的變種，而多項(xiàng)式時(shí)間算法通常只有在對(duì)問(wèn)題的結(jié)構(gòu)有了某些比較深入的了解之后才有可能給出。艱多人都認(rèn)為只有知道了問(wèn)題的多項(xiàng)式時(shí)間算法才能認(rèn)為“很好地解決了”這個(gè)問(wèn)題。因此，如果一個(gè)問(wèn)題困難到不可能用多項(xiàng)式時(shí)間如果一個(gè)問(wèn)題困難到不可能用多項(xiàng)式時(shí)間算法求解，那末我們就認(rèn)為這個(gè)問(wèn)題是算法求解，那末我們就認(rèn)為這個(gè)問(wèn)

3、題是“難解的難解的”。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)3 不過(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)證明線(xiàn)性規(guī)劃的單純形算法單純形算法具有指數(shù)時(shí)間復(fù)雜性Klee and Minty，1972，但是在實(shí)際中它計(jì)算得很好，給人留下了深刻印象。同樣，背包問(wèn)題背包問(wèn)題的分支界限算法分支界限算法雖然也具有指數(shù)時(shí)間復(fù)雜性，但是它是一種非常成功的

4、算法，使得許多人認(rèn)為背包問(wèn)題已經(jīng)很好地解決了。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)4 遺憾的是，像這樣的例子太少了。雖然對(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)算。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(

5、C)5 另一方面，如果多項(xiàng)式時(shí)間算法滿(mǎn)足對(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)為滿(mǎn)足這些限制的算法是“可可證地有效證地有效”算法。正是這種特別需要的性質(zhì)使我們優(yōu)先考慮用多項(xiàng)式時(shí)間算法解決問(wèn)題。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)6 關(guān)于計(jì)算機(jī)模型計(jì)算機(jī)模型的選擇可以作類(lèi)似的注釋。至今研究過(guò)的所有實(shí)際的計(jì)算機(jī)模型，例如單帶圖靈機(jī)單帶圖靈機(jī)，多帶圖靈機(jī)多帶圖

6、靈機(jī)以及隨機(jī)存取機(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)題類(lèi)就不受使采用實(shí)際的計(jì)算機(jī)標(biāo)準(zhǔn)模型，難解的問(wèn)題類(lèi)就不受使用的具體模型的影響用的具體模型的影響。因而我們可以根據(jù)方便與否來(lái)選擇計(jì)算機(jī)模型，而不會(huì)妨礙結(jié)果的使用。 “合理的”計(jì)算機(jī)模型也稱(chēng)為是“確定型確定型”（determ

7、inistic)的計(jì)算機(jī)模型。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)7 這樣一來(lái)，“難解的”定義在理論上給出了重要的一般原則。即問(wèn)題的難度在本質(zhì)上不依賴(lài)于用來(lái)決定時(shí)間復(fù)雜性的具體編碼方案和計(jì)算機(jī)模型。 能夠用實(shí)際的計(jì)算機(jī)標(biāo)準(zhǔn)模型在多項(xiàng)式時(shí)間算法（Polynomial time algorithm)內(nèi)求解的問(wèn)題稱(chēng)為P P類(lèi)類(lèi)問(wèn)題。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)82 2、可證的難解問(wèn)題、可證的難解問(wèn)題 最早證出的難解性問(wèn)題結(jié)果是經(jīng)典的圖靈不可判定性圖靈不可判定性。四十多年前，圖靈證明某些問(wèn)題困難到“不可判定的”程度，即根本不可能給出解這些問(wèn)題的算法根

8、本不可能給出解這些問(wèn)題的算法。例如，他證明不可能給出一個(gè)算法，當(dāng)任意給定一個(gè)計(jì)算機(jī)程序和這個(gè)程序的輸入時(shí)，該算法可以判定當(dāng)把這個(gè)程序應(yīng)用于這個(gè)輸入時(shí)最終是否停機(jī)Turing，1936?，F(xiàn)在已經(jīng)知道還有各種其它問(wèn)題也是不可判定的，這些問(wèn)題包括有限表示群的平凡問(wèn)題Rabin，1958，希爾伯特第十問(wèn)題（整數(shù)多項(xiàng)式的可解性） Matijasevic，1970等。因?yàn)椴豢赡苡萌魏嗡惴ǎ?dāng)然更不可能用多項(xiàng)式時(shí)間算法解這些不可判定問(wèn)題，所以它們的確是在特別強(qiáng)的意義下難解的在特別強(qiáng)的意義下難解的。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)9 第一個(gè)難解的“可判定”問(wèn)題是在六十年代初獲得的，它

9、是Hartmanis和Stearns1965的復(fù)雜性“譜系”工作的一部分，但是，這些結(jié)果只包括一些“人工制造的”問(wèn)題，它們被專(zhuān)門(mén)構(gòu)造成具有所需要的性質(zhì)。直到七十年代初，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ī)模型在N

10、P完全性理論中起著重要的作用。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)10 迄今為止我們已經(jīng)知道的所有可證的難解問(wèn)題分成剛才敘述的兩種類(lèi)型，它們或者是“不可判定不可判定的的”，或者是“非確定型非確定型”難解的。但是，大多數(shù)在實(shí)際中遇到的在表面上看來(lái)難解的問(wèn)題是可判定的，并且可以用非確定型計(jì)算機(jī)在多項(xiàng)式時(shí)間內(nèi)求解。因此，要證明這些問(wèn)題的表面上的難解性，至今所研究過(guò)的證明方法都還不夠有力。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)113 3、NPNP完全問(wèn)題完全問(wèn)題 可以用可以用“非確定型非確定型”計(jì)算機(jī)通過(guò)多項(xiàng)式時(shí)間算法求解計(jì)算機(jī)通過(guò)多項(xiàng)式時(shí)間算法求解的問(wèn)題稱(chēng)為

11、的問(wèn)題稱(chēng)為“NPNP類(lèi)類(lèi)”問(wèn)題。問(wèn)題。理論工作者們一方面繼續(xù)尋找更有力的方法來(lái)證明問(wèn)題的難解性，同時(shí)又在努力研究就難度而言各種問(wèn)題相互聯(lián)系的方式。發(fā)現(xiàn)問(wèn)題之間的這種相互聯(lián)系常?？梢越o算法設(shè)計(jì)人員提供有用的信息。證明兩個(gè)問(wèn)題相關(guān)的基本方法是通過(guò)給出一個(gè)構(gòu)造性變換把第一個(gè)問(wèn)題的任一實(shí)例映射到第二個(gè)問(wèn)題的一個(gè)等價(jià)的實(shí)例，從而把第一個(gè)問(wèn)題“歸歸約約”為第二個(gè)問(wèn)題。這樣的變換提供了一個(gè)手段，把解第二個(gè)問(wèn)題的任何算法轉(zhuǎn)變成解第一個(gè)問(wèn)題的相應(yīng)的算法。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)12 早期就找到了許多這種簡(jiǎn)單的歸約。例如，Dantzig1960把一些組合最優(yōu)化問(wèn)題歸約為一般的0-

12、l整數(shù)線(xiàn)性規(guī)劃問(wèn)題，Edmonds1962把圖論問(wèn)題“用最少的頂點(diǎn)覆蓋所有邊”和“尋找最大的頂點(diǎn)獨(dú)立集”歸約為一般的“集合覆蓋問(wèn)題”。Gimple1965把一般的集合覆蓋問(wèn)題歸約為邏輯設(shè)計(jì)的“素蘊(yùn)涵覆蓋問(wèn)題”，Dantzig，Blattner和Rao1966描述了一個(gè)“著名的”歸約，把巡回推銷(xiāo)員問(wèn)題歸約為帶非負(fù)邊長(zhǎng)的“最短路徑問(wèn)題”。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)13 Stephen Cook于1971年發(fā)表的題為“定理證明過(guò)程的復(fù)雜性”一文奠定了NP完全性理論的基礎(chǔ)。在這篇簡(jiǎn)潔而又精致的文章中Cook做了幾件重要的事情。 第一，他強(qiáng)調(diào)了“多項(xiàng)式時(shí)間可歸約性”的重要

13、意義，所謂多項(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í)間算法。 第二，他把注意力集中在判定向題的NP類(lèi)上，這類(lèi)問(wèn)題可以用非確定型計(jì)算機(jī)在多項(xiàng)式時(shí)間內(nèi)解決。（如果問(wèn)題的解不是“是”就是“否”，則稱(chēng)這個(gè)問(wèn)題是判定向題。）在實(shí)際中遇到的表面上看來(lái)難解的問(wèn)題，當(dāng)把它們表成判定問(wèn)題時(shí)，大多數(shù)屬于這一類(lèi)。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)14 第三，他證明了NP中的一個(gè)名叫“可滿(mǎn)足性”問(wèn)題的具體問(wèn)題具有這樣的性質(zhì)：NP類(lèi)中的所有其它問(wèn)題都可以多

14、項(xiàng)式歸約為這個(gè)問(wèn)題。如果可滿(mǎn)足性問(wèn)題可以用如果可滿(mǎn)足性問(wèn)題可以用多項(xiàng)式時(shí)間算法解決，那末多項(xiàng)式時(shí)間算法解決，那末NPNP類(lèi)中的所有問(wèn)題也都可以類(lèi)中的所有問(wèn)題也都可以用多項(xiàng)式時(shí)間算法解決用多項(xiàng)式時(shí)間算法解決。如果如果NPNP中的某個(gè)問(wèn)題是難解的，中的某個(gè)問(wèn)題是難解的，那末可滿(mǎn)足性問(wèn)題也一定是難解的那末可滿(mǎn)足性問(wèn)題也一定是難解的。因此，在某種意義下，可滿(mǎn)足性問(wèn)題是可滿(mǎn)足性問(wèn)題是NPNP類(lèi)中類(lèi)中“最難的最難的”問(wèn)題問(wèn)題。 最后，Cook認(rèn)為NP類(lèi)中的一些其它問(wèn)題可能和可滿(mǎn)足性問(wèn)題一樣，具有這種成為NP類(lèi)中“最難的”問(wèn)題的性質(zhì)。他證明對(duì)于問(wèn)題“給定的圖G是否包含k個(gè)頂點(diǎn)上的完全子圖？其中k 是給定的自

15、然數(shù)”就是這種清況。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)15 隨后，Richard Karp給出了一組結(jié)果1972，證明許多著名的組合問(wèn)題,包括巡回推銷(xiāo)員問(wèn)題在內(nèi)的判定問(wèn)題形式確實(shí)恰好與可滿(mǎn)足性問(wèn)題一樣難。從那以后證明了各種各樣的其它問(wèn)題在難度上等價(jià)于這些問(wèn)題，這些問(wèn)題構(gòu)成了一個(gè)NPNP等價(jià)問(wèn)題等價(jià)問(wèn)題(NP equivalent problem)類(lèi) ，并給這個(gè)等價(jià)類(lèi)起了一個(gè)名字，叫做NPNP完全問(wèn)題完全問(wèn)題(NP complete problem)類(lèi)，它是由NP中所有“最難的”問(wèn)題組成。 已經(jīng)證明Cook的原始思想是相當(dāng)有力的。它提供了一些方法把許多個(gè)別的復(fù)雜性問(wèn)題聯(lián)合

16、成一個(gè)問(wèn)題：NP完全問(wèn)題是難解的嗎？由于越來(lái)越多的具有獨(dú)立意義的問(wèn)題被證明屬于這個(gè)等價(jià)類(lèi)，所以它的重要性還在繼續(xù)增長(zhǎng)。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)16 現(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)題必須有重大的突破。2021-10-29算法設(shè)計(jì)與分析演示稿 紀(jì)玉波制作(C)17 實(shí)用中，知道一個(gè)問(wèn)題是NP完全的就給我們提供了有價(jià)值的信息，告訴我們采用什么樣的途徑可以是最富有成效的。一定不要去優(yōu)先尋找有效的、精確的算法?，F(xiàn)在比較適當(dāng)?shù)耐緩绞羌芯χ铝τ谄渌^低目標(biāo)的方法。例如，你可以尋找解決這個(gè)問(wèn)題的各種特殊情況的有效算法。尋找在大多數(shù)情況下看來(lái)能快速運(yùn)算的算