奥地利符号计算研究所(Research Institute for Symbolic Computation,简
称 RISC)做了一个调查,投票选出 32 个最重要的算法:
1. A* 搜索算法——图形搜索算法,从给定起点到给定终点计算出路径。其
中使用了一种启发式的估算,为每个节点估算通过该节点的最佳路径,并
以之为各个地点排定次序。算法以得到的次序访问这些节点。因此,A*
搜索算法是最佳优先搜索的范例。
2. 集束搜索(又名定向搜索,Beam Search)——最佳优先搜索算法的优化。
使用启发式函数评估它检查的每个节点的能力。不过,集束搜索只能在每
个深度中发现最前面的 m 个最符合条件的节点,m 是固定数字——集束
的宽度。
3. 二分查找(Binary Search)——在线性数组中找特定值的算法,每个步骤
去掉一半不符合要求的数据。
4. 分支界定算法(Branch and Bound)——在多种最优化问题中寻找特定最
优化解决方案的算法,特别是针对离散、组合的最优化。
5. Buchberger 算法——一种数学算法,可将其视为针对单变量最大公约数
求解的欧几里得算法和线性系统中高斯消元法的泛化。
6. 数据压缩——采取特定编码方案,使用更少的字节数(或是其他信息承载
单元)对信息编码的过程,又叫来源编码。
7. Diffie-Hellman 密钥交换算法——一种加密协议,允许双方在事先不了解
对方的情况下,在不安全的通信信道中,共同建立共享密钥。该密钥以后
可与一个对称密码一起,加密后续通讯。
8. Dijkstra 算法——针对没有负值权重边的有向图,计算其中的单一起点最
短算法。
9. 离散微分算法(Discrete differentiation)
10.动态规划算法(Dynamic Programming)——展示互相覆盖的子问题和最
优子架构算法
11.欧几里得算法(Euclidean algorithm)——计算两个整数的最大公约数。
最古老的算法之一,出现在公元前 300 前欧几里得的《几何原本》。
12.期望-最大算法(Expectation-maximization algorithm,又名
EM-Training)——在统计计算中,期望-最大算法在概率模型中寻找可能
性最大的参数估算值,其中模型依赖于未发现的潜在变量。EM 在两个步
骤中交替计算,第一步是计算期望,利用对隐藏变量的现有估计值,计算
其最大可能估计值;第二步是最大化,最大化在第一步上求得的最大可能
值来计算参数的值。