下面整理了一些比较重要的算法。原文罗列了 32 个,但其中不少属于数论范畴或过于生僻,与计算机工程的关联度不高,因此本文做了筛选。下面这些算法里,有的我们日常就在使用,有的则基本用不到;有的非常常见,有的则相当冷门。了解一下总是好的,也欢迎你留言补充自己觉得有意义的算法。(注:本文并非翻译,其中的算法描述大部分摘自 Wikipedia,因为维基百科的描述已经足够专业。)
A* 搜寻算法
俗称 A 星算法,是一种在图形平面上、针对多个节点路径求出最低通过成本的算法,常用于游戏中 NPC 的移动计算,或在线游戏中 BOT 的移动计算。它既像 Dijkstra 算法那样能够找到最短路径,也像 BFS 那样进行启发式搜索。
Beam Search
束搜索(beam search)是解决优化问题的一种启发式方法,在分支定界方法的基础上发展而来。它使用启发式方法估计 k 条最优路径,只沿着这 k 条路径继续向下搜索,也就是每一层只保留满意的节点,其余节点则被永久抛弃,因此相比分支定界法能大大节省运行时间。束搜索最早于 20 世纪 70 年代中期被应用于人工智能领域:1976 年 Lowerre 在其名为 HARPY 的语音识别系统中首次使用了束搜索方法,其目标是并行搜索几条潜在的最优决策路径以减少回溯,并快速获得一个解。
二分查找算法
二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始:若中间元素正好是要查找的元素,则搜索结束;若目标元素大于或小于中间元素,则在大于或小于中间元素的那一半区间里继续查找,每次同样从中间元素开始比较。这种搜索算法每比较一次,搜索范围就会缩小一半。
Branch and bound
分支定界(branch and bound)算法是一种在问题的解空间树上搜索问题解的方法。与回溯算法不同,分支定界算法采用广度优先或最小耗费优先的策略搜索解空间树,并且在分支定界算法中,每个活结点只有一次机会成为扩展结点。
数据压缩
数据压缩是通过减少计算机中所存储数据或通信传播中数据的冗余度,从而提高数据密度、最终使数据占用存储空间减少的技术。数据压缩在文件存储和分布式系统领域有着十分广泛的应用,也意味着存储媒介容量的增大和网络带宽的扩展。
Diffie–Hellman 密钥协商
Diffie–Hellman key exchange(简称 D–H)是一种安全协议,它可以让双方在完全没有对方任何预先信息的条件下,通过不安全信道建立起一个共享密钥。这个密钥可以在后续的通信中作为对称密钥,用来加密通信内容。
Dijkstra 算法
迪科斯彻算法(Dijkstra)由荷兰计算机科学家艾兹格·迪科斯彻(Edsger Wybe Dijkstra)发明,用于解决有向图中单源点到其他所有顶点的最短路径问题。举例来说,如果图中的顶点代表城市,边上的权重代表城市间开车行经的距离,那么 Dijkstra 算法就可以用来找到两座城市之间的最短路径。
动态规划
动态规划是一种在数学和计算机科学中使用的、用于求解包含重叠子问题的最优化问题的方法。其基本思想是将原问题分解为相似的子问题,在求解过程中通过子问题的解求出原问题的解。动态规划的思想是许多算法的基础,被广泛应用于计算机科学和工程领域,比较著名的应用实例有:求解最短路径问题、背包问题、项目管理、网络流优化等。
欧几里得算法
在数学中,辗转相除法又称欧几里得算法,是求最大公约数的算法。辗转相除法最早出现于欧几里得的《几何原本》(第 VII 卷,命题 i 和 ii)中,而在中国则可以追溯至东汉时期的《九章算术》。
最大期望(EM)算法
在统计计算中,最大期望(EM)算法是一种在概率(probabilistic)模型中寻找参数最大似然估计的算法,其中概率模型依赖于无法直接观测的隐藏变量(Latent Variable)。最大期望算法经常用于机器学习和计算机视觉中的数据聚类(Data Clustering)领域。该算法通过两个步骤交替进行计算:第一步是期望步(E),利用对隐藏变量的现有估计值计算其最大似然估计值;第二步是最大化步(M),最大化在 E 步上求得的最大似然值来计算新的参数值。M 步上得到的参数估计值会被用于下一个 E 步的计算,这个过程不断交替进行。
快速傅里叶变换(FFT)
快速傅里叶变换(Fast Fourier Transform,FFT)是离散傅里叶变换的快速算法,也可用于计算离散傅里叶变换的逆变换。FFT 有着广泛的应用,例如数字信号处理、计算大整数乘法、求解偏微分方程等。本条目只描述各种快速算法,至于离散傅里叶变换本身的性质和应用,请参见离散傅里叶变换。
哈希函数
Hash Function 是一种从任意一种数据中生成小的数字"指纹"的方法。该函数将数据打乱混合,重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的、由随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突;在散列表和数据处理中,如果不抑制冲突来区别数据,就会使得数据库记录更难被找到。
堆排序
Heapsort 是指利用堆积树(堆)这种数据结构设计的一种排序算法。堆积树是一个近似完全二叉树的结构,并同时满足堆积属性,即子结点的键值或索引总是小于(或大于)它的父结点。
归并排序
Merge sort 是建立在归并操作上的一种有效的排序算法,是采用分治法(Divide and Conquer)的一个非常典型的应用。
RANSAC 算法
RANSAC 是 "RANdom SAmple Consensus" 的缩写。该算法是一种用于从一组观测数据中估计数学模型参数的迭代方法,由 Fischler and Bolles 在 1981 年提出。它是一种非确定性算法,因为它只能以一定的概率得到合理的结果,而随着迭代次数的增加,这种概率会不断提高。算法的基本假设是:观测数据集中同时存在 "inliers"(对模型参数估计起到支持作用的点)和 "outliers"(不符合模型的点),并且这组观测数据受到噪声影响。RANSAC 假设给定一组 "inliers" 数据,就能够得到最优的、符合这组点的模型。
RSA 加密算法
这是一个公钥加密算法,也是世界上第一个适合用来做数字签名的算法。今天的 RSA 已经专利失效,被广泛地用于电子商务加密。大家都相信,只要密钥足够长,这个算法就会是安全的。
并查集 Union-find
并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题,在使用中常常以森林来表示。
Viterbi 算法
寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states)。