人工智能盲目搜索三大法则，你要懂！

不需要重新安排OPEN表的搜索叫做无信息搜索或盲目搜索,它包括宽度优先搜索、深度优先搜索和等代价搜索等,盲目搜索只适用于求解比较简单的问题。

宽度优先搜索

如果搜索是以接近起始节点的程度依次扩展节点的,那么这种搜索就叫做宽度优先搜索(breadth-first search),这种搜索是逐层进行的;在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。

宽度优先搜索算法如下:

(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点,则求得一个解答)。

(2)如果OPEN是个空表,则没有解,失败退出;否则继续。

(3)把第一个节点(节点n)从OPEN表移出,并把它放入 CLOSED的扩展节点表中。

(4)扩展节点n。如果没有后继节点,则转向上述第(2)步。

(5)把n的所有后继节点放到OPEN表的末端,并提供从这些后继节点回到n的指针。

(6)如果n的任一个后继节点是个目标节点,则我到一个解答,成功退出;否则转向第(2)步。

宽度优先搜索

深度优先搜索

另一种盲目(无信息)搜索叫做深度优先搜索( depth-first search),在深度优先搜索中,首先扩展最新产生的(即最深的)节点。扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行;只有当搜索到达一个没有后裔的状态时,它才考虑另一条替代的路径。替代路径与前面已经试过的路径的不同之处仅仅在于改变最后n步,而且保持n尽可能小。

对于许多问题,其状态空间搜索树的深度可能为无限深,或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去),往往给出一个节点扩展的最大深度一一深度界限。任何节点如果达到了深度界限,那么都将把它们作为没有后继节点处理。值得说明的是,即使应用了深度界限的规定,所求得的解答路径并不一定就是最短的路径。

深度优先搜索算法如下:

(1)把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点,则得到一个解。

(2)如果OPEN为一空表,则失败退出。

(3)把第一个节点(节点n)从OPEN表移到 CLOSED表。

(4)如果节点n的深度等于最大深度,则转向(2)。

(5)扩展节点m,产生其全部后商,并把它们放入OPEN表的前头。如果没有后,则转向(2)。

(6)如果后继节点中有任一个为目标节点,则求得一个解,成功退出;否则,转向(2)。

深度优先搜索

等代价搜索

有些问题并不要求有应用算符序列为最少的解,而是要求具有某些特性的解。搜索树中每条连接弧线上的有关代价以及随之而求得的具有最小代价的解答路径,与许多这样的广义准则相符合,宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题,这种推广了的宽度优先搜索算法叫做等代价搜索算法。

如果所有的连接弧线具有相等的代价,那么等代价算法就简化为宽度优先搜索算法,在等代价搜索算法中,不是描述沿着等长度路径断层进行的扩展,而是描述沿着等代价路径断层进行的扩展。

等代价搜索算法如下：

(1)把起始节点S放到未扩展节点表OPEN中。如果此起始节点为一目标节点,则求得一个解,否则令g(S)=0。

(2)如果OPEN是个空表,则没有解而失败退出。

(3)从OPEN表中选择一个节点,使其g()为最小。如果有几个节点都合格,那么就要选择一个目标节点作为节点(要是有目标节点的话);否则,就从中选一个作为节点i。把节点i从OPEN表移至扩展节点表 CLOSED中。

(4)如果节点i为目标节点,则求得一个解。

(5)扩展节点i。如果没有后继节点,则转向第(2)步。

(6)对于节点i的每个后继节点j,计算g(j)=g(i)+c(i,j),并把所有后继节点j放进OPEN表。提供回到节点i的指针。

(7)转向第(2)步。

等代价搜索