二近似演算法

⑴ 如何設計近似演算法

舉一個例子：
解方程 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]內，以此類推，直到到達所要求的精確度時，區間內的任意值都可以當做方程的解，通常取區間端點。