一、宽度优先搜索(breadth-first search)

1.定义
    如果搜索是以接近起始节点的程度依次扩展节点的,那么这种搜索就叫做宽度优先搜索。 自动控制网www.eadianqi.com版权所有

2.特点
    这种搜索是逐层进行的,在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。 自动控制网www.eadianqi.com版权所有

3.宽度优先搜索算法
    (1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点,则求得一个解答)。
    (2) OPEN是个空表,则没有解,失败退出;否则继续。
    (3) 把第一个节点(节点n)从OPEN表移出,并把它放入CLOSED的扩展节点表中。
    (4) 扩展节点n。如果没有后继节点,则转向上述第(2)步。
    (5) 把n的所有后继节点放到OPEN表的末端,并提供从这些后继节点回到n的指针。
    (6) 如果n的任一后继节点是目标节点,则找到一个解答,成功退出;否则转向(2)。

4.宽度优先搜索方法分析
    宽度优先搜索是图搜索一般过程的特殊情况,将图搜索一般过程中的第(8)步具体化为本算法中的第(5)步,这实际是将OPEN表作为“先进先出”的队列进行操作。
    宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径;这棵搜索树提供了所有存在的路径(如果没有路径存在,那么对有限图来说,我们就说该法失败退出;对于无限图来说,则永远不会终止)。 本文来自www.eadianqi.com

5.例
    把宽度优先搜索应用于八数码难题时所生成的搜索树,这个问题就是要把初始棋局变为如下目标棋局的问题:

自动控制网www.eadianqi.com版权所有

二、 深度优先搜索(depth-first search) 本文来自www.eadianqi.com

1.定义
    如果搜索时首先扩展最新产生的(即最深的)节点,这种搜索就叫做深度优先搜索。

2.特点
    扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行,只有当搜索到达一个没有后裔的状态时,它才考虑另一条替代的路径。

自动控制网www.eadianqi.com版权所有

3.深度界限
    为了避免考虑太长的路径,往往给出一个节点扩展的最大深度——深度界限。任何节点如果达到了深度界限,那么都将把它们作为没有后继节点处理。

自动控制网www.eadianqi.com版权所有

4.含有深度界限的深度优先搜索算法
    请同学们课后自学,并回答课后思考题。

本文来自www.eadianqi.com

思考  有界深度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径吗? 本文来自www.eadianqi.com

三、等代价搜索(depth-first search) 本文来自www.eadianqi.com

1.定义
    宽度优先搜索可被推广用来解决寻找从起始状态至目标状态的具有最小代价的路径问题,这种推广了的宽度优先搜索算法叫做等代价搜索算法。 本文来自www.eadianqi.com

2.等代价搜索中的几个记号
    起始节点记为S;
    从节点i到它的后继节点j的连接弧线代价记为c(i,j);
    从起始节点S到任一节点i的路径代价记为g(i)。

本文来自www.eadianqi.com

3.等代价搜索算法
    请同学们课后认真阅读本算法,指出与宽度优先、深度优先算法有何特别之处。

4.等代价搜索方法分析
    如果所有的连接弧线具有相等的代价,那么等代价算法就简化为宽度优先搜索算法。

本文来自www.eadianqi.com