0.摘要

本文主要介绍三种盲目搜索算法:广度优先、深度优先和等代价搜索。

首先,介绍几个之后会用到的概念:

OPEN表:存放未扩展节点的表格

CLOSE表:存放以扩展节点的表格

 

1.宽度优先搜索

宽度优先搜索(BFS,Breadth First Search。 )又称广度优先搜索,是最简便的图的搜索算法之一。

定义:如果搜索是以接近初始节点的程度一次扩展节点的,那么这种搜索就叫做宽度优先搜索。



算法流程:

step1:把起始节点放到OPEN表中。如果起始节点为目标节点,找到一个解,结束;否则,转step2。

step2:如果OPEN表是空表,则无解,结束;如果不为空,转step3。

step3:把第一个节点(节点n)从OPEN表中移除,并存放到CLOSE表中,转step4。

step4:如果节点n存在后续节点,扩展节点n,转step5;否则,转step2。

step5:把节点n的所有后续节点存放到OPEN表末端,并提供这些后续节点返回到节点n的指针,转step6。

step6:如果节点n的任一后续节点为目标节点,求解完成,结束;否则,转step2。



 

2.深度优先搜索

深度优先搜索(DFS,depth-first search)。在深度优先搜索中,首先扩展的是最新生成的节点(即最深的节点)。

深度优先搜索节点深度:

* 起始节点(即根节点)的深度为0
* 任何其他节点的深度等于其父辈节点深度+1
算法流程:

step1:把起始节点S放到未拓展节点OPEN表。如果此节点为目标节点,则得到一个解,结束;否则,转step2

step2:如果OPEN表为空,则未找到解,结束;否则,转step3

step3::把第一个节点(节点n)从OPEN表移到CLOSE表中,转step4

step4:如果节点n的深度达到最大的深度,转step2

step5:扩展节点n,产生器全部后裔,并把它们放到OPEN表的前端,转step6;如果没有后裔,转step2

step6:如果后继节点有任何一个为目标节点,则求得一个解,结束;否则,转step2



 

3.等代价搜索

等代价搜索(UCS,uniform cost search),又称一致性代价搜索。

在前面的阐述中,我们都假设搜索树的连接的代价是相同的。


但假设问题中的树做一些改变,使得每条连接上都有一定的代价参数,并在问题中给定了起始状态和目标状态。这时候,若我们使用宽度优先搜索,并解决寻找从起始状态到目标状态具有最小代价的路径问题,那么,这种被推广了的宽度优先搜索就称作等代价搜索。



算法流程:

为表述方便,我们做以下规定:

* 把从节点i到它的后继节点j的连接狐仙代价记为c(i,j);
* 把从起始节点S到任一节点i的路径代价记为g(i)
step1:把起始节点S放到未扩展节点表OPEN中。如果起始节点为一目标节点,则求得一个解,结束;否则,令g(s) = 0,转step2

step2:如果OPEN表为空,则表示没有解,结束;否则,转step3


step3:从OPEN表中选择一个节点,使得g(i)最小。如果有几个节点都符合,若存再目标节点,则选择一个目标节点,结束;否则选择一个作为节点i。并把节点i从OPEN表移至CLOSE表中,转step4

step4:如果节点i为目标节点,则求得一个解,结束;否则,转step5

step5:扩展节点i。如果没有后继节点,转step2;否则,转step6

step6:对于节点i的每个后继节点,计算g(i) = g(i) + c(i,j),并把所有后继节点j放在OPEN表中,提供返回到节点i的指针,转step2