《与或图搜索andorgraphsearch》由会员分享，可在线阅读，更多相关《与或图搜索andorgraphsearch（28页珍藏版）》请在金锄头文库上搜索。
1、与或图搜索 AND/OR Graph Search问题归约 问题归约是人求解问题常用的策略，其把 复杂的问题变换为若干需要同时处理的较 为简单的子问题后再加以分别求解。只有 当这些子问题全部解决时，问题才算解决 ，问题的解答就由子问题的解答联合构成 。问题归约可以递归地进行，直到把问题 变换为本原问题的集合。所谓本原问题就 是不可或不需再通过变换化简的“原子“问题 。与或图的搜索目标目标n0n1 n2n3n4n5n6n7n8基本概念 与或图是一个超图，节点间通过连接符连 接。 k-连接符：.k个解图费用的计算k(n, N) = Cn+k(n1, N)+k(ni, N) 其中：N为终止节点集Cn
2、为连接符的费用.i个nn1n2ni前提初始节点 解图(对应普通图中 的解路径)：几个解图的费用目标目标n0n1 n2n3n4n5n6n7n8目标目标初始节点 解图(对应普通图中 的解路径)：解图的费用：8假设k连接 符的费用为k目标目标初始节点 解图(对应普通图中 的解路径)：解图的费用：7与或图启发式搜索算法AO*目标目标初始节点两个过程 图生成过程，即扩展节点 计算费用的过程AO*算法其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0设：k-连接符 费用的值为k目标目标初始节点n0n1 n2n3n4n5n6n
3、7n8目标目标初始节点n0n1n 2n3n4n5n6n7n8初始节点n0(3)n1(2)n4(1)n5(1)红色：4蓝色：3目标目标初始节点n0n1 n2n3n4n5n6n7n8初始节点n4(1)n5(1)红色：4蓝色：6n1 (2-5)n2(4)n3(4)n0(3)n0(3-4)目标目标初始节点n0n1 n2n3n4n5n6n7n8初始节点n4(1)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4)n5(1)n5(1-2)目标目标初始节点n0n1 n2n3n4n5n6n7n8红色：5蓝色：6初始节点n0(4 )n4(1)n5(1-2)n1(5)n2(4)n3(4)n6(2
4、)n7(0)n8(0)n0(4-5)目标目标初始节点n0n1 n2n3n4n5n6n7n8红色：5蓝色：6初始节点n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)目标目标初始节点n0n1 n2n3n4n5n6n7n8红色：5蓝色：6初始节点n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)目标目标初始节点n0n1 n2n3n4n5n6n7n8红色：5蓝色：6初始节点n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)博弈博弈树搜索 博弈问题 双人 一人一步 双方信息完备 零和
5、中国象棋 一盘棋平均走50步，总状态数约为10的161 次方。 假设1毫微（十亿分之一）秒走一步，约需 10的145次方年。（宇宙年龄最新估计约 147亿年10的10次方年 ） 结论：不可能穷举。000-3030133222211-311-5-5-5222233-33-13-1004444-1-1-1-1-10-0-1-剪枝 极大节点的下界为。 极小节点的上界为。 剪枝的条件： 后辈节点的值祖先节点的值时， 剪枝 后辈节点的 值祖先节点的值时， 剪枝 简记为： 极小极大，剪枝 极大极小，剪枝-剪枝 1) 当任何M I N节点的值小于等于它的M A X的祖 先节点的值，则可中止该M I N节点以下的搜索。 该M I N节点的值可以当作最终倒推值。该值与完 全最小化搜索得到的值不等，但同样可以选择到 相同的最佳移动方式。 2) 当任何M A X节点的值大于等于它的M I N的祖 先节点的值时，则可中止该M A X节点以 下的搜索，该M A X节点的值可以当作最终倒推 值。 M A X节点的值等于它的后继节点中的最大最终倒推值。 M I N节点的值等于它的后继节点中的最小最终倒推值。Pearl指出，假如后继节点随机排列， - 搜索深度会增加约4 / 3倍，即平均分枝因 子减少到大约b的3/4次方。我们用Nd表示叶节点的最小值：-过程的搜索效率
