搜索(和或图搜索实例AO算法)PPT讲座.ppt

与或图表示HMBCDEFGAN父节点与节点弧线或节点子节点终结点与或图是一个超图,节点间通过连接符连接。K-连接符:…...0→{n7,n8}的3个解图目标n7目标n8初始节点n0目标n7目标n8初始节点n0目标n7目标n8初始节点n0(a)(b)(c)ttttttttt(a)(b)有解节点无解节点终结点能解节点终节点是能解节点若非终节点有“或”子节点时,当且仅当其子节点至少有一能解时,该非终节点才能解。若非终节点有“与”子节点时,当且仅当其子节点均能解时,该非终节点才能解。不能解节点没有后裔的非终节点是不能解节点。若非终节点有“或”子节点,当且仅当所有子节点均不能解时,该非终节点才不能解。若非终节点有“与”子节点时,当至少有一个子节点不能解时,该非终节点才不能解。,则k(n,N)={n1,..ni}k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中:为连接符的耗散值…...i个nn1n2ni搜索解图耗散值的递归计算:n0=2+k(4,N)+k(5,N)k(5,N)=min(2+k(7,N)+k(8,N),…)=2k(4,N)=min(1+k(5,N),1+k(8,N))=min(3,1)=1N0=2+1+2=5(a)的解图耗散值为8(b)的解图耗散值为7具有最小耗散值的解图称为最佳解图,其值也用h*(n)*(n)=5(c)n4n5目标n7目标n8初始节点n0普通图搜索的情况f(n)=g(n)+h(n) 对n的评价实际是对从s经过n到目的地这条路径的评价ns与或图:对局部图的评价目标目标初始节点abc与或图搜索:AO*算法两个过程图生成过程,即扩展节点自顶向下,从最优的局部途中选择一个节点扩展计算耗散值的过程自下向顶,对当前的局部图重新计算耗散值