文档介绍：2017/11/11
人工智能
Artificial Intelligence (AI)
许建华
******@njnu.
南京师范大学计算机科学系
2006年9-12月
2017/11/11
与或图的搜索技术
与或树的盲目搜索技术
与或图的启发式搜索算法(AO*算法)
2017/11/11
与或图的启发式搜索算法
约定:
讨论一般的(有向)“与或图”(一个节点可以有多个父节点、一个节点的后继节点同时可以具有“与关系”和“或关系”)
“与或图”中不存在着环(即某一个节点的后继节点同时又是它的前辈节点)
2017/11/11
一般的与或图
环
2017/11/11
例
2017/11/11
与或图的解图(前面的定义):
由最少的可解节点所构成的子图,这些节点能够使问题的起始节点是可解的
2017/11/11
扩展的与或图解图的定义: G是与或图, G’是G中从节点 n 到节点集 N 的一个解图,如果
1、若 n 属于N,则 G’由单一节点 n 构成
2、若 n 有 k 个与关系的子节点{ n1 , …, nk } ,且每一个子节点 ni 到 N 都有一个解图,则 G’由节点n、k个子节点{ n1 , …, nk }、每一个子节点 ni 到 N 的解图组成
3、否则,从 n 到 N 不存在解图
2017/11/11
如果 n 为起始节点, N 为某一些叶节点的集合,则从 n 到 N 的解图就是问题的解
n = n0, N={ n7 , n8 }
解图
2017/11/11
代价:设 k(n,N) 是从 n 到 N 的一个解图的代价,则 k(n , N) 的递归定义为:
1、若 n 属于 N,则k(n , N) = 0
2、若 n 不属于 N,则
其中, 是节点 n 的 k 个连接弧的代价之和,ni (i=1,…,k)为 n 的与子节点
2017/11/11
0
注:连接弧上的代价值为1
2
2
0
6
7
8
0
0
5
1
2