没有合适的资源?快使用搜索试试~ 我知道了~
首页经典算法研究集锦:15个核心技术深度解析
经典算法研究集锦:15个核心技术深度解析
需积分: 10 9 下载量 118 浏览量
更新于2024-07-18
收藏 13.12MB PDF 举报
"《十五个经典算法研究与总结》是由作者July于2010年12月末至2011年12月期间创作的一系列原创作品,旨在深入研究和讲解15个基础且重要的经典算法,包括A*搜索、Dijkstra最短路径算法、动态规划、广度优先搜索(BFS)与深度优先搜索(DFS)、红黑树、KMP字符串匹配、遗传算法、启发式搜索、SIFT图像特征提取以及傅立叶变换等。这些算法覆盖了图论、数据结构、搜索算法、字符串处理、机器学习等多个领域。 作者首先介绍了A*搜索算法,通过性能比较探讨其应用价值,随后详尽解析了Dijkstra算法,从基本原理到实际实现,甚至涉及到与Fibonacci堆和堆数据结构的结合。动态规划算法章节深入剖析了其在解决优化问题中的核心作用。BFS和DFS作为基础搜索策略,被逐一介绍并对比。 红黑树部分是系列中的亮点,不仅有理论讲解,还有六个篇幅详尽的文章,成为国内最全面的红黑树教程。KMP算法则通过一系列文章从基础到进阶,讲解了其原理和变种BM算法。遗传算法和启发式搜索同样被深入探讨,展示了它们在优化问题中的实用性和灵活性。 此外,还有图像特征提取技术SIFT的介绍,这是计算机视觉领域的重要工具。整个系列共计31篇文章,不仅包含算法理论,还提供了具体的编程实现,适合算法爱好者和程序员深入学习和实践。作者鼓励读者在阅读过程中提出疑问,可通过博客留言或邮件交流,共同提升算法理解和技能。" 这个系列作品是对计算机科学基础知识的深度挖掘,对于想要提升算法技能的读者来说,是一份宝贵的学习资料。每一项算法都被细致地剖析,旨在帮助读者从理论到实践,全面提升对这些经典算法的理解和应用能力。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/10390581/bg10.jpg)
16
1. A* (使用曼哈顿距离)
2. A*(采用欧氏距离)
![](https://csdnimg.cn/release/download_crawler_static/10390581/bg11.jpg)
17
3. A*(利用切比雪夫距离)
4. Dijkstra
![](https://csdnimg.cn/release/download_crawler_static/10390581/bg12.jpg)
18
5. Bi-Directional Breadth-First-Search(双向广度优先搜索) //覆盖范围同上述
Dijkstra 算法一样很大,效率低下。
![](https://csdnimg.cn/release/download_crawler_static/10390581/bg13.jpg)
19
A*搜寻算法的高效之处
如上,是不是对 A*、Dijkstra、双向 BFS 算法各自的性能有了个总体大概的印象列?由
上述演示,我们可以看出,在最短路径搜寻效率上,一般有 A*>Dijkstra、双向 BFS,其中
Dijkstra、双向 BFS 到底哪个算法更优,还得看具体情况。
由上,我们也可以看出,A*搜寻算法的确是一种比较高效的寻路算法。
A*算法最为核心的过程,就在每次选择下一个当前搜索点时,是从所有已探知的但未
搜索过点中(可能是不同层,亦可不在同一条支路上),选取 f 值最小的结点进行展开。
而所有“已探知的但未搜索过点”可以通过一个按 f 值升序的队列(即优先队列)进行排
列。
这样,在整体的搜索过程中,只要按照类似广度优先的算法框架,从优先队列中弹出队
首元素(f 值),对其可能子结点计算 g、h 和 f 值,直到优先队列为空(无解)或找到终止点
为止。
A*算法与广度、深度优先和 Dijkstra 算法的联系就在于:当 g(n)=0 时,该算法类似于
DFS,当 h(n)=0 时,该算法类似于 BFS。且同时,如果 h(n)为 0,只需求出 g(n),即求出起
点到任意顶点 n 的最短路径,则转化为单源最短路径问题,即 Dijkstra 算法。这一点,可以
通过上面的 A*搜索树的具体过程中将 h(n)设为 0 或将 g(n)设为 0 而得到。
BFS、DFS 与 A*搜寻算法的比较
参考了算法驿站上的部分内容:
不管以下论述哪一种搜索,都统一用这样的形式表示:搜索的对象是一个图,它面向一
个问题,不一定有明确的存储形式,但它里面的一个结点都有可能是一个解(可行解),搜
索的目的有两个方面,或者求可行解,或者从可行解集中求最优解。
我们用两张表来进行搜索,一个叫 OPEN 表,表示那些已经展开但还没有访问的结点
集,另一个叫 CLOSE 表,表示那些已经访问的结点集。
蛮力搜索(BFS,DFS)
BFS(Breadth-First-Search 宽度优先搜索)
首先将起始结点放入 OPEN 表,CLOSE 表置空,算法开始时:
1、如果 OPEN 表不为空,从表中开始取一个结点 S,如果为空算法失败
2、S 是目标解吗?是,找到一个解(继续寻找,或终止算法);不是到 3
3、将 S 的所有后继结点展开,就是从 S 可以直接关联的结点(子结点),如果不在 CLOSE
表中,就将它们放入 OPEN 表末尾,而把 S 放入 CLOSE 表,重复算法到 1。
DFS(Depth-First-Search 深度优先搜索)
首先将起始结点放入 OPEN 表,CLOSE 表置空,算法开始时:
1、如果 OPEN 表不为空,从表中开始取一个结点 S,如果为空算法失败
2、S 是目标解吗?是,找到一个解(继续寻找,或终止算法);不是到 3
3、将 S 的所有后继结点展开,就是从 S 可以直接关联的结点(子结点),如果不在 CLOSE
表中,就将它们放入 OPEN 表开始,而把 S 放入 CLOSE 表,重复算法到 1。
是否有看出:上述的 BFS 和 DFS 有什么不同?
仔细观察 OPEN 表中待访问的结点的组织形式,BFS 是从表头取结点,从表尾添加结
点,也就是说 OPEN 表是一个队列,是的,BFS 首先让你想到‘队列’;而 DFS,它是从
OPEN 表头取结点,也从表头添加结点,也就是说 OPEN 表是一个栈!
DFS 用到了栈,所以有一个很好的实现方法,那就是递归,系统栈是计算机程序中极
重要的部分之一。用递归也有个好处就是,在系统栈中只需要存结点最大深度那么大的空间,
![](https://csdnimg.cn/release/download_crawler_static/10390581/bg14.jpg)
20
也就是在展开一个结点的后续结点时可以不用一次全部展开,用一些环境变量记录当前的状
态,在递归调用结束后继续展开。
利用系统栈实现的 DFS
函数 dfs(结点 s)
{
s 超过最大深度了吗?是:相应处理,返回;
s 是目标结点吗?是:相应处理;否则:
{
s 放入 CLOSE 表;
for(c=s.第一个子结点 ;c 不为空 ;c=c.下一个子结点() )
if(c 不在 CLOSE 表中)
dfs(c);递归
}
}
如果指定最大搜索深度为 n,那系统栈最多使用 n 个单位,它相当于有状态指示的 OPEN
表,状态就是 c,在栈里存了前面搜索时的中间变量 c,在后面的递归结束后,c 继续后移。
在象棋等棋类程序中,就是用这样的 DFS 的基本模式搜索棋局局面树的,因为如果用 OPEN
表,有可能还没完成搜索 OPEN 表就暴满了,这是难于控制的情况。
我们说 DFS 和 BFS 都是蛮力搜索,因为它们在搜索到一个结点时,在展开它的后续结
点时,是对它们没有任何‘认识’的,它认为它的孩子们都是一样的‘优秀’,但事实并非
如此,后续结点是有好有坏的。好,就是说它离目标结点‘近’,如果优先处理它,就会更
快的找到目标结点,从而整体上提高搜索性能。
启发式搜索
为了改善上面的算法,我们需要对展开后续结点时对子结点有所了解,这里需要一个估
值函数,估值函数就是评价函数,它用来评价子结点的好坏,因为准确评价是不可能的,所
以称为估值。打个比方,估值函数就像一台显微镜,一双‘慧眼’,它能分辨出看上去一样
的孩子们的手,哪个很脏,有细菌,哪个没有,很干净,然后对那些干净的孩子进行奖励。
这里相当于是需要‘排序’,排序是要有代价的,而花时间做这样的工作会不会对整体搜索
效率有所帮助呢,这完全取决于估值函数。
排序,怎么排?用哪一个?快排吧,qsort!不一定,要看要排多少结点,如果很少,简
单排序法就很 OK 了。看具体情况了。
排序可能是对 OPEN 表整体进行排序,也可以是对后续展开的子结点排序,排序的目
的就是要使程序有启发性,更快的搜出目标解。
如果估值函数只考虑结点的某种性能上的价值,而不考虑深度,比较有名的就是有序搜
索(Ordered-Search),它着重看好能否找出解,而不看解离起始结点的距离(深度)。
如果估值函数考虑了深度,或者是带权距离(从起始结点到目标结点的距离加权和),
那就是 A*,举个问题例子,八数码问题,如果不考虑深度,就是说不要求最少步数,移动
一步就相当于向后多展开一层结点,深度多算一层,如果要求最少步数,那就需要用 A*。
简单的来说 A*就是将估值函数分成两个部分,一个部分是路径价值,另一个部分是一
般性启发价值,合在一起算估整个结点的价值。
从 A*的角度看前面的搜索方法,如果路径价值为 0 就是有序搜索,如果路径价值就用
所在结点到起始结点的距离(深度)表示,而启发值为 0,那就是 BFS 或者 DFS,它们两
剩余462页未读,继续阅读
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/23285431a27843bf8edc84afeeaed0ff_m0_37992398.jpg!1)
m0_37992398
- 粉丝: 0
- 资源: 5
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 贵州煤矿矿井水分类与处理策略:悬浮物、酸性与非酸性
- 醛固酮增多症肾上腺静脉采样对比:ACTH后LR-CAV的最优评估
- 开源云连接传感器监控平台:农业土壤湿度远程监测
- 母婴用品企业年度生产计划线性规划优化模型:实证与应用
- 井下智能变电站:Rogowski线圈电流检测系统的研发与性能验证
- 霍州矿区煤巷稳定性分析及支护策略
- ARM嵌入式系统远程软件更新方案:基于TFTP协议
- 煤炭选煤中汞分布规律与洗选脱汞效果
- 提升码垛机器人性能:拉格朗日动力学模型与滑模模糊控制的应用
- 增强现实技术提升学前手写教学:设计与开发案例
- 不规则工作面沉陷三角剖分算法提升与应用
- 卡尔曼滤波在瞬变电磁干扰压制中的应用研究
- 煤矿安全能力研究:理论与系统构建
- LonWorks总线技术在斜巷运输车辆定位与跑车防护中的应用
- 神东煤炭集团高效煤粉锅炉系统:节能环保新实践
- Ti/SnO2+Sb2Ox/PbO2电极分形维数与电催化性能研究
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)