常见的几种搜索算法

ゝ一纸荒年。 2023-02-17 02:16 18阅读 0赞

### 目录 ###

*   *   *  广度优先搜索（BFS）
         *  深度优先搜索（DFS）
         *  爬山法（Hill Climbing）
         *  最佳优先算法（Best-first search strategy）
         *  回溯法 （Backtracking）
         *  分支限界算法（Branch-and-bound Search Algorithm）
         *  A\*算法

### 广度优先搜索（BFS） ###

广度优先搜索算法（Breadth-First Search，BFS）是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

类似树的按层遍历，其过程为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2……Vit，并均标记为已访问过，然后再按照Vi1、Vi2……Vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。

### 深度优先搜索（DFS） ###

如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。

它的基本思想是：为了求得问题的解，先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。深度优先搜索的实现方式可以采用递归或者栈来实现。

由此可见，把通常问题转化为树的问题是至关重要的一步，完成了树的转换基本完成了问题求解。

1.  减少节点数，思想：尽可能减少生成的节点数
2.  定制回溯边界，思想：定制回溯边界条件，剪掉不可能得到最优解的子树

在很多情况下，我们已经找到了一组比较好的解。但是计算机仍然会义无返顾地去搜索比它更“劣”的其他解，搜索到后也只能回溯。为了避免出现这种情况，我们需要灵活地去定制回溯搜索的边界。

![在这里插入图片描述][Center]  
通过上图来加深了解，比方说 8 是出口，1是出发点，2 ， 5 ， 6 ， 9 是第一处分岔口， 假如我们选择 2 ， 然后 3 ， 4成为第二个分岔口，我们随便选择 3 ，发现是死胡同，然后返回上一个分岔口 2 ，再选择 4 ， 结果又是死胡同，我们又返回 2 ，发现 2 没有别的路了， 然后返回 1 ， 再走别的路， 直到走到 8 。

### 爬山法（Hill Climbing） ###

DFS的变形，不同的是每次选择的是最优的一个子结点，即局部最优解

例如，对于8数码问题，设置一个函数表示放错位置的数目，每次选择子结点中放错最少的结点

步骤：

> 1.建立一个栈，将根结点放入栈
> 
> 2.判断栈顶元素是否是目标结点，如果是，算法结束，如果不是，进入第三步
> 
> 3.栈顶元素出栈，根据评估函数计算的顺序将此结点的子结点入栈
> 
> 4.如果栈空，则输出失败，否则，进入第二步

### 最佳优先算法（Best-first search strategy） ###

是DFS和BFS的结合

每次找到的是所有结点中最好估计值的那个结点

找到的是全局最优解

步骤：

> 1.根据评估函数建立一个堆（或用优先队列），将根结点放入堆中  
> 2.判断栈顶元素是否是目标结点，如果是，算法结束，如果不是，进入第三步  
> 3.移出堆顶元素结点，将此结点的所有子结点加入堆  
> 4.如果堆空，输出失败，否则，进入第二步

### 回溯法 （Backtracking） ###

找到所有选择，走不通则回溯

假定问题的解是一个向量(a1,a2,a3,…,an)，其中的每个元素ai都是问题的一个元素

步骤：

> 建立一个问题的部分解v=(a1,a2,…,ak)  
> 若这个部分解是可行解，则继续，若不是可行解，删除ak，加入ak情况的另一种可能  
> 若ak的可能已经遍历完，回溯并寻找ak-1的下一个可能

### 分支限界算法（Branch-and-bound Search Algorithm） ###

**分支限界法与回溯法的区别：**

1.  求解目标不同 ：

*  回溯法的求解目标是找出解空间树中满足约束条件的所有解
 *  分支限界法的求解目标则是尽快找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解
 *  分支限界法通常用于解决离散值的最优化问题

1.  搜索方式不同 ：

*  回溯法以深度优先的方式（遍历结点）搜索解空间树
 *  分支限界法以广度优先或最小耗费优先的方式搜索解空间树

1.  对扩展结点的扩展方式不同 ：

*  分支限界法中，每一个活结点只有一次机会成为扩展结点
 *  活结点一旦成为扩展结点，就一次性产生其所有儿子结点

1.  存储空间的要求不同 ：

*  分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大

### A\*算法 ###

个人感觉类似最佳优先算法，都是维护一个优先队列或堆，将结点按照某个值优先的情况放进去，不同的是这次需要一个估计函数h(n)

算法思想：对于优先队列，每取出一个结点n，将他的所有儿子结点n’放入优先队列，优先级由函数f(n)计算出

> g(n)：起点到结点n的代价

> h(n)：结点n到终点的估计代价

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

A\*算法是一种启发式算法

设h\*(n)为结点n到目标结点的实际最小代价

只要h(n)<=h\*(n)，那么代价就不会被高估，这个算法就可以找出最优解

A\*算法使用最佳优先策略，用来解决优化问题

步骤：

> 1.把起点放入优先队列  
> 2.重复如下过程：  
> 取出优先级最高的结点n，即f(n)最小的结点，作为当前要处理的结点  
> 将这个结点放入一个close表中，这个表储存父结点子结点等信息  
> 对于此结点可达的结点n’：  
> ①若这个结点不在队列中，计算g(n’),h(n’),f(n’)，将其加入队列，并将n设为n’的父亲  
> ②若n’在队列中，计算由n到n’的g(n’)值，更小的g(n’)意味着这是更好的路径，如果g(n’)更小，则将n设为n’的父亲，并重新计算g(n’)和f(n’)  
> 停止，当：  
> ①终点被找到  
> ②队列为空，此时查找失败  
> 3.保存路径，从终点开始，沿着父结点移动至起点，即为路径

[Center]: https://img-blog.csdn.net/20170724142249027?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTFBMX2hhY2tlcg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center