文档介绍：第三确定性推理
§
§
§
§
§
§
§
*
人工智能第三搜索推理技术
*
第三搜索推理技术
一般一个问题可以用好几种搜索技术解决, 选择一种好的搜索技术对解决问题的效率很有关系, 甚至关系到求解问题有没有解。     搜索方法好的标准, 一般认为有两个：     (1)搜索空间小;     (2)解最佳。
Sg
*
人工智能第三搜索推理技术
*
§
§
(图搜索问题描述)
把求解问题看成一个状态图，求初始节点到目标节点的路径。
*
人工智能第三搜索推理技术
*
§
回顾一下图论中几个术语的含义。
节点深度：根节点的深度为0, 其他节点的深度规定为父节点深度加1, 即dn+1=dn+1。
路径：设一节点序列为(n0、n1,…,ni,…,nk), 对i=1,2,…, k, 若节点ni-1都具有一个后继节点ni, 则该节点序列称为节点n0到节点nK长度为k的一条路径。
路径耗散值：令C(ni,nj)为节点ni到nj 这段路径(或弧线)的耗散值, 一条路径的耗散值等于连接这条路径各节点间所有弧线耗散值的总和。路径耗散值可按如下式递归公式计算:     C(ni,t)=C(ni,nj)+C(nj,t)     C(nj,t)为ni→t这条路径的耗散值。
*
人工智能第三搜索推理技术
*
§
回顾一下图论中几个术语的含义。
扩展一个节点: 后继节点操作符(相当于可应用规则)作用到节点(对应于某一状态描述)上, 生成出其所有后继节点(新状态), 并给出连接弧线的耗散值(相当于使用规则的代价), 这个过程叫做扩展一个节点。扩展节点可使定义的隐含图生成为显式表示的状态空间图。
*
人工智能第三搜索推理技术
*
§
S～起始结点 G～搜索图
OPEN ～表存放未扩展节点
CLOSED ～表存放已扩展节点
(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。
(2)建立一个叫做CLOSED的已扩展节点表，其初始为空表。
(3)LOOP: 若OPEN表是空表，则失败退出。
(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中，称此节点为节点n。
*
人工智能第三搜索推理技术
*
§
(5) 若n为一目标节点n，则有解并成功退出。此解是追踪图G中沿着指针从n到s这条路径而得到的。
(6) 扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继结点添入图G中。
(7) 对于那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已经在CLOSED表上的每一个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。
(8) 按某一任意方式或按某个探试值，重排OPEN表。
(9)GO LOOP
*
人工智能第三搜索推理技术
*
§
举例：
S
A
B
C
D
E
M
F
S
OPEN(S) CLOSED( )
OPEN(A, B) CLOSED(S)
OPRN(B, C, D) CLOSED(S, A)
OPEN(C, D, E) CLOSED(S, A, B)
OPEN(D,E) CLOSED(S, A,B,C)
OPEN(E,M,F) CLOSED(S, A,B,C,D)
求解
目标节点
2
3
5
6
4
7
3
8
4
×
*
人工智能第三搜索推理技术
*
§
开始
把S放表入OPEN表中
OPEN表为空表
把第一个节点n从OPEN
表移至CLOSED表
N为目标节点
把节点n的后继节点放入OPEN表
，提供返回节点n的指针
修正指针方向
重排OPEN表
失败
成功
是
是
①
②
③
*
人工智能第三搜索推理技术
*
§