July的13个经典算法研究与详解

需积分: 9 50 浏览量更新于2024-07-30 1 收藏 21.11MB PDF 举报

"《13经典算法研究by_July》是由博主July在二零一零年十二月末至二零一一年四月期间创作的一系列深入研究的算法文章集合。该系列作品旨在分享和探讨十三个关键的算法，包括但不限于A*搜索算法、Dijkstra算法、动态规划、广度优先搜索(BFS)和深度优先搜索(DFS)、红黑树、KMP算法、遗传算法以及SIFT图像特征提取等。作者在创作过程中投入了大量的时间和精力，不仅对算法理论进行了详尽的研究，还提供了编程实现的步骤，例如Dijkstra算法的C和C++版本，以及红黑树的逐步实现和详解。 A*搜索算法部分被分为几个章节，不仅对比了A*、Dijkstra和BFS的性能，并且展示了其实际应用。Dijkstra算法是系列中的核心，除了基础介绍外，还涉及了Fibonacci堆和普通堆的不同实现，以及算法的理解深化。动态规划作为优化问题的解决方法，也被详细讲解。 BFS和DFS作为基础图搜索算法，是学习其他算法的基础。红黑树是数据结构的重要组成部分，作者通过一系列文章帮助读者深入理解和实现。KMP算法则是字符串处理中的重要工具，而遗传算法则展示了启发式搜索的另一面。最后，SIFT算法则涉及到计算机视觉领域，用于图像特征提取和匹配。整个系列作品不仅是作者原创思考的结晶，也是对算法理论和实践的系统梳理。尽管作者表示仍有改进的空间，尤其是对于KMP算法，但承诺将继续完善并保持BLOG内经典算法研究系列的长期更新和维护，预计最终将涵盖超过100篇算法文章。博主欢迎读者提出问题和意见，共同提升对这些经典算法的理解。这个目录+索引形式的集锦为读者提供了方便，便于他们按照自己的兴趣和需求进行深入学习。"

2. A*(采用欧氏距离)

3. A*(利用切比雪夫距离)

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 用到了栈，所以有一个很好的实现方法，那就是递归，系统栈是计算机程序中极重

要的部分之一。用递归也有个好处就是，在系统栈中只需要存结点最大深度那么大的空间，

也就是在展开一个结点的后续结点时可以不用一次全部展开，用一些环境变量记录当前的状

态，在递归调用结束后继续展开。

利用系统栈实现的 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，它们两刚

好是个反的，BFS 是从 OPEN 表中选一个深度最小的进行展开，

而 DFS 是从 OPEN 表中选一个深度最大的进行展开。当然只有 BFS 才算是特殊的 A*，

所以 BFS 可以求要求路径最短的问题，只是没有任何启发性。下文稍后，会具体谈 A*搜寻

算法思想。

BFS、DFS、Kruskal、Prim、Dijkstra 算法时间复杂度

上面，既然提到了 A*算法与广度、深度优先搜索算法的联系，那么，下面，也顺便再

比较下 BFS、DFS、Kruskal、Prim、Dijkstra 算法时间复杂度吧：

一般说来，我们知道，BFS，DFS 算法的时间复杂度为 O（V+E），

最小生成树算法 Kruskal、Prim 算法的时间复杂度为 O（E*lgV）。

而 Prim 算法若采用斐波那契堆实现的话，算法时间复杂度为 O（E+V*lgV），当|V|<<|E|

时，E+V*lgV 是一个较大的改进。

//|V|<<|E|，=>O（E+V*lgV） << O（E*lgV），对吧。:D

Dijkstra 算法，斐波纳契堆用作优先队列时，算法时间复杂度为 O（V*lgV + E）。

//看到了吧，与 Prim 算法采用斐波那契堆实现时，的算法时间复杂度是一样的。

所以我们，说，BFS、Prime、Dijkstra 算法是有相似之处的，单从各算法的时间复杂度

比较看，就可窥之一二。

A*搜寻算法的思想

ok，既然，A*搜寻算法作为是一种好的、高效的寻路算法，咱们就来想办法实现它吧。

实现一个算法，首先得明确它的算法思想，以及算法的步骤与流程，从我之前的一篇文

章中，可以了解到：

A*算法，作为启发式算法中很重要的一种，被广泛应用在最优路径求解和一些策略设

计的问题中。

而 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 的，从而为这个算法的推广起到了决定性的作用。

A*搜寻算法的应用

剩余345页未读，继续阅读

wjsdwbw

粉丝: 1
资源: 9

July的13个经典算法研究与详解

七月分享：13个经典算法深度解析与实战

经典算法深度解析与实现

July的微软面试100题系列：数据结构与算法解析

经典算法研究by_July

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

最新十五个经典算法研究与总结之高清完整PDF文档[带目录+标签]by_July

程序员编程艺术by_July 修订稿最终版

程序员编程艺术第一~三十七章集锦by_July

微软面试100题系列之高清完整版PDF文档[带目录+标签]by_July

程序员编程艺术第一~二十七章集锦与总结（教你如何编程）(by_July)定稿版

最新资源