1、1第二章第二章 与或图搜索问题与或图搜索问题目标目标初始节点sabc22.1 基本概念基本概念 与或图是一个超图，节点间通过连接符连接。 K-连接符：.K个3耗散值的计算耗散值的计算k(n, N) = Cn+k(n1, N)+k(ni, N)其中：N为终节点集 Cn为连接符的耗散值.i个nn1n2ni4目标目标初始节点 解图：5能解节点能解节点 终节点是能解节点 若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。 若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。6不能解节点不能解节点 没有后裔的非终节点是不能解节点。 若非终节点有“或”子节点
2、，当且仅当所有子节点均不能解时，该非终节点才不能解。 若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。7普通图搜索的情况普通图搜索的情况f(n) = g(n) + h(n)对n的评价实际是对从s到n这条路径的评价ns8与或图与或图: 对局部图的评价对局部图的评价目标目标初始节点abc9两个过程两个过程 图生成过程，即扩展节点 从最优的局部途中选择一个节点扩展 计算耗散值的过程 对当前的局部图从新计算耗散值10AO*算法举例算法举例其中： 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
3、(n8)=0设：K连接符的耗散值为K目标目标初始节点n0n1n2n3n4n5n6n7n811目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)红色：4黄色：312目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n4(1)n5(1)红色：4黄色：6n1n2(4)n3(4)513目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)214目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n
4、1n2(4)n3(4)5n6(2)n7(0)n8(0)21152.3 博弈树搜索博弈树搜索 博弈问题 双人 一人一步 双方信息完备 零和16分钱币问题分钱币问题（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）对方先走我方必胜17中国象棋中国象棋 一盘棋平均走50步，总状态数约为10的161次方。 假设1毫微秒走一步，约需10的145次方年。 结论：不可能穷举。181，极小极大过程，极小极大过程05-333-3022-30-23541-30689-30-33-3-3-21-36-30316011极大极小ab19 - 剪枝剪枝 极大节点的下界为。 极小节点的上界为。 剪枝的条件： 后辈节点的值祖先节点的值时， 剪枝 后辈节点的 值祖先节点的值时， 剪枝 简记为： 极小极大，剪枝 极大极小，剪枝2086-31453-350 - 剪枝（续）剪枝（续）3-3022-30-2309-300-303305411-31661abcdefghijkmn21 - 剪枝的其他应用剪枝的其他应用 故障诊断 A B C D 风险投资
