文档介绍：1
第三章搜索推理技术
图搜索策略
盲目搜索
启发式搜索
消解原理
规则演绎系统
产生式系统
系统组织技术
不确定性推理
非单调推理
小结
问题:知识表示有那些方法?知识表示的目的是什么?构建智能系统的关键是什么?
2
图搜索策略
思考:状态空间法的基本特点?基本推理方法?其求解结果是什么?简单回顾实例:猴子与香蕉。
3
用一个四元表列(W,x,Y,z)表示这个问题状态
W 猴子的水平位置
x 当猴子在箱子顶上时取 x = 1;否则取 x = 0
Y 箱子的水平位置
z 当猴子摘到香蕉时取 z=1;否则取 z=0
算符:
Goto(U),
(W,0,Y,z) goto(U) (U,0,Y,z)
Pushbox(V),
(W,0,W,z) pushbox(V) (V,0,V,z)
Climbbox,
(W,0,W,z) climbbox (W,1,W,z)
Grasp,
(c,1,c,0) grasp (c,1,c,1)
图搜索策略
4
(b,1,b,0)
(U,0,b,0)
(V,0,V,0)
(c,1,c,0)
(U,0,V,0)
(c,1,c,1)
(a,0,b,0)
U=b,climbbox
猴子和香蕉问题的状态空间图
提问:人工搜索求解的解答?
目标状态
goto(U)
goto(U)
goto(U)
U=b, pushbox(V)
pushbox(V)
goto(U)
V≠c,climbbox
V=c,climbbox
图搜索策略
5
猴子和香蕉问题自动演示:
猴子
香蕉
箱子
猴子
香蕉
箱子
Ha!Ha!
图搜索策略
思考:计算机的搜索策略?
6
图搜索控制策略:一种在图中寻找路径的方法。
图中每个节点对应一个状态;
每条连线对应一个操作符。
用产生式系统的数据库和规则来标记:
初始节点————初始数据库;
目标节点————目标数据库;
状态图的一条路径问题————求得把一个数据库变换为另一数据库的规则序列问题。
图搜索过程(GraphSearch)
图搜索策略
7
图搜索的一般过程如下:
1)建立一个只含有起始节点S的搜索图G,把S放到一个叫做OPEN 的未扩展节点表中。
2)建立一个叫做CLOSED的已扩展节点表,其初始为空表.
3)LOOP:若OPEN表是空表,则失败退出。
4)选择OPEN表上的第一个节点,把它从OPEN表移出并放进CLOSED表中。称此节点为节点n
5)若n为一目标节点,则有解并成功退出,此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。
图搜索策略
8
6)扩展节点n,同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。
7)对那些未曾在G中出现过的M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员,确定是否需更改通到n的指针方向。对已在CLOSED表上的每个M成员,确定是否需要更改图G中通向它的每个后裔节点的指针方向。
8)按某一任意方式或按某个探试值,重排OPEN表。
9)GO LOOP。
图搜索策略
9
开始
把S放入OPEN表
OPEN表为空表?
把第一个节点(n)从OPEN表移至CLOSED表
n为目标节点吗?
把n的后继节点放入OPEN表的末端,提供返回节点n的指针
修改指针方向
重排OPEN表
失败
成功
图搜索过程框图
是
是
否
否
图搜索策略
(1)
(3)
(4)
(5)
(6)
(7)
(7)
(8)
(9)
OPEN
CLOSED
(1)
(2)
宽度优先
10
图搜索的生成结果:
搜索图(G)
搜索树(T)
修正算法:
一次只生成一个后继节点;
思考:
(1)结果路径的形成中,为什么其节点顺序是明确的?
(2)OPEN表中的节点具有什么特点?
(3)CLOSED表中的节点具有什么特点?
(4)对OPEN表节点的排序有何意义?
提出:盲目搜索与启发式搜索。
图搜索策略