十五个经典算法研究与总结、目录+索引资源-CSDN文库

4星 · 超过85%的资源需积分: 10 11 浏览量 2013-11-12 22:06:58 上传评论收藏 14.85MB PDF 举报

资源推荐

资源详情

资源评论

十五个经典算法研究与总结

作者：July

时间：2010 年 12 月末-2011 年 12 月。

微博：http://weibo.com/julyweibo

出处：http://blog.csdn.net/v_JULY_v

文档制作者：花明月暗 & 有鱼网 http://www.youyur.com/ＣＥＯ吴超

前言：

本人的原创作品经典算法研究系列，自从１０年１２月末至１１年１２月，写了近一年。

可以这么说，开博头俩个月一直在整理微软等公司的面试题，而后的四个月至今，则断断续

续，除了继续微软面试１００题系列，和程序员编程艺术系列之外，便在写这经典算法研究

系列和相关算法文章。

本经典算法研究系列，涵盖 A*.Dijkstra.DP.BFS/DFS.红黑树.KMP.遗传.启发式搜索.图像

特征提取 SIFT.傅立叶变换.Hash.快速排序.SPFA.快递选择 SELECT 等 15 个经典基础算法，

共计 31 篇文章，包括算法理论的研究与阐述，及其编程的具体实现。很多个算法都后续写

了续集，如第二个算法：Dijkstra 算法，便写了 4 篇文章；sift 算法包括其编译及实现，写

了 5 篇文章；而红黑树系列，则更是最后写了 6 篇文章，成为了国内最为经典的红黑树教程。

OK，任何人有任何问题，欢迎随时在 blog 上留言评论，或来信：zhoulei0907@yahoo.cn

批评指正。谢谢。以下是已经写了的 15 个经典算法集锦，算是一个目录+索引，共计 31 篇

文章：

十五个经典算法研究集锦+目录

一、A*搜索算法

一（续）、A*，Dijkstra，BFS 算法性能比较及 A*算法的应用

二、Dijkstra 算法初探

二（续）、彻底理解 Dijkstra 算法

二（再续）、Dijkstra 算法+fibonacci 堆的逐步 c 实现

二（三续）、Dijkstra 算法+Heap 堆的完整 c 实现源码

三、动态规划算法

四、BFS 和 DFS 优先搜索算法

五、教你透彻了解红黑树（红黑数系列六篇文章之其中两篇）

五（续）、红黑树算法的实现与剖析

六、教你初步了解 KMP 算法、updated （KMP 算法系列三篇文章）

六（续）、从 KMP 算法一步一步谈到 BM 算法

六（三续）、KMP 算法之总结篇（必懂 KMP）

七、遗传算法透析 GA 本质

八、再谈启发式搜索算法

九、图像特征提取与匹配之 SIFT 算法（SIFT 算法系列五篇文章）

九（续）、sift 算法的编译与实现

九（再续）、教你一步一步用 c 语言实现 sift 算法、上

九（再续）、教你一步一步用 c 语言实现 sift 算法、下

九（三续）：SIFT 算法的应用--目标识别之 Bag-of-words 模型

十、从头到尾彻底理解傅里叶变换算法、上

十、从头到尾彻底理解傅里叶变换算法、下

十一、从头到尾彻底解析 Hash 表算法

十一（续）、倒排索引关键词 Hash 不重复编码实践

十二、快速排序算法（快速排序算法 3 篇文章）

十二（续）、快速排序算法的深入分析

十二（再续）：快速排序算法之所有版本的 c/c++实现

十三、通过浙大上机复试试题学 SPFA 算法

十四、快速选择 SELECT 算法的深入分析与实现

十五、多项式乘法与快速傅里叶变换

注解

自从本人写这个算法系列以来，总有不少的朋友问我如何学算法，问我怎么会有那么多

的时间来学算法，在此，我愿回复各位俩句话：1、兴趣。2、没有兴趣的东西一般不会占

用我的时间。

非常感谢，各位对我的支持与关注，谢谢大家。完。

一、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)就没有过强的区分能力，算法效率并不会

通过上面的 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)

剩余462页未读，继续阅读

评论收藏

内容反馈

harderc111

2014-04-27

很好有助于学习
xiyingkejia

2014-01-02

这个资源还好。有助于学习。谢谢。
luxiao6666

2014-07-16

讲的很全面收藏了作为今后基础学习的材料

力都

粉丝: 1
资源: 5

十五个经典算法研究与总结、目录+索引

软件开发中的十五个经典算法研究

十三个经典算法研究与总结、目录+索引

十五个经典算法研究与总结、目录+索引（by_....pdf

十五个经典算法研究与总结、目录+索引（by_....rar

十五个经典算法研究与总结、目录+索引（by_July）定稿版

十五个经典算法研究与总结、目录+索引(定稿版)

十五个经典算法研究与总结、目录

十五个经典算法研究与总结、目录+索引.rar

十五个经典算法研究与总结、目录+索引.zip

十五个经典算法研究与总结、目录+索引（by_....rar_十五个经典算法_经典算法

程序员最常见的笔试面试题合集

大数据应用-基于大数据的推荐算法研究.pptx

大数据位图索引压缩算法研究

算法文档,来看看吧

基于GPU的内存数据库索引技术研究

Qt上位机软件串口通讯，视频源码，免费下载

代码随想录算法PDF.rar

张玉生《C语言程序设计》双色版 C语言程序设计理论教材习题参考答案.pdf

cloud compare用户手册（中文+英文）

CRC8/CRC16/CRC32常见几个标准的算法及C语言实现

STM32F4 ADC采样FFT运算测试代码

第十二届蓝桥杯大赛模拟赛（第三期）.pdf

Qt Qss三套样式文件 qss.zip

C++读取excel数据

点云粗配准算法

2021csp-j初赛试题及答案.docx

基于STM32F103+ADS1292的心率实时显示（串口助手），心电图波形

C++语言程序设计第五版郑莉

点云完全配准算法比较

最新资源