计算机科学中32个常用的基础算法_.docx

《计算机科学中32个常用的基础算法_.docx》由会员分享，可在线阅读，更多相关《计算机科学中32个常用的基础算法_.docx（7页珍藏版）》请在一课资料网上搜索。

1、计算机科学中32个常用的基础算法_ 奥地利符号计算讨论所（Research Institute for Symbolic Computation，简称RISC）的Christoph Koutschan博士在自己的页面上发布了一篇文章，提到他做的一个调查，参加者大多数是计算机科学家，他请这些科学家投票选出最重要的算法，以下是这次调查的结果，根据英文名称字母挨次排序： 1、A* 搜索算法图形搜索算法，从给定起点到给定终点计算出路径。其中用法了一种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此，A*搜索算法是最佳优先搜索的范例。 2、集

2、束搜索（又名定向搜索，Beam Search）最佳优先搜索算法的优化。用法启发式函数评估它检查的每个节点的力量。不过，集束搜索只能在每个深度中发觉最前面的m个最符合条件的节点，m是固定数字集束的宽度。 3、二分查找（Binary Search）在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。 4、分支界定算法（Branch and Bound）在多种最优化问题中查找特定最优化解决方案的算法，格外是针对离散、组合的最优化。 5、Buchberger算法一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。 6、数据压缩实行特定编码方案，用法更少

3、的字节数（或是其他信息承载单元）对信息编码的过程，又叫来源编码。 7、Diffie-Hellman密钥交换算法一种加密协议，允许双方在事先不了解对方的状况下，在担心全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一起，加密后续通讯。 8、Dijkstra算法针对没有负值权重边的有向图，计算其中的单一起点最短算法。 9、离散微分算法（Discrete differentiation） 10、动态规划算法（Dynamic Programming）展现相互掩盖的子问题和最优子架构算法 11、欧几里得算法（Euclidean algorithm）计算两个整数的最大公约数。最古老的算法之一，

4、消失在公元前300前欧几里得的几何原本。 12、期望-最大算法（Expectation-maximization algorithm，又名EM-Training）在统计计算中，期望-最大算法在概率模型中查找可能性最大的参数估算值，其中模型依靠于未发觉的潜在变量。EM在两个步骤中交替计算，第一步是计算期望，利用对隐蔽变量的现有估量值，计算其最大可能估量值；其次步是最大化，最大化在第一步上求得的最大可能值来计算参数的值。 13、快速傅里叶变换（Fast Fourier transform，FFT）计算离散的傅里叶变换（DFT）及其反转。该算法应用范围很广，从数字信号处理到解决偏微分方程，到快速计算

5、大整数乘积。 14、梯度下降（Gradient descent）一种数学上的最优化算法。 15、哈希算法（Hashing） 16、堆排序（Heaps） 17、Karatsuba乘法需要完成上千位整数的乘法的系统中用法，比如计算机代数系统和大数程序库，假如用法长乘法，速度太慢。该算法发觉于1962年。 18、LLL算法（Lenstra-Lenstra-Lovasz lattice reduction）以格规约（lattice）基数为输入，输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量用法：背包加密系统（knapsack）、有特定设置的RSA加密等等。 19、最大流量算法（Maxim

6、um flow）该算法试图从一个流量网络中找到最大的流。它优势被定义为找到这样一个流的值。最大流问题可以看作更简单的网络流问题的特定状况。最大流与网络中的界面有关，这就是最大流-最小截定理（Max-flow min-cut theorem）。Ford-Fulkerson 能找到一个流网络中的最大流。 20、合并排序（Merge Sort） 21、牛顿法（Newtons method）求非线性方程（组）零点的一种重要的迭代法。 22、Q-learning学习算法这是一种通过学习动作值函数（action-value function）完成的强化学习算法，函数实行在给定状态的给定动作，并计算出期望的

7、效用价值，在此后遵循固定的策略。Q-leanring的优势是，在不需要环境模型的状况下，可以对比可接受行动的期望效用。 23、两次筛法（Quadratic Sieve）现代整数因子分解算法，在实践中，是目前已知其次快的此类算法（仅次于数域筛法Number Field Sieve）。对于110位以下的十位整数，它仍是最快的，而且都认为它比数域筛法更简洁。 24、RANSAC是“RANdom SAmple Consensus”的缩写。该算法依据一系列观看得到的数据，数据中包含特别值，估算一个数学模型的参数值。其基本假设是：数据包含非异化值，也就是能够通过某些模型参数说明的值，异化值就是那些不符合模

8、型的数据点。 25、RSA公钥加密算法。首个适用于以签名作为加密的算法。RSA在电商行业中仍大规模用法，大家也信任它有足够平安长度的公钥。 26、Schnhage-Strassen算法在数学中，Schnhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法简单度为：O(N log(N) log(log(N)，该算法用法了傅里叶变换。 27、单纯型算法（Simplex Algorithm）在数学的优化理论中，单纯型算法是常用的技术，用来找到线性规划问题的数值解。线性规划问题包括在一组实变量上的一系列线性不等式组，以及一个等待最大化（或最小化）的固定线性函数。 28、奇异值分解

9、（Singular value decomposition，简称SVD）在线性代数中，SVD是重要的实数或复数矩阵的分解方法，在信号处理和统计中有多种应用，比如计算矩阵的伪逆矩阵（以求解最小二乘法问题）、解决超定线性系统（overdetermined linear systems）、矩阵靠近、数值天气预报等等。 29、求解线性方程组（Solving a system of linear equations）线性方程组是数学中最古老的问题，它们有许多应用，比如在数字信号处理、线性规划中的估算和预报、数值分析中的非线性问题靠近等等。求解线性方程组，可以用法高斯约当消去法（Gauss-Jordan

10、elimination），或是柯列斯基分解（ Cholesky decomposition）。 30、Strukturtensor算法应用于模式识别领域，为全部像素找出一种计算方法，看看该像素是否处于同质区域（ homogenous region），看看它是否属于边缘，还是是一个顶点。 31、合并查找算法（Union-find）给定一组元素，该算法经常用来把这些元素分为多个分别的、彼此不重合的组。不相交集（disjoint-set）的数据结构可以跟踪这样的切分方法。合并查找算法可以在此种数据结构上完成两个有用的操作：查找：推断某特定元素属于哪个组；合并：联合或合并两个组为一个组。 32、维特比算法（Viterbi algorithm）查找隐蔽状态最有可能序列的动态规划算法，这种序列被称为维特比路径，其结果是一系列可以观看到的大事，格外是在隐蔽的Markov模型中。 以上就是Christoph博士对于最重要的算法的调查结果，这些算法有着广泛的应用，虽然说是计算机算法，其实其中不少条目都是一门数学课程，或者某课程中的重要章节，广泛地涉及基础数学、计算数学等课程，比如数值计算，信息论，矩阵论等。 更多信息请查看IT技术专栏 .