二近似算法

⑴ 如何设计近似算法

举一个例子：
解方程 lnx = x/5 （1）
这类方程没有精确解，只能采用数值方法近似求解：如迭代法等。
先建立迭代格式：
x1 = e^(x0 / 5) （2）
由 (1) 两边取 e 运算得来 ；x0为方程(2)根的初始近似值，可用观察法给出，
比如取： x0=0 ；将x0的值代入(2)，算出(2)的新的近似根：x1=1，
X1=1 1.2214 1.2765 1.2908 1.2944 1.2953 1.2956 1.2957
迭代了8步，得到方程(1) 的近似解： X = 1.295 保留4位有效数字。注意(2)的解也是(1)的解。
为了提高精度可继续迭代下去。（用的是附件中的计算器）。这就是迭代近似算法的设计过程的一个简例。

⑵ 近似算法的基本概念

所有已知的解决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。

⑶ 两种近似算法组成的算法怎么求解近似比

二分法是利用函数求方程近似解的一种方法。
对函数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]内，以此类推，直到到达所要求的精确度时，区间内的任意值都可以当做方程的解，通常取区间端点。