第9章np完全性理論與近似算法-在線(xiàn)瀏覽
2024-12-20 13:02本頁(yè)面
【正文】 圖靈機(jī)允許移動(dòng)函數(shù) δ 具有不確定性 ，即對(duì)于 Q?Tk中的每一個(gè)值 (q。x 1,x2,… ,xk)與之對(duì)應(yīng)。x 1,x2,… ,xk)中隨意選定一個(gè)值作為它的函數(shù)值。 13 P類(lèi)與 NP類(lèi)語(yǔ)言 P類(lèi)和 NP類(lèi)語(yǔ)言的定義： P={L|L是一個(gè)能在 多項(xiàng)式時(shí)間內(nèi) 被一臺(tái) DTM所接受的語(yǔ)言 } NP={L|L是一個(gè)能在 多項(xiàng)式時(shí)間 內(nèi)被一臺(tái) NDTM所接受的語(yǔ)言 } 由于一臺(tái)確定性圖靈機(jī)可看作是非確定性圖靈機(jī)的特例，所以可在多項(xiàng)式時(shí)間內(nèi)被確定性圖靈機(jī)接受的語(yǔ)言也可在多項(xiàng)式時(shí)間內(nèi)被非確定性圖靈機(jī)接受。 14 P類(lèi)與 NP類(lèi)語(yǔ)言 NP類(lèi)語(yǔ)言舉例 —— 無(wú)向圖的團(tuán)問(wèn)題 。 要求判定圖 G是否包含一個(gè) k頂點(diǎn)的 完全子圖 (團(tuán) )，即判定是否存在 V’?V， |V’|=k， 且對(duì)于所有的u， v∈V ’， 有 (u， v)∈E 。因此，團(tuán)問(wèn)題可表示為語(yǔ)言： CLIQUE={wv|w， v∈{0 ， 1}*， 以 w為鄰接矩陣的圖 G有一個(gè) k頂點(diǎn)的團(tuán)，其中 v是 k的二進(jìn)制表示。算法分為 3個(gè)階段： 算法的第一階段將輸入串 wv分解，并計(jì)算出 n= ， 以及用 v表示的整數(shù) k。顯而易見(jiàn)，第一階段可 在時(shí)間內(nèi)完成。 算法的第三階段是確定性地檢查 V’的團(tuán)性質(zhì)。這顯然可以在 時(shí)間內(nèi)完成。 )( 4nO)( 4nO非確定性算法在多項(xiàng)式時(shí)間內(nèi)接受語(yǔ)言 CLIQUE， 故 CLIQUE∈NP 。 多項(xiàng)式時(shí)間可驗(yàn)證語(yǔ)言類(lèi) VP可定義為： 定理 91： VP=NP。可用語(yǔ)言 HAMCYCLE 定義該問(wèn)題如下： HAMCYCLE={G|G含有哈密頓回路 } 17 NP完全問(wèn)題 ? P?NP。 ? 大多數(shù)的計(jì)算機(jī)科學(xué)家認(rèn)為 NP類(lèi)中包含了不屬于 P類(lèi)的語(yǔ)言 ， 即 P≠NP。 ? 目前還沒(méi)有一個(gè) NP完全問(wèn)題有多項(xiàng)式時(shí)間算法 。 如果有一個(gè)語(yǔ)言 L滿(mǎn)足上述性質(zhì) (2)，但不一定滿(mǎn)足性質(zhì) (1)，則稱(chēng)該語(yǔ)言是 NP難 的。 設(shè) ， 是 2個(gè)語(yǔ)言。 *11 ??L *22 ??L 1L2L 1L2L*2*1 ???1L 2L*1?19 多項(xiàng)式時(shí)間變換 定理 92：設(shè) L是 NP完全的，則 (1)L∈P 當(dāng)且僅當(dāng) P＝ NP； (2)若 L∝ p ， 且 ∈ NP， 則 是 NP完全的。但前提是：要有第一個(gè) NP完全問(wèn)題 L。 對(duì)于這類(lèi)問(wèn)題，通?？刹扇∫韵聨追N解題策略。在通常情況下，該性能比是問(wèn)題輸入規(guī)模 n的一個(gè)函數(shù) ρ(n) ， 即 ≤ ρ(n) 。若對(duì)問(wèn)題的輸入規(guī)模 n， 有一函數(shù) ε(n) 使得 ≤ ε(n) ， 則稱(chēng)ε(n) 為該 近似算法的相對(duì)誤差界 。 **ccc?**ccc?23 頂點(diǎn)覆蓋問(wèn)題的近似算法 問(wèn)題描述：無(wú)向圖 G=(V,E)的頂點(diǎn)覆蓋是它的頂點(diǎn)集 V的一個(gè)子集 V’?V， 使得若 (u,v)是 G的一條邊，則 v∈V ’或u∈V ’。 VertexSet approxVertexCover ( Graph g ) { cset=?； e1=； while (e1 != ?) { 從 e1中任取一條邊 (u,v)； cset=cset∪{u,v} ； 從 e1中刪去與 u和 v相關(guān)聯(lián)的所有邊； } return c } Cset用來(lái)存儲(chǔ)頂點(diǎn)覆蓋中的各頂點(diǎn)。即 e1為空。 (e)表示算法產(chǎn)生的近似最優(yōu)頂點(diǎn)覆蓋 cset，它由頂點(diǎn)b,c,d,e,f,g所組成。 算法 approxVertexCover的性能比為 2。 要找出 G的最小費(fèi)用哈密頓回路。當(dāng)圖 G中的頂點(diǎn)就是平面上的點(diǎn)，任意 2頂點(diǎn)間的費(fèi)用就是這 2點(diǎn)間的歐氏距離時(shí)，費(fèi)用函數(shù) c就具有三角不等式性質(zhì)。 void approxTSP (Graph
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1