第9章np完全性理論與近似算法(編輯修改稿)
2024-11-22 13:02 本頁面
【文章內(nèi)容簡介】 成。 ||w)( 2nO 在算法的第二階段中，非確定性地選擇 V的一個 k元子集 V’?V。 算法的第三階段是確定性地檢查 V’的團性質(zhì)。若 V’是一個團則接受輸入，否則拒絕輸入。這顯然可以在 時間內(nèi)完成。因此，整個算法的時間復(fù)雜性為 。 )( 4nO)( 4nO非確定性算法在多項式時間內(nèi)接受語言 CLIQUE， 故 CLIQUE∈NP 。 16 多項式時間驗證 VP={L|L∈∑* ， ∑ 為一有限字符集，存在一個多項式 p和一個多項式時間驗證算法 A(X， Y)使得對任意 X∈∑* ， X∈L 當(dāng)且僅當(dāng)存在 Y∈∑* ， |Y|≤p(|X|) 且 A(X， Y)=1}。 多項式時間可驗證語言類 VP可定義為： 定理 91： VP=NP。 例如 (哈密頓回路問題 )：一個無向圖 G含有哈密頓回路嗎 ? 無向圖 G的哈密頓回路是通過 G的每個頂點恰好一次的簡單回路 ?？捎谜Z言 HAMCYCLE 定義該問題如下： HAMCYCLE={G|G含有哈密頓回路 } 17 NP完全問題 ? P?NP。 ? 直觀上看 ， P類問題是確定性計算模型下的易解問題類 ， 而 NP類問題是非確定性計算模型下的易驗證問題類 。 ? 大多數(shù)的計算機科學(xué)家認(rèn)為 NP類中包含了不屬于 P類的語言 ， 即 P≠NP。 ? NP完全問題有一種令人驚奇的性質(zhì) ， 即如果一個 NP完全問題能在多項式時間內(nèi)得到解決 ， 那么 NP中的每一個問題都可以在多項式時間內(nèi)求解 ， 即 P=NP。 ? 目前還沒有一個 NP完全問題有多項式時間算法 。 18 多項式時間變換 定義： 語言 L是 NP完全的當(dāng)且僅當(dāng) (1)L∈NP ； (2)對于所有 L’∈NP 有 L’ ∝ p L。 如果有一個語言 L滿足上述性質(zhì) (2)，但不一定滿足性質(zhì) (1)，則稱該語言是 NP難 的。所有 NP完全語言構(gòu)成的語言類稱為 NP完全語言類 ，記為 NPC。 設(shè) ， 是 2個語言。所謂語言 能在多項式時間內(nèi)變換為語言 (簡記為 ∝ p )是指存在映身 f: ，且 f滿足： (1)有一個計算 f的多項式時間確定性圖靈機； (2)對于所有 x∈ ， x∈ ， 當(dāng)且僅當(dāng) f(x)∈ 。 *11 ??L *22 ??L 1L2L 1L2L*2*1 ???1L 2L*1?19 多項式時間變換 定理 92：設(shè) L是 NP完全的，則 (1)L∈P 當(dāng)且僅當(dāng) P＝ NP； (2)若 L∝ p ， 且 ∈ NP， 則 是 NP完全的。 1L 1L 1L定理的 (2)可用來證明問題的 NP完全性。但前提是：要有第一個 NP完全問題 L。 20 9. 一些典型的 NP完全問題 部分 NP完全問題樹 21 迄今為止，所有的 NP完全問題都還沒有多項式時間算法。 對于這類問題，通?？刹扇∫韵聨追N解題策略。 (1)只對問題的特殊實例求解 (2)用動態(tài)規(guī)劃法或分支限界法求解 (3)用概率算法求解 (4)只求近似解 (5)用啟發(fā)式方法求解 NP完全問題的近似算法 22 近似算法的性能 若一個最優(yōu)化問題的最優(yōu)值為 c*， 求解該問題的一個近似算法求得的近似最優(yōu)解相應(yīng)的目標(biāo)函數(shù)值為 c， 則將該 近似算法的性能比 定義為 ?= 。在通常情況下，該性能比是問題輸入規(guī)模 n的一個函數(shù) ρ(n) ， 即 ≤ ρ(n) 。 ?????? cccc *,*m a x?????? cccc *,*m a x 該 近似算法的相對誤差 定義為 ?= 。若對問題的輸入規(guī)模 n， 有一函數(shù) ε(n) 使得 ≤ ε(n) ， 則稱ε(n) 為該 近似算法的相對誤差界 。近似算法的性能比ρ(n) 與相對誤差界 ε(n) 之間顯然有如下關(guān)系：ε(n)≤ρ(n)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1