BFS详解

广度优先搜索详解

1. 也称宽度优先搜索，顾名思义，就是将一棵树一层一层往下搜。算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。BFS是一种完备策略，即只要问题有解，它就一定可以找到解。并且，广度优先搜索找到的解，还一定是路径最短的解。但是它盲目性较大，尤其是当目标节点距初始节点较远时，将产生许多无用的节点，因此其搜索效率较低。需要保存所有扩展出的状态，占用的空间大。

一般需求最优解的时候用广搜。

搜索过程是：从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。

假设有两个表：Open表存放待处理节点，Closed表存放处理完节点

Open表中的节点总是按进入的先后排序，先进入Open表的节点排在前面，后进入Open表的节点排在后面。

广度优先搜索算法如下：（用 QUEUE）

(1) 把初始节点S0放入Open表中；

(2) 如果Open表为空，则问题无解，失败退出；

(3) 把Open表的第一个节点取出放入Closed表，并记该节点为n；

(4) 考察节点n是否为目标节点。若是，则得到问题的解，成功退出；

(5) 若节点n不可扩展，则转第(2)步；

(6) 扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。

代码框架：

BFS()

{

初始化队列

while(队列不为空且未找到目标节点)

{

取队首节点扩展，并将扩展出的节点放入队尾；

必要时要记住每个节点的父节点；

}

Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法。

2. 判重

新扩展出的节点如果和以前扩展出的节点相同，则则个新节点就不必再考虑。设定判重的方法的时候要注意时间和空间的代价。

方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。（ 228< 99=387,420,489 <229）

判重需要一个标志位序列，每个状态对应于标志位序列中的1位，标志位为0表示该状态尚未扩展，为1则说明已经扩展过了

标志位序列可以用字符数组存放。数组的每个元素存放8个状态的标志位。位序列最多需要99位，因此存放位序列的数组需要99/8 + 1个字节 48,427,562字节

如果某个状态对应于一个9进制数a,则其标志位就是标志位序列中的第a位（其所属的数组元素下标是a/8)

方案二：为节点编号

把每个节点都看一个排列，以此排列在全部排列中的位置作为其编号

排列总数：9!=362880

只需要一个整数(4字节)即可存下一个节点

判重用的标志数组只需要362,880字节即可。

此方案比方案1省空间

此方案需要编写给定排列求序号和给定序号求排列的函数，这些函数的执行速度慢于字符串形式的9进制数到其整型值的互相转换函数。

时间与空间的权衡

对于状态数较小的问题，可以用最直接的方式编码以空间换时间，

对于状态数太大的问题，需要利用好的编码方法以时间换空间。

3. 改进

双向广度优先搜索：从两个方向以广度优先的顺序同时扩展。

DBFS算法从两个方向以广度优先的顺序同时扩展，一个是从起始节点开始扩展，另一个是从目的节点扩展，直到一个扩展队列中出现另外一个队列中已经扩展的节点，也就相当于两个扩展方向出现了交点，那么可以认为我们找到了一条路径。DBFS算法相对于BFS算法来说，由于采用了从两个跟开始扩展的方式，搜索树的深度得到了明显的减少，所以在算法的时间复杂度和空间复杂度上都有较大的优势！

DBFS的框架

一、主控函数:

void solve()

{

1. 将起始节点放入队列q1,将目的节点放入队列q2；

2. 当两个队列都未空时，作如下循环：

1) 如果队列q1里的未处理节点比q2中的少（即tail[0]-head[0] < tail[1]-head[1]),则扩展（expand()）队列q1；

2) 否则扩展（expand()）队列q2 (即tail[0]-head[0] >= tail[1]-head[1]时)；

3. 如果队列q1未空，循环扩展（expand()）q1直到为空；

4. 如果队列q2未空，循环扩展（expand()）q2直到为空；

}

二、扩展函数

int expand(i) //其中i为队列的编号(表示q0或者q1)

{

取队列qi的头结点H；

对头节点H的每一个相邻节点adj，作如下循环：

1 如果adj已经在队列qi之前的某个位置出现，则

抛弃节点adj；

2 如果adj在队列qi中不存在[函数 isduplicate(i)]

1）将adj放入队列qi；

2) 如果adj 在队列(q(1-i))，也就是另外一个

队列中出现[函数 isintersect()]；

输出找到路径；

}

三、判断当前扩展出的节点是否在另外一个队列出现，也就是判断相交的函数：

int isintersect(i,j) //i为队列编号，j为当前节点在队列中的指针

{

遍历队列,判断是否存在

}

//【线性遍历的时间复杂度为O（N)，如果用HashTable优化，时间复杂度可以降到O(1)】

A*：启发式搜索搜索

A*算法基本上与BFS算法相同，但是在扩展出一结点后，要根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。

估价函数： f'(n) = g'(n) + h'(n) 这里f'(n)是估价函数，g'(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h'(n)是n到目标的最短路经的启发值。

由于这个f‘(n)其实是无法预先知道的，所以实际上使用“不在位”数和当前层数之和。

A*算法的基本步骤

建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。

取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。

检查扩展的新结点是否与队列中的结点重复

若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；

若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。

如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针

如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。

例子解析：

sicily1050

要求：给出5个数和一个目标数，求对5个数用加减乘除四种方法任意计算，能得到的最接近目标数的数。

方法：使用广度搜索，在广搜开始前，先比较当前这5个数中离目标数最接近的数，是否为目前得到的最近距离，是就将最近距离更新，并记录当前这个得到最近距离的数。然后开始广搜：从第一个数开始，计算第一个数和之后每一个数进行加减乘除后得到的值替换为第一个数，然后将第二个数标为已访问，再重复这个广搜过程。

最后得到的那个得到最近距离的数，就是要求的答案。

广搜代码：

这里的判重使用的是一个数组，来标记对应的5个数是否已经被访问。当回退时，记得将标记还原为未访问。

sicily 1444

每次改变一个数字，且每次改变后的数依然是素数，找出一个四位素数最少经过几次变换可以得到另一个四位素数。

1. 建素数表

isprime[0] = isprime[1] = false;

for(i = 2; i <= 100; i++)

for(j = i; i*j <= 10000; j++)

if(isprime[i])

isprime[i*j] = false;

2. bfs过程

巴特西

BFS详解

最新文章

热门文章