与或图搜索ANDORGraphSearch.ppt

与或图搜索ANDORGraphSearch Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望问题归约问题归约是人求解问题常用的策略，其把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解。只有当这些子问题全部解决时，问题才算解决，问题的解答就由子问题的解答联合构成。问题归约可以递归地进行，直到把问题变换为本原问题的集合。所谓本原问题就是不可或不需再通过变换化简的原子问题。与或图的搜索目标目标n0n1n2n3n4n5n6n7n8基本概念与或图是一个超图，节点间通过连接符连接。k-连接符：.k个解图费用的计算k(n,N)=Cn+k(n1,N)+k(ni,N)其中：N为终止节点集 Cn为连接符的费用.i个nn1n2ni前提前提初始节点 解图(对应普通图中的解路径)：几个解图的费用目标目标n0n1n2n3n4n5n6n7n8目标目标初始节点 解图(对应普通图中的解路径)：解图的费用：8假设k连接符的费用为k目标目标初始节点 解图(对应普通图中的解路径)：解图的费用：7与或图启发式搜索算法AO*目标目标初始节点两个过程图生成过程，即扩展节点计算费用的过程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目标目标初始节点n0n1n2n3n4n5n6n7n8目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0(3)n1(2)n4(1)n5(1)红色：4蓝色：3目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n4(1)n5(1)红色：4蓝色：6n1(2-5)n2(4)n3(4)n0(3)n0(3-4)目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n4(1)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4)n5(1)n5(1-2)目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5蓝色：6初始节点n0(4)n4(1)n5(1-2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4-5)目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5蓝色：6初始节点n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5蓝色：6初始节点n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5蓝色：6初始节点n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)博弈博弈博弈树搜索博弈问题双人一人一步双方信息完备零和中国象棋一盘棋平均走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表示叶节点的最小值：-过程的搜索效率