《人工智能与或图搜索.ppt》由会员分享,可在线阅读,更多相关《人工智能与或图搜索.ppt(40页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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 不能满足基本条件 第四十页,编辑于星期六:十五点 四十三分。