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