《2015AI课件知识表示精简》由会员分享，可在线阅读，更多相关《2015AI课件知识表示精简（40页珍藏版）》请在金锄头文库上搜索。
1、2019/7/7,人工智能原理,1,表示方法,概述 状态空间法 问题规约法 谓词逻辑表示 产生式规则表示法 语义网络表示法,框架表示法 脚本方法 过程表示 混合型知识表示方法 面向对象的表示方法,2019/7/7,人工智能原理,2,表示方法 问题归约法,问题归约是不同于状态空间的人工智能中另一种问题描述和求解方法,问题归约表示也是一个三元组(S0,F,G):S0-一个初始问题描述,即要解决的问题(初始问题)；F-一套把问题变换为子问题的操作符（操作算子集）；G-一套本原问题描述，其中的每一个问题是不需证明的，自然成立的，如公理、已知的实事等（本原问题集）。 所有问题归约的目的是最终产生具有明显
2、解答的本原问题。这些问题可能是由状态空间搜索中走动一步解决的问题，或者可能是别的具有已知解答的更复杂的问题。 问题归约相当于对问题进行分解成若干个子问题集，然后进一步分解子问题，直至分解得到本原问题为止。,2019/7/7,人工智能原理,3,表示方法 问题归约法,梵塔难题 有3个柱子（1，2，3）和3个圆盘尺寸从小到大为A，B，C。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部圆盘都堆在柱子1上：最大的C在底部，最小的A在顶部。要求把所有圆盘都挪到柱子3上。每次只允许移动一个，而且只能搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。,2019/7/7,人工智能原
3、理,4,表示方法 问题归约法,我们把原始难题归约为以下三个子难题： 移动圆盘A和B至柱子2的双圆盘难题 移动圆盘C至柱子3的单圆盘难题 移动圆盘A和B至柱子3双圆盘难题,1 2 3,1 2 3,ABC,2019/7/7,人工智能原理,5,梵塔难题归约图（与或图）,(111)=(333),(111)=(122),(122)=(322),(322)=(333),(111)=(113),(113)=(123),(123)=(122),(322)=(321),(321)=(331),(331)=(333),状态：用三元组(x,y,z)表示， 其中: “x”表示圆盘C所在的柱号，“y”表示圆盘B所在的柱
4、号, “z”表示圆盘A所在的柱号。,2019/7/7,人工智能原理,6,与或图表示 与或图：用一个类似图的结构来表示把问题归约为后继问题的替换集合（例：见右图，将问题A分解为三个问题集合，即B, C、D, E, F、 H）。 或节点： 与节点： 圆弧：标记与节点 与或图是一种超图，普通图是与或图的一个特例，与或图需要其特有的搜索技术（AO*） 状态空间与问题归约问题求解方法的区别：是否存在与节点。,A,B,C,D,E,F,H,（子问题替换结构图）,A,M,N,H,B,C,D,E,F,一个与或图,表示方法 问题归约法(与或图表示),2019/7/7,人工智能原理,7,表示方法 问题归约法(与或图
5、表示),父辈节点、后继节点： 起始节点：对应于原始问题描述。 终叶节点：对应于本原问题。 解图：由可解节点构成的子图，这些节点能够证明其初始节点是可解的。 可解节点： （1）终叶节点是可解的。 （2）如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。 （3）如果某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解的时，此非终叶节点才是可解的。 不可解节点： （1）没有后裔的非终叶节点是不可解的。 （2）如果某个非终叶节点含有或后继节点， （3）如果某个非终叶节点含有与后继节点， ,2019/7/7,人工智能原理,8,表示方法 问题归约法
6、(问题归约机理),规划机理 一种问题归约技术 把状态空间搜索问题(S, F, G)归约为越来越简单的搜索，直至所有问题能够被归约为平凡解为止。 识别路标状态序列（g1,g2, ,gn） 将初始问题归约为由（S,F,g1）,(g1,F, g2 , ,(gn, F, G)规定的问题集合。解答所有这些问题就等价于解答该初始问题。（giGi） 关键算符（对问题求解具有决定性作用的算符） 问题求解的决定性步骤 例如， “移动圆盘C至柱子3”这个算符可被认为梵塔问题的决定性步骤。,2019/7/7,人工智能原理,9,状态空间搜索问题归约 设 f F 是关键算符， Gf 表示 f 适用的所有状态集合， g
7、Gf ， f(g)是算符作用于状态g而得到的状态， 则可将初始问题（S, F, G）归约如下：,（S,F,G）,（S,F,Gf）,（f(g),F,G）,表示方法 问题归约法(问题归约机理),f,2019/7/7,人工智能原理,10,状态空间搜索问题归约 设 f F 是关键算符， Gf 表示 f 适用的所有状态集合， g Gf ， f(g)是算符作用于状态g而得到的状态， 则可将初始问题（S, F, G）归约如下：,表示方法 问题归约法(问题归约机理),（S,F,G）,（S,F,Gf）,（f(g),F,G）,(g,F, f(g) ）,本原问题,f,2019/7/7,人工智能原理,11,表示方法
8、问题归约法(问题归约机理),差别 粗略地说，问题（S,F,G）的差别就是用S的元对由集合G规定的目标进行测试失败原因的部分表列(如果S的某个元是在G中，那么此问题就获得解决，也就不存在差别)。 寻找候选关键算符的一种方法：计算某个问题（ S,F,G ）的差别。 例如，设TG 是 规定G的状态条件集合，TG是TG的子集,且sS 满足TG，令D= TG TG（D不满足 s ）,则D中最重要的条件可作为差别（如果这些条件可以按其重要性分类）。 关键算符就是用来消去差别的，即把算符和差别结合起来。 示例（用问题归约法解猴子和香蕉问题）,2019/7/7,人工智能原理,12,c,b,a,例：猴子摘香蕉问
9、题,2019/7/7,人工智能原理,13,状态：用一个四元表列（W,x,Y,z）来表示这个问题的状态。 W: 猴子的水平位置 。x:当猴子在箱子顶上时为1，否则为0。 Y: 箱子的水平位置 。z:当猴子摘到香蕉时为1，否则为0。 初始状态为（a,0,b,0）,目标状态为 z=1 操作（算符） f1: goto(U) : (W, 0, Y, z)(U, 0, Y, z) f2: pushbox(V): (W, 0, W, z)(V, 0, V, z) f3: climbbox: (W, 0, W, z)(W, 1, W, z) f4: grasp: (c, 1, c, 0)(c, 1, c, 1
10、),问题的表式猴子摘香蕉问题,2019/7/7,人工智能原理,14,用问题归约法解猴子和香蕉问题,更改为：goto(c),2019/7/7,人工智能原理,15,表示方法,概述 状态空间法 问题规约法 谓词逻辑表示 产生式规则表示法 语义网络表示法,框架表示法 脚本方法 过程表示 混合型知识表示方法 面向对象的表示方法,2019/7/7,人工智能原理,16,表示方法,概述 状态空间法 问题规约法 谓词逻辑表示 产生式规则表示法 语义网络表示法,框架表示法 脚本方法 过程表示 混合型知识表示方法 面向对象的表示方法,2019/7/7,人工智能原理,17,表示方法语义网络表示法,表示形式 每一个要表
11、达的事实用一个“结点”表示，而事实之间的关系用“弧线”表示。即，有向图表示的三元组，（结点1， 弧，结点2）连接而成。 推理特点 不十分明了，有继承规则。可以用来表示关系如：成员联系、特征联系、相互作用联系、集合联系、合成联系、因果联系、活动方式联系、活动目标联系、蕴含联系等。还可以将语义网络引入逻辑含义。表示，关系，适用归结推理法。,2019/7/7,人工智能原理,18,表示方法语义网络表示法,结论 语义网络的优点: 结构性 联想性 自索引性 自然性 语义网络的缺点: 非严格性 复杂性,2019/7/7,人工智能原理,19,表示方法二元语义网络表示,例1,swallow,bird,swall
12、ow,swallow,xiaoyan,bird,xiaoyan,bird,wings,isa,(a),isa,isa,isa,isa,has-part,(b),(c),2019/7/7,人工智能原理,20,表示方法二元语义网络表示,例2,(a),2019/7/7,人工智能原理,21,表示方法二元语义网络表示,例2,nest-1,nest,own-1,spring,time,fall,ownership,situation,isa,owner,owner,isa,isa,isa,isa,starttime,endtime,(b),2019/7/7,人工智能原理,22,表示方法二元语义网络表示,例
13、3,my car,tan,green,tan,my car,Lihuas car,car,color,color,isa,isa,color,2019/7/7,人工智能原理,23,表示方法二元语义网络表示,例4,furniture,my chair,chair,person,seat,x,brown,leather,isa,isa-part,isa,color,covering,owner,isa,2019/7/7,人工智能原理,24,表示方法多元语义网络表示,为了表示多元语义，可将多元关系转化为二元关系的组合 。 例：北大(BU)和清华(TU)两校篮球队在北大进行的一场比赛的比分是85比89
14、。,2019/7/7,人工智能原理,25,表示方法多元语义网络表示,建立一个G25表示这场特定的球赛，是一个附加节点。,2019/7/7,人工智能原理,26,表示方法连接词和量化的表示,合取(conjunction) Join gave Mary the book. 谓词表示可以为: GIVE(JOIN,MARY,BOOK),JOHN,BOOK,GIVE,MARY,G25,object,isa,giver,recipient,2019/7/7,人工智能原理,27,表示方法连接词和量化的表示,析取 ISA（A，B）PARTOF（B，C）,B,A,C,part-of,isa,DIS,2019/7/
15、7,人工智能原理,28,表示方法连接词和量化的表示,否定 （a）和（b）表示（A isa B）和（B part of C） （c）表示ISA（A，B）PART-OF（B，C）,B,A,C,Part-of,isa,NEG,(c),A,B,(a),(b),isa,part-of,2019/7/7,人工智能原理,29,表示方法连接词和量化的表示,蕴含 在语义网络中可用标注ANTE和CONSE界限来表示蕴含关系。ANTE表示先决条件antecedent及CONSE表示结果consequence。用以一条虚线把两个界限连接起来，以表示一对蕴含关系的先决条件和结果。,address,37-maple,occupation,programmer,O(x,y),Y,X,isa,isa,profession,person,worker,loc,ANTE,CONSE,2019/7/7,人工智能原理,30,表示方法连接词和量化的表示,量化 The dog bit the postman.,dog,postman,P,D,bite,B,isa,isa,isa,assailiant,victin,(a),2019/7/7,人工智能原理,31,表示方法连接词和量化的表示,dog,postman,P,D,bite,B,
