第3章 和或图搜素问题ppt课件

1、第二章第二章 与或图搜索问题与或图搜索问题目的目的初始节点初始节点sabc2.1 基本概念基本概念与或图是一个超图，节点间通过连接符连接。与或图是一个超图，节点间通过连接符连接。K-连接符：连接符：.K个个耗散值的计算耗散值的计算k(n, N) = Cn+k(n1, N)+k(ni, N)其中：其中：N为终节点集为终节点集 Cn为连接符的耗散值为连接符的耗散值.i个个nn1n2ni目的目的初始节点 解图：解图：能解节点能解节点终节点是能解节点终节点是能解节点若非终节点有若非终节点有“或子节点时，当且仅当其或子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。子节点至少有一能解时，该非终

2、节点才能解。若非终节点有若非终节点有“与子节点时，当且仅当其与子节点时，当且仅当其子节点均能解时，该非终节点才能解。子节点均能解时，该非终节点才能解。不能解节点不能解节点没有后裔的非终节点是不能解节点。没有后裔的非终节点是不能解节点。若非终节点有若非终节点有“或子节点，当且仅当所有或子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。子节点均不能解时，该非终节点才不能解。若非终节点有若非终节点有“与子节点时，当至少有一与子节点时，当至少有一个子节点不能解时，该非终节点才不能解。个子节点不能解时，该非终节点才不能解。普通图搜索的情况普通图搜索的情况f(n) = g(n) + h(n)对对n

3、的评价实际是对通过的评价实际是对通过n的这条路的这条路径的评价径的评价ns与或图与或图: 对局部图的评价对局部图的评价目的目的初始节点abc两个过程两个过程图生成过程，即扩展节点图生成过程，即扩展节点从最优的局部途中选择一个节点扩展从最优的局部途中选择一个节点扩展计算耗散值的过程计算耗散值的过程对当前的局部图重新计算耗散值对当前的局部图重新计算耗散值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目的目的目的目的初始节点初始节点n0n1n2n3n4

4、n5n6n7n8目的目的初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)红色：4黄色：3目的目的初始节点n0n1n2n3n4n5n6n7n8初始节点n0n4(1)n5(1)红色：4黄色：6n1n2(4)n3(4)5目的目的初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目的目的初始节点初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)212.3 博弈树

5、搜索博弈树搜索博弈问题博弈问题双人双人一人一步一人一步双方信息完备双方信息完备零和零和分钱币问题分钱币问题（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）对方先走对方先走我方必胜我方必胜中国象棋中国象棋一盘棋平均走50步，总状态数约为10的161次方。假设1毫微秒走一步，约需10的145次方年。结论：不可能穷举。极小极大搜索法极小极大搜索法 其基本思想是：其基本思想是： (1)设博弈的双方中一方为设博弈的双方中一方为A，另一方，

6、另一方为为B。为一方。为一方(如如A)寻找最优行动方寻找最优行动方案。案。 (2)为了找到当前的最优行动方案，为了找到当前的最优行动方案，需要对各个可能的方案所产生的后需要对各个可能的方案所产生的后果进行比较。果进行比较。 (3)为计算得分，需要根据问题的特为计算得分，需要根据问题的特性信息定义一个估价函数，用来估性信息定义一个估价函数，用来估算当前博弈树端节点的得分。算当前博弈树端节点的得分。 (4)当端节点的估值计算出来后，再推算出父节点的得分，方法是：对“或节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与节点，选其子节点中

7、一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。 (5)如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。1，极小极大过程，极小极大过程05-333-3022-30-23541-30689-30-33-3-3-21-36-30316011极大极大极小极小ab例 一字棋游戏。设有如图所示的九个空格，由A，B二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线谁就取得了胜利。ba图图 一字棋一字棋 设A的棋子用“a表示，B的棋子用“b表示。为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下：设棋局为P，估价函数为f(P)。 (1)

8、若P是A必胜的棋局，则f(P)=+。 (2)若P是B必胜的棋局，则f(P)=-。 (3)若P是胜负未定的棋局，那么 f(P)=e(+P)-e(-P) 其中其中e(+P)表示棋局表示棋局P上有上有可能使可能使a成为三子成一线的成为三子成一线的数目；数目；e(-P)表示棋局表示棋局P上有上有可能使可能使b成为三子成一线的成为三子成一线的数目。例如，对于所示棋数目。例如，对于所示棋局局: e(P)=6-4=2另外，我们假定具有对称另外，我们假定具有对称性的两个棋局算作一个棋性的两个棋局算作一个棋局。还假定局。还假定A先走棋，我们先走棋，我们站在站在A的立场上。的立场上。 baab1ab0ab1ab0

9、ab 1aS1 1aS2 2ab 1ab0ab 1ab0a b 2a1ab1S4ab2S5S0 如图给出了A的第一着走棋生成的博弈树。图中节点旁的数字分别表示相应节点的静态估值或倒推值。3-, +AB-,3(a)-, +12AB3-,3(b)12AB3, +383,3(c)12ABC3, +-,23823,3(d)-,1412ABDC3,14-,2382143,3(e)12ABDC3,3-,22,238214523,3(f ) - 剪枝剪枝极大节点的下界为极大节点的下界为。极小节点的上界为极小节点的上界为。剪枝的条件：剪枝的条件：后辈节点的后辈节点的值值祖先节点的祖先节点的值时，值时， 剪枝剪

10、枝后辈节点的后辈节点的 值值祖先节点的祖先节点的值时，值时， 剪枝剪枝简记为：简记为：极小极小极大，剪枝极大，剪枝极大极大极小，剪枝极小，剪枝86-31453-350-剪枝续）3-3022-30-2309-300-303305411-31661abcdefghijkmn - 剪枝的效率剪枝的效率 - 剪枝的效率很大程度上取决于检查后剪枝的效率很大程度上取决于检查后继节点的次序继节点的次序应该先检查那些可能最应该先检查那些可能最好的后继好的后继如果能够先检查那些最好的后继，那么如果能够先检查那些最好的后继，那么 - 剪枝算法只需检查剪枝算法只需检查O(bd/2)个节点以个节点以决定最佳招数决定最佳招数 / 极