第9章np完全性理論與近似算法-資料下載頁
2025-10-08 13:02本頁面
【導(dǎo)讀】理解RAM，RASP和圖靈機(jī)計(jì)算模型。理解P類與NP類語言的概念。理解近似算法的性能比及多項(xiàng)式時(shí)間近似格式的概念。通過范例學(xué)習(xí)NP完全問題的近似算法。旅行售貨員問題；在進(jìn)行問題的計(jì)算復(fù)雜性分析之前，首先必須建立求解問題所用的計(jì)算模型，包括定。這3個(gè)計(jì)算模型在計(jì)算能力上是等價(jià)的，但在計(jì)算速度上是不同的。一個(gè)RAM程序定義了從輸入帶到輸出帶的一個(gè)映射。這種映射關(guān)系作2種不同的解釋。后停機(jī)，那么就說程序P計(jì)算了函數(shù)f(x1，x2，…格中放入符號(hào)a1，第二個(gè)方格中放入符號(hào)a2，…然后在第n+1個(gè)方格中放入0，作為輸入串的結(jié)束標(biāo)。如果一個(gè)RAM程序P讀了字符串S及結(jié)束標(biāo)志符0后，在輸出。個(gè)寄存器占用一個(gè)單位空間。以后除特別注明，RAM程序的復(fù)雜。性將按照均勻耗費(fèi)標(biāo)準(zhǔn)衡量。與以二進(jìn)制表示的指令的操作數(shù)長度成比例。每條RASP指令占據(jù)2個(gè)連續(xù)的寄存器。qf是終止(或接受)狀態(tài)。式時(shí)間才能求解的問題看作是難處理的問題。,xk)中隨意選定一個(gè)值作為它的函數(shù)值。
【正文】 示集合 X。F={S1,S2,S3,S4,S5,S6,}， 如圖所示。容易看出，對(duì)于這個(gè)例子，最小集合覆蓋為：C={S3,S4,S5,}。 31 集合覆蓋問題的近似算法 集合覆蓋問題近似算法 —— 貪心算法 算法的循環(huán)體最多執(zhí)行 min{|X|， |F|}次。而循環(huán)體內(nèi)的計(jì)算顯然可在 O(|X||F|)時(shí)間內(nèi)完成。因此，算法的計(jì)算時(shí)間為 O(|X||F|min{|X|，|F|})。 由此即知，該算法是一個(gè)多項(xiàng)式時(shí)間算法。 Set greedySetCover (X,F) { U=X； C=?； while (U !=?) { 選擇 F中使 |S∩U| 最大的子集 S； U=US； C=C∪{S} ； } return C； } 32 子集和問題的近似算法 問題描述：設(shè)子集和問題的一個(gè)實(shí)例為〈 S,t〉。其中， S={x1， x2， … ， xn}是一個(gè)正整數(shù)的集合， t是一個(gè)正整數(shù)。子集和問題判定是否存在 S的一個(gè)子集S1， 使得 。 txSx??? 133 1 子集和問題的指數(shù)時(shí)間算法 int exactSubsetSum (S,t) { int n=|S|； L[0]={0}； for (int i=1； i=n； i++) { L[i]=mergeLists(L[i1],L[i1]+S[i])； 刪去 L[i]中超過 t的元素； } return max(L[n])； } 算法以集合 S={x1，x2， … ， xn}和目標(biāo)值 t作為輸入。算法中用到將 2個(gè)有序表L1和 L2合并成為一個(gè)新的有序表的算法mergeLists(L1,L2)。 34 2 子集和問題的完全多項(xiàng)式 時(shí)間近似格式 基于算法 exactSubsetSum， 通過對(duì)表 L[i]作適當(dāng)?shù)男拚⒁粋€(gè)子集和問題的 完全多項(xiàng)式時(shí)間近似格式 。 在對(duì)表 L[i]進(jìn)行修整時(shí)，用到一個(gè)修整參數(shù) δ ， 0＜ δ ＜ 1。用參數(shù) δ 修整一個(gè)表 L是指從 L中刪去盡可能多的元素，使得每一個(gè)從 L中刪去的元素 y， 都有一個(gè)修整后的表 L1中的元素 z滿足 (1δ)y≤z≤y 。 可以將 z看作是被刪去元素 y在修整后的新表 L1中的代表。 舉例： 若 δ= ， 且 L=〈 10,11,12,15,20,21,22,23,24,29〉，則用 δ 對(duì) L進(jìn)行修整后得到 L1=〈 10， 12， 15， 20， 23， 29〉。其中被刪去的數(shù) 11由 10來代表， 21和 22由 20來代表， 24由 23來代表。 35 2 子集和問題的完全多項(xiàng)式 時(shí)間近似格式 對(duì)有序表 L修整算法 List trim(L,δ) { int m=|L|； L1=〈 L[1]〉 ； int last=L[1]； for (int i=2； i=m； i++) { if (last(1δ)*L[i]) { 將 L[i]加入表 L1的尾部； last=L[i]； } return L1； } 子集和問題近似格式 int approxSubsetSum(S,t,ε) { n=|S|； L[0]=〈 0〉 ； for (int i=1； i=n； i++) { L[i]=MergeLists(L[i1], L[i1]+S[i])； L[i]=Trim(L[i],ε/n)； 刪去 L[i]中超過 t的元素； } return max(L[n])； } 36 課后作業(yè) ? 習(xí)題 91， 93， 94， 95， 99， 916 37
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1