高級算法設(shè)計與分析近似算法林海lin.hai@B站：foretmer目錄概述旅行商問題子集和問題集合覆蓋-整數(shù)規(guī)劃斯坦納最小樹概述NPC問題該如何求解?如果規(guī)模很小，用指數(shù)運行時間算法對一些特殊的情況，如果有多項式時間可以解決，則設(shè)計多項式算法對用一般情況，則通過多項式時間的近似解法概述近似解的精確度C：某一算法解的代價C*：最優(yōu)解的代價如果一個解達到此因子，則稱算法C為ρ(n)近似算法概述近似模式：對于一個輸入為n的實例，通常近似算法的因子為（1+ε）算法時間除了和n相關(guān)，和ε也相關(guān)如果對于任意一個ε>0，該算法都可以在輸入規(guī)模為n的多項式時間內(nèi)完成，稱此模式為多項式時間近似模式顯然此種模式下，當(dāng)ε趨近于0時，算法逼近最優(yōu)值，但可能算法的復(fù)雜度急劇增加，如時間復(fù)雜度為多項式時間近似模式中一種更好的模式稱為完全多項式時間近似模式，其復(fù)雜度為：這種模式當(dāng)ε減少時，運行時間不會指數(shù)增長，而是多項式增長旅行商問題旅行商問題為NPC問題定義：對于完全無向圖G=（V，E），設(shè)c(A)為子集A的總代價三角不等式：旅行商問題滿足三角不等式的旅行商問題生成最小生成樹按對樹進行先序的順序訪問節(jié)點上述算法中，生成最下生成樹可以用Kruskal算法或者Prim算法，復(fù)雜度都為O(mlogn)。先序遍歷的復(fù)雜度為O(n)，所以旅行商問題的近似算法復(fù)雜度為O(mlogn)

旅行商問題旅行商問題最優(yōu)旅行線路（H*）的總代價的下限為最小生成樹（T）邊的總代價對T進行按先序往返（返回時會再次遍歷節(jié)點）遍歷（W），W剛好對所有的邊遍歷兩次旅行商問題一般旅行商問題三角不等式不成立的條件下，ρ近似的旅行商問題是一個NPC問題，則定理自然成立旅行商問題如果圖G存在一條哈密頓回路H，則G′必然存在一條代價為n的旅行商回路TSP(同H),此回路為ρ近似旅行商回路如果圖G′存在一條ρ近似的旅行商回路TSPρ，則圖G必然存在一條哈密頓回路H

子集和問題準(zhǔn)確算法（指數(shù)時間復(fù)雜度）:得出集合S的所有子集，并計算所有子集的和優(yōu)化在第i-1輪迭代中，計算(e1,e2,…,ei-1)所有的子集和在第i輪迭代中，計算(e1,

e2,…,ei)在相加的過程中，一旦子集和超過t，舍棄子集和問題子集和問題去除相近的元素：x可以被y代替例子子集和問題子集和問題子集和問題子集和問題子集和問題按這兩種不同的情況討論子集和問題子集和問題子集和問題所以：子集和問題子集和問題Ln必然包含0元素，可能包含1元素集合覆蓋問題簡單集合覆蓋

集合覆蓋問題：例子集合覆蓋問題貪心算法集合覆蓋問題算法第i次選擇了子集Si加入到頂點覆蓋集R，則其總代價+1在選取第i個子集Si時，假設(shè)ni個元素被Si首次覆蓋，其中每個元素分配到的代價為：集合覆蓋問題集合覆蓋問題當(dāng)近似算法選擇了i個子集后，子集S中未被覆蓋的元素的個數(shù)集合覆蓋問題集合覆蓋問題集合覆蓋問題集合覆蓋-整數(shù)規(guī)劃帶權(quán)重的集合覆蓋：覆蓋所有的元素，其權(quán)重總和最小設(shè)E={1,2,3,4,5,6,7,8}子集有:S1={1,2,3}w1=1S2={2,7,8}w2=2S3={4,5,6,7}w3=3S4={4,5,6,8}w4=4解:C={S1,S2,S3},C={S1,S2,S4}最優(yōu)解：C={S1,S2,S3}集合覆蓋-整數(shù)規(guī)劃松弛集合覆蓋-整數(shù)規(guī)劃算法元素的最大頻率f：設(shè)g表示包含某一元素的子集個數(shù)，則最大的g即元素的最大頻率f在所有的LP最優(yōu)解的子集中，選取xi（每個子集通過LP求解得出的值）的值大于1/f的子集作為IP的解集合覆蓋-整數(shù)規(guī)劃證明1：以上選取的子集包含了E中所有的元素集合覆蓋-整數(shù)規(guī)劃集合覆蓋-原始-對偶算法集合覆蓋-原始-對偶算法集合覆蓋-原始-對偶算法集合覆蓋-原始-對偶算法集合覆蓋-原始-對偶算法集合覆蓋-原始-對偶算法集合覆蓋-原始-對偶算法集合覆蓋-原始-對偶算法斯坦納最小樹斯坦納最小樹用最小生成樹來近似斯坦納樹？斯坦納最小樹斯坦納最小樹：例子GRTMTGMTTST斯坦納最小樹：例子算法基于原圖G，生成R的一個完全圖GR，其中任意一條邊的權(quán)重為原圖G中的最短路徑基于GR，生成最小生成樹TMT

將TMT

中的邊替換成原來的最短路徑，得到圖GMT

如果替換成最短路徑后生成的圖不是樹，則需進一步生成最小生成樹TST

斯坦納最小樹：例子斯坦納最小樹：例子斯坦納最小樹：例子W對TST按照先序往返(返回時會再次遍歷節(jié)點)遍歷斯坦納最小樹：例子GS