人工智能 一般搜索原理---盲目搜索.ppt

人工智能及其应用
第六讲一般搜索原理--盲目搜索
搜索:从问题表示到问题解决的求解过程.
:人为给定搜索顺序的无信息搜索.



:根据检测到的信息决定搜索顺序的有信息搜索.
,,*算法
第六讲一般搜索原理--盲目搜索


以接近起始节点的程度依次扩展节点的搜索,搜索过程是逐层进行的,在下一层的任意一个节点进行搜索之前,必须完成本层的所有节点的搜索.
设: OPEN表:未扩展节点表
CLOSED表: 已扩展节点表
第六讲一般搜索原理--盲目搜索
算法
(1)把起始节点放到OPEN表中,若该节点为一目标节点,则得一个解,退出.
(2)如果OPEN表是一个空表,则没有解,.
(3)把第一个节点N从OPEN 表中移出到CLOSED表中.
(4),则goto(2).
(5)把N的所有后继节点放到OPEN表末端,并提供从这些后继节点回到N的指针.
(6)如果N的任一后继节点是目标,则成功退出,否则,goto (2).
第六讲一般搜索原理--盲目搜索
S
L O
M F P Q
N
F
宽度优先搜索示意图
第六讲一般搜索原理--盲目搜索
例如:八数码难题
2 8 3
1 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
2 8
1 4 3
7 6 5
2 8 3
1 4 5
7 6
2 8 3
1 6 4
7 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
7 1 4
6 5
8 3
2 1 4
7 6 5
2 8 3
1 4
7 6 5
宽度优先搜索示意图

扩展最新产生的节点,搜索沿着状态空间某条单一的路径从起始节点向下搜索,结果使得只有搜索到一个没有后裔的状态时,才考虑另一条替代的路径.
问题:当搜索深度很深时,需要控制.
第六讲一般搜索原理--盲目搜索
第六讲一般搜索原理--盲目搜索
算法
(1)把起始节点放到OPEN表中,若该节点为一目标节点,则求得一个解,退出.
(2)如果OPEN表是一个空表,则没有解,.
(3)把第一个节点N从OPEN 表中移出到CLOSED表中.
(4)如果节点N的深度等于最大深度,则goto(2).
(5),,则goto(2).
(6)如果N的任一后继节点是目标,则成功退出,否则,goto (2).
S
L O
M F P Q
N
F
深度优先搜索示意图
第六讲一般搜索原理--盲目搜索
第六讲一般搜索原理--盲目搜索
2 8 3
1 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
2 8
1 4 3
7 6 5
2 8 3
1 4 5
7 6
2 8 3
1 6 4
7 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
7 1 4
6 5
8 3
2 1 4
7 6 5
2 8 3
1 4
7 6 5
深度优先搜索示意图