`
chroya
  • 浏览: 655584 次
  • 性别: 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)

附录

本文转自:http://blog.csdn.net/haoel/archive/2010/07/22/5755241.aspx

分享到:
评论

相关推荐

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

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

    数据结构 演示重要的算法 (考研必备)

    这一款软件动态展示一些重要算法,计算机统考的朋友不要错过

    计算机图形学算法的实现源代码和程序

    本工程是有关计算机图形学一些重要算法的实现(如DDA画线,中点画线,Bresenham画线,DDA画圆,中点画圆,Bresenham画圆,Bresenham画椭圆,中点画椭圆,区域填充,图形裁剪,三次样条曲线,Bezier曲线,B样条曲线,...

    算法是计算机科学领域最重要的基石之一,但却受到了国内一些程序员

    算法是计算机科学领域最重要的基石之一,但却受到了国内一些程序员算法是计算机科学领域最重要的基石之一,但却受到了国内一些程序员算法是计算机科学领域最重要的基石之一,但却受到了国内一些程序员算法是计算机科学...

    算法谜题(算法谜题)

    算法是计算机科学领域最重要的基石之一。算法谜题,就是能够直接或间接地采用算法来加以解决的谜题。求解算法谜题是培养和锻炼算法思维能力一种最有效和最有乐趣的途径。 本书是一本经典算法谜题的合集。本书包括了...

    rose algorithms:该库包含一些重要的算法-开源

    欢迎使用玫瑰算法,该库包含Ali Abdul Ghani(ali奇迹)的一些重要算法邮件:blade.vp2020@gmail.com许可证:lgpl

    数据挖掘18大算法实现以及其他相关经典DM算法

    朴素贝叶斯算法是贝叶斯算法里面一种比较简单的分类算法,用到了一个比较重要的贝叶斯定理,用一句简单的话概括就是条件概率的相互转换推导。详细介绍链接 SVM 支持向量机算法。支持向量机算法是一种对线性和非...

    算法基础 打开算法之门

    本课程将介绍并探讨有关数据组织、算法设计、时间和空间效率的概念和通用分析方法,帮助学员学会数据的组织方法和一些典型算法的实现,能够针对问题的应用背景分析,选择合适的数据结构,从而培养高级程序设计技能。

    甲虫天线搜索算法(Python实现)

    特别是,其中一些算法不仅在以计算机科学为主的学术界发挥着相当重要的作用,而且在许多其他实际工程领域也发挥着重要作用。Mirjalili等人[1]通过模仿自然界中灰狼的领导力和猎物提出了一个灰狼优化器。受一些布谷鸟...

    基于TDMA的RFID多标签识别防碰撞算法研究

    射频识别(RFID)技术是一种非接触式的自动识别技术,是物联网(IOT)的核心技术之一。...本文主要对Aloha类算法、树搜索算法、混合算法以及主要的改进算法进行分析研究,并对未来研究方向提出一些见解。

    Java常用算法手册

    现代的设计任务大多通过计算机编程来完成,而算法起到了至关重要的作用。可以毫不夸张地说,算法是一切程序设计的灵魂和基础。选择合理的算法,可以起到事半功倍的效果。  赵志云、衡友跃编著的《Java常用算法手册...

    算法导论中文版

    一项巧妙而又重要的修改是提前引入循环不变式,并在全书中用来证明算法的正确性。在不改变数学和分析重点的前提下,作者将许多数学基础知识从第一部分移到了附录中,并在开始部分加入了一些富有诱导性的题材。 ★...

    算法设计与分析基础(第3版) 原版

    《算法设计与分析基础(第3版)》作为第3版,相对前版调整了多个章节的内容和顺序,同时增加了一些算法,并扩展了算法的应用,使得具体算法和通用算法设计技术的对应更加清晰有序;各章累计增加了70道习题,其中包括...

    数学建模算法

    8.一些连续离散化方法(很多问题都是实际来的,数据可以是连续的,而计算机只认的是离散的数据,因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的) 9.数值分析算法(如果在比赛中采用高级语言进行...

    C算法(第2卷)(图算法)

    《C算法(第2卷)(图算法)(第3版)(中文版)》所讨论的图算法,都是实际中解决图问题的最重要的已知方法。《C算法(第2卷)(图算法)(第3版)(中文版)》的主要宗旨是让越来越多需要了解这些算法的人的能够掌握这些方法及基本...

    Java数据结构与算法

    本书可帮助读者: 通过由基于JAVA的演示所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程...它使用JAVA语言说明重要的概念,而避免了C/C++语言的复杂性,以便集中精力论述数据结构和算法。

    数学建模竞赛中应当掌握的十类算法

    身而轻视算法的时候,可以使用这种暴力方案,最好使用一些高级语言作为编程工具。 8.一些连续数据离散化方法。很多问题都是实际来的,数据可以是连续的,而计算机只能处理离散的 数据,因此将其离散化后进行差分代替...

    算法设计与分析NP完全问题一些重要的概念PPT学习教案.pptx

    算法设计与分析NP完全问题一些重要的概念PPT学习教案.pptx

    算法设计与分析课件与知识点复习

    课程主要讨论和介绍计算机算法的复杂性理论,结合对一些熟悉的算法进行分析和总结,强化基础理论知识,对一些大型工程软件的分析,会有一定的辅助作用。它主要介绍计算机科学及应用领域常见的有代表性的非数值算法及...

    图论中的概念和重要算法

    图论中的概念和重要算法 简单讲,一个图是由一些点和这些点之间的连线组成的。严格意义讲,图是一种数据结构,定义为:graph=(V,E),V是点(称为“顶点”)的非空有限集合,E是线(称为“边”)的集合,边一般用...

Global site tag (gtag.js) - Google Analytics