大学人工智能课件.ppt

文档介绍：第二章与或图搜索问题
目标
目标
初始节点s
a
b
c
1
基本概念
与或图是一个超图,节点间通过连接符连接。
K-连接符:
…...
K个
2
耗散值的计算
k(n, N) = Cn+k(n1, N)+…+k(ni, N)
其中:N为终节点集
Cn为连接符的耗散值
…...
i个
n
n1
n2
ni
3
目标
目标
初始节点
解图:
4
能解节点
终节点是能解节点
若非终节点有“或”子节点时,当且仅当其子节点至少有一能解时,该非终节点才能解。
若非终节点有“与”子节点时,当且仅当其子节点均能解时,该非终节点才能解。
5
不能解节点
没有后裔的非终节点是不能解节点。
若非终节点有“或”子节点,当且仅当所有子节点均不能解时,该非终节点才不能解。
若非终节点有“与”子节点时,当至少有一个子节点不能解时,该非终节点才不能解。
6
普通图搜索的情况
f(n) = g(n) + h(n)
对n的评价实际是对从s到n这条路径的评价
n
s
7
与或图: 对局部图的评价
目标
目标
初始节点
a
b
c
8
两个过程
图生成过程,即扩展节点
从最优的局部途中选择一个节点扩展
计算耗散值的过程
对当前的局部图从新计算耗散值
9
AO*算法举例
其中:
h(n0)=3
h(n1)=2
h(n2)=4
h(n3)=4
h(n4)=1
h(n5)=1
h(n6)=2
h(n7)=0
h(n8)=0
设:K连接符
的耗散值为K
目标
目标
初始节点
n0
n1
n2
n3
n4
n5
n6
n7
n8
10