《20世纪最好的算法.doc》由会员分享，可在线阅读，更多相关《20世纪最好的算法.doc（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、20世纪最好的算法20世纪最好的算法，计算机时代的挑选标准是对科学和工程的研究和实践影响最大。本文按年代次序排列的20世纪最好的10个算法。一、算法一词的来源Algos是希腊字，意思是“疼”，A1gor是拉丁字，意思是“冷却”。这两个字都不是Algorithm(算法)一词的词根，a1gorithm一词却与9世纪的阿拉伯学者al-Khwarizmi有关，他写的书al-jabr wal muqabalah(代数学)演变成为现在中学的代数教科书。Ad-Khwarizmi强调求解问题的有条理的步骤。如果他能活到今天的话，他一定会被以他的名字而得名的方法的进展所感动。二、20世纪10最好的算法20世纪最
2、好的算法，计算机时代的挑选标准是对科学和工程的研究和实践影响最大。下面就是按年代次序排列的20世纪最好的10个算法。1. Monte Carlo方法1946年，在洛斯阿拉莫斯科学实验室工作的John von Neumann，Stan Ulam和Nick Metropolis编制了Metropolis算法，也称为Monte Carlo方法。Metropolis算法旨在通过模仿随机过程，来得到具有难以控制的大量的自由度的数值问题和具有阶乘规模的组合问题的近似解法。数字计算机是确定性问题的计算的强有力工具，但是对于随机性（不确定性）问题如何当时并不知晓，Metropolis算法可以说是最早的用来生成
3、随机数，解决不确定性问题的算法之一。2. 线性规划的单纯形方法1947年，兰德公司的Grorge Dantzig创造了线性规划的单纯形方法。就其广泛的应用而言，Dantzig算法一直是最成功的算法之一。线性规划对于那些要想在经济上站住脚，同时又有赖于是否具有在预算和其他约束条件下达到最优化的能力的工业界，有着决定性的影响(当然，工业中的“实际”问题往往是非线性的；使用线性规划有时候是由于估计的预算，从而简化了模型而促成的)。单纯形法是一种能达到最优解的精细的方法。尽管理论上讲其效果是指数衰减的，但在实践中该算法是高度有效的它本身说明了有关计算的本质的一些有趣的事情。3. Krylov子空间叠代
4、法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子空间由作用在初始“余量
5、”向量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. 矩阵计
6、算的分解方法1951年，橡树岭国家实验室的A1ston Householder系统阐述了矩阵计算的分解方法。研究证明能把矩阵因子分解为三角、对角、正交和其他特殊形式的矩阵是极其有用的。这种分解方法使软件研究人员能生产出灵活有效的矩阵软件包。这也促进了数值线性代数中反复出现的大问题之一的舍入误差分析问题。 (1961年伦敦国家物理实验室的James Wilkinson基于把矩阵分解为下和上三角矩阵因子的积的LU分解，在美国计算机协会(ACM)的杂志上发表了一篇题为“矩阵逆的直接方法的误差分析 ”的重要文章。)5. Fortran最优编译程序1957年，John Backus在IBM领导一个小组研
7、制Fortran最优编译程序。Fortran的创造可能是计算机编程历史上独一无二的最重要的事件：科学家(和其他人)终于可以无需依靠像地狱那样可怕的机器代码，就可告诉计算机他们想要做什么。虽然现代编译程序的标准并不过分 Fortran I只包含23，500条汇编语言指令早期的编译程序仍然能完成令人吃惊的复杂计算。就像Backus本人在1998年在IEEE annals of the History of computing 发表的有关Fortran I，II, III的近代历史的文章中回忆道：编译程序“所产生的如此有效的代码，使得其输出令研究它的编程人员都感到吓了一跳。”6. 矩阵本征值计算的Q
8、R算法195961年，伦敦Ferranti Ltd.的J.G. F. Francis找到了一种称为QR算法的计算本征值的稳定的方法。本征值大概是和矩阵相连在起的最重要的数了，而且计算它们可能是最需要技巧的。把个方阵变换为一个“几乎是”上三角的矩阵意即在紧挨着矩阵主对角线下面的一斜列上可能有非零元素是相对容易的，但要想不产生大量的误差就把这些非零元素消去，就不是平凡的事了。QR 算法正好是能达到这一目的的方法，基于QR 分解， A可以写成正交矩阵Q 和一个三角矩阵R 的乘积，这种方法叠代地把 A=Q(k)R(k) 变成 A(k+1)=Q(k)R(k) 就加速收敛到上三角矩阵而言多少有点不能指望。
9、20世纪60年代中期QR 算法把一度难以对付的本征值问题变成了例行程序的计算。7. 快速分类法1962：伦敦Elliott Brothers, Ltd.的Tony Hoare提出了快速(按大小)分类法.把n个事物按数或字母的次序排列起来，在心智上是不会有什么触动的单调平凡的事。智力的挑战在于发明一种快速完成排序的方法。Hoare的算法利用了古老的分割开和控制的递归策略来解决问题：挑一个元素作为“主元”、把其余的元素分成“大的”和“小的”两堆(当和主元比较时)、再在每一堆中重复这一过程。尽管可能要做受到严厉责备的做完全部N(N-1)/2 次的比较(特别是，如果你把主元作为早已按大小分类好的表列的
10、第一个元素的话！)，快速分类法运行的平均次数具有O(Nlog(N) 的有效性，其优美的简洁性使之成为计算复杂性的著名的例子。8. 快速Fourier变换1965年，IBM的T. J. Watson研究中心的James Cooley以及普林斯顿大学和ATT贝尔实验室的John Tukey向公众透露了快速Fourier变换(方法)(FFT)。应用数学中意义最深远的算法，无疑是使信号处理实现突破性进展的FFT。其基本思想要追溯到Gauss(他需要计算小行星的轨道)，但是CooleyTukey的论文弄清楚了 Fourier变换计算起来有多容易。就像快速分类法一样，FFT有赖于用分割开和控制的策略，把表
11、面上令人讨厌的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
12、)/x(2) 的连分数展开中的各项。如果x(1)/x(2) 是有理数，展开会终止，在适当展开后就给出了“最小的”整数a(1)和a(2) 。欧几里得算法不终止或者如果你只是简单地由于厌倦计算那么展开的过程至少提供了最小整数关系的大小的下界。Ferguson和Forcade的推广更有威力，尽管这种推广更难于执行(和理解)。例如，他们的侦查算法被用来求得逻辑斯谛(logistic)映射的第三和第四个分歧点，b(3)=3. 和 b(4)=3.所满足的多项式的精确系数。(后者是120 阶的多项式；它的最大的系数是25730 。)已证明该算法在简化量子场论中的Feynman图的计算中是有用的。10. 快速
13、多极算法1987年，耶鲁大学的Leslie Greengard 和Vladimir Rokhlin发明了快速多极算法。该算法克服了N体模拟中最令人头疼的困难之一：经由引力或静电力相互作用的N个粒子运动的精确计算(想象一下银河系中的星体，或者蛋白质中的原于)看来需要O(N*N) 的计算量比较每一对质点需要一次计算。该算法利用多极展开(净电荷或质量、偶极矩、四矩，等等)来近似遥远的一组质点对当地一组质点的影响。空间的层次分解用来确定当距离增大时，比以往任何时候都更大的质点组。快速多极算法的一个明显优点是具有严格的误差估计，这是许多算法所缺少的性质。处理量子多体理论的数值方法量子蒙卡方法大纲量子蒙卡
14、的基本思路首先由Suzuki在1976年提出，基本思路就是把d维量子格点系统投影成一个d+1维的经典系统，其中多出的1维来自于系统温度有关的虚时，从而可以按照经典蒙卡的思路进行计算。正如量子力学有三个表象：Schroding表象，Heisengber表象和相互作用表象一样，量子蒙卡也可以在不同的表象下进行计算，随系统的不同，需要选取适当的表象来加快或改进算法。主要表象(Representation)有：世界线（World Line）表象，随机级数展开（Stochastic Series Expansion,SSE）表象等，其中时间轴可以有两种取法，离散化的时间轴与连续的时间轴。确定了量子蒙卡的
15、表象，仅仅是蒙卡理论的一个出发点，重要的是如何实现蒙特卡罗步，即如何Update?经典蒙卡中常用的Metropolis算法，由于它是一种Local Update,在研究二级相变问题或者一级相变亚稳态的隧穿问题时会带来临界慢化(Critical Slwoing Dwon)等一系列严重问题而需要改进，主要方法有：1993年H. G. Evertz提出的回路算法(Loop Algorithms),它是经典集团算法对量子系统的一个推广；1996年提出的连续时间Loop 算法改进了需要外推才能消除离散时间的误差；1998年蠕虫(Worm)算法、回路算符(Loop-operator)算法以及有向回路(Di
16、rected Loop)算法进一步去掉了回路算法只能处理满足粒子空穴对称系统的限制；2003年Flat Histogram方法解决了一级相变时亚稳态实现高效的隧穿。用Monte-Carlo方法研究二维Ising模型的相变问题#include #include #include #include #define L 150#define preN#define lateN #define deltaN (lateN-preN)double recordEnergydeltaN;int recordMagnetdeltaN;int latticeLL;int tempLL;double energ
17、y;int magnet;double T;struct CXdouble C;double X;void InitialLattice();void SaveInitial();void GetInitial();void CaculateFirstMagnet();void CaculateFirstEnergy();void GenerateNext();struct CX Caculate_C_and_X();int main()int i;struct CX cx200;FILE *ft,*fx,*fc;ft=fopen(T.txt,w);fx=fopen(X.txt,w);fc=f
18、open(C.txt,w);srand(time(NULL);T = 1.0;for(i=0;T4.0;i+)InitialLattice();cx=Caculate_C_and_X();fprintf(ft,%fn,T);fprintf(fx,%fn,cx.X);fprintf(fc,%fn,cx.C);printf(T=%f ,T);printf(X=%f ,cx.X);printf(C=%fn,cx.C);T = T+0.05;fclose(ft);fclose(fx);fclose(fc);return 0;void InitialLattice()int i,j;for(i=0;iL
19、;i+)for(j=0;j5) latticej=1;elselatticej=1;void SaveInitial()int k,m;for(k=0;kL;k+)for(m=0;mL;m+)tempkm=latticekm;void GetInitial()int k,m;for(k=0;kL;k+)for(m=0;mL;m+)latticekm=tempkm;void CaculateFirstMagnet()int i,j;int iMagnet=0;for(i=0;iL;i+)for(j=0;jL;j+)iMagnet += latticej;magnet = iMagnet;void
20、 CaculateFirstEnergy()double dEnergy = 0.0;int up,down,right,left,px,py;for(px=0;pxL;px+)for(py=0;py0 )if(rand()*1.0/RAND_MAX) = exp(-1.0)*dE/T)latticepxpy = -latticepxpy;magnet += 2*latticepxpy;energy += dE;elselatticepxpy = -latticepxpy;magnet += 2*latticepxpy;energy += dE;struct CX Caculate_C_and
21、_X()struct CX cx;int i;double AvgEnergy=0.0;double AvgSquareEnergy=0.0;double AvgMagnet=0.0;double AvgSquareMagnet=0.0;CaculateFirstMagnet();CaculateFirstEnergy();for(i=0; i=preN)recordEnergyi-preN = energy;recordMagneti-preN = magnet;for(i=0;ideltaN;i+)AvgEnergy += (double)recordEnergy/deltaN;AvgSquareEnergy += (double)recordEnergy*recordEnergy/deltaN;AvgMagnet += (double)recordMagnet/deltaN;AvgSquareMagnet += (double)recordMagnet*recordMagnet/deltaN;cx.C = (AvgSquareEnergy - AvgEnergy*AvgEnergy)/T/T;cx.X = (AvgSquareMagnet - AvgMagnet*AvgMagnet)/T;return cx;C-T曲线：C-X曲线：