在計算機科學與運籌學，近似算法是指用來發現近似方法來解決最佳化問題的算法。近似算法通常與NP-hard問題相關; 由於不可能有效的多項式時間精確算來解決NP-hard問題，所以一個求解多項式時間次優解。與啟發式算法不同，通常只能找到合理的解決方案相當快速，需要可證明的解決方案質量和可證明的運行時間範圍，既近似算法通常可得到一個有質量保證的解。
理想情況下，近似值最優可達到一個小的常數因子（例如在最優解的5%以內）。近似算法越來越多地用於已知精確多項式時間算法但由於輸入大小而過於昂貴的問題。
基本介紹
- 中文名：近似算法
- 外文名：approximation algorithm
- 1：基本概念
- 2：算法設計技術
- 3：策略
- 4：實例
算法設計技術,策略,實例,
算法設計技術
現在有幾種標準技術可以設計一種近似算法。這些包括以下內容。
1.貪婪算法
2.本地搜尋
3.枚舉和動態規劃
4.解決凸規劃鬆弛以獲得分數解，然後通過一些適當的捨入將這個分數解解成一個可行的解。流行的放鬆包括以下：
1.線性規劃放鬆
2.半封閉編程放鬆
5.將問題嵌入到一些簡單的度量中，然後解決度量上的問題。這也被稱為度量嵌入
策略
所有已知的解決NP-難問題算法都有指數型運行時間。但是，如果我們要找一個“好”解而非最優解，有時候多項式算法是存在的。
給定一個最小化問題和一個近似算法，我們按照如下方法評價算法：首先給出最優解的一個下界，然後把算法的運行結果與這個下界
進行比較。對於最大化問題，先給出一個上界然後把算法的運行結果與這個上界比較。
近似算法比較經典的問題包括：最小頂點覆蓋、旅行售貨員問題、集合覆蓋等。
迄今為止，所有的NP完全問題都還沒有多項式時間算法。
對於這類問題，通常可採取以下幾種解題策略。
(1)只對問題的特殊實例求解
(2)用動態規劃法或分支限界法求解
(3)用機率算法求解
(4)只求近似解
(5)用啟發式方法求解
若一個最最佳化問題的最優值為c*，求解該問題的一個近似算法求得的近似最優解相應的目標函式值為c，
則將該近似算法的性能比定義為max(c/c*, c*/c)。在通常情況下，該性能比是問題輸入規模n的一個函式
ρ(n)，即 max(c/c*, c*/c) <= ρ(n)。
該近似算法的相對誤差定義為Abs[(c-c*)/c*]。若對問題的輸入規模n，有一函式ε(n)使得Abs[(c-c*)/c*] <= ε(n)，則稱ε(n)為該近似算法的相對誤差界。近似算法的性能比ρ(n)與相對誤差界ε(n)之間顯然有如下
關係：ε(n)≤ρ(n)-1。
實例
頂點覆蓋問題的近似算法
問題描述：無向圖G=(V,E)的頂點覆蓋是它的頂點集V的一個子集V’，使得若(u,v)是G的一條邊，則v∈V’或u∈V’。頂點覆蓋V’的大小是它所包含的頂點個數|V’|。
VertexSet approxVertexCover ( Graph g )
{ cset=NULL；
e1=g.e；
while (e1 !=NULL) {
從e1中任取一條邊(u,v)；
cset=cset∪{u,v}；
從e1中刪去與u和v相關聯的所有邊；
}
return c
}
Cset用來存儲頂點覆蓋中的各頂點。初始為空，不斷從邊集e1中選取一邊(u,v)，將邊的端點加入cset中，並將e1中已被u和v覆蓋的邊刪去，直至cset已覆蓋所有邊。即e1為空。
圖(a)～(e)說明了算法的運行過程及結果。(e)表示算法產生的近似最優頂點覆蓋cset，它由頂點b,c,d,e,f,g所組成。(f)是圖G的一個最小頂點覆蓋，它只含有3個頂點：b,d和e。
旅行售貨員問題近似算法
問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)∈E有一非負整數費用c(u,v)。要找出G的最小費用哈密頓迴路。
旅行售貨員問題的一些特殊性質：
比如，費用函式c往往具有三角不等式性質，即對任意的3個頂點u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。當圖G中的頂點就是平面上的點，任意2頂點間的費用就是這2點間的歐氏距離時，費用函式c就具有三角不等式性質。
對於給定的無向圖G，可以利用找圖G的最小生成樹的算法設計找近似最優的旅行售貨員迴路的算法。
void approxTSP (Graph g)
{
(1)選擇g的任一頂點r；
(2)用Prim算法找出帶權圖g的一棵以r為根的最小生成樹T；
(3)前序遍歷樹T得到的頂點表L；
(4)將r加到表L的末尾，按表L中頂點次序組成迴路H，作為計 算結果返回；
}
當費用函式滿足三角不等式時，算法找出的旅行售貨員迴路的費用不會超過最優旅行售貨員迴路費用的2倍。
(b)表示找到的最小生成樹T；(c)表示對T作前序遍歷的次序；(d)表示L產生的哈密頓迴路H；
(e)是G的一個最小費用旅行售貨員迴路。
一般的旅行售貨員問題
在費用函式不一定滿足三角不等式的一般情況下，不存在具有常數性能比的解TSP問題的多項式時間近似算法，除非P=NP。換句話說，若P≠NP，則對任意常數ρ>1，不存在性能比為ρ的解旅行售貨員問題的多項式時間近似算法。
集合覆蓋問題的近似算法
問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)∈E有一非負整數費用c(u,v)。要找出G的最小費用哈密頓迴路。
集合覆蓋問題的一個實例〈X,F〉由一個有限集X及X的一個子集族F組成。子集族F覆蓋了有限集X。也就是說X中每一元素至少屬於F中的一個子集，即X= 。對於F中的一個子集CF，若C中的X的子集覆蓋了X，即X= ，則稱C覆蓋了X。集合覆蓋問題就是要找出F中覆蓋X的最小子集C*，使得
|C*|=min{|C||CF且C覆蓋X}
集合覆蓋問題舉例：用12個黑點表示集合X。F={S1,S2,S3,S4,S5,S6,}，如圖所示。容易看出，對於這個例子，最小集合覆蓋為：C={S3,S4,S5,}。
集合覆蓋問題近似算法——貪心算法
Set greedySetCover (X,F)
{
U=X；
C=；
while (U !=) {
選擇F中使|S∩U|最大的子集S；
U=U-S；
C=C∪{S}；
}
return C；
}
算法的循環體最多執行min{|X|，|F|}次。而循環體內的計算顯然可在O(|X||F|)時間內完成。因此，算法的計算時間為O(|X||F|min{|X|，|F|})。由此即知，該算法是一個多項式時間算法。
子集和問題的近似算法
問題描述：設子集和問題的一個實例為〈S,t〉。其中，S={x1，x2，…，xn}是一個正整數的集合，t是一個正整數。子集和問題判定是否存在S的一個子集S1，使得∑x = t。(x屬於S1)
1 子集和問題的指數時間算法
int exactSubsetSum (S,t)
{
int n=|S|；
L[0]={0}；
for (int i=1；i<=n；i++) {
L[i]=mergeLists(L[i-1],L[i-1]+S[i])；
刪去L[i]中超過t的元素；
}
return max(L[n])；
}
算法以集合S={x1，x2，…，xn}和目標值t作為輸入。算法中用到將2個有序表L1和L2合併成為一個新的有序表的算法mergeLists(L1,L2)。
2 子集和問題的完全多項式時間近似格式
基於算法exactSubsetSum，通過對表L[i]作適當的修整建立一個子集和問題的完全多項式時間近似格式。
在對表L[i]進行修整時，用到一個修整參數δ，0<δ<1。用參數δ修整一個表L是指從L中刪去儘可能多的元素，使得每一個從L中刪去的元素y，都有一個修整後的表L1中的元素z滿足(1-δ)y≤z≤y。可以將z看作是被刪去元素y在修整後的新表L1中的代表。
舉例：若δ=0.1，且L=〈10,11,12,15,20,21,22,23,24,29〉，則用δ對L進行修整後得到L1=〈10，12，15，20，23，29〉。其中被刪去的數11由10來代表，21和22由20來代表，24由23來代表。
對有序表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]=Merge-Lists(L[i-1],
L[i-1]+S[i])；
L[i]=Trim(L[i],ε/n)；
刪去L[i]中超過t的元素；
}
return max(L[n])；
}
