一些重要的算法
marz
posted @ Aug 11, 2010 06:13:44 AM
in algorithm
, 2005 readers
从 酷壳 - CoolShell.cn 作者:陈皓
有超过 100 人喜欢此条目
下面是一些比较重要的算法,原文罗 列了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’s 算法
迪科斯彻算法(Dijkstra)是由荷兰计算机科学家艾兹格·迪科斯彻(Edsger Wybe Dijkstra)发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说,如果图中的顶点表示城市,而边上的权重表示著城市间开车行经的距离,迪科斯彻算法可以用来找到两个城市之间的最短路径。
- 动态规划
动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。其基本思想是,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础,被广泛应用于计算机科学和工程领域。比较著名的应用实例有:求解最短路径问题,背包问题,项目管理,网络流优化等。这里也有一篇文章说得比较详细。
- 最大期望(EM)算法
在统计计算中,最大期望(EM)算法是在概率(probabilistic)模型中寻找参数最大似然估计的算法,其中概率模型依赖于无法观测的隐藏变量(Latent Variable)。最大期望经常用在机器学习和计算机视觉的数据聚类(Data Clustering) 领域。最大期望算法经过两个步骤交替进行计算,第一步是计算期望(E),利用对隐藏变量的现有估计值,计算其最大似然估计值;第二步是最大化(M),最大 化在 E 步上求得的最大似然值来计算参数的值。M 步上找到的参数估计值被用于下一个 E 步计算中,这个过程不断交替进行。
- 快速傅里叶变换 (FFT)
快速傅里叶变换(Fast Fourier Transform,FFT),是离散傅里叶变换的快速算法,也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用,如数字信号处理、计算大整数乘法、求解偏微分方程等等。本条目只描述各种快速算法,对于离散傅里叶变换的性质和应用,请参见离散傅里叶变换。
- 哈希函数
Hash Function是一种从任何一种数据中创建小的数字“指纹”的方法。该函数将数据打乱混合,重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的 随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中,不抑制冲突来区别数据,会使得数据库记录更难找到。
- RANSAC 算法
RANSAC 是”RANdom SAmple Consensus”的缩写。该算法是用于从一组观测数据中估计数学模型参数的迭代方法,由Fischler and Bolles在1981 提出,它是一种非确定性算法,因为它只能以一定的概率得到合理的结果,随着迭代次数的增加,这种概率是增加的。 该算法的基本假设是观测数据集中存在”inliers”(那些对模型参数估计起到支持作用的点)和”outliers”(不符合模型的点),并且这组观测 数据受到噪声影响。RANSAC 假设给定一组”inliers”数据就能够得到最优的符合这组点的模型。
- RSA加密演算法
这是一个公钥加密算法,也是世界上第一个适合用来做签名的算法。今天的RSA已经专利失效,其被广泛地用于电子商务加密,大家都相信,只要密钥足够长,这个算法就会是安全的
- 并查集Union-find
并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。
- Viterbi algorithm
寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states)
附录
- 关于这个世界上的算法,你可以看看Wikipedia的这个网页:http://en.wikipedia.org/wiki/List_of_algorithms
- 关于排序算法,你可以看看本站的这几篇文章《一个显示排序过程的Python脚本》、《一个排序算法比较的网站》
。
Jan 14, 2023 01:04:46 AM
You are my inspiration I possess few web logs and sometimes run out from to post . 카지노사이트
Feb 12, 2023 11:52:19 PM
There are a handful of fascinating points with time in this post but I don’t know if these center to heart. You can find some validity but I’ll take hold opinion until I explore it further. Good write-up , thanks and that we want far more! Included with FeedBurner as well Macbook air
=================================
site promotion will always be a tedious job but you can outsource site promotion on some indian or pakistani guy` 여우알바
Feb 22, 2023 10:13:50 PM
I wish to show my appreciation for your generosity for persons that actually need help on in this niche. Your special dedication to passing the solution throughout ended up being rather significant and have continually encouraged somebody much like me to attain their dreams. Your personal warm and helpful useful information indicates a great deal a person like me and even more to my peers. Best wishes; from each one of us. 여우알바
Oct 05, 2023 11:21:47 PM
You have brought up a very excellent details , thankyou for the post. “Beginnings are apt to be shadowy and so it is the beginnings of the great mother life, the sea.” by Rachel Carson. 插花班
Aug 05, 2024 03:27:54 AM
Wonderful blog! I found it while browsing on Yahoo News. Do you have any suggestions on how to get listed in Yahoo News? I’ve been trying for a while but I never seem to get there! Cheers 二手MacBook回收
=================
Hey there, You have done a fantastic job. I will definitely digg it and personally recommend to my friends. I’m confident they will be benefited from this website. 手機回收價格表
=================
There are incredibly lots of details that adheres to that take into consideration. That is a fantastic denote raise up. I provde the thoughts above as general inspiration but clearly you will find questions like the one you raise up the place that the most crucial factor will likely be working in honest good faith. I don?t determine if guidelines have emerged about things such as that, but I know that a job is clearly recognized as a good game. Both youngsters glance at the impact of a little moment’s pleasure, through out their lives. iphone trade in
=================
Hi there! I just wish to give an enormous thumbs up for the nice info you’ve right here on this post. I shall be coming again to your blog for extra soon. 62mas
=================
Nice blog here! after reading, i decide to buy a blog seiko skx
=================
I have been reading out some of your stories and i can claim pretty nice stuff. I will surely bookmark your blog. rubber strap
=================
Really instructive and superb structure of articles, now that’s user friendly . Seiko King Samurai
=================
After study a few of the blog posts on your website now, and I truly like your way of blogging. I bookmarked it to my bookmark website list and will be checking back soon. Pls check out my web site as well and let me know what you think. 魔術表演
=================
I was suggested this website by my cousin. I am not sure whether this post is written by him as nobody else know such detailed about my trouble. You are wonderful! Thanks!Nice blog here! Also your web site loads up fast! What web host are you using? Can I get your affiliate link to your host? I wish my website loaded up as quickly as yours lol 兒童魔術班
=================
Thanks for your recommendations on this blog. One thing I want to say is that purchasing electronic products items over the Internet is not something new. The fact is, in the past several years alone, the marketplace for online electronic devices has grown noticeably. Today, you’ll find practically any kind of electronic device and tools on the Internet, ranging from cameras and also camcorders to computer elements and video games consoles. 魔術
=================
Alfred North Whitehead~ Ideas wont keep something must be done about them. [Reply] 署期魔術班
Aug 30, 2024 12:17:26 PM
With havin so much written content do you ever run into any problems of plagorism or copyright violation? My website has a lot of exclusive content I’ve either written myself or outsourced but it seems a lot of it is popping it up all over the internet without my agreement. Do you know any solutions to help reduce content from being ripped off? I’d genuinely appreciate it. 插花技巧
=====================
I’m impressed, I have to admit. Really rarely do you encounter a weblog that’s both educative and entertaining, and without a doubt, you might have hit the nail to the head. Your idea is outstanding; the problem is an element that not enough individuals are speaking intelligently about. My business is very happy that we stumbled across this within my look for something relating to this. 花藝證書
=====================
This is a great blog. and i want to visit this every day of the week . 花束課程
=====================
Thank you, I’ve recently been looking for information about this subject for ages and yours is the best I have located so far. 插花
Sep 11, 2024 07:44:29 PM
I’d need to consult you here. Which isn’t some thing Which i do! I enjoy reading a post that can make people feel. Also, appreciate your allowing me to comment! opp袋
This may be the right blog for everyone who is wishes to learn about this topic. You already know much its nearly challenging to argue to you (not too I personally would want…HaHa). You definitely put a whole new spin over a topic thats been revealed for several years. Fantastic stuff, just great! packing bag
I dugg some of you post as I thought they were very beneficial invaluable 真空袋
Wow that was strange. I just wrote an incredibly long comment but after I clicked submit my comment didn’t appear. Grrrr… well I’m not writing all that over again. Regardless, just wanted to say wonderful blog! 購物袋
Some truly interesting points you have written. Assisted me a lot, just what I was looking for . 二手MacBook回收
I got what you mean ,bookmarked , very nice internet site . 手機回收價格表
Great post, you have pointed out some good details , I besides believe this s a very fantastic website. iphone trade in
This blog really is good. How was it made ? 魔術表演
I’m really impressed along with your writing abilities well with the structure in your weblog. Is that this a paid subject matter or did you modify it your self? Either way stay up the nice quality writing, it is uncommon to look a great weblog like this one nowadays. 到校興趣班
This is the right weblog for everyone who wishes to be familiar with this topic. You are aware of a great deal of its virtually tricky to argue to you (not too I personally would want…HaHa). You actually put a new spin using a topic thats been written about for many years. Wonderful stuff, just excellent! 魔術
I will tell your friends to visit this site. .Thanks for the article. 署期魔術班
Sep 14, 2024 01:52:42 AM
Thanks for taking time for sharing this article, it was excellent and very informative. It’s my first time that I visit here. I found a lot of informative stuff in your article. Keep it up. Thank you. 有效減肥藥
Oct 04, 2024 03:28:16 AM
This is really attractive, You’re a really experienced writer. I’ve enrolled with your feed plus expect enjoying your astounding write-ups. Moreover, I’ve got shared your blog inside our myspace. 減肥藥
Oct 15, 2024 03:59:21 AM
Spot lets start on this write-up, I actually think this fabulous website needs a lot more consideration. I’ll apt to be once more to see a lot more, many thanks that info. NUSTABET