前言
最近研究路径规划问题，看了一大堆的算法：爬山算法、模拟退火算法、深度优先搜索、广度优先搜索、Dijkstra算法、Floyd算法、A星算法、prim和kruskal算法等等等等。看得太多感觉头都有点大了，所以希望乘着这个机会把这些零散的算法整理一下。
不同类型的搜索
一直以来，我就没有理清楚过这些算法之间的关系，今天仔细分析，才发现原来这些算法都有一个共同的性质，那就是搜索。不过很快我又发现，我说了等于白说，因为好像绝大多数问题都是能看做是搜索问题，只不过他们搜索的对象不一样，搜索的目标不一样。所以我暂且我就以搜索为线索，从搜索对象和搜索目标这两个角度来分析。
1. 不同对象的搜索
从搜索对象来看，我们发现针对不同的搜索对象其难易度是天差地别。我们将搜索对象抽象成我们常用的数据结构来分析：
- 线性表：由于结构简单、所以搜索算法也简单，特别是有序的线性表，搜索效率会非常高；不过我们也要看到在存储结构上的差异，使得不同的线性表搜索的方法有所差异。如：有序的数组可以用二分查找，但是链表就只能顺序搜索了。
- 树：树的结构比线性表要复杂，所以搜索的方法也开始多而复杂起来，笼统来讲树的搜索可分两类：深度优先和广度优先。树的结构虽然复杂，但是由于其结构的灵活性和规整性，它能够综合顺序存储线性表和链式存储线性表各自的优点。因此前人发明了很多特殊结构的树，特别是平衡查找二叉树。这些特殊结构的二叉树在搜索时也可以采用通用的深度优先和广度优先，但是结合它们自身结构的特殊性质能达到更优秀的性能。
- 图：在基本的数据结构中图是最复杂的，图又有有向图、无向图、带权图等等之分。由于图也可以看做树的推广所以深度优先和广度优先也是图的通用搜索方法，但是在结构复杂的图中这种通用的方法往往效率太低，所以才出现个各种各样的图搜索算法，当然他们的搜索目标也可能不一样。
另外还需要额外提及的一类搜索算法，这类算法通常不关心被测对象的特殊结构，而是以最通用目标去设计，这类算法通常被归到人工智能领域。其中上面提到的基本的深度优先和广度优先搜索就属于这一类，所以所有类型的树所有的种类图都能使用它来搜索。除了这两种最基本搜索外，还有以下两种比较常用的算法（其实属于这一类的还有很多，这里就直选两种简单的）。
Hill Climbing（爬山算法）：爬山算法是一种非常简单的贪心算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。
Simulated Annealing（模拟退火算法）：模拟退火算法对爬山算法进行了一定的优化，它除了向领域空间的更优解移动，也能提供一定几率向更差的领域空间去移动，这样能够让算法有机会跳出局部最小值。这个向更差的地方移动的概率就是模拟退火后物体温度降低的变化情况（e的指数下降），当温度越低，向更差地点移动的概率越小，温度低于下限结束搜索。模拟退火算法是一种随机算法，并不一定能找到全局的最优解，可以比较快的找到问题的近似最优解。
2. 不同搜索的搜索
从实际问题来看搜索的目标太多了，不同的问题有不同的搜索目标，所以我就将其分类为几种常见的类型（也许不严谨但是很典型）：
- 搜索特殊个体：如最大值、最小值等等
- 搜索特殊结构：如特定结构的字符串搜索
- 搜索特殊关系：如图的最短路径、图的最小生成树
从以上可以看出图的搜索是最多样、最复杂的，但是在实际的问题中的对象往往都是以图为模型很复杂的结构，所以下面对图的各种搜索算法做详细的讨论。
图的各种搜索算法
图的复杂性在与它其中的每一个元素（端点）与其他各个元素之间的链接关系（边），因此在图的搜索中单独搜索图中的端点是比较单一，但是只要和边以及其他端点联系起来就变得丰富多彩起来。
1. 最短路径
最短路径问题是图在应用最常见的问题之一，最短路径问题是在图两个端点的路径搜索的基础上，加上了一个最短长度的约束。最短路径的求解有很多经典的算法，不过它们也有各自的使用条件。
- Dijkstra算法（迪杰斯特拉算法）：能够求解单源最短路径，要求边的权重不能为负数，一般具有O(N2)的时间复杂度。Dijkstra算法思路是：利用贪心策略，从起点开始，向外搜索，一次搜索选择整体路径最短的端点作为新的搜索点，同时更新以搜索过的节点到起点的最短路径（在搜索过程中会依次比较，各个以搜端点一直记录当前到起点的最短路径），直到找到终点或搜索完所有端点。
- Floyd算法（弗洛伊德算法）：能够求解多源最短路径，多源最短路程是求任意两个端点之间的最短路径，可以正确处理负权边的问题，时间复杂度为O(N3)，空间复杂度为O(N2)。Floyd算法是典型的动态规划，它的思路是：从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离
- Bellman-Ford算法：和Dijkstra算法一样处理单源最短路径问题，但是它能够解决负权边的情况，采用动态规划（Dynamic Programming）进行设计，实现的时间复杂度为 O(VxE)，其中 V 为顶点数量，E 为边的数量。其算法思路为：对每一个顶点v，设置变量dis(v)，意义是源点到v的最短路径。对每一条边做v－1次松弛操作，所谓松弛操作：对于边（u,v）如果dis(v)>dis(u)+a(u,v)，那么dis(v)＝dis(u)+dis(u,v)。
另外还有SPFA算法、拓扑序列算法就不都列举了。在最短路径搜索中还有一类算法式启发式的，最典型的就是A*了。
- A*算法 : 所谓启发式，不属于问题直接的逻辑推理，而是利用经验和其他信息来探索和尝试来解决问题。A*也可以被归到人工智能搜索的领域，不过它一般用于地图搜索居多（满足欧式几何），对于一般的图则需要更强的条件来约束，启发式的方法才能有效，搜索到的路径才能保证是最短路径。A*的启发方法是利用地图信息找到一个估计当前点到到目标点的路程函数，同时记录当前点到起始点的距离，用两者之和作为当前最优估计，从而依次找到目标点。所以总体看来，A*算法的难点在于如何选择启发式函数，通常最简单的地图搜索的启发式估计函数可以直接定义为当前点坐标到目标点坐标的直线距离。
2. 最小生成树
图的最小生成树为题是指：在原图中去除多余的边但能保持所有结点连通的最少的边的构造，新的图是原图的子图。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。
kruskal算法（克鲁斯卡尔算法）：此算法可以称为“加边法”，初始最小生成树边数为0，每次选择最小的边，将所选边和其顶点加入到最小生成树的边集合里，然后选择次小的边加入，依次按边的权重大小选择，直到覆盖到所有的顶点。
prim算法（普里姆算法）：此算法可以称为“加点法”，算法从某一个顶点s开始，选择与其相连接的最小的边，将边的另一个顶点加入最小树，然后以这个顶点为基点找与其相连的最短边，这样逐渐覆盖整个连通网的所有顶点。