第9章np完全性理論與近似算法-閱讀頁
2024-11-06 13:02本頁面
【正文】 g) { (1)選擇 g的任一頂點 r； (2)用 Prim算法找出帶權圖 g的一棵以 r為根的最小生成樹 T； (3)前序遍歷樹 T得到的頂點表 L； (4)將 r加到表 L的末尾 ， 按表 L中頂點次序組成回路 H， 作為計 算結(jié)果返回； } 當費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的 2倍。 28 2 一般 的 旅行售貨員問題 在費用函數(shù)不一定滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解 TSP問題的多項式時間近似算法，除非 P=NP。 29 集合覆蓋問題的近似算法 問題描述：給定一個完全無向圖 G=(V,E)， 其每一邊(u,v)∈E 有一非負整數(shù)費用 c(u,v)。 集合覆蓋問題的一個實例〈 X,F〉 由一個有限集 X及 X的一個子集族 F組成。 也就是說 X中每一元素至少屬于 F中的一個子集，即 X= 。 集合覆蓋問題就是要找出 F中覆蓋 X的最小子集 C*， 使得 |C*|=min{|C||C?F且 C覆蓋 X} ?FS S??CS S?30 集合覆蓋問題的近似算法 集合覆蓋問題舉例： 用 12個黑點表示集合 X。容易看出，對于這個例子，最小集合覆蓋為：C={S3,S4,S5,}。而循環(huán)體內(nèi)的計算顯然可在 O(|X||F|)時間內(nèi)完成。 由此即知，該算法是一個多項式時間算法。其中， S={x1， x2， … ， xn}是一個正整數(shù)的集合， t是一個正整數(shù)。 txSx??? 133 1 子集和問題的指數(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}和目標值 t作為輸入。 34 2 子集和問題的完全多項式 時間近似格式 基于算法 exactSubsetSum， 通過對表 L[i]作適當?shù)男拚⒁粋€子集和問題的 完全多項式時間近似格式 。用參數(shù) δ 修整一個表 L是指從 L中刪去盡可能多的元素，使得每一個從 L中刪去的元素 y， 都有一個修整后的表 L1中的元素 z滿足 (1δ)y≤z≤y 。 舉例： 若 δ= ， 且 L=〈 10,11,12,15,20,21,22,23,24,29〉，則用 δ 對 L進行修整后得到 L1=〈 10， 12， 15， 20， 23， 29〉。 35 2 子集和問題的完全多項式 時間近似格式 對有序表 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è) ? 習題 91， 93， 94， 95， 99， 916 37
教學課件相關推薦
鄂ICP備17016276號-1