三大算法總結

近似算法：概述：1.1近似算法的設計思想：許多難解問題實質上是最優(yōu)化問題，即要求在滿足約束條件的前提下，使某個目標函數(shù)達到最大值或最小值的解。在這類問題中，求得最優(yōu)解往往需要付出極大的代價。在現(xiàn)實世界中，很多問題的輸入數(shù)據(jù)是用測量方法獲得的，而測量的數(shù)據(jù)本身就存在著一定程度的誤差，因此，輸入數(shù)據(jù)是近似的。同時，很多問題的解允許有一定程度的誤差，只要給出的解是合理的、可接受的，近似最優(yōu)解常常就能滿足實際問題的需要。此外，采用近似算法可以在很短的時間內得到問題的近似解，所以，近似算法是求解難解問題的一個可行的方法。即使某個問題存在有效算法，好的近似算法也會發(fā)揮作用。因為待求解問題的實例是不確定的，或者在一定程度上是不準確的，如果使用近似算法造成的誤差比不精確的數(shù)據(jù)帶來的誤差小，并且近似算法遠比精確算法高效，那么，出于實用的目的，當然更愿意選擇近似算法了。近似算法的基本思想是用近似最優(yōu)解代替最優(yōu)解，以換取算法設計上的簡化和時間復雜性的降低。近似算法是這樣一個過程：雖然它可能找不到一個最優(yōu)解，但它總會為待求解的問題提供一個解。為了具有實用性，近似算法必須能夠給出算法所產生的解與最優(yōu)解之間的差別或者比例的一個界限，它保證任意一個實例的近似最優(yōu)解與最優(yōu)解之間相差的程度。顯然，這個差別越小，近似算法越具有實用性。1.2近似算法的性能：衡量近似算法性能最重要的標準有兩個：（1）算法的時間復雜性：近似算法的時間復雜性必須是多項式階的，這是設計近似算法的基本目標；（2）解的近似程度：近似最優(yōu)解的近似程度也是設計近似算法的重要目標。近似程度可能與近似算法本身、問題規(guī)模，乃至不同的輸入實例都有關。不失一般性，假設近似算法求解的是最優(yōu)化問題，且對于一個確定的最優(yōu)化問題，每一個可行解所對應的目標函數(shù)值均為正數(shù)。若一個最優(yōu)化問題的最優(yōu)值為，求解該問題的一個近似算法求得的近似最優(yōu)值為，則將該近似算法的近似比（ApproximateRatio）η定義為：在通常情況下，該性能比是問題輸入規(guī)模n的一個函數(shù)，即：這個定義對于最大化問題和最小化問題都是適用的。對于一個最大化問題，≤，此時近似算法的近似比表示最優(yōu)值比近似最優(yōu)值大多少倍；對于一個最小化問題，≤，此時近似算法的近似比表示近似最優(yōu)值比最優(yōu)值大多少倍。所以，近似算法的近似比η不會小于1，近似算法的近似比越大，它求出的近似解就越差。顯然，一個能求得最優(yōu)解的近似算法，其近似比為1。有時用相對誤差表示一個近似算法的近似程度會更方便些。若一個最優(yōu)化問題的最優(yōu)值為，求解該問題的一個近似算法求得的近似最優(yōu)值為，則該近似算法的相對誤差（RelativeError）定義為：=近似算法的相對誤差總是非負的，它表示一個近似最優(yōu)解與最優(yōu)解相差的程度。若問題的輸入規(guī)模為n，存在一個函數(shù)，使得則稱為該近似算法的相對誤差界（RelativeErrorBound）。近似算法的近似比與相對誤差界之間顯然有如下關系：有許多問題的近似算法具有固定的近似比和相對誤差界，即和不隨著問題規(guī)模的變化而變化，在這種情況下，用和來表示近似比和相對誤差界。還有許多問題的近似算法沒有固定的近似比，即近似比隨著問題規(guī)模的增長而增長，換言之，問題規(guī)模越大，近似算法求出的近似最優(yōu)解與最優(yōu)解相差得就越多。對有些難解問題，可以找到這樣的近似算法，其近似比可以通過增加計算量來改進，也就是說，在計算量和解的精確度之間有一個折衷，較少的計算量得到較粗糙的近似解，而較多的計算量可以得到較精確的近似解。圖問題中的近似解：2.1頂點覆蓋問題：無向圖G=(V,E)的頂點覆蓋是頂點集V的一個子集V'V，使得若(u,v)是G的一條邊，則v∈V'或u∈V'。頂點覆蓋V'的大小是它所包含的頂點個數(shù)|V'|。頂點覆蓋問題是求出圖G中的最小頂點覆蓋，即含有頂點數(shù)最少的頂點覆蓋。頂點覆蓋問題是一個NP難問題，因此，沒有一個多項式時間算法有效地求解。雖然要找到圖G的一個最小頂點覆蓋是很困難的，但要找到圖G的一個近似最小覆蓋卻很容易?？梢圆捎萌缦虏呗裕撼跏紩r邊集E'={}，頂點集V'={}，每次從邊集E'中任取一條邊(u,v)，把頂點u和v加入到頂點集V'中，再把與u和v頂點相鄰接的所有邊從邊集E'中刪除，直到邊集E'為空。顯然，最后得到的頂點集V'是無向圖的一個頂點覆蓋，由于每次把盡量多的相鄰邊從邊集E'中刪除，可以期望V'中的頂點數(shù)盡量少，但不能保證V'中的頂點數(shù)最少。圖11.1中給出了一個頂點覆蓋問題的近似算法求解過程。aabcedfgabcedfgabcedfgabcedfgabcedfgabcedfg(a)一個無向圖(b)V'={a,b}(c)V'={a,b,c,f}

刪除與a或b相關聯(lián)的邊刪除與c或f相關聯(lián)的邊(d)V'={a,b,c,f,d,e}(e)近似最小頂點覆蓋(f)最小頂點覆蓋

刪除與d或e相關聯(lián)的邊V'={a,b,c,f,d,e}V'={a,b,c,e}

圖2.1最小覆蓋問題的近似算法求解過程假設無向圖G中n個頂點的編號為0～n-1，頂點覆蓋問題的近似算法如下：算法2.1——頂點覆蓋問題1．for(i=0;i<n;i++)//頂點覆蓋初始化為空x[i]=0;2．E'=E；3．循環(huán)直到E'為空3.1從E'中任取一條邊(u,v)；3.2x[u]=1;x[v]=1;//將頂點u和v加入頂點覆蓋中3.3從E'中刪去與u和v相關聯(lián)的所有邊；算法2.1可以用鄰接表的形式存儲無向圖，由于算法中對每條邊只進行一次刪除操作，設圖G含有個頂點條邊，則算法2.1的時間復雜性為O(+)。下面考察算法2.1的近似比。若用A表示算法在步驟3.1中選取的邊的集合，則A中任何兩條邊沒有公共頂點。因為算法選取了一條邊，并在將其頂點加入頂點覆蓋后，就將E'中與該邊的兩個頂點相關聯(lián)的所有邊從E'中刪除，因此，下一次再選取的邊就與該邊沒有公共頂點。由數(shù)學歸納法易知，A中的所有邊均沒有公共頂點。算法結束時，頂點覆蓋中的頂點數(shù)|V'|=2|A|。另一方面，圖G的任一頂點覆蓋一定包含A中各邊的至少一個端點，因此，若最小頂點覆蓋為V*，則|V*|≥|A|。由此可得，|V'|≤2|V*|，即算法2.1的近似比為2。2.2TSP問題TSP問題是指旅行家要旅行n個城市，要求各個城市經歷且僅經歷一次然后回到出發(fā)城市，并要求所走的路程最短。如果無向圖G=(V,E)的頂點在一個平面上，邊(i,j)∈E的代價c(i,j)均為非負整數(shù)，且兩個頂點之間的距離為歐幾里德距離（EuclideanDistance），則對圖G的任意3個頂點i,j,k∈V，顯然滿足如下三角不等式：c(i,j)+c(j,k)≥c(i,k)事實上，很多以TSP問題為背景的應用問題，如交通、航線、機械加工等應用問題，頂點之間的代價都滿足三角不等式?？梢宰C明，滿足三角不等式的TSP問題仍為NP難問題，但是，可以設計一個近似算法，其近似比為2。圖2.2(a)給出了一個滿足三角不等式的無向圖，圖中方格的邊長為1。求解TSP問題的近似算法首先采用Prim算法生成圖的最小生成樹T，如圖(b)所示，圖中粗線表示最小生成樹中的邊，然后對T進行深度優(yōu)先遍歷，經過的路線為a→b→c→b→h→b→a→d→e→f→e→g→e→d→a，得到遍歷序列L=(a,b,c,h,d,e,f,g)，由序列L得到哈密頓回路，即近似最優(yōu)解，如圖(d)所示，其路徑長度約為19.074，圖(e)所示是(a)的最優(yōu)解，其路徑長度約為16.084。22adbchfegadbchfegadbchfeg1345678adbchfegadbchfeg(a)圖G的頂點(b)生成最小生成樹T(c)對T進行深度優(yōu)先遍歷(d)由遍歷序列產生哈密頓回路(e)TSP問題的最優(yōu)解

圖2.2TSP問題的近似算法求解示例算法2.2——滿足三角不等式的TSP問題1．在圖中任選一個頂點v；2．采用Prim算法生成以頂點v為根結點的最小生成樹T；3．對生成樹T從頂點v出發(fā)進行深度優(yōu)先遍歷，得到遍歷序列L；4．根據(jù)L得到圖G的哈密頓回路；算法2.2的時間主要耗費在采用Prim算法構造最小生成樹，因此，其時間復雜性為O()。下面考察算法2.2的近似比。設滿足三角不等式的無向圖G的最短哈密頓回路為H*，W(H*)是H*的代價之和；T是由Prim算法求得的最小生成樹，W(T)是T的代價之和；H是由算法2.2得到的近似解，也是圖G的一個哈密頓回路，W(H)是H的代價之和。因為圖G的任意一個哈密頓回路刪去一條邊，構成圖G的一個生成樹，所以，有W(T)≤W(H*)設算法2.2中深度優(yōu)先遍歷生成樹T得到的路線為R，則R中對于T的每條邊都經過兩次，所以，有：W(R)=2W(T)算法2.2得到的近似解H是R刪除了若干中間點（不是第一次出現(xiàn)的頂點）得到的，每刪除一個頂點恰好是用三角形的一條邊取代另外兩條邊。例如，在圖2.2中，遍歷生成樹的路線為a→b→c→b→h→b→a→d→e→f→e→g→e→d→a，刪除第2次出現(xiàn)的頂點b，相當于用邊(c,h)取代另外兩條邊(c,b)和(b,h)。由三角不等式可知，這種取代不會增加總代價，所以，有W(H)≤W(R)從而W(H)≤2W(H*)由此，算法2.2的近似比為2。2.3裝箱問題設有n個物品和若干個容量為C的箱子，n個物品的體積分別為{,,…,}，且有≤C（1≤≤n），把所有物品分別裝入箱子，求占用箱子數(shù)最少的裝箱方案。最優(yōu)裝箱方案可以通過把n個物品劃分為若干子集，每個子集的體積和小于C，然后取子集個數(shù)最少的劃分方案。但是，這種劃分可能的方案數(shù)有種，在多項式時間內不能夠保證找到最優(yōu)裝箱方案。大多數(shù)裝箱問題的近似算法采用貪心策略，即在每個物品裝箱時規(guī)定一種局部選擇方法。下面介紹4種不同的求解裝箱問題的近似算法。2.3.1首次適宜法（FirstFit）首次適宜法首先將所有的箱子初始化為空，然后依次取每一個物品，將該物品裝入第一個能容納它的箱子中。例如，有10個物品，其體積分別為S＝(4,2,7,3,5,4,2,3,6,2)，若干個容量為10的箱子，采用首次適宜法得到的裝箱結果如圖2.3所示。0.3(s4)

0.3(s4)

0.2（s2）

0.4(s1)0.2(s7)

0.7(s3)0.4(s6)

0.5(s5)

0.6(s9)

0.3(s8)

0.2(s10)(a)箱子1(b)箱子2(c)箱子3(d)箱子4(e)箱子5

圖2.3首次適宜法求解裝箱問題示例（陰影表示閑置部分）首次適宜法求解裝箱問題的算法如下：算法2.3——首次適宜法intFirstFit(intn,intC,ints[],intb[]){//假設物品體積均為整數(shù)，b[j]為第j個箱子已裝入物品的體積，數(shù)組下標均從1開始k=0;for(j=1;j<=n;j++)//初始化b[j]=0;for(i=1;i<=n;i++)//裝入第i個物品{j=1;while(C-b[j]<s[i])//查找第1個能容納物品i的箱子j++;b[j]=b[j]+s[i];k=max(j,k);//已裝入物品的箱子個數(shù)}returnk;}算法FirstFit的基本語句是查找第1個能容納物品的箱子，其時間復雜性為O()。下面考察算法2.3的近似比。不失一般性，假設箱子的容量C為一個單位的體積，為第個箱子已裝入物品的體積，由首次適宜裝箱策略，有+>1。設裝箱問題的近似解為k，則若k為偶數(shù)，則++…+>k/2若k為奇數(shù)，則++…+>(k-1)/2將兩式相加，得：設裝箱問題的最優(yōu)解為m，則在最優(yōu)化裝入時，所有箱子恰好裝入全部物品，即:所以，有：即：由此，算法FirstFit的近似比小于2。2.3.2最適宜法最適宜法的物品裝入過程與首次適宜法類似，不同的是，總是把物品裝到能夠容納它并且目前最滿的箱子中，使得該箱子裝入物品后閑置空間最小。例如，有10個物品，其體積分別為S＝(4,2,7,3,5,4,2,3,6,2)，若干個容量為10的箱子，采用最適宜法得到的裝箱結果如圖2.4所示。0.4(s6)

0.2(s2)

0.4(s1)0.4(s6)

0.2(s2)

0.4(s1)0.3(s4)

0.7(s3)0.3(s8)

0.2(s7)

0.5(s5)0.2(s10)

0.6(s9)(a)箱子1(b)箱子2(c)箱子3(d)箱子4

圖2.4最適宜法求解裝箱問題示例（陰影表示閑置部分）算法2.4——最適宜法intBestFit(intn,intC,ints[],intb[]){//假設物品體積均為整數(shù)，b[j]為第j個箱子已裝入物品的體積，數(shù)組下標均從1開始k=0;for(j=1;j<=n;j++)//初始化b[j]=0;for(i=1;i<=n;i++)//裝入第i個物品{min=C;m=k+1;for(j=1;j<=k;j++)//查找能夠容納物品i并且目前最滿的編號最小的箱子{temp=C-b[j]-s[i];//求箱子j裝入物品i后的剩余容量if(temp>0&&temp<min){min=temp;m=j;b[m]=b[m]+s[i];}}k=max(m,k);//已裝入物品的箱子個數(shù)}returnk;}2.3.3首次適宜降序法首次適宜降序法首先將物品按體積從大到小排序，然后用首次適宜法裝箱。例如，有10個物品，其體積分別為S＝(4,2,7,3,5,4,2,3,6,2)，若干個容量為10的箱子，采用首次適宜降序法得到的裝箱結果如圖2.5所示。0.3(s4)

0.7(s3)0.3(s4)

0.7(s3)0.4(s6)

0.5(s5)0.2(s10)

0.2(s7)

0.2(s2)

0.3(s8)(a)箱子1(b)箱子2(c)箱子3(d)箱子4

圖2.5首次適宜降序法求解裝箱問題示例（陰影表示閑置部分）0.4(s1)

0.6(s9)2.3.4最適宜降序法最適宜降序法將物品按體積從大到小排序，然后用最適宜法裝箱。例如，有10個物品，其體積分別為S＝(4,2,7,3,5,4,2,3,6,2)，若干個容量為10的箱子，采用首次適宜降序法得到的裝箱結果如圖2.6所示。0.3(s4)

0.7(s3)0.3(s4)

0.7(s3)0.4(s6)

0.5(s5)0.2(s10)

0.2(s7)

0.2(s2)

0.3(s8)(a)箱子1(b)箱子2(c)箱子3(d)箱子4

圖2.6首次適宜降序法求解裝箱問題示例（陰影表示閑置部分）0.4(s1)

0.6(s9)2.4子集合問題問題描述：設子集和問題的一個實例為〈S,t〉。其中，S={，，…，}是一個正整數(shù)的集合，t是一個正整數(shù)。子集和問題判定是否存在S的一個子集S1，使得。2.4.1子集合問題的指數(shù)時間算法：intexactSubsetSum(S,t){intn=|S|;L[0]={0};for(inti=1；i<=n；i++){L[i]=mergeLists(L[i-1],L[i-1]+S[i]);刪去L[i]中超過t的元素；}returnmax(L[n]);}算法以集合S={，，…，}和目標值t作為輸入。算法中用到將2個有序表L1和L2合并成為一個新的有序表的算法mergeLists(L1,L2)。2.4.2子集合問題的完全多項式時間近似格式:基于算法exactSubsetSum，通過對表L[i]作適當?shù)男拚⒁粋€子集和問題的完全多項式時間近似格式在對表L[i]進行修整時，用到一個修整參數(shù)δ，0＜δ＜1。用參數(shù)δ修整一個表L是指從L中刪去盡可能多的元素，使得每一個從L中刪去的元素y，都有一個修整后的表L1中的元素z滿足(1-δ)y≤z≤y?？梢詫看作是被刪去元素y在修整后的新表L1中的代表。舉例：若δ=0.1，且L=〈10,11,12,15,20,21,22,23,24,29〉，則用δ對L進行修整后得到L1=〈10，12，15，20，23，29〉。其中被刪去的數(shù)11由10來代表，21和22由20來代表，24由23來代表。對有序表L修整算法Listtrim(L,δ){intm=|L|；L1=〈L[1]〉；intlast=L[1]；for(inti=2；i<=m；i++){if(last<(1-δ)*L[i]){將L[i]加入表L1的尾部；last=L[i]；}returnL1；}子集和問題近似格式intapproxSubsetSum(S,t,ε){n=|S|；L[0]=〈0〉；for(inti=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的元素；}returnmax(L[n])；}網格算法2.1定義網格計算即分布式計算

什么是分布式計算？所謂分布式計算是一門計算機科學，它研究如何把一個需要非常巨大的計算能力才能解決的問題分成許多小的部分，然后把這些部分分配給許多計算機進行處理，最后把這些計算結果綜合起來得到最終的結果。最近的分布式計算項目已經被用于使用世界各地成千上萬位志愿者的計算機的閑置計算能力，通過因特網，您可以分析來自外太空的電訊號，尋找隱蔽的黑洞，并探索可能存在的外星智慧生命；您可以尋找超過1000萬位數(shù)字的梅森質數(shù)；您也可以尋找并發(fā)現(xiàn)對抗艾滋病病毒的更為有效的藥物。這些項目都很龐大，需要驚人的計算量，僅僅由單個的電腦或是個人在一個能讓人接受的時間內計算完成是決不可能的。

分布式計算是利用互聯(lián)網上的計算機的CPU的閑置處理能力來解決大型計算問題的一種計算科學。

隨著計算機的普及，個人電腦開始進入千家萬戶。與之伴隨產生的是電腦的利用問題。越來越多的電腦處于閑置狀態(tài)，即使在開機狀態(tài)下CPU的潛力也遠遠不能被完全利用。我們可以想象，一臺家用的計算機將大多數(shù)的時間花費在“等待”上面。即便是使用者實際使用他們的計算機時,處理器依然是寂靜的消費，依然是不計其數(shù)的等待（等待輸入，但實際上并沒有做什么）?；ヂ?lián)網的出現(xiàn),使得連接調用所有這些擁有限制計算資源的計算機系統(tǒng)成為了現(xiàn)實。

那么，一些本身非常復雜的但是卻很適合于劃分為大量的更小的計算片斷的問題被提出來，然后由某個研究機構通過大量艱辛的工作開發(fā)出計算用服務端和客戶端。服務端負責將計算問題分成許多小的計算部分，然后把這些部分分配給許多聯(lián)網參與計算的計算機進行并行處理，最后將這些計算結果綜合起來得到最終的結果。

當然，這看起來也似乎很原始、很困難，但是隨著參與者和參與計算的計算機的數(shù)量的不斷增加,計算計劃變得非常迅速，而且被實踐證明是的確可行的。目前一些較大的分布式計算項目的處理能力已經可以達到甚而超過目前世界上速度最快的巨型計算機。您也可以選擇參加某些項目以捐贈的CPU內核處理時間,您將發(fā)現(xiàn)您所提供的CPU內核處理時間將出現(xiàn)在項目的貢獻統(tǒng)計中。您可以和其他的參與者競爭貢獻時間的排名，您也可以加入一個已經存在的計算團體或者自己組建一個計算小組。這種方法很利于調動參與者的熱情。

隨著民間的組隊逐漸增多,許多大型組織(例如公司、學校和各種各樣的網站)也開始了組建自己的戰(zhàn)隊。同時，也形成了大量的以分布式計算技術和項目討論為主題的社區(qū)，這些社區(qū)多數(shù)是翻譯制作分布式計算項目的使用教程及發(fā)布相關技術性文章，并提供必要的技術支持。那么誰可能加入到這些項目中來呢?當然是任何人都可以!如果您已經加入了某個項目，而且曾經考慮加入計算小組,您將在中國分布式計算總站及論壇里找到您的家。任何人都能加入任何由我站的組建的分布式計算小組。希望您在中國分布式總站及論壇里發(fā)現(xiàn)樂趣。

參與分布式計算——一種能充分發(fā)揮您的個人電腦的利用價值的最有意義的選擇——只需要下載有關程序，然后這個程序會以最低的優(yōu)先度在計算機上運行，這對平時正常使用計算機幾乎沒有影響。2.2專業(yè)定義（中國科學技術信息研究所對分布式計算的定義）

分布式計算是近年提出的一種新的計算方式。所謂分布式計算就是在兩個或多個軟件互相共享信息，這些軟件既可以在同一臺計算機上運行，也可以在通過網絡連接起來的多臺計算機上運行。分布式計算比起其它算法具有以下幾個優(yōu)點：

1、稀有資源可以共享，

2、通過分布式計算可以在多臺計算機上平衡計算負載，

3、可以把程序放在最適合運行它的計算機上，

其中，共享稀有資源和平衡負載是計算機分布式計算的核心思想之一。

實際上，網格計算就是分布式計算的一種。如果我們說某項工作是分布式的，那么，參與這項工作的一定不只是一臺計算機，而是一個計算機網絡，顯然這種“螞蟻搬山”的方式將具有很強的數(shù)據(jù)處理能力。網格計算的實質就是組合與共享資源并確保系統(tǒng)安全。2.3工作原理下面，我們看看它是怎么工作的：

首先,要發(fā)現(xiàn)一個需要非常巨大的計算能力才能解決的問題。這類問題一般是跨學科的、極富挑戰(zhàn)性的、人類急待解決的科研課題。其中較為著名的是:

1.解決較為復雜的數(shù)學問題，例如：GIMPS（尋找最大的梅森素數(shù)）。

2.研究尋找最為安全的密碼系統(tǒng)，例如：RC-72（密碼破解）。

3.生物病理研究，例如：Folding@home（研究蛋白質折疊，誤解，聚合及由此引起的相關疾?。?/p>

4.各種各樣疾病的藥物研究，例如：UnitedDevices（尋找對抗癌癥的有效的藥物）。

5.信號處理，例如：SETI@Home（在家尋找地外文明）。

從這些實際的例子可以看出，這些項目都很龐大，需要驚人的計算量，僅僅由單個的電腦或是個人在一個能讓人接受的時間內計算完成是決不可能的。在以前，這些問題都應該由超級計算機來解決。但是,超級計算機的造價和維護非常的昂貴，這不是一個普通的科研組織所能承受的。隨著科學的發(fā)展，一種廉價的、高效的、維護方便的計算方法應運而生——分布式計算！2.4常見網格算法常見網格算法有多重網格算法，海量數(shù)據(jù)三角網格生成算法，網格聚類算法，代數(shù)多重網格算法等，現(xiàn)僅對代數(shù)多重網格算法加以描述。2.4.1代數(shù)多重網格算法：1.基本思想Gauss-Seidel算法的特點是,最初幾步收斂的很快,但是很快就開始停滯不前.到最后幾乎不收斂.從數(shù)值試驗的圖像可以看出,Gauss-Seidel迭代當插值點少的時候,收斂速度極快,但當插值點多的時候,由于上述效應收斂速度極慢.因此,代數(shù)多重網格(AlgebraicMulti-Grid)算法利用這些特點,將由具體方程離散出來的矩陣,重投到一系列由細到粗的網格上,在每一層網格上只做若干次Gauss-Seidel迭代.與傳統(tǒng)的多重網格算法不同,該算法不需要提供任何網格的信息.所有的信息完全只來自方程離散后的矩陣.假設Possion方程(1)用某種離散方法(比如,有限元或有限差分),在某個相當細的網格上,最后產生線性問題(2)現(xiàn)在考慮如何將其投影到一個較粗的網格上.假設,=1,···,N為細網格上的一組分片一次線性有限元基函數(shù).則矩陣A是一個N×N的矩陣,且元素可以看作是對應基函數(shù)的一個雙線性運算.我們如果要將A重新投影到一個對應基函數(shù)為,=1,···,M,M<<N的粗網格上,則根據(jù)用表出的關系,我們可以得到(3)這里P是一個M×N的矩陣.相應的,如果令(4)則(5)就可以看作是(2)投影到粗網格上以后的問題.代數(shù)多重網格的做法,就是對第步的線性問題(6)先用Gauss-Seidel迭代進行幾步迭代,得到一個近似解,然后將殘問題(7)用投影矩陣Pk重投到粗一層的網格上得到第k+1步的問題(8)如此不斷迭代和重投,直到得到一個規(guī)模相當小的線性問題后,可以用直接法(Gauss消去法)求得精確解,然后用記錄下的一系列Pk矩陣,還原出原問題的解.在還原的時候,仍然使用Gauss-Seidel迭代在每一層來改進數(shù)值解.如此整個過程為一步AMG迭代.2.算法步驟現(xiàn)在給出嚴格的算法步驟.對過程，第一步如果的階數(shù)小于一個給定的整數(shù),比如20,則用Gauss消去法解出并并返回;否則,對問題(6)做3至5步Gauss-Seidel迭代；第二步產生問題(8),令=0;第三步遞歸調用；第四步；第五步做3至5步Gauss-Seidel迭代,返回.所以對問題(2),執(zhí)行AMG(A,x,b)完成一次AMG迭代(迭代更新了x).而整個求解過程為DoAMG(A,x,b)while(|b-Ax|<e).這里e為控制誤差.現(xiàn)在整個算法過程,還剩下的問題就是如何產生P.假設(2)是在網格點x=,=1,···,N上離散的,那么我們首先要確定一個粗網格,也就是說,要考慮在x移除一些點,保留一些點.我們將保留的點稱為核心點(corepoints)。核心點的選取,應該滿足如下兩點:1.不能太多:核心點彼此之間,不能相鄰；2.不能太少:所有被移除的點,必須至少與一個核心點相鄰.根據(jù)這個原則,和稀疏矩陣存儲規(guī)則,我們設計算法如下：第一步產生一維數(shù)組c[1:N],并置所有元素初值為零；第二步選出核心點:fori=1:N,如果c[i]==0,則為核心點,同時將所有滿足=0的c[j]+1;第三步假設為第k個選出的核心點,則P的第k行元素為:0如果==0,1如果0.注意該算法仍然只用了矩陣的信息而沒有使用網格的信息.算法分析該算法實際上的迭代過程完全基于Gauss-Seidel迭代.所以其收斂的要求和Gauss-Seidel一樣，為矩陣對稱正定。但是要達到加速收斂的效果,要求矩陣必須有網格和方程的背景,否則這樣做是沒有意義的。PRAM算法1.PRAM概述隨著并行處理硬件性能的迅速提高，人們對并行算法的興趣也日益增加。所謂并行算法是指一次可執(zhí)行多個操作的算法。對并行算法的研究現(xiàn)在已發(fā)展為一個獨立的研究領域。很多用串行算法解決的問題也已經有了相應的并行算法。在本文中，我們將闡述一些簡單的并行算法以說明一些基本概念和技術。這里介紹的并行算法將用一種流行的理論模型即并行隨機存取計算機(PRAM)來描述。很多關于數(shù)組、表、樹和圖的并行算法都可以很容易地用PRAM模型來描述。如果一個PRAM算法在性能上超過另一個PRAM算法，則當兩個算法在一臺實際的并行計算機上運行時其相對性能不會有很大變化。PRAM模型圖1說明了PRAM的基本結構。其中有n個普通的串行處理器,,...,共享一個全局存儲器。所有處理器都可以“并行地”(同時)從全局存儲器讀出信息或向全局存儲器寫入信息。各處理器也可以并行地執(zhí)行各種算術和邏輯操作。圖lPRAM的基本構造在PRAM模型中關于算法性能的最關鍵的一點是：假設運行時間可以用算法執(zhí)行的并行的存儲器存取次數(shù)來衡量。這一假設是對普通的RAM模型的直接推廣，并且用存儲器存取次數(shù)來衡量運行時間對PRAM模型也是很適合的。這一簡單的假設對于我們研究并行算法有很大幫助，不過真正的并行計算機并不能做到在單位時間內對全局存儲器并行地執(zhí)行存取操作：對存儲器進行存取操作所需的時間隨著并行計算機中處理器數(shù)目的增加而相應增加。然而，對于以任意方式對數(shù)據(jù)進行存取的并行計算機來說，可以證明存取操作為單位時間的假設是成立的。實際中的并行計算機都包含一個通訊網絡以便支持一個抽象的全局存儲器。與算術操作等其他操作相比，通過網絡存取數(shù)據(jù)是相當慢的。因此，計算出兩種并行算法所執(zhí)行的并行的