《人工智能与或图搜索课件》由会员分享，可在线阅读，更多相关《人工智能与或图搜索课件（40页珍藏版）》请在金锄头文库上搜索。
1、第四章 与或图搜索,4.1问题归约法 当问题复杂时，可把初始问题分解成若干简单的子问题，若子问题仍复杂，可再进一步分解，直到这些子问题的解可直接得到。这种问题的描述和求解方法，称为问题归约法。 可直接解答的问题称为本原问题。 归约法的问题表示可由下列三部分组成： 1） 一个初始问题的描述 2） 一组把问题变成子问题的算符 3） 一组本原问题的描述,4.2 与或图 对问题归约的描述可以很方便地用一个与或图的结构来表示它。 与节点：一个归约算符能够把单个问题变为几个子问题组成的集合，这时所有子问题都有解，该父辈节点才有解。这种关系称为“与”关系，对应的节点成为与节点。 或节点：几个算符适用于同一个
2、问题，从而产生不同的后继问题集合。这时只要有一个后继集合有解，则意味该父辈问题有解，此时关系是“或”关系，对应节点为或节点。,在图中N，M，H是或节点，B，C，D，E，F分别是与节点。 A N M H B C D E F 图 与节点和或节点,与或节点是针对与或树而言，对于一般的与或图有歧义,K连接符： 假设节点N被某个算符归约为一个包含K个子问题的替换集合，K 1，我们用一个叫做K连接符的超弧线把它们和节点N连接起来。每个K连接符从一个父节点指向一个含有K个后继节点的集合，并说N有一个外向连接符K。这种图称为超图，但我们仍把这种结构叫与或图。 问题归约描述对应的结构就是一个与或图，原始问题描述
3、对应于起始节点（或根节点），本原问题所对应的节点叫做叶节点。在某些特殊情况下，不出现任何与节点，此时的图成了普通图，问题归约描述也就成为状态空间描述。,4.3 与或图搜索 在与或图上执行搜索的过程，其目的在于表明起始节点是有解的，也就是说，搜索不是去寻找目标节点，而是寻找一个解图。 定义： 一个与或图G中，从节点 n到节点集 N的解图记为 G， G是 G的子图。 1若 n是 N的一个元素，则 G由一节点组成； 2若 n有一个指向节点 n1,nk的外向连接符 K，使得从每一个 ni到 N有一个解图 (i=1,k)，则 G由节点 n，连接符K，及 n1 ,nk中的每一个节点到 N的解图所组成； 3
4、否则 n 到N不存在解图。,目标,目标,初始节点,解图：,在搜索解图的过程中，还需要进行耗散值的计算。设连接符的耗散值规定为：k-连接符的耗散值=k，若解图的耗散值记为k(n, N)，则可递归计算如下： 1 若n是N的一个元素，则k(n, N)=0； 2 若n有一个外向连接符指向后继节点(n1,ni)，并设该连接符的耗散值为Cn，则 k(n, N)=Cn+k(n1, N)+k(ni, N) 具有最小耗散值的解图称为最佳解图，其值也用h*(n)标记。,耗散值的计算:,k(n, N) = Cn+k(n1, N)+k(ni, N) 其中：N为终节点集 Cn为连接符的耗散值,搜索过程还要标记能解节点(
5、SOLVED)，为此给出如下定义： 能解节点,终节点是能解节点 若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。 若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。,不能解节点,没有后裔的非终节点是不能解节点。 若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。 若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。,不过与或图搜索与状态空间图搜索有所不同，说明如下： 搜索目的是证明起始节点是否可解，而可解节点是递归定义的，取决于后继节点是否可解，即搜索是否找到叶节点。因此，搜索有可解标示过程和
6、不可解标示过程。初始节点被标示为可解，则搜索成功结束，初始节点被标示为不可解，则搜索失败。,普通图的情况,f(n) = g(n) + h(n) 对n的评价实际是对从s到n这条路径的评价,n,s,与或图: 对局部图的评价,目标,目标,初始节点,a,b,c,两个过程,图生成过程，即扩展节点 从最优的局部途中选择一个节点扩展 计算耗散值的过程 对当前的局部图新计算耗散值,下面我们讨论一般与或图的启发式搜索算法AO*算法。与A*算法不同，其评价函数f(n)=h(n)，只考虑h(n)这个分量，h(n)作为h* (n)的一个估计。 过程AO*: 1 建立一个搜索图G，G:=s，计算q(s)=h(s)，IF
7、 GOAL(s) THEN M(s, SOLVED)；开始时图G只包括s，耗散值估计为h(s)，若s是终节点,则标记上能解。,2 Until s已标记上SOLVED, do: 3 begin 4 G :=FIND(G)；根据连接符标记（指针）找出一个待扩展的局部解图G，指针后面步骤有说明。 5 n:=G中的任一非终节点;选一个非终结点作为当前节点。 6 EXPAND(n),生成子节点集(ni)， G:=ADD(nj), G),计算q(nj)=h(nj)，其中nj G， IF GOAL(nj) THEN M(nj, SOLVED);把n的子节点添加到G中,对G中未出现的子节点计算耗散值，若有终节
8、点则加能解标记。,7 S:=(n); 建立含n的单一节点集合S. 8 Until S为空, do: 9 begin 10 REMOVE(m, S),mc (S);这个m的子节点mc,应不在S中。 11 修改m的耗散值q(m): 对m指向节点集(n1i，n2i,nki)的每一个连接符i分别计算qi, qi (m)=Ci+q(n1i)+q(nki), q(m):=min qi (m);对m的i个连接符,取计算结果最小的那个耗散值为q(m)。,加指针到min qi (m)的连接符上,或把指针修改到min qi (m)的 连接符上,即原来指针与新确定的不一致时应删去. IF M(nji, SOLVED
9、) THEN M(m, SOLVED);若该连接符的所有子节点都是能解的,则m也标上能解. 12 IF M(m, SOLVED) (q(m) q(m0) THEN ADD(ma, S); m 能解或修正的耗散值与原先估算q0不同,则把m的所有先辈节点ma,添加到S中. 13 end 14 end,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,红色：4 蓝色：3,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色：4
10、蓝色：6,n1,5,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色：5 蓝色：6,2,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色：5 蓝色：6,2,1,本节所指博弈问题是指二人完备博弈： 1由二人对垒，二人轮流走步，自己的走步自己选择 2任何一方都完全知道对方过去的走步情况和今后可能的走步，不包括碰运气的情况。,4.4 博弈树的搜索,分钱币问题,（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
11、,1,1）,（2,2,1,1,1）,（2,1,1,1,1,1）,对方先走,我方必胜,中国象棋,一盘棋平均走50步，总状态数约为10的161次方。 假设1毫微秒走一步，约需10的145次方年。 结论：不可能穷举。,4.4.1博弈树的极大极小搜索法,对简单的博弈问题，我们可用类似与或图的搜索技术求出解图。 极大极小搜索法是考虑双方对弈若干步之后，选一步好的走步。,下面说明极大极小过程MINLMAX： 1.T:=(s, MAX)，OPEN:=(s)，CLOSED:=( );开始时树由初始节点构成，OPEN表只含有S. 2.LOOP1: IF OPEN =( ) THEN GO LOOP2; 3.N:
12、=FIRST(OPEN)，REMOVE(n,OPEN)，ADD(n,CLOSED); 4.IF n可直接判定为赢, 输或平局 THEN f(n):= -0，GO LOOP1 ELSE EXPAND(n)ni， ADD (ni ，T) IF dni k THEN ADD(ni, OPEN) ,GO LOOP1 ELSE 计算f(ni),GO LOOP1; ni达到深度k,计算各端节点f值.,5.LOOP2：IF CLOSED=NIL,THEN GO LOOP3 ELSE nd=FIRST(CLOSED); 6.IF(nd MAX) (f(nci MIN)有值) THEN f(nd):=maxf(
13、nci),REMOVE(Nd，CLOSED);若MAX所有子节点均有值,则该MAX取其极大值. IF(nd MIN) (f(nci MAX)有值) THEN f(nd):=minf(nci),REMOVE(Nd，CLOSED);若MIN所有子节点均有值，则该MIN取其极小值. 7.GO LOOP2; 8.LOOP3:IF f(s)NIL THEN EXIT(END M(Move,T) ; s有值,或则结束或标记走步。,下面我们以井字棋为例，说明极大极小搜索法。 如图4.4 有一井字形棋盘，甲乙二人轮流在空格中放入自己的棋子，谁先使三子成一线则胜，设甲先走用表示，乙用表示，p表示某种格局，e(p
14、)表示对格局的评价值。 e(p)定义如下： 1）甲胜，e(p)=+ 2）乙胜，e(p)=- 图4.4 井字棋 3）若p不是可定胜负的格局，则e(p)= e+(p)- e-(p) 其中，e+(p)表示当前棋局所有空格都放上甲的棋子后，甲构成的行、列和对角线的个数。同理，e-(p)表示当前棋局所有空格都放上乙的棋子后，乙构成的行、列和对角线的个数。对于图4.4，e(p)=6-4=2,例： (-1) (-2) (1) 6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-6=-1 5-4=1,极小极大过程,0,-3,3,-3,-3,-2,1,-3,6,-3,0,3,1,6,0,1,1,极
15、大,极小,a,b,在极大极小过程中，把生成树和棋局估值两个过程完全分离，使效率大大降低，若同时进行，再根据一定的条件判断，有可能尽早剪掉一些无用的分支，则可能减少搜索工作量，这是-搜索过程的基本思想。下面我们用井字棋说明-剪枝方法。 假设以深度优先方法生成了部分搜索树，则可使用终止搜索规则-剪枝。,4.4.2 -搜索过程,极大节点的下界为。 极小节点的上界为。 剪枝的条件： 后辈节点的值祖先节点的值时， 剪枝 后辈节点的 值祖先节点的值时， 剪枝 简记为： 极小极大，剪枝 极大极小，剪枝,例：MAX =-1 MIN (= -1) (=-1) ( =1) 6-5=1 5-5=0 6-5=1 5-5=0 4-5=-1 5-6=-1 5-4=1 6-4=2,
