广度优先搜索（广度优先搜索c++代码）



①深度搜索（DFS）实际上是一个类似枚举的搜索尝试过程，主要是在搜素尝试过程中寻找问题的解，当发现已满足求解条件时，就“回溯”返回，尝试别的路径。从一条路往前走，能进则进，不能进则退回来，换一条路再试。

题目：从（1.0）位置出发，如果能走到出口（7，8）则输出1，否则输出0。

迷宫中，常用1代表该格子有路线，0代表有障碍物。所以只需要判断maze[i][j]==1即可。

使用递归的思想，从起点出发，每个点都可以向尝试向上下左右移动，即一个点，分叉成4条路，但是每条路都需判断一下是否可行。（回溯用于计算多少条不同路径走到终点时，需要回溯该点，例如上图有个圈，可从不同的路径走到终点。）

②广度优先搜索（Breadth-First-Search，简称BFS），又称宽度优先算法。它采用的是一种地毯式层层推进的搜索策略，即：从起始顶点开始从近到远依次搜索，直到找到目标顶点。

由于BFS是以先进先出的方式遍历顶点，因此，可以使用队列（queue）存储已经被搜索、相连顶点还未被搜索的顶点。

题目：图如上，从（1，0）出发，到达（7，8）最少走了多少步？

思路：如上图：从（1，0）点出发，把上下左右的点都遍历一次，能走的点添加进队列里。直到（5，2），把（5，3）（5，4）添加进队列。由于队列关系，先遍历（5，3）接下来的可行点，再遍历（5，4）的下一步，依次添加。

③记忆化搜索

记忆化搜索（Memoization Search）：是一种通过存储已经遍历过的状态信息，从而避免对同一状态重复遍历的搜索算法，常用数组存储。

斐波那契数列：

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/cjjbc/12021.html