`
liuxinglanyue
  • 浏览: 565245 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

一些重要的算法

阅读更多

下面是一些比较重要的算法,原文罗列了32个,但我觉得有很多是数论里的,和计算机的不相干,所以没有选取。下面的这些,有的我们经常在用,有的基本不用。有的很常见,有的很偏。不过了解一下也是好事。也欢迎你留下你觉得有意义的算法。(注:本篇文章并非翻译,其中的算法描述大部份摘自Wikipedia,因为维基百科描述的很专业了)

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

附录

分享到:
评论

相关推荐

    对密码学中的一些重要算法进行了实现.zip

    对密码学中的一些重要算法进行了实现.zip

    常用算法程序集-徐士良-常用算法程序集-徐士良

    首先,让我们来看看书中可能涉及的一些重要算法类型: 1. 排序算法:包括冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等。排序算法是计算机科学的基础,它们在处理大量数据时尤其重要,可以优化数据...

    数学建模十大算法程序详解

    以下是对标题和描述中提及的一些重要算法的详细解释: 1. **图论算法**:图论是数学的一个分支,研究的是点与点之间连接的结构。在数学建模中,它常用于解决网络优化问题,如最短路径、最小生成树等。Dijkstra算法...

    常用到的一些算法学习.zip

    以下是根据标题、描述和标签提取出的一些重要算法知识点: 1. **排序算法**:排序是计算机科学中最基础的算法之一,包括快速排序、归并排序、冒泡排序、插入排序、选择排序、堆排序等。了解它们的时间复杂度、空间...

    c常用算法集合

    下面,我将详细讲解其中可能包含的一些重要算法及其应用。 1. **排序算法**:排序是计算机科学中最基础的问题之一。常见的排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序。这些排序算法在...

    ACM考研上机经典算法

    此外,还有其他一些重要算法,如字符串匹配(KMP、Boyer-Moore等)、回溯法、贪心策略等,它们在解决特定问题时有显著优势。在ACM和考研中,熟悉这些算法并能灵活应用是获取高分的关键。 在《经典算法(C).doc》文...

    java算法大全源码包

    下面我们将详细探讨其中可能涉及的一些重要算法及其应用场景。 1. 排序算法:如冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等。这些是计算机科学的基础,适用于数据处理和分析场景。在Java中,你...

    经典算法集合

    让我们逐一探讨其中的一些重要算法。 1. **河内之塔 (Towers of Hanoi)**:这是一个经典的递归问题,展示了如何通过辅助柱在不违反规则的情况下将所有盘子从一个柱子移动到另一个柱子。它体现了递归思想,解决复杂...

    经典算法Flash演示

    以下是可能涵盖的一些重要算法及其核心概念: 1. **排序算法**:包括快速排序(Quick Sort)、归并排序(Merge Sort)、冒泡排序(Bubble Sort)、插入排序(Insertion Sort)和希尔排序(Shell Sort)。这些算法...

    信息学奥赛各大算法模板

    以下是对标题和描述中涉及的一些重要算法进行的详细解释: 1. **最小生成树算法**:用于找到一个无向图中的最小权值树,这棵树包含了所有节点且权值总和最小。常见的算法有Prim算法和Kruskal算法。Prim算法从一个...

    计算机视觉算法与应用.pptx

    计算机视觉算法是计算机视觉领域的核心内容,本书籍对计算机视觉领域的一些重要算法进行了深入的探讨,包括基于像素的分割算法、基于区域的分割算法、基于边缘的分割算法、基于特征的分割算法等。 人脸检测与识别是...

    C语言常用算法程序集

    下面将详细探讨这个程序集中涉及的一些重要算法及其应用。 1. **排序算法**:程序集中可能包含了各种排序算法的实现,如冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。这些排序算法各有特点,适用...

    数据结构与算法

    以下是数据结构与算法中的一些重要算法: 1. 排序算法:如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,它们用于将元素按特定顺序排列。 2. 搜索算法:线性搜索、二分搜索、哈希搜索等,用于在...

    一些常用算法汇集集锦

    这个"一些常用算法汇集集锦"包含了一系列基础且重要的算法,适合学习和面试准备。以下是对这些算法的详细解释: 1. **Word2000使用技巧**: 虽然不是算法,但熟练掌握文档处理软件的使用技巧可以提高工作效率。Word...

    数学建模是十大算法

    "数学建模是十大算法"这个标题可能指的是在解决数学建模问题时常用的一些重要算法。虽然具体的文件内容无法直接查看,但我们可以基于常见的数学建模应用场景来探讨这些算法。 首先,线性规划是数学建模中的一大经典...

    C常用算法程序集~~

    下面,我们将详细探讨其中可能包含的一些重要算法及其应用。 1. **排序算法**:排序是计算机科学中最基础的问题之一,常见的有冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。这些排序算法各有优劣...

    一些小算法 一些小算法

    "一些小算法 一些小算法"这个标题暗示了我们可能讨论的是各种基础或特定的算法概念,它们可能是编程中的常见问题解决方案。描述中的重复内容进一步强调了算法的重要性,但没有提供具体的信息。标签"一些小算法"再次...

    十大算法 (2).docx

    十大算法是一份基于网络评选的榜单,涵盖了数学建模中常用的一些重要算法。虽然这个列表并不全面,但它们在数学建模竞赛中具有广泛的应用。以下是这十大算法的简要介绍: 1. 蒙特卡罗算法 蒙特卡罗方法是由John ...

    程序设计大赛算法专题.rar

    下面我们将详细探讨这个专题可能涵盖的一些重要算法知识点。 1. **排序算法**:在任何程序设计比赛中,排序都是常见的问题。快速排序、归并排序、堆排序、冒泡排序和插入排序等基础排序算法是必不可少的知识。同时...

    算法分析与设计课程作业代码.zip

    下面我们将详细探讨其中可能涉及的一些重要算法知识。 1. **排序算法**:作业中可能包含了各种排序算法的实现,如快速排序、归并排序、冒泡排序、插入排序、选择排序和堆排序等。快速排序以其高效的平均性能而著名...

Global site tag (gtag.js) - Google Analytics