近似演算法的近似比

⑴ 如何設計近似演算法

舉一個例子：
解方程 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。

⑶ 數字的近似數怎麼演算法

根據要精確的小數位數四捨五入嘛。也可以用Matlab的「round()」函數，括弧內放你要處理的數，按回車，它會輸出你要的整數，也可以用format long這個代碼，打在Matlab的common window編程框中回車。
這里有個相關教程，你參考一下：
求近似數（A）
福建省廈門市湖明小學 吳炯鷺、林齊麗師

教學內容：
教科書第14－15頁例5、例6，「做一做」及練習二第3－5、7－8題。
教學目的：
1．會將整萬的數改成用「萬」作單位的數。
2．會用「四捨五入」法省略億以內數萬後面的尾數，求出它的近似數。
3．引導學生觀察、體驗數學與生活的密切聯系，讓學生體會數學知識來源於生活，服務於生活，培養學生主動探究的精神和用數學的意識。
教學重點、難點、關鍵：
1．重點：能把整萬的數改寫用「萬」作單位的數。
2．難點：能正確地省略萬後面的尾數寫出它的近似數。
3．關鍵：把生活中的某些鏡頭帶到學生面前，由果到因，讓學生體會「近似值」在社會生活中的實際應用。
教學過程：
一、教學把整萬的數改寫成用「萬」作單位的數。
1．投影出示白細胞和紅細胞的圖片，介紹白細胞：能消滅病菌，清潔血液；紅細胞：能輸送氧氣。一小滴血液含有：紅細胞：5000000個，白細胞：10000個。
2．讓學生把紅細胞 和白細胞的個數讀出來。
①按照四位分級的方法把上面三個數表示成下面形式：
500 0000 1 0000
②讓學生讀出二個數：五百萬、一萬。
③教師：讀了這些數以後，你發現了什麼？
④教師根據學生的讀數過程作如下板書：
500 0000＝500萬 1 0000＝1萬
3．學生觀察、比較等號右邊與等號左邊的數。
①同學們仔細觀察一下，等號右邊的數與等號左邊的數有什麼不同？
（等號右邊的數省略了萬位後面的尾數，等號左邊的數沒有省略萬位後面的尾數。
②它們有哪些相同的地方？（等號兩邊的數大小完全相同）
4．學生小組討論：
①請同學們想一想，怎樣用「萬」作單位表示整萬的數？（用萬作單位表示整萬的數只需要去掉萬位後面的四個「0」，並寫上「萬」字。）
②用萬作單位表示數有什麼好處？
（用萬作單位表示數既簡單又不容易寫錯，使人一看就知道數的大小。）
5．小結：為了讀數和寫數的方便，今後我們可以直接用「萬」作單位表示整萬數。
6．練習：
⑴讓學生獨立完成第14頁「做一做」1、2題，師巡視。
⑵改寫完後，抽一部分同學把完成的練習在展示台上展示出來，集體評價。
二、教學用「四捨五入」法求近似數。
1．導入：
有些較大的數，有時沒有必要或者無法說出它的准確數。比如，重慶市開展萬人長跑活動，參加的人數約15000人，這個15000人就是一個近似數。又比如北京申辦2008年奧運會的經費是20000000（2千萬）美元，摺合人民幣約為1億6千萬元，這個1億6千萬也只是一個大概數據。既然生活中用到近似數這么多，那我們就應重視近似數的學習，怎樣求一個數的近似數呢？
我們已經學過用四捨五入法求一個數的近似數。
2．復習：
用什麼方法省略4926和9375千位後面的尾數？兩個數的省略方法有什麼不同？（引導學生說出省略千位後面的尾數要根據百位上的數進行「四捨五入」的方法。）
師：如果把數擴大到比萬大的數，還可以用同樣的方法來求它的近似數嗎？
3．教師出示例6
①讓學生試做，同時指定一名學生在黑板上完成。
②集本訂正，然後分組議一議：⑴在省略12756和1389000萬位後面的尾數時，要根據哪一位上的數進行「四捨五入」？⑵在求近似數時，12756的千位上的數不滿5，應該怎麼辦？1389000千位上的數比5大，該怎麼辦？⑶求出的近似數為什麼不使用「等號」而要使用「約等號」？
③引導學生通過討論，解決以上三個問題。要特別注意讓學生搞清楚：因為是求一個數的近似數，不是准確數，所以要使用「約等號」。
④讓學生完成第15頁「做一做」的題目，然後抽學生說說是怎樣想的？
4．小結：
①同學們，我們學習了把一個較大的數省略萬位後面的尾數，求出近似數；我們還學習了把一個整萬的數改寫成用「萬」作單位的數。這兩方面內容在意義和方法上有什麼相同的地方和不同的地方？
②學生分小組討論，然後由每小組推薦一個代表匯報討論結果，最後由教師總結：求近似數和改寫數都要改變數的表現形式，但它們的實質是不同的，求近似數改變了原數的大小，而用「萬」作單位只改變了數的表現形式，沒有改變數的大小。
三、鞏固練習
①完成練習二第3、5題。
訂正時讓學生說說改寫成用「萬」作單位的數和省略萬後面的尾數求出近似數在方法上有什麼不同。
②學生獨立完成練習二第4題。
四、課堂小結
教師：同學們回憶一下，這節課我們都學了哪些知識？把一個數改寫成用「萬」作單位的數以及求一個數的近似數時要注意些什麼？
學生小結後教師做概括性的總結和評價。

⑷ 計算方法求近似值的方法

1．四捨五入法
這種最常用的求近似數的方法，主要是看它省略的尾數是4或比4小時，就把尾數捨去；如果省略的尾數最高位上的數是5或比5大時，把尾數省略去掉後，要向前一位進一。如3096401≈310萬，1÷3=0.333……≈0.3。從上面兩例可以看出「四舍」時近似數比准確值小，「五入」時近似數比准確值大。
2．進一法
在實際生活中，有時把一個數的尾數省略後，不管尾數最高位上的數是幾，都要向前一位進一。比如一輛車能容納4個人，現在有15個人，則需要的車輛數目為15除以4等於3.75約定於4
3．去尾法
在實際生活中，有時把一個數的尾數省略後，不管尾數的最高位上的數是幾，都不要向它的前一位進一。例如一個牛皮盒子需要3平方分米的牛皮才能完成，而現在只有10平方分米的牛皮，則只能完成10除以3等於3,3約等於3個
這三種求近似數的方法，各自適用於不同的情況，一般來說，如果沒有特殊要求或其他條件的限制時，都應採取四捨五入法。
最後，有些時候需要用科學計數法表達。

⑸ 近似演算法的子集和問題的近似演算法

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

⑹ 近似演算法的介紹

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

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

二分法是利用函數求方程近似解的一種方法。
對函數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]內，以此類推，直到到達所要求的精確度時，區間內的任意值都可以當做方程的解，通常取區間端點。

⑻ 近似演算法和啟發式演算法的區別與聯系

在計算機科學與運籌學，近似演算法是指用來發現近似方法來解決優化問題的演算法。近似演算法通常與NP-hard問題相關; 由於不可能有效的多項式時間精確算來解決NP-hard問題，所以一個求解多項式時間次優解。與啟發式演算法不同，通常只能找到合理的解決方案相當快速，需要可證明的解決方案質量和可證明的運行時間范圍。理想情況下，近似值最優可達到一個小的常數因子（例如在最優解的5%以內）。近似演算法越來越多地用於已知精確多項式時間演算法但由於輸入大小而過於昂貴的問題。
啟發式演算法（heuristic algorithm)是相對於最優化演算法提出的。一個問題的最優演算法求得該問題每個實例的最優解。啟發式演算法可以這樣定義：一個基於直觀或經驗構造的演算法，在可接受的花費（指計算時間和空間）下給出待解決組合優化問題每一個實例的一個可行解，該可行解與最優解的偏離程度一般不能被預計。現階段，啟發式演算法以仿自然體演算法為主，主要有蟻群演算法、模擬退火法、神經網路等。

⑼ 對於有scaling性質的問題，近似演算法的絕對性能比和漸近性能比是相同的，為什麼

有scaling的性質的話,他的最優解的值函數可以無限的擴張,所以不管N是多少,都可以通過擴張來滿足opt(I)>N的條件,從而使得對任何一個I屬於D,有RA(I)小於等於r成立,然後這就是絕對性能比的定義...我jio著可能是這樣的,純粹個人理解..