算法設(shè)計(jì)與分析-鐘

1、CH6 計(jì)算復(fù)雜性 6.1 P類(lèi)問(wèn)題分類(lèi)理論上能用算法解決的P類(lèi): 有有效算法的理論上不能用算法解決的NP類(lèi): 無(wú)有效算法的26.1 P類(lèi)3丘奇-圖靈論題的定量細(xì)化如下：多項(xiàng)式界限的TM和P類(lèi)分別適當(dāng)刻畫(huà)了實(shí)際可行算法和實(shí)際可解問(wèn)題的直覺(jué)概念。 定理6.1.1 P在補(bǔ)運(yùn)算下封閉證明：如果語(yǔ)言L被多項(xiàng)式界限的TM M判定，那么它的補(bǔ)被交換M的y和n得到的TM M判定。故多項(xiàng)式界限不受影響。6.1 P類(lèi)46.1 P類(lèi)5P是多項(xiàng)式可判定語(yǔ)言的類(lèi)嚴(yán)格地說(shuō)，只包含語(yǔ)言所有正則語(yǔ)言都屬于 P問(wèn)題與語(yǔ)言的關(guān)系？6.2 若干問(wèn)題66.2 若干問(wèn)題問(wèn)題的定義：?jiǎn)栴}是(無(wú)窮)輸入的集合 + 對(duì)每個(gè)輸入問(wèn)的判定性(

2、是或否)問(wèn)題例：可達(dá)性輸入集是所有三元組(G, vi, vj) 的集合，其中G是有窮圖, vi, vj是G的兩個(gè)頂點(diǎn)。問(wèn)題是在G里是否存在從vi到vj的路徑76.2 若干問(wèn)題可達(dá)性是否屬于P?嚴(yán)格說(shuō)，P只包含語(yǔ)言，所以與可達(dá)性無(wú)關(guān)語(yǔ)言是對(duì)問(wèn)題的編碼。當(dāng)然，任何語(yǔ)言也被認(rèn)為是問(wèn)題。問(wèn)題和對(duì)應(yīng)的語(yǔ)言是同一個(gè)事物的兩個(gè)不同方面語(yǔ)言更適合與Turing機(jī)相聯(lián)系問(wèn)題更清楚陳述了與算法相關(guān)的實(shí)際計(jì)算任務(wù)86.2 若干問(wèn)題：可達(dá)性問(wèn)題可達(dá)性問(wèn)題的語(yǔ)言描述：R=k(G)b(i)b(j)：在G中有從vi到vj的路徑b(i)是整數(shù)i的二進(jìn)制編碼k(G)是G的字符串編碼可達(dá)性屬于P，即語(yǔ)言R屬于P 計(jì)算G的自反傳遞

3、閉包，這可用(n3) 時(shí)間里完成檢查G的自反傳遞閉包里對(duì)應(yīng)vj 和vj 的項(xiàng)，它告訴我們?cè)贕里是否存在從vi到vj的路徑96.2 若干問(wèn)題：可達(dá)性問(wèn)題106.2 若干問(wèn)題:歐拉圖 圖G是歐拉圖當(dāng)且僅當(dāng) ：對(duì)任意一對(duì)都不是孤立的頂點(diǎn)u, vV，存在從u到v的通路 所有頂點(diǎn)都有同樣數(shù)目的入邊和出邊歐拉圖對(duì)應(yīng)的語(yǔ)言L = k(G)：G是歐拉圖驗(yàn)證歐拉圖：在多項(xiàng)式時(shí)間里確定是否除孤立點(diǎn)外所有頂點(diǎn)都連通。方法是先計(jì)算圖的自反傳遞閉包，再驗(yàn)證是否除孤立點(diǎn)外所有頂點(diǎn)都連通驗(yàn)證是否所有頂點(diǎn)都有同樣數(shù)目的入邊和出邊，也可在多項(xiàng)式時(shí)間里完成歐拉圖屬于P116.2 若干問(wèn)題：優(yōu)化問(wèn)題優(yōu)化問(wèn)題要求的不是“是”或“否”

4、的回答要求從許多可行解里找出最好的（根據(jù)成本函數(shù)）可轉(zhuǎn)變?yōu)檎Z(yǔ)言形式：給每個(gè)輸入加上成本函數(shù)的界限旅行商問(wèn)題給定整數(shù) n2，n n距離矩陣dij，以及整數(shù)預(yù)算B0，是否存在1, 2, , n的排列使得c() B。126.2 若干問(wèn)題：優(yōu)化問(wèn)題獨(dú)立集給定無(wú)向圖G和整數(shù) K2，是否存在V的子集C滿足 |C|K，使得對(duì)所有vi,vjC，在vi和vj間沒(méi)有邊？團(tuán)給定無(wú)向圖G和整數(shù) K2，是否存在V的子集C滿足 |C|K，使得對(duì)所有vi,vjC，在vi和vj間有邊？頂點(diǎn)覆蓋給定無(wú)向圖G和整數(shù) K2，是否存在V的子集C滿足 |C|K，使得C覆蓋G的所有邊？13尚未找到多項(xiàng)式時(shí)間算法整數(shù)劃分1415B(7)亦

5、含數(shù)字151，等于所有數(shù)字和的一半復(fù)雜度：O(nH)整數(shù)劃分166.3 布爾可滿足性176.3 布爾可滿足性186.3 布爾可滿足性對(duì)這個(gè)問(wèn)題，至今沒(méi)有已知的多項(xiàng)式時(shí)間算法，并且人們普遍相信不存在這樣的算法。19二元可滿足性:所有子句只有兩個(gè)或更少文字的公式6.3 布爾可滿足性 假設(shè)在公式里存在只有一個(gè)文字的子句 ，比方說(shuō)第三個(gè)子句(x1) 。那么顯然這個(gè)文字在任何滿足的真值賦值里都必須是T。即在本例中立即決定T(x1)=T，然后繼續(xù)進(jìn)行。既然我們知道T(x1)=T，我們就從公式里刪除包含x1作為文字的所有子句，因?yàn)檫@些子句已經(jīng)被滿足了（在本例中我們刪除第一個(gè)子句）。不過(guò)如果子句包含否定文字，

6、那么我們就從子句里刪除這個(gè)文字，因?yàn)檫@個(gè)文字是因此它不能用來(lái)滿足子句。20 我們把尋找單文字子句直到不存在這樣的子句為止的過(guò)程稱(chēng)為清洗 。如果在清洗的任何一步產(chǎn)生了空子句, 即假定因?yàn)閷?duì)某個(gè) i, 單文字子句及其否定都在前一步出現(xiàn), 那么我們說(shuō)清洗已經(jīng)失敗。假定我們的公式在每個(gè)子句里恰有兩個(gè)文字。選擇還沒(méi)有賦真值的任何變?cè)?，試?yàn)設(shè)置它的真值是T并完成清洗；然后把公式恢復(fù)原狀，把同一個(gè)變?cè)O(shè)置成并再次完成清洗。若兩次清洗都失敗則搜索結(jié)束，公式是不可滿足的。若兩次清洗中至少有一次成功，則設(shè)置變?cè)扔诔晒Φ那逑粗械恼嬷挡⒗^續(xù)。6.3 布爾可滿足性216.3 布爾可滿足性因?yàn)樗惴▽?duì)每個(gè)變?cè)疃嗤瓿蓛杀?/p>

7、清洗并且每遍清洗都在多項(xiàng)式時(shí)間里完成，所以由此得出二元可滿足性屬于P。226.4 NP類(lèi)對(duì)非確定型TM判定語(yǔ)言L的含義: 對(duì)每個(gè)不屬于L的輸入，機(jī)器的所有計(jì)算都必須拒絕輸入；對(duì)每個(gè)屬于L的輸入，我們僅僅要求存在至少一個(gè)計(jì)算接受輸入只要存在一個(gè)接受計(jì)算，在其余的計(jì)算里就可以沒(méi)有、或有些、或大多數(shù)、或全部都拒絕這個(gè)輸入。23非確定型TM在給定輸入上所有可能的計(jì)算最好是畫(huà)成樹(shù)的結(jié)構(gòu)。頂點(diǎn)表示格局，向下的線表示步。非確定性選擇表示成有多條線離開(kāi)的頂點(diǎn)。用垂直維度量時(shí)間。6.4 NP類(lèi)246.4 NP類(lèi)例6.4.1 可滿足性屬于NP已經(jīng)證明過(guò)不屬于P設(shè)計(jì)在多項(xiàng)式非確定性時(shí)間里判定可滿足布爾公式的所有編碼

8、的非確定性Turing機(jī)M，對(duì)于輸入w步1：計(jì)算w中出現(xiàn)的變?cè)獋€(gè)數(shù)n，同時(shí)向第2條帶上填入變?cè)淖址?In （P）步2：非確定性階段，把第2條帶上所有I變?cè)膶?xiě)為T(mén)或。每個(gè)變?cè)娜≈凳欠谴_定的步3：對(duì)每種I的賦值序列進(jìn)行驗(yàn)證，是否可滿足 （P）M滿足 NP，且給出y或n的判定256.4 NP類(lèi)例6.4.2 旅行商問(wèn)題也屬于NP給定整數(shù) n2，n n距離矩陣dij，以及整數(shù)預(yù)算B0，是否存在1, 2, , n的排列使得c() B。證明這個(gè)結(jié)論的非確定型TM M在第二條帶上非確定性地寫(xiě)與輸入的長(zhǎng)度相等的0,1和|_|的字符串然后機(jī)器進(jìn)入確定性階段，其中它驗(yàn)證寫(xiě)在第二條帶上的字符串是否碰巧是整數(shù)

9、1, , n的雙射的編碼，其中，n是給定輸入里的城市數(shù)。雙射編碼成用二進(jìn)制寫(xiě)的(1), (2), , 用|_|分隔。若字符串確實(shí)是雙射的編碼，則機(jī)器繼續(xù)確定性地計(jì)算巡回路線的成本，并且與輸入里的“預(yù)算”比較。若成本不超過(guò)B，則機(jī)器接受 ；在所有其他的最終結(jié)局里（若所猜測(cè)的字符串不是雙射的編碼，或者若它表示成本大于B的巡回路 線）這臺(tái)機(jī)器都拒絕。顯然字符串屬于這臺(tái)機(jī)器所判定的語(yǔ)言當(dāng)且僅當(dāng)它編碼旅行商問(wèn)題的 “是”實(shí)例 。26同理 ，容易證明我們?cè)谇耙还?jié)遇到的其它明顯的困難問(wèn)題都屬于NP ，包括獨(dú)立集哈密頓圈劃分等非確定性 “算法” 聰明地利用了在非確定性時(shí)間界限計(jì)算的定義里的基本非對(duì)稱(chēng)性它們?cè)讵?dú)

10、立的計(jì)算里試驗(yàn)所處理的問(wèn)題的所有可能解，一旦發(fā)現(xiàn)可行解就立即接受它，忘掉其他的非可行解。6.4 NP類(lèi)276.4 NP類(lèi)28PNP？是復(fù)雜性理論里具有核心重要性的目前還懸而未決的問(wèn)題NPEXP？是另一個(gè)懸而未決的問(wèn)題，不過(guò)重要性要低一些。但是我們確實(shí)知道下列結(jié)論：在包含關(guān)系之鏈 P NP EXP里，第三個(gè)類(lèi)真包含第一個(gè)類(lèi)。雖然我們猜想上面顯示的兩個(gè)包含關(guān)系都是包含，但是目前我們能證明的全部東西就是其中至少一個(gè)是真包含，而且我們不知道是哪個(gè)。6.4 NP類(lèi)29為判定可滿足性和旅行商問(wèn)題設(shè)計(jì)的TM很類(lèi)似首先非確定性地產(chǎn)生字符串，然后確定性地驗(yàn)證所產(chǎn)生的字串是否具有與輸入相關(guān)的某種需要的性質(zhì)。若輸入

11、屬于這個(gè)語(yǔ)言則至少存在一個(gè)合適的字符串。若輸入不屬于這個(gè)語(yǔ)言則找不到具有所需要性質(zhì)的字符串。這樣的字符串稱(chēng)為證書(shū)，或者見(jiàn)證。所有NP里的問(wèn)題都有證書(shū) ，并且只有NP里的問(wèn)題才有證書(shū) 。6.4 NP類(lèi): 證書(shū)30證書(shū)必須是多項(xiàng)式那么短的，即它的長(zhǎng)度最多是輸入長(zhǎng)度的多項(xiàng)式。還必須是在多項(xiàng)式時(shí)間里可驗(yàn)證的。在可滿足性的情形里驗(yàn)證證書(shū)就是要求驗(yàn)證真值賦值是否滿足輸入公式的所有子句；在旅行商問(wèn)題的情形里就是要求驗(yàn)證建議的巡回路線的總成本是否在預(yù)算之內(nèi)；對(duì)于獨(dú)立集就是驗(yàn)證給定的頂點(diǎn)集是否大小合適并且在它們之間沒(méi)有邊等等。最后，問(wèn)題的所有“是”輸入都必須有至少一個(gè)證書(shū)，而所有“否”輸入都必須沒(méi)有任何證書(shū)。6.4 NP類(lèi): 證書(shū)310/1背包問(wèn)題給定背包問(wèn)題的實(shí)例a1, a2, an和K, 滿足 ip ai=K的1, , n的子集P可作為對(duì)給定實(shí)例的回答是 “是”的證書(shū)。它是多項(xiàng)式短的，并且它可在多項(xiàng)式時(shí)間里通過(guò)二進(jìn)制加法來(lái)驗(yàn)證。6.4 NP類(lèi): 證書(shū)32簡(jiǎn)短的證書(shū)示例：合數(shù)集合 CN4 294 967 297 是否合數(shù)？不存在有效方法，但每一個(gè)屬于C的數(shù)確實(shí)有簡(jiǎn)短的證書(shū)6 700 417和641可作為4