影响世界的十大算法_轻松概念性总结分享一下改变世界5大算法

【引言】算法是指对解题方案的准确完整的描述，一系列解决问题的明确指令，算法代表了描述解题策略机制的系统方法。今天是周末。今天，我们就来简单总结一下，分享一下改变世界的五大算法。当然，能改变世界的算法不止五种。比如还有卡尔曼滤波算法之类的，以后有机会我再整理。

大都会算法

在统计学和统计物理中，Metropolis-Hastings算法是一种马尔可夫链蒙特卡罗(MCMC)方法，用于从难以直接采样的概率分布中获得随机样本序列。此序列可用于近似分布(例如，生成直方图)或计算积分(例如，期望值)。Metropolis-Hastings等MCMC算法通常用于多维分布采样，尤其是在多维的情况下。对于一维分布，通常还有其他方法(如自适应拒绝抽样)可以直接从分布返回独立样本，这些方法不会有MCMC方法固有的自相关样本问题。

Metropolis算法是一种马尔可夫链蒙特卡罗方法，用于根据玻尔兹曼分布生成系统状态。由此算法衍生出的更一般的Metropolis-Hastings算法，可以模拟随机变量序列，更精确地模拟期望分布为平稳分布的马尔可夫链，特别是当很多随机变量的分布不能直接模拟时。

该算法以Nicholas Metropolis的名字命名，Nicholas Metropolis在1953年与Arianna W. Rosenbluth、Marshall Rosenbluth、Augusta H. Teller和爱德华泰勒共同撰写了文章《Equation of State Calculations by Fast Computing Machines》。

为什么这个算法很牛逼？Metropolis算法是蒙特卡罗方法中最著名的算法，其应用领域包括统计物理、QCD、天体物理、物理化学、数学、计算生物学、人工智能等等，甚至社会科学。

使用Metropolis-Hastings算法对Rosenbrock函数运行3D马尔可夫链的结果。该算法从具有高后验概率的区域中采样，并且链在这些区域中开始混合。

单纯形法

在数学优化中，Dantzig的单纯形算法(或单纯形法)是一种流行的线性规划算法。这种算法的名字来源于T. S. Motzkin提出的单纯形概念。单纯形法(也叫单纯形算法)是一种求解线性优化问题的数值优化方法，也叫线性规划(LP)。它只需要有限的步骤来解决这个问题或确定其不可解性或无穷性。单纯形法的基本思想是由乔治丹齐格于1947年提出的。此后，通过大量的改进，它们已经发展成为实践中最重要的线性优化解。单纯形法是主元法。

线性不等式系统将多面体定义为可行域。单纯形算法从一个起点开始，沿着多面体的边缘移动，直到到达最优解的顶点。

单纯形算法三维多面体；

如今，线性规划的理论和算法已经非常成熟，广泛应用于实际问题和生产生活中。线性规划问题的诞生标志着应用数学的一个新分支——的到来——数学规划时代。在过去的60年里，数学规划已经成为一门成熟的学科。其理论和方法已经应用于经济、金融、军事、机器学习等领域。在数学规划领域，其他重要分支中的许多问题都是建立在线性规划理论和算法的基础上，也是利用线性规划理论来解决和处理的。可见，线性规划在整个数学规划和应用数学领域中的地位举足轻重。因此，研究单纯形法的产生和发展，对于理解整个数学规划的发展具有重要意义。

快速傅立叶算法

什么是傅立叶变换？意思是满足一定条件的函数可以表示为三角函数(正弦和/或余弦函数)或者它们积分的线性组合。在不同的研究领域，傅里叶变换有许多不同的变体，如连续傅里叶变换和离散傅里叶变换。首先，傅立叶分析被提出作为热过程分析的工具。通过以下步骤来看看近似方波近似叠加过程：

如果一个点匀速圆周运动，它离地面的高度是正弦函数。点移动的速度对应频率，圆的半径对应振幅。

再加一个速度圈。

再加几个看看：

它接近方波吗？

快速傅立叶变换(FFT)是一种高效计算离散傅立叶变换(DFT)的算法。它可以用来将数字信号分解成频率成分，然后进行分析。类似地，还有离散傅里叶逆变换(IFFT)。IFFT使用相同的算法，但使用共轭系数。

下图显示了FFT后时域信号的频谱图：

快速傅立叶变换是由J.W. Cooley和T.W. Tukey在1965年提出的。利用这种算法，可以大大减少计算机计算离散傅里叶变换所需的乘法次数，特别是变换的采样点N越多，FFT算法的节省就越显著。

詹姆斯库利：

约翰图基：

计算量小的明显优势使得FFT在信号处理技术领域得到广泛应用，结合高速硬件可以实现实时信号处理。例如，FFT用于语音信号的分析和合成，通信系统中全数字时分制和频分制(TDM/FDM)的复用转换，频域的信号滤波和相关分析，以及雷达、声纳和振动信号的频谱分析，以提高搜索和跟踪目标的分辨率。可以说，FFT的出现对数字信号处理的发展起到了重要的作用。

快速排序算法

众所周知的快速排序是一种快速、递归、不稳定的排序算法，其工作原理是部分和优势。它是C. Antony R. Hoare在1960年左右开发的基本形式，后来被许多研究人员改进。这种算法的优点是内部循环非常短(大大提高了执行速度)。它不需要额外的内存(除了递归调用栈上需要的额外空间)。

不用说，这种算法在计算机科学中被广泛使用。当然也是本文几个算法中比较容易理解的一个算法。这个算法对现代软件编程影响深远，流传已久！

计算特征值的QR算法

QR算法是一种计算二次矩阵所有特征值和特征向量的数值方法。QR法或QR迭代法是由John G. F. Francis和Wera Nikolajewna Kublanowskaja于1961-1962年在QR分解的基础上独立提出的。其前身是Heinz Rutishauser(1958)提出的LR算法，稳定性差，基于LR分解。QR算法的迭代经常收敛到矩阵的Schur形式。初始过程相当复杂，所以即使在今天的计算机上，对于行列数十万的矩阵也是不可行的。

派生的变体，如Z. Bai和James Demmel 1989的多移位方法和K. Braman、R. Byers和R. Mathias 2002的数值上更稳定的变体，具有实际的运行时间，它们的大小是矩阵的立方。后一种方法在LAPACK中实现，LAPACK是一个数值软件库，用于许多计算机代数系统(CAS)中的数值矩阵算法。

系统辨识是现代控制理论的重要组成部分。辨识系统的结构和参数在工程和理论上都有重要的作用。最小二乘法是系统参数辨识中一种重要的估计方法，在许多领域和场合得到了广泛的应用。

QR分解算法是人工智能热门领域的基础算法之一，改变世界并不为过。