20世紀最好的10個算法
三鏡先生
一、算法一詞的來源
Algos是希臘字，意思是“疼”，A1gor是拉丁字，意思是“冷卻”。這兩個字都不是A1gorithm(算法)一詞的詞根，a1gorithm一詞卻與9世紀的阿拉伯學者al-Khwarizmi有關，他寫的書《al-jabr w’al muqabalah》(代數學)演變成為現在中學的代數教科書。Ad-Khwarizmi強調求解問題的有條理的步驟。如果他能活到今天的話，他一定會被以他的名字而得名的方法的進展所感動。
二、20世紀10最好的算法
20世紀最好的算法，計算機時代的挑選標準是對科學和工程的研究和實踐影響最大。下面就是按年代次序排列的20世紀最好的10個算法。
1.? Monte Carlo方法
???1946年，在洛斯阿拉莫斯科學實驗室工作的John von Neumann，Stan Ulam和Nick Metropolis編制了Metropolis算法，也稱為Monte Carlo方法。Metropolis算法旨在通過模仿隨機過程，來得到具有難以控制的大量的自由度的數值問題和具有階乘規模的組合問題的近似解法。數字計算機是確定性問題的計算的強有力
工具，但是對于隨機性（不確定性）問題如何當時并不知曉，Metropolis算法可以說是最早的用來生成隨機數，解決不確定性問題的算法之一。
2.? 線性規劃的單純形方法
??? 1947年，蘭德公司的Grorge Dantzig創造了線性規劃的單純形方法。就其廣泛的應用而言，Dantzig算法一直是最成功的算法之一。線性規劃對于那些要想在經濟上站住腳，同時又有賴于是否具有在預算和其他約束條件下達到最優化的能力的工業界，有著決定性的影響(當然，工業中的“實際”問題往往是非線性的；使用線性規劃有時候是由于估計的預算，從而簡化了模型而促成的)。單純形法是一種能達到最優解的精細的方法。盡管理論上講其效果是指數衰減的，但在實踐中該算法是高度有效的——它本身說明了有關計算的本質的一些有趣的事情。
3.? Krylov子空間疊代法
1950年，來自美國國家標準局的數值分析研究所的Magnus Hestenes, Eduard Stiefel和Cornelius Lanczos開創了Krylov子空間疊代法的研制。這些算法處理看似簡單的求解形為???
Ax=b
的方程的問題。當然隱藏的困難在于A是一個巨型的n*n 矩陣，致使代數解??
x=b/A
是不容易計算的(確實，矩陣的“相除”不是一個實際上有用的概念)。疊代法——諸如求解形為
Kx(k+1)=Kx(k)+b-Ax(k)
的方程，其中K 是一個理想地“接近”A 的較為簡單的矩陣——導致了Krylov子空間的研究。以俄羅斯數學家Nikolai Krylov命名的Krylov子空間由作用在初始“余量”向量
????????????????????????????? r(0)=b-Ax(0)
上的矩陣冪張成的。當 A是對稱矩陣時，Lanczos找到了一種生成這種子空間的正交基的極好的方法。對于對稱正定的方程組，Hestenes 和Stiefel提出了稱為共軛梯度法的甚至更妙的方法。過去的50年中，許多研究人員改進并擴展了這些算法。當前的一套方法包括非對稱方程組的求解技巧，像字首縮拼詞為GMRES和Bi-CGSTAB那樣的算法。(GMRES和Bi-CGSTAB分別首次出現于1986和1992? SIAM journal on Scientific and Statistical computing(美國工業與應用數學學會的科學和統計計算雜志)。
4.? 矩陣計算的分解方法
???1951年，橡樹嶺國家實驗室的A1ston Householder系統闡述了矩陣計算的分解方法。研究證明能把矩陣因子分解為三角、對角、正交和其他特殊形式的矩陣是極其有用的。這種分解方法使軟件研究人員能生產出靈活有效的矩陣軟件包。這也促進了數值線性代數中反復出現的大問題之一的舍入誤差分析問題。 (1961年倫敦國家物理實驗室的James Wilkinson基于把矩陣分解為下和上三角矩陣因子的積的LU分解，在美國計算機協會(ACM)的雜志上發表了一篇題為“矩陣逆的直接方法的誤差分析”的重要文章。)
5.? Fortran最優編譯程序
??? 1957年，John Backus在IBM領導一個小組研制Fortran最優編譯程序。
Fortran
的創造可能是計算機編程歷史上獨一無二的最重要的事件：科學家(和其他人)終于可以無需依靠像地獄那樣可怕的機器代碼，就可告訴計算機他們想要做什么。雖然現代編譯程序的標準并不過分――Fortran I只包含23，500條匯編語言指令――早期的編譯程序仍然能完成令人吃驚的復雜計算。就像Backus本人在1998年在IEEE annals of the History of computing 發表的有關Fortran I，II, III的近代歷史的文章中回憶道：編譯程序“所產生的如此有效的代碼，使得其輸出令研究它的編程人員都感到嚇了一跳。”
6.? 矩陣本征值計算的QR算法
??? 1959—61年，倫敦Ferranti Ltd.的J.G. F. Francis找到了一種稱為QR算法的計算本征值的穩定的方法。本征值大概是和矩陣相連在—起的最重要的數了，而且計算它們可能是最需要技巧的。把—個方陣變換為一個“幾乎是”上三角的矩陣――意即在緊挨著矩陣主對角線下面的一斜列上可能有非零元素――是相對容易的，但要想不產生大量的誤差就把這些非零元素消去，就不是平凡的事了。QR 算法正好是能達到這一目的的方法，基于QR 分解， A可以寫成
正交矩陣Q 和一個三角矩陣R 的乘積，這種方法疊代地把
?A=Q(k)R(k)
變成A(k+1)==Q(k)R(k) 就加速收斂到上三角矩陣而言多少有點不能指望。20世紀60年代中期QR 算法把一度難以對付的本征值問題變成了例行程序的計算。
7.? 快速分類法
???1962：倫敦Elliott Brothers, Ltd.的Tony Hoare提出了快速(按大小)分類法
.把n個事物按數或字母的次序排列起來，在心智上是不會有什么觸動的單調平凡的事。智力的挑戰在于發明一種快速完成排序的方法。Hoare的算法利用了古老的分割開和控制的遞歸策略來解決問題：挑一個元素作為“主元”、把其余的元素分成“大的”和“小的”兩堆
(
當和主元比較時)、再在每一堆中重復這一過程。盡管可能要做受到嚴厲責備的做完全部N(N-1)/2 次的比較(特別是，如果你把主元作為早已按大小分類好的表列的第一個元素的
話！)，快速分類法運行的平均次數具有O(Nlog(N)) 的有效性，其優美的簡潔性使之成為計算復雜性的著名的例子。
8.? 快速Fourier變換
??? 1965年，IBM的T. J. Watson研究中心的James Cooley以及普林斯頓大學和AT＆T貝爾實驗室的John Tukey向公眾透露了快速Fourier變換(方法)(FFT)。應用數學中意義最深遠的算法，無疑是使信號處理實現突破性進展的FFT。其基本思想要追
溯到Gauss(他需要計算小行星的軌道)，但是Cooley—Tukey的論文弄清楚了Fourier變換計算起來有多容易。就像快速分類法一樣，FFT有賴于用分割開和控制的策略，把表面上令人討厭的O(N*N) 降到令人歡樂的O(Nlog(N)) 。但是不像快速分類法，其執行(初一看)是非直觀的而且不那么直接。其本身就給計算機科學一種推動力去研究計算問題和算法的固有復雜性。
9.? 整數關系偵查算法
??? 1977年，BrighamYoung大學的Helaman Ferguson 和Rodney Forcade提出了整數關系偵查算法。這是一個古老的問題：給定—組實數，例如說x(1),x(2),...,x(n) ，是否存在整數a(1),a(2),..,a(n) （不全為零），使得
???????????????????? a(1)x(1)+a(2)x(2)+...+a(n)x(n)=0
對于n=2 ，歷史悠久的歐幾里得算法能做這項工作、計算x(1)/x(2) 的連分數展開中的各項。如果x(1)/x(2) 是有理數，展開會終止，在適當展開后就給出了“最小的”整數a(1)?和a(2) 。歐幾里得算法不終止——或者如果你只是簡單地由于厭倦計算——那么展開的過程至少提供了最小整數關系的大小的下界。Ferguson和Forcade的推廣更有威力，盡管這種推廣更難于執行(和理解)。例如，他們的偵查算法被用來求得邏輯斯諦(logistic)映射的第三和第四個分歧點，b(3)=3.544090 和 b(4)=3.564407所滿足的多項式的精確系數。(后者是120 階的多項式；它的最大的系數是257^30 。)已證明該算法在簡化量子場論中的Feynman圖的計算中是有用的。
10. 快速多極算法
??? 1987年，耶魯大學的Leslie Greengard 和Vladimir Rokhlin發明了快速多極算法。
該算法克服了N體模擬中最令人頭疼的困難之一：經由引力或靜電力相互作用的N個粒子運動的精確計算(想象一下銀河系中的星體，或者蛋白質中的原于)看來需要O(N*N) 的計算量
——
比較每一對質點需要一次計算。該算法利用多極展開(凈電荷或質量、偶極矩、四矩，等等)來近似遙遠的一組質點對當地一組質點的影響。空間的層次分解用來確定當距離增大時，比以往任何時候都更大的質點組。快速多極算法的一個明顯優點是具有嚴格的誤差估計，這是許多算法所缺少的性質。
三、結束語
???
2l世紀將會帶來什么樣的新的洞察和算法？對于又一個一百年完整的回答顯然是不知道的。然而，有一點似乎是肯定的。正如20世紀能夠產生最好的l0個算法一樣，新世紀對我們來說既不會是很寧靜的，也不會是弱智的。