近似演算法

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。

2. 淺談近似計算的幾種常用方法

一四捨五入進行計算
二取有效數字進行計算
三考慮實際意義，然後進行取捨，然後計算。

3. 等價無窮小和近似計算的區別

等價無窮小代換的實質是捨去余項後的近似計算,使用等價無窮小代換能夠簡捷的計算某些極限，因此簡化了某些計算過程。等價無窮小的實質就是泰勒公式在0點展開保留一階，與x等價。
線性近似其實按照字面意思可以理解成一小段平滑曲線可以用很多段小直線近似代替。這也是微分的幾何意義。那我們必須提一個重要人物——泰勒，他提出了拉格朗日余項，這個式子告訴我們，任何任意階可導的函數都可以在某一點展開成多項式的和，也就是說，用這個多項式去逼近函數值。

4. 近似演算法的介紹

本文對幾種近似演算法做了較為祥細的介紹，主要有頂點覆蓋問題的近似演算法旅行售貨員問題近似演算法一般的旅行售貨員問題集合覆蓋問題的近似演算法子集和問題的近似演算法

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。

6. 近似演算法的集合覆蓋問題的近似演算法

問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)∈E有一非負整數費用c(u,v)。要找出G的最小費用哈密頓迴路。
集合覆蓋問題的一個實例〈X,F〉由一個有限集X及X的一個子集族F組成。子集族F覆蓋了有限集X。也就是說X中每一元素至少屬於F中的一個子集，即X= 。對於F中的一個子集CF，若C中的X的子集覆蓋了X，即X= ，則稱C覆蓋了X。集合覆蓋問題就是要找出F中覆蓋X的最小子集C*，使得
|C*|=min{|C||CF且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|})。由此即知，該演算法是一個多項式時間演算法。

7. 近似演算法在程序設計中的一些應用 最好是C語言 或者java的

自己去GNU下載。

8. 兩種近似演算法組成的演算法怎麼求解近似比

二分法是利用函數求方程近似解的一種方法。
對函數y=f(x)，若在區間[a,b]上是連續不斷的一條曲線，且f(a)*f(b)<0，則方程f(x）=0在區間[a,b]上有解。
當確定方程的解在區間[a,b]上時，取區間[a,b]的中點c=(a+b)/2，再確定方程的解在區間[a,c]內還是區間[c,b]內，以此類推，直到到達所要求的精確度時，區間內的任意值都可以當做方程的解，通常取區間端點。

9. 近似演算法的子集和問題的近似演算法

問題描述：設子集和問題的一個實例為〈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])；
}

10. 近似計算的方法有哪些

雖然聽說圓周率的計算方法有很多,但我都不知道具體內容和演算法,所以很希望歷史上曾採用過圓周率的多種近似值,早期大都是通過實驗而得到的結果,如古