世紀(jì)十大算法

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