世紀十大算法

20世紀的十大算法來自：/home.php?mod=space&uid=83029&do=blog&id=468247胡關(guān)虎本世紀初，美國物理學會(AmericanInstituteofPhysics)和IEEE計算機社團(IEEEComputerSociety)的一本聯(lián)合刊物《科學與工程中的計算》發(fā)表了由田納西大學的JackDongarra和橡樹嶺國家實驗室的FrancisSullivan聯(lián)名撰寫的“世紀十大算法”一文，該文“試圖整理出在20世紀對科學和工程領(lǐng)域的發(fā)展產(chǎn)生最大影響力的十大算法”。作者苦于“任何選擇都將是充滿爭議的，因為實在是沒有最好的算法”，他們只好用編年順序依次列出了這十項算法領(lǐng)域人類智慧的巔峰之作——給出了一份沒有排名的算法排行榜。有趣的是，該期雜志還專門邀請了這些算法相關(guān)領(lǐng)域的“大拿”為這十大算法撰寫十篇綜述文章，實在是蔚為壯觀。本文的日的，便是要帶領(lǐng)讀者走馬觀花，一同回顧當年這一算法界的盛舉。1、1946蒙特卡洛方法在廣場上畫一個邊長一米的正方形，在正方形內(nèi)部隨意用粉筆畫一個不規(guī)則的形狀，呃，能幫我算算這個不規(guī)則圖形的面積么？蒙特卡洛(MonteCarlo)方法便是解決這個問題的巧妙方法:隨機向該正方形內(nèi)扔N(N是一個很大的自然數(shù))個黃豆，隨后數(shù)數(shù)有多少個黃豆在這個不規(guī)則幾何形狀內(nèi)部，比如說有M個:那么，這個奇怪形狀的面積便近似于M/N，N越大，算出來的值便越精確。別小看這個數(shù)黃豆的笨辦法，大到國家的民意測驗，小到中子的移動軌跡，從金融市場的風險分析，到軍事演習的沙盤推演，蒙特卡洛方法無處不在背后發(fā)揮著它的神奇威力。蒙特卡洛方法由美國拉斯阿莫斯國家實驗室的三位科學家JohnvonNeumann（看清楚了，這位可是馮諾伊曼同志?。?StanUlam和NickMetropolis共同發(fā)明。就其本質(zhì)而言，蒙特卡洛方法是用類似于物理實驗的近似方法求解問題，它的魔力在于，對于那些規(guī)模極大的問題，求解難度隨著問題的維數(shù)（自變量個數(shù)）的增加呈指數(shù)級別增長，出現(xiàn)所謂的“維數(shù)的災難”（CourseofDimensionality）o對此，傳統(tǒng)方法無能為力，而蒙特卡洛方法卻可以獨辟蹊徑，基于隨機仿真的過程給出近似的結(jié)果。最后八卦一下，MonteCarlo這個名字是怎么來的？它是摩納哥的一座以博彩業(yè)聞名的城市，賭博其實是門概率的高深學問，不是么？2、1947單純形法單純形法是由大名鼎鼎的“預測未來”的蘭德公司的GrorgeDantzig發(fā)明的，它成為線性規(guī)劃學科的重要基石。所謂線性規(guī)劃，簡單的說，就是給定一組線性（所有變量都是一次冪）約束條件（例如a1*x1+b1*x2+c1*x3>0），求一個給定的目標函數(shù)的極值。這么說似乎也太太太抽象了，但在現(xiàn)實中能派上用場的例子可不罕見一一比如對于一個公司而言，其能夠投入生產(chǎn)的人力物力有限（“線性約束條件”），而公司的目標是利潤最大化（“目標函數(shù)取最大值”），看，線性規(guī)劃并不抽象吧！線性規(guī)劃作為運籌學（operationresearch）的一部分，成為管理科學領(lǐng)域的一種重要工具。而Dantzig提出的單純形法便是求解類似線性規(guī)劃問題的一個極其有效的方法，說來慚愧，本科二年級的時候筆者也學過一學期的運籌學，現(xiàn)在腦子里能想起的居然只剩下單純形法了一一不過這不也正說明了該方法的簡單和直觀么？順便說句題外話，寫過《萬歷十五年》的黃仁宇曾說中國的傳統(tǒng)是“不能從數(shù)日字上管理”，我們習慣于“拍腦袋”，而不是基于嚴格的數(shù)據(jù)做決定，也許改變這一傳統(tǒng)的方法之一就是全民動員學習線性規(guī)劃喔。3、1950Krylov子空間迭代法4、1951矩陣計算的分解方法50年代初的這兩個算法都是關(guān)于線性代數(shù)中的矩陣計算的，看到數(shù)學就頭大的讀者恐怕看到算法的名字已經(jīng)開始皺眉毛了。Krylov子空間疊代法是用來求解形如Ax=b的方程，A是一個n*n的矩陣，當n充分大時，直接計算變得非常困難，而Krylov方法則巧妙地將其變?yōu)镵xi+1=Kxi+b-Axi的迭代形式來求解。這里的K（來源于作者俄國人NikolaiKrylov姓氏的首字母）是一個構(gòu)造出來的接近于A的矩陣，而迭代形式的算法的妙處在于，它將復雜問題化簡為階段性的易于計算的子步驟。1951年由橡樹嶺國家實驗室的AlstonHouseholder提出的矩陣計算的分解方法，則證明了任何矩陣都可以分解為三角、對角、正交和其他特殊形式的矩陣，該算法的意義使得開發(fā)靈活的矩陣計算軟件包成為可能。5、1957優(yōu)化的Fortran編譯器說實話，在這份學術(shù)氣息無比濃郁的榜單里突然冒出一個編譯器（Compiler）如此工程化的東東實在讓人有“關(guān)公戰(zhàn)秦瓊”的感覺。不過換個角度想想，F(xiàn)ortran這一門幾乎為科學計算度身定制的編程語言對于科學家（尤其是數(shù)學家，物理學家）們實在是太重要了，簡直是他們形影不離的一把瑞士軍刀，這也難怪他們紛紛搶著要把票投給了它。要知道，F(xiàn)ortran是第一種能將數(shù)學公式轉(zhuǎn)化為計算機程序的高級語言，它的誕生使得科學家們真正開始利用計算機作為計算工具為他們的研究服務(wù)，這是計算機應(yīng)用技術(shù)的一個里程碑級別的貢獻。話說回來，當年這幫開發(fā)Fortran的家伙真是天才只用23500行匯編指令就完成了一個Fortran編譯器，而且其效率之高令人嘆為觀止:當年在IBM主持這一項目的負責人JohnBackus在數(shù)十年后，回首這段往事的時候也感慨，說它生成代碼的效率“出乎了所有開發(fā)者的想象”。看來作為程序員，自己寫的程序跑起來“出乎自己的想象”，有時候還真不一定是件壞事！6、1959-61計算矩陣特征值的QR算法呼，又是一個和線性代數(shù)有關(guān)的算法，學過線性代數(shù)的應(yīng)該還記得“矩陣的特征值”吧？計算特征值是矩陣計算的最核心內(nèi)容之一，傳統(tǒng)的求解方案涉及到高次方程求根，當問題規(guī)模大的時候十分困難。QR算法把矩陣分解成一個正交矩陣(什么是正交矩陣？！還是趕緊去翻書吧！)與一個上三角矩陣的積，和前面提到的Krylov方法類似，這又是一個迭代算法，它把復雜的高次方程求根問題化簡為階段性的易于計算的子步驟，使得用計算機求解大規(guī)模矩陣特征值成為可能。這個算法的作者是來自英國倫敦的J.G.F.Franciso7、1962快速排序算法不少讀者恐怕和我一樣，看到“快速排序算法”(QuickSort)這個條目時,心里的感覺是——“這可總算找到組織了”。相比于其他一些對程序員而言高深莫測的數(shù)學物理公式,快速排序算法真是我們朝夕相處的好伙伴——老板讓你寫個排序算法，如果你寫出來的不是快速排序，你都不好意思跟同事打招呼。其實根本不用自己動手實現(xiàn)，不論是ANSIC,C++STL,還是JavaSDK,天下幾乎所有的SDK里都能找到它的某種實現(xiàn)版本?？焖倥判蛩惴ㄗ钤缬蒚onyHoare爵士設(shè)計，它的基本思想是將待排序列分為兩半，左邊的一半總是“小的”，右邊的一半總是“大的”，這一過程不斷遞歸持續(xù)下去，直到整個序列有序。說起這位TonyHoare爵士，快速排序算法其實只是他不經(jīng)意間的小小發(fā)現(xiàn)而已，他對于計算機貢獻主要包括形式化方法理論，以及ALGOL60編程語言的發(fā)明等，他也因這些成就獲得1980年圖靈獎?？焖倥判虻钠骄鶗r間復雜度僅僅為O(Nlog(N))，相比于普通選擇排序和冒泡排序等而言，實在是歷史性的創(chuàng)舉。8、1965快速傅立葉變換如果要評選對我們的日常生活影響最大的算法，快速傅立葉變換算法應(yīng)該是當仁不讓的總冠軍每天當拿起話筒，打開手機，聽mp3，看DVD，用DC拍照——毫不夸張的說，哪里有數(shù)字信號處理，哪里就有快速傅立葉變換。快速傅立葉算法是離散傅立葉算法(這可是數(shù)字信號處理的基石)的一種快速算法，它有IBM華生研究院的JamesCooley和普林斯頓大學的JohnTukey共同提出，其時間復雜度僅為O(Nlog(N))；比時間效率更為重要的是，快速傅立葉算法非常容易用硬件實現(xiàn)，因此它在電子技術(shù)領(lǐng)域得到極其廣泛的應(yīng)用。9、1977整數(shù)關(guān)系探測算法整數(shù)關(guān)系探測是個古老的問題，其歷史甚至可以追溯到歐幾里德的時代。具體的說：給定一組實數(shù)X1,X2,...,Xn，是否存在不全為零的整數(shù)a1,a2,...an，使得:a1x1+a2x2+...+anxn=0這一年BrighamYoung大學的HelamanFerguson和RodneyForcade解決了這一問題。至于這個算法的意義嘛，呃，該算法應(yīng)用于“簡化量子場論中的Feynman圖的計算”——太深奧的學問拉！10、1987快速多極算法日歷翻到了1987年，這一年的算法似乎更加玄奧了，耶魯大學的LeslieGreengard和VladimirRokhlin提出的快速多極算法用來計算“