AlphaGo是什么鬼？告诉你20世纪的十大算法

1.1946年计算蒙特卡洛过程度伦敦算法；

在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，呃，能帮我算算这个不规则图形的面积么？蒙特卡洛(Monte Carlo)方法便是解决这个问题的巧妙方法:随机向该正方形内扔N（N 是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个:那么，这个奇怪形状的面积便近似于M/N，N越大，算出来的值便越精确。别小看这个数黄豆的笨办法，大到国家的民意测验，小到中子的移动轨迹，从金融市场的风险分析，到军事演习的沙盘推演，蒙特卡洛方法无处不在背后发挥着它的神奇威力。蒙特卡洛方法由美国拉斯阿莫斯国家实验室的三位科学家John von Neumann（看清楚了，这位可是冯诺伊曼同志！）,Stan Ulam 和 Nick Metropolis共同发明。就其本质而言，蒙特卡洛方法是用类似于物理实验的近似方法求解问题，它的魔力在于，对于那些规模极大的问题，求解难度随着问题的维数（自变量个数）的增加呈指数级别增长，出现所谓的“维数的灾难”（Course of Dimensionality）。对此，传统方法无能为力，而蒙特卡洛方法却可以独辟蹊径，基于随机仿真的过程给出近似的结果。

最后八卦一下，Monte Carlo这个名字是怎么来的？它是摩纳哥的一座以博彩业闻名的城市，赌博其实是门概率的高深学问，不是么？

如何简单表达？

每当我们讨论概率时，我们其实都是在对概率密度进行积分。在贝叶斯分析中，我们所用到的很多概率密度都不是能解析表达的：对它们积分你需要付出很大的代价，如果它们真的可积。所以，我们用一种代替的方法，就是大量的仿真这个随机变量，然后从我们仿真出的随机数里得到概率。如果我们想要知道X小于10的概率，我们就计算仿真出的随机数里小于10的比例，用它作为我们的估算结果。这就是“蒙特卡洛”部分，它是一种基于随机数的概率估计方法。当仿真出的随机数足够多的时候，估计的结果就非常好，但是它本质上仍然是随机的。

那又为什么用“马尔科夫”呢？因为在特定的技术条件下，你可以生成一个无记忆的过程（例如，一个马尔科夫过程），这个过程和你想要仿真的随机变量有一样的分布。你可以迭代任意数量的不同的仿真过程，这些仿真过程可以生成相关的随机数（只基于这些数的当前值），并且这个过程保证了一旦你生成足够多的结果，你将能得到一组数，它们看起来就好像你用某种方法成功地从你想要知道的复杂分布中获得了独立的样本一样。

例如，如果我想估计一个标准正态分布的随机变量小于0.5的概率，我可以从标准正态分布中生成10000个独立的样本，然后数出其中小于0.5的样本的数量；假设，我得到6905个样本小于0.5，那么我对P(Z<0.5)的估计就是0.6905，这个估计和真实值相去不远。这就是个蒙特卡洛估计。

现在想像我没办法生成独立的标准正态分布的随机变量，于是我从0开始，每一步加一些-0.5到0.5之间均匀分布的随机数到我的当前值，然后根据一种特殊的检验方法来决定我是不是接受这个新值，如果我不接受，那我就拒绝这个值保留我的旧值。因为我只考虑新值和当前值，所以这是个马尔科夫链。如果我正确地建立了决定是否保留新值的检验方法（可以是随机游走Metropolis-Hastings方法，细节比较复杂），于是尽管我没生成哪怕一个正态随机变量，如果我仿真这个过程足够长时间，我从这个过程得到的数列就将分布得像用某种方法生成的正态随机变量的大量样本一样。这就是对一个标准正态分布随机变量的马尔科夫蒙特卡洛仿真。如果我用这种方法去估计概率，这就是一个马尔科夫蒙特卡洛估计。

2.1947 单纯形法

单纯形法是由大名鼎鼎的“预测未来”的兰德公司的Grorge Dantzig发明的，它成为线性规划学科的重要基石。所谓线性规划，简单的说，就是给定一组线性（所有变量都是一次幂）约束条件（例如a1*x1+ b1*x2+c1*x3>0)，求一个给定的目标函数的极值。这么说似乎也太太太抽象了，但在现实中能派上用场的例子可不罕见——比如对于一个公司而言，其能够投入生产的人力物力有限（“线性约束条件”），而公司的目标是利润最大化（“目标函数取最大值”），看，线性规划并不抽象吧！线性规划作为运筹学(operation research)的一部

分，成为管理科学领域的一种重要工具。而Dantzig提出的单纯形法便是求解类似线性规划

问题的一个极其有效的方法，说来惭愧，本科二年级的时候笔者也学过一学期的运筹学，现

在脑子里能想起的居然只剩下单纯形法了——不过这不也正说明了该方法的简单和直么？顺便说句题外话，写过《万历十五年》的黄仁宇曾说中国的传统是“不能从数目字上管理”

，我们习惯于“拍脑袋”，而不是基于严格的数据做决定，也许改变这一传统的方法之一就

是全民动员学习线性规划喔。

3.1950 Krylov子空间迭代法

4.1951 矩阵计算的分解方法

50年代初的这两个算法都是关于线性代数中的矩阵计算的，看到数学就头大的读者恐怕看到 算法的名字已经开始皱眉毛了。Krylov子空间叠代法是用来求解形如Ax=b 的方程，A是一个 n*n 的矩阵，当n充分大时，直接计算变得非常困难，而Krylov方法则巧妙地将其变为 Kxi+1=Kxi+b-Axi的迭代形式来求解。这里的K(来源于作者俄国人Nikolai Krylov姓氏的首字母)是一个构造出来的接近于A的矩阵，而迭代形式的算法的妙处在于，它将复杂问题化简为阶段性的易于计算的子步骤.1951年由橡树岭国家实验室的Alston House holder提出的矩阵计算的分解方法，则证明了任何矩阵都可以分解为三角、对角、正交和其他特殊形式的矩阵，该算法的意义使得开发灵活的矩阵计算软件包成为可能。

5.1957 优化的Fortran编译器

说实话，在这份学术气息无比浓郁的榜单里突然冒出一个编译器(Compiler)如此工程化的东 东实在让人有“关公战秦琼”的感觉。不过换个角度想想，Fortran这一门几乎为科学计算 度身定制的编程语言对于科学家（尤其是数学家，物理学家）们实在是太重要了，简直是他 们形影不离的一把瑞士军刀，这也难怪他们纷纷抢着要把票投给了它。要知道，Fortran是 第一种能将数学公式转化为计算机程序的高级语言，它的诞生使得科学家们真正开始利用计 算机作为计算工具为他们的研究服务，这是计算机应用技术的一个里程碑级别的贡献。话说回来，当年这帮开发Fortran的家伙真是天才——只用23500行汇编指令就完成了一个 Fortran编译器，而且其效率之高令人叹为观止:当年在IBM主持这一项目的负责人 JohnBackus在数十年后，回首这段往事的时候也感慨，说它生成代码的效率“出乎了所有开发者的想象”。看来作为程序员，自己写的程序跑起来“出乎自己的想象”，有时候还真不 一定是件坏事！

6.1959-61 计算矩阵特征值的QR算法

呼，又是一个和线性代数有关的算法，学过线性代数的应该还记得“矩阵的特征值”吧？计 算特征值是矩阵计算的最核心内容之一，传统的求解方案涉及到高次方程求根，当问题规模 大的时候十分困难。QR算法把矩阵分解成一个正交矩阵（什么是正交矩阵？！还是赶紧去翻书吧！）与一个上三角矩阵的积，和前面提到的 Krylov 方法类似，这又是一个迭代算法， 它把复杂的高次方程求根问题化简为阶段性的易于计算的子步骤，使得用计算机求解大规模 矩阵特征值成为可能。这个算法的作者是来自英国伦敦的J.G.F. Francis。

7.1962 快速排序算法

不少读者恐怕和我一样,看到“快速排序算法”（Quick Sort）这个条目时,心里的感觉是——“这可总算找到组织了”。相比于其他一些对程序员而言高深莫测的数学物理公式,快速 排序算法真是我们朝夕相处的好伙伴——老板让你写个排序算法,如果你写出来的不是快速 排序,你都不好意思跟同事打招呼。其实根本不用自己动手实现, 不论是ANSI C,C++ STL,还 是Java SDK,天下几乎所有的SDK里都能找到它的某种实现版本。快速排序算法最早由Tony Hoare爵士设计，它的基本思想是将待排序列分为两半，左边的一半总是“小的”，右边的一半总是“大的”，这一过程不断递归持续下去，直到整个序列有 序。说起这位Tony Hoare爵士，快速排序算法其实只是他不经意间的小小发现而已，他对于计算机贡献主要包括形式化方法理论，以及ALGOL60 编程语言的发明等，他也因这些成就获得1980 年图灵奖。快速排序的平均时间复杂度仅仅为O(Nlog(N))，相比于普通选择排序和冒泡排序等而言，实在是历史性的创举。

8.1965 快速傅立叶变换

如果要评选对我们的日常生活影响最大的算法，快速傅立叶变换算法应该是当仁不让的总冠 军——每天当拿起话筒，打开手机，听mp3，看DVD，用DC拍照 ——毫不夸张的说，哪里有 数字信号处理，哪里就有快速傅立叶变换。快速傅立叶算法是离散傅立叶算法（这可是数字 信号处理的基石）的一种快速算法，它有 IBM 华生研究院的James Cooley和普林斯顿大学 的John Tukey共同提出，其时间复杂度仅为O(Nlog(N))；比时间效率更为重要的是，快速傅立叶算法非常容易用硬件实现，因此它在电子技术领域得到极其广泛的应用。

9.1977 整数关系探测算法

整数关系探测是个古老的问题，其历史甚至可以追溯到欧几里德的时代。具体的说:给定—组实数X1,X2,...,Xn，是否存在不全为零的整数a1,a2,...an，使得:a 1 x 1 +a 2 x

2 + . . . + a n x n ＝ 0 这一年BrighamYoung大学的Helaman Ferguson 和Rodney Forcade解决了这一问题。至于这个算法的意义嘛，呃，该算法应用于“简化量子场论中的 Feynman图的计算”——太深奥的学问拉！

10.  1987 快速多极算法

日历翻到了1987 年，这一年的算法似乎更加玄奥了，耶鲁大学的Leslie Greengard和Vladimir Rokhlin提出的快速多极算法用来计算“经由引力或静电力相互作用的N 个粒子运动的精确计算——例如银河系中的星体，或者蛋白质中的原子间的相互作用”，天哪，不是我不明白，这世界真是变得快！

所谓浪花淘尽英雄，这些算法的发明者许多已经驾鹤西去。二十一世纪的头五年也已经在不知不觉中从我们指尖滑过，不知下一次十大算法评选的盛事何时再有，也许我们那时已经垂垂老去，也许我们早已不在人世，只是心中唯一的希望——里面该有个中国人的名字吧！

--如欲平治天下，当今之世，舍我其谁！！！

相关文献：

1  Jack Dongarra, Francis Sullivan,Guest Editors Introduction The Top 10 Algorithms,Computing in Science and Engineering,Volume 2, Number 1, January/February 2000, pages 22-23.

Guest Editors Introduction The Top 10 Algorithms.pdf

2   Barry Cipra, The Best of the 20th Century: Editors Name Top 10 Algorithms,SIAM News,Volume 33, Number 4, May 2000, page 1. 

The Best of the 20th Century Editors Name Top 10 Algorithms.pdf

3 The Top 10 Computational Methods of the 20th Century, IACM Expressions, Number 11, September 2001, pages 5-9.

the top 10 computational methods of the 20th century.pdf