近似算法

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. 近似计算的方法有哪些

虽然听说圆周率的计算方法有很多,但我都不知道具体内容和算法,所以很希望历史上曾采用过圆周率的多种近似值,早期大都是通过实验而得到的结果,如古