搜索算法的一些简介和理解

1、概述：

　　搜索算法是我们经常要用到的算法，比如深度优先搜索、广度优先搜索算法等等，当然搜索算法千变万化，往往根据实际应用会加一些优化等等。例如，A*算法就是加了启发函数的广度优先搜索。回溯算法解决四皇后问题就可以看成加了一个估计函数深度优先搜索。

下面会介绍深度优先搜索，广度优先搜索，A*算法等等。

2、深度优先搜索（DFS）：

　　搜索算法的要点有三个，（1）初始状态 （2）扩展新状态  （3）如果为目标状态结束否则重复（2）。而深度优先搜索的扩展新状态的方式是优先扩展新产生的状态，而广度优先搜索依次扩展接近初始状态的状态。

　　基本思想为：对每一个可能的分支路径深入到不能再深入为止然后回溯其他路径继续深入，而且每个节点只能访问一次。这种方式的搜索适用于尽快找到一个解。

　　上图为一个八码难题图搜索的过程，从初始状态一直搜索到结束状态搜索了所有的情况，这种穷举的方式非常地不够高效，下面会介绍一种A*算解决这种贪婪的搜索方法。

适用范围:常常用于遍历图找到一个解，也可以利用与拓扑排序和找到关键路径等图算法中等。

邻接矩阵伪码：

邻接链表伪码：

2、广度优先搜索

　　跟深度优先搜索的不同是，每次扩展新状态的时候是依次访问接近初始状态的后续节点。

邻接矩阵伪码：

邻接矩阵伪码：

3.A*算法

　　A*算法其实是一种启发式搜索算法。A*算法的例子挺多的，最典型的有游戏人物自动寻找路径，解决八码问题等等。所谓启发式搜索算法就是按照一个估价函数的规则决定下一个状态搜索路径，按照这种方式缩小了搜索的路径量。

　　估价函数：f(n) = g(n) + h(n) ,f(n)是估价函数，g(n)是起点到终点的最短路径值，h(n)是n到目标的最断路经的启发值.

　　当然估价函数要满足可采纳的条件，按照这个规则搜索可以找到最短的搜索路径并且能找到解。另外A(n)<A*(n)，意思是f（n）估价函数的值要小于实际需要搜索的次数。　　

　　不过对于启发函数