没有合适的资源?快使用搜索试试~ 我知道了~
首页十三个经典算法研究与总结、目录+索引
十三个经典算法研究与总结、目录+索引
5星 · 超过95%的资源 需积分: 9 14 下载量 74 浏览量
更新于2023-03-03
评论
收藏 21.11MB PDF 举报
本人的原创作品,经典算法研究系列,自从去年十二月末至今,已写了近四个月,而本人开博还不到半年。可以这么说,开博头俩个月一直在整理微软等公司的面试题,而后的四个月至今,则断断续续,在写此经典算法研究系列。 本经典算法研究系列,如今已写了22篇,13个算法,包括算法理论的研究,算法编程的实现,很多个算法都后续写了续集,如第二个算法:Dijkstra 算法,便写了4篇文章。而红黑树系列,则更是最后写了6篇文章,成为了国内最为经典的红黑树教程。 此过程中,费了不少精力和心血。如在文章的排版上,总是不断的调整,文章内容,也是不断的修正,尤其在一些算法的实现上,则更显复杂与艰难了,如红黑树的c,c++实现,sift算法的步步c 实现等等。而仅此,还远远不够。虽然,我无愧于心:这些个算法,个人认为是网上写的最好的,但还是有个别如KMP算法,还亟待完善。 不过,个人会继续写下去,同时,本BLOG内的此经典算法研究系列,永久更新,永久维护。估计,最后会写将近100篇算法文章。
资源详情
资源评论
资源推荐
十三个经典算法研究与总结、目录+索引
作者:July
时间:二零一零年十二月末------------二零一一年四月初。
邮箱:zhoulei0907@yahoo.cn
微博:http://weibo.com/julyweibo
出处:http://blog.csdn.net/v_JULY_v
声明:版权所有,侵权定究。
前言:
本人的原创作品,经典算法研究系列,自从去年十二月末至今,已写了近四个月,而本
人开博还不到半年。可以这么说,开博头俩个月一直在整理微软等公司的面试题,而后的四
个月至今,则断断续续,在写此经典算法研究系列。
本经典算法研究系列,如今已写了 22 篇,13 个算法,包括算法理论的研究,算法编程
的实现,很多个算法都后续写了续集,如第二个算法:Dijkstra 算法,便写了 4 篇文章。而
红黑树系列,则更是最后写了 6 篇文章,成为了国内最为经典的红黑树教程。
此过程中,费了不少精力和心血。如在文章的排版上,总是不断的调整,文章内容,也
是不断的修正,尤其在一些算法的实现上,则更显复杂与艰难了,如红黑树的 c,c++实现,
sift 算法的步步 c 实现等等。而仅此,还远远不够。虽然,我无愧于心:这些个算法,个人
认为是网上写的最好的,但还是有个别如 KMP 算法,还亟待完善。
不过,个人会继续写下去,同时,本 BLOG 内的此经典算法研究系列,永久更新,永久
维护。估计,最后会写将近 100 篇算法文章。
应众多网友强烈要求,同时也是为了各位以后看着方便,以下是已经写了的十三个算法
集锦,算是一个目录+索引,共计二十二篇文章。任何人有任何问题,欢迎留言评论,或批
评指正。谢谢。以下是十三个经典算法的目录及内容:
十三个经典算法集锦
一、A*搜索算法
一(续)、A*,Dijkstra,BFS 算法性能比较及 A*算法的应用
二、Dijkstra 算法初探
二(续)、彻底理解 Dijkstra 算法
二(再续)、Dijkstra 算法+fibonacci 堆的逐步 c 实现
二(三续)、Dijkstra 算法+Heap 堆的完整 c 实现源码
三、dynamic programming
四、BFS 和 DFS 优先搜索算法
五、红黑树算法的实现与剖析
五(续)、教你透彻了解红黑树
六、教你从头到尾彻底理解 KMP 算法
七、遗传算法 透析 GA 本质
八、再谈启发式搜索算法
九、图像特征提取与匹配之 SIFT 算法
九(续)、sift 算法的编译与实现
九(再续)、教你一步一步用 c 语言实现 sift 算法、上九(再续)、教你一步一步用 c 语言实
现 sift 算法、下
十、从头到尾彻底理解傅里叶变换算法、上
十、从头到尾彻底理解傅里叶变换算法、下
十一、从头到尾彻底解析 Hash 表算法
十二、快速排序算法之所有版本的 c/c++实现
十三、通过浙大上机复试试题学 SPFA 算法
后记
自从本人写这个算法系列以来,总有不少的朋友问我如何学算法,问我怎么会有那么多
的时间来学算法,在此,我愿回复各位俩句话:1、兴趣。2、没有兴趣的东西一般不会占
用我的时间。
非常感谢,各位对我的支持与关注,谢谢大家。完。
版权声明:本人及 CSDN 对本 BLOG 内的此经典算法研究系列,享有全部的版权。
任何人,任何组织或网站转载,必须以超链接形式注明出处。
任何出版社未经本人书面许可,不得出版本博客内任何文章及内容。谢谢。
July、二零一一年四月六日。
一、A*搜索算法
作者:July、二零一一年一月
---------------------------------------------------------------------------------------------------------------------------------
博主说明:
1、本经典算法研究系列,此系列文章写的不够好之处,还望见谅。
2、本经典算法研究系列,系我参考资料,一篇一篇原创所作,转载必须注明作者本人
July 及出处。
3、本经典算法研究系列,精益求精,不断优化,永久更新,永久勘误。
欢迎,各位,与我一同学习探讨,交流研究。
有误之处,不吝指正。
---------------------------------------------------------------------------------------------------------------------------------
引言
1968 年,的一篇论文,“P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the
heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics,
SSC-4(2):100-107, 1968”。从此,一种精巧、高效的算法------A*算法横空出世了,并在相关领
域得到了广泛的应用。
启发式搜索算法
要理解 A*搜寻算法,还得从启发式搜索算法开始谈起。
所谓启发式搜索,就在于当前搜索结点往下选择下一步结点时,可以通过一个启发函数
来进行选择,选择代价最少的结点作为下一步搜索结点而跳转其上(遇到有一个以上代价最
少的结点,不妨选距离当前搜索点最近一次展开的搜索点进行下一步搜索)。
DFS 和 BFS 在展开子结点时均属于盲目型搜索,也就是说,它不会选择哪个结点在下一
次搜索中更优而去跳转到该结点进行下一步的搜索。在运气不好的情形中,均需要试探完整
个解集空间, 显然,只能适用于问题规模不大的搜索问题中。
而与 DFS,BFS 不同的是,一个经过仔细设计的启发函数,往往在很快的时间内就可得到
一个搜索问题的最优解,对于 NP 问题,亦可在多项式时间内得到一个较优解。是的,关键
就是如何设计这个启发函数。
A*搜寻算法
A*搜寻算法,俗称 A 星算法,作为启发式搜索算法中的一种,这是一种在图形平面上,
有多个节点的路径,求出最低通过成本的算法。常用于游戏中的 NPC 的移动计算,或线上
游戏的 BOT 的移动计算上。该算法像 Dijkstra 算法一样,可以找到一条最短路径;也像 BFS
一样,进行启发式的搜索。
A*算法最为核心的部分,就在于它的一个估值函数的设计上:
f(n)=g(n)+h(n)
其中 f(n)是每个可能试探点的估值,它有两部分组成:
一部分,为 g(n),它表示从起始搜索点到当前点的代价(通常用某结点在搜索树中的深
度来表示)。
另一部分,即 h(n),它表示启发式搜索中最为重要的一部分,即当前结点到目标结点的
估值,h(n)设计的好坏,直接影响着具有此种启发式函数的启发式算法的是否能称为 A*算法。
一种具有 f(n)=g(n)+h(n)策略的启发式算法能成为 A*算法的充分条件是:
1、搜索树上存在着从起始点到终了点的最优路径。
2、问题域是有限的。
3、所有结点的子结点的搜索代价值>0。
4、h(n)=<h*(n) (h*(n)为实际问题的代价值)。
当此四个条件都满足时,一个具有 f(n)=g(n)+h(n)策略的启发式算法能成为 A*算法,并
一定能找到最优解。
对于一个搜索问题,显然,条件 1,2,3 都是很容易满足的,而条件 4: h(n)<=h*(n)是需
要精心设计的,由于 h*(n)显然是无法知道的,所以,一个满足条件 4 的启发策略 h(n)就来
的难能可贵了。
不过,对于图的最优路径搜索和八数码问题,有些相关策略 h(n)不仅很好理解,而且已
经在理论上证明是满足条件 4 的,从而为这个算法的推广起到了决定性的作用。
且 h(n)距离 h*(n)的呈度不能过大,否则 h(n)就没有过强的区分能力,算法效率并不会
很高。对一个好的 h(n)的评价是:h(n)在 h*(n)的下界之下,并且尽量接近 h*(n)。
A*搜寻算法的实现
先举一个小小的例子:即求 V0->V5 的路径,V0->V5 的过程中,可以经由 V1,V2,V3,
V4 各点达到目的点 V5。下面的问题,即是求此起始顶点 V0->途径任意顶点 V1、V2、V3、
V4->目标顶点 V5 的最短路径。
//是的,图片是引用 rickone 的。
通过上图,我们可以看出::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 而得到。
A*算法流程:
首先将起始结点 S 放入 OPEN 表,CLOSE 表置空,算法开始时:
1、如果 OPEN 表不为空,从表头取一个结点 n,如果为空算法失败。
2、n 是目标解吗?是,找到一个解(继续寻找,或终止算法)。
3、将 n 的所有后继结点展开,就是从 n 可以直接关联的结点(子结点),如果不在 CLOSE
表中,就将它们放入 OPEN 表,并把 S 放入 CLOSE 表,同时计算每一个后继结点的估价值 f(n),
将 OPEN 表按 f(x)排序,最小的放在表头,重复算法,回到 1。
//OPEN-->CLOSE,起点-->任意顶点 g(n)-->目标顶点 h(n)
closedset := the empty set //已经被估算的节点集合
openset := set containing the initial node //将要被估算的节点集合
g_score[start] := 0 //g(n)
h_score[start] := heuristic_estimate_of_distance(start, goal) //h(n)
f_score[start] := h_score[start]
while openset is not empty //若 OPEN 表不为空
x := the node in openset having the lowest f_score[] value //x 为 OPEN 表中最小的
if x = goal //如果 x 是一个解
return reconstruct_path(came_from,goal) //
remove x from openset
add x to closedset //x 放入
CLSOE 表
for each y in neighbor_nodes(x)
if y in closedset
continue
tentative_g_score := g_score[x] + dist_between(x,y)
if y not in openset
add y to openset
tentative_is_better := true
else if tentative_g_score < g_score[y]
tentative_is_better := true
else
tentative_is_better := false
if tentative_is_better = true
came_from[y] := x
g_score[y] := tentative_g_score
h_score[y] := heuristic_estimate_of_distance(y, goal) //x-->y-->goal
f_score[y] := g_score[y] + h_score[y]
return failure
function reconstruct_path(came_from,current_node)
if came_from[current_node] is set
p = reconstruct_path(came_from,came_from[current_node])
return (p + current_node)
else
return the empty path
与结点写在一起的数值表示那个结点的价值 f(n),当 OPEN 表为空时 CLOSE 表中将求得
剩余345页未读,继续阅读
thjfk
- 粉丝: 11
- 资源: 103
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论2