图像处理十五个经典算法的研究与总结

1

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

作者：July

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

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

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

声明：版权所有，侵权定究。

系列和相关算法文章。

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

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

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

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

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

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

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

文章：

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

三、动态规划算法

四、BFS 和 DFS 优先搜索算法

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

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

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

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

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

七、遗传算法 透析 GA 本质

八、再谈启发式搜索算法

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

2

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

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

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

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

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

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

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

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

注解

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

一、A*搜索算法

作者：July、二零一一年一月

博主说明：

1、本经典算法研究系列，此系列文章写的不够好之处，还望见谅。

3

heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics,

领域得到了广泛的应用。

启发式搜索算法

要理解 A*搜寻算法，还得从启发式搜索算法开始谈起。

所谓启发式搜索，就在于当前搜索结点往下选择下一步结点时，可以通过一个启发函数

来进行选择，选择代价最少的结点作为下一步搜索结点而跳转其上（遇到有一个以上代价最

少的结点，不妨选距离当前搜索点最近一次展开的搜索点进行下一步搜索）。

DFS 和 BFS 在展开子结点时均属于盲目型搜索，也就是说，它不会选择哪个结点在下

一次搜索中更优而去跳转到该结点进行下一步的搜索。在运气不好的情形中，均需要试探完

整个解集空间, 显然，只能适用于问题规模不大的搜索问题中。

而与 DFS,BFS 不同的是，一个经过仔细设计的启发函数，往往在很快的时间内就可得

到一个搜索问题的最优解，对于 NP 问题，亦可在多项式时间内得到一个较优解。是的，关

键就是如何设计这个启发函数。

f(n)=g(n)+h(n)

其中 f(n)是每个可能试探点的估值，它有两部分组成：

一部分，为 g(n)，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深

度来表示）。

另一部分，即 h(n)，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的

估值，h(n)设计的好坏，直接影响着具有此种启发式函数的启发式算法的是否能称为 A*算

法。

一种具有 f(n)=g(n)+h(n)策略的启发式算法能成为 A*算法的充分条件是：

1、搜索树上存在着从起始点到终了点的最优路径。

2、问题域是有限的。

的难能可贵了。

不过，对于图的最优路径搜索和八数码问题，有些相关策略 h(n)不仅很好理解，而且已

经在理论上证明是满足条件 4 的，从而为这个算法的推广起到了决定性的作用。

且 h(n)距离 h*(n)的呈度不能过大，否则 h(n)就没有过强的区分能力，算法效率并不会

4

V3、V4->目标顶点 V5 的最短路径。

//是的，图片是引用 rickone 的。

通过上图，我们可以看出：：A*算法最为核心的过程，就在每次选择下一个当前搜索点

为止。

A*算法与广度、深度优先和 Dijkstra 算法的联系就在于：当 g(n)=0 时，该算法类似于

DFS，当 h(n)=0 时，该算法类似于 BFS。且同时，如果 h(n)为 0，只需求出 g(n)，即求出起

点到任意顶点 n 的最短路径，则转化为单源最短路径问题，即 Dijkstra 算法。这一点，可以

5

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)

while openset is not empty //若 OPEN 表不为空

x := the node in openset having the lowest f_score[] value //x 为 OPEN 表中最小的

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

return failure

function reconstruct_path(came_from,current_node)