算法-广度优先、深度优先和等代价搜索 - 好文

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

热门工具换一换