人工智能与或图搜索.ppt

《人工智能与或图搜索.ppt》由会员分享，可在线阅读，更多相关《人工智能与或图搜索.ppt（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 图 与节点和或节点第三页，编辑于星期六：十五点 四十三分。与或节点是针对与或树而言，对于一般的与或图有歧义目标目标初始节点sabc第四页，编辑于星期六：十五点 四十三分。 K连接符：连接符： 假设节点N被某个算符归约为一个包含K个子问题的替换集合，K

3、 1，我们用一个叫做K连接符的超弧线把它们和节点N连接起来。每个K连接符从一个父节点指向一个含有K个后继节点的集合，并说N有一个外向连接符K。这种图称为超图，但我们仍把这种结构叫与或图。 问题归约描述对应的结构就是一个与或图，原始问题描述对应于起始节点（或根节点），本原问题所对应的节点叫做叶节点。在某些特殊情况下，不出现任何与节点，此时的图成了普通图，问题归约描述也就成为状态空间描述。第五页，编辑于星期六：十五点 四十三分。 4.3 与或图搜索与或图搜索 在与或图上执行搜索的过程，其目的在于表明起始节点是有解的，也就是说，搜索不是去寻找目标节点，而是寻找一个解图。 定义：定义： 一个与或图G中

4、，从节点 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否则 n 到N不存在解图。第六页，编辑于星期六：十五点 四十三分。目标目标初始节点解图：第七页，编辑于星期六：十五点 四十三分。 在搜索解图的过程中，还需要进行耗散值的计算。设连接符的耗散值规定为：k-连接符的耗散值=k，若解图的耗散值记为k(n, N)，则可递归计算如下： 1 若n是N的一个元素，则k(

5、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为连接符的耗散值.i个nn1n2ni第九页，编辑于星期六：十五点 四十三分。搜索过程还要标记能解节点(SOLVED)，为此给出如下定义： 能解节点 终节点是能解节点 若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能

6、解。 若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。第十页，编辑于星期六：十五点 四十三分。不能解节点 没有后裔的非终节点是不能解节点。 若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。 若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。第十一页，编辑于星期六：十五点 四十三分。 不过与或图搜索与状态空间图搜索有所不同，说明如下： 搜索目的是证明起始节点是否可解，而可解节点是递归定义的，取决于后继节点是否可解，即搜索是否找到叶节点。因此，搜索有可解标示过程和不可解标示过程。初始节点被标示为可解，则搜索成功结束，初始

7、节点被标示为不可解，则搜索失败。第十二页，编辑于星期六：十五点 四十三分。普通图的情况f(n) = g(n) + h(n)对n的评价实际是对从s到n这条路径的评价ns第十三页，编辑于星期六：十五点 四十三分。与或图: 对局部图的评价目标目标初始节点abc第十四页，编辑于星期六：十五点 四十三分。两个过程 图生成过程，即扩展节点 从最优的局部途中选择一个节点扩展 计算耗散值的过程 对当前的局部图新计算耗散值第十五页，编辑于星期六：十五点 四十三分。 下面我们讨论一般与或图的启发式搜索算法AO*算法。与A*算法不同，其评价函数f(n)=h(n)，只考虑h(n)这个分量，h(n)作为h* (n)的一

8、个估计。 过程过程AO*: 1 建立一个搜索图G，G:=s，计算q(s)=h(s)，IF 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

9、， IF GOAL(nj) THEN M(nj, SOLVED);把n的子节点添加到G中,对G中未出现的子节点计算耗散值，若有终节点则加能解标记。 第十七页，编辑于星期六：十五点 四十三分。 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个连接符,取计算结果最小的那个耗散

10、值为q(m)。第十八页，编辑于星期六：十五点 四十三分。 加指针到min qi (m)的连接符上,或把指针修改到min qi (m)的 连接符上,即原来指针与新确定的不一致时应删去. IF M(nji, SOLVED) 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

11、)=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初始节点n0n1(2)n4(1)n5(1)红色：4蓝色：3第二十一页，编辑于星期六：十五点 四十三分。目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n4(1)n5(1)红色：4蓝色：6n1n2(4)n3(4)5第二十二页，编辑于星期六：十五点 四十三分。目标目标初始节点n0n1n2n3n4n5

12、n6n7n8红色：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)21第二十四页，编辑于星期六：十五点 四十三分。 本节所指博弈问题是指二人完备博弈： 1由二人对垒，二人轮流走步，自己的走步自己选择 2任何一方都完全知道对方过去的走步情况和今后可能的走步，不包括碰运气的情况。4.4 博弈树的搜索博弈树的搜索第二十五页，编辑于星期六：十五点 四十三

13、分。分钱币问题（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次方年。 结论：不可能穷举。第二十七页，编辑于星期六：十五点 四十三分。4.4.1博弈树的极大极小搜索法博弈树的极大极小搜索法 对简单的博弈问题，我们可用类似与或图的搜索对简单的博弈问题，我们可用类似与或图的搜索

14、技术求出解图技术求出解图。 极大极小搜索法是考虑双方对弈若干步之后，选极大极小搜索法是考虑双方对弈若干步之后，选一步好的走步。一步好的走步。第二十八页，编辑于星期六：十五点 四十三分。 下面说明极大极小过程下面说明极大极小过程MINLMAX： 1.T:=(s, MAX)，OPEN:=(s)，CLOSED:=( );开始时树由初始节点构成，OPEN表只含有S. 2.LOOP1: IF OPEN =( ) THEN GO LOOP2; 3.N:=FIRST(OPEN)，REMOVE(n,OPEN)，ADD(n,CLOSED); 4.IF n可直接判定为赢, 输或平局 THEN f(n):= -0，

15、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(nci),REMOVE(Nd，CLOSED);若MAX所有子节点均有值,则该MAX取其极大值. IF(nd MI

16、N) (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)表示对格局的评价值。e(p)定义如下： 1）甲胜，e(p)=+ 2）

17、乙胜，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 第三十二页，编辑于星期六：十五点 四十三分。极小极大过程05-333-3022-30-23541-30689-30-33-

18、3-3-21-36-30316011极大极小ab第三十三页，编辑于星期六：十五点 四十三分。 在极大极小过程中，把生成树和棋局估值两个过程完全分离，使效率大大降低，若同时进行，再根据一定的条件判断，有可能尽早剪掉一些无用的分支，则可能减少搜索工作量，这是-搜索过程的基本思想。下面我们用井字棋说明-剪枝方法。 假设以深度优先方法生成了部分搜索树，则可使用终止搜索规则-剪枝。4.4.2 - 搜索过程搜索过程第三十四页，编辑于星期六：十五点 四十三分。 极大节点的下界为。 极小节点的上界为。 剪枝的条件： 后辈节点的值祖先节点的值时， 剪枝 后辈节点的 值祖先节点的值时， 剪枝 简记为： 极小极大，

19、剪枝 极大极小，剪枝第三十五页，编辑于星期六：十五点 四十三分。 例：MAX =-1MIN(= -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第三十六页，编辑于星期六：十五点 四十三分。-剪枝05-333-3022-30-23541-30689-300-303305411-31661abcdefghijkmn第三十七页，编辑于星期六：十五点 四十三分。 作业: A B C D E F G H I J K L M N O P Q R S T U V W X Y 2 3 8 5 7 6 0 1 5 2 8 4 10

20、2第三十八页，编辑于星期六：十五点 四十三分。 梵塔问题的状态空间图 A B C AAA(大中小都在A柱上） AAB AAC ACB ABC ACC ABB ACA ABA BCC CBB BCA BCB CBC CBA BBA BAB CAC CCA BBB BBC BAC BAA CAA CAB CCB CCC第三十九页，编辑于星期六：十五点 四十三分。 梵塔问题的问题空间图 3 2 1，AB（大为3，中为2，小为1）21,AC 3,AB 21,CB 1,AC32,AB1,CB 1,CA2,CB1,AB1,AB 2,AC 1,BC 2,AC3,AB2,CB 不能满足基本条件 第四十页，编辑于星期六：十五点 四十三分。