人工智能 第二章 知识表示方法

单击此处编辑母版文本样式,第二层,第三层,第四层,第五层,单击此处编辑母版标题样式,*,CSU,CSU,CSU,CSU,CSU,CSU,CSU,CSU,CSU,第二章 知识表示方法,2.1,状态空间法,2.2,问题归约法,2.3,谓词逻辑法,2.4,语义网络法,2.5,其他方法,2.6,小结,2.1,状态空间法,先看下面的例子,农夫渡河问题,有一农夫带一条狼,一只羊和一筐菜欲从河的东岸渡到河的西岸,但受下列条件限制,:,(1),船太小,农夫每次只能带一样东西过河,;,(2),如果没有农夫看管,则狼要吃羊,羊要吃菜,.,请设计一个过河方案,使得农夫,狼,羊,菜能不受损失地过河,.,2,先要将问题表示出来,表示成计算机能够处理的数据结构,.,该问题可以较好地用状态空间的方法表示,.,状态空间的方法,:(1),状态集,;(2),初始状态,目标状态,;(3),规则集合,.,3,用状态空间法表示,用一个四元组,(,m,n,x,y,),表示东岸的状态,其中,:,m=0 or 1,n=0 or 1,x=0 or 1,y=0 or 1.,m=1,表示人在东岸,m=0,表示人不在东岸,;,n=1,表示狼在东岸,n=0,表示狼不在东岸,;,x=1,表示羊在东岸,x=0,表示羊不在东岸,;,y=1,表示菜在东岸,y=0,表示菜不在东岸,.,4,状态集为,:,(1,1,1,1),(1,1,1,0),(1,1,0,1),(1,1,0,0)(,不合法,),(1,0,1,1),(1,0,1,0),(1,0,0,1)(,不合法,),(1,0,0,0)(,不合法,),(0,1,1,1)(,不合法,),(0,1,1,0)(,不合法,),(0,1,0,1),(0,1,0,0),(0,0,1,1)(,不合法,),(0,0,1,0),(0,0,0,1),(0,0,0,0),状态集,S,为,10,种状态,.,5,初始状态和目标状态,初始状态为,(1,1,1,1);,目标状态为,(0,0,0,0).,6,规则,F0,F1,F2,F3,是过河的动作,其中,:,F0,表示人单独过河,;,F1,表示人带狼过河,;,F2,表示人带养过河,;,F3,表示人带菜过河,.,7,规则,If(1,n,x,y)S and(0,n,x,y)S then F0;,If(1,1,x,y)S and(0,0,x,y)S then F1;,If(1,n,1,y)S and(0,n,0,y)S then F2;,If(1,n,x,1)S and(0,n,x,1)S then F3.,8,控制策略,If m n x y=1 then F2;,If m x=0 and n y=1 then F0;,If m n x y=1 then F1;,If m n x y=0 then F2;,If m n x y=1 then F3;,If m n x y=0 then F0;,If n y=0 and m x=1 then F2.,9,解答,(1,1,1,1)F2 (0,1,0,1),F0 (1,1,0,1),F1 (0,0,0,1),F2 (1,0,1,1),F3 (0,0,1,0),F0 (1,0,1,0),F2 (0,0,0,0),10,2.1,状态空间法,野人渡河问题,设有三个传教士和三个野人来到河边,打算乘一只船从右岸渡到左岸去,.,该船的负载能力为两人,.,在任何时候,如果野人人数超过传教士人数,那么野人就会把传教士吃掉,.,他们怎样才能用这条船安全地把所有人都渡过河去,?,11,状态表示,(3,3,1)(3,1,0)(3,2,1),(3,0,0)(3,1,1),(1,1,0)(2,2,1),(0,2,0)(0,3,1),(0,1,0)(0,2,1),(0,0,0),12,2.1,状态空间法,（,State Space Representation,）,问题求解技术主要是两个方面：,问题的表示,求解的方法,状态空间法,状态,（,state,）,算符,（,operator,）,13,2.1.1,问题状态描述,定义,状态：,描述某类不同事物间的差别而引入的一组最少变量,q,0,，,q,1,，,，,q,n,的有序集合。,算符：,使问题从一种状态变化为另一种状态的手段称为操作符或算符。,问题的状态空间：,是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态,（,S,，,F,，,G,）,。,2.1,状态空间法,14,2.,状态空间表示概念详释,例如下棋、迷宫及各种游戏。,Original,State,Middle,State,Goal,State,2.1,状态空间法,15,例,:,三数码难题（,3 puzzle problem,）,1,2,3,1,2,3,1,2,3,3,1,2,3,1,2,3,1,2,初始棋局,目标棋局,2.1,状态空间法,16,有向图,路径,代价,图的显示说明,图的隐示说明,2.1.2,状态图示法,A,B,2.1,状态空间法,17,2.1.3,状态空间表示举例,产生式系统,（,production system,）,一个总数据库：,它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂,。,一套规则：,它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。,一个控制策略：,它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。,2.1,状态空间法,18,状态空间表示举例,例：猴子和香蕉问题,2.1,状态空间法,19,解题过程,用一个四元表列,（,W,，,x,，,Y,，,z,）,来表示这个问题状态,.,这个问题的操作（算符）如下：,goto,（,U,）,表示猴子走到水平位置,U,或者用产生式规则表示为,（,W,，,0,，,Y,，,z,）,goto,（,U,）,（,U,，,0,，,Y,，,z,）,2.1,状态空间法,20,pushbox,（,V,）,猴子把箱子推到水平位置,V,，,即有,（,W,，,0,，,W,，,z,）,pushbox,（,V,）,（,V,，,0,，,V,，,z,）,climbbox,猴子爬上箱顶，即有,（,W,，,0,，,W,，,z,）,climbbox,（,W,，,1,，,W,，,z,）,2.1,状态空间法,21,grasp,猴子摘到香蕉，即有,（,c,，,1,，,c,，,0,）,grasp,（,c,，,1,，,c,，,1,）,该初始状态变换为目标状态的操作序列为,goto(b),pushbox(c),climbbox,grasp,2.1,状态空间法,22,(b，1，b，0),（U，0，b，0）,（V，0，V，0）,（c，1，c，0）,（U，0，V，0）,（c，1，c，1）,（a，0，b，0）,目标状态,goto,（,U,）,goto,（,U,）,U=b,，,climbbox,goto,（,U,）,U=b,pushbox,（,V,）,猴子和香蕉问题的状态空间图,goto,（,U,）,U=V,2.1,状态空间法,23,2.2,问题归约法（,Problem Reduction Representation,）,子问题,1,子问题,n,原始问题,子问题集,本,原,问,题,24,问题归约表示的组成部分：,一个初始问题描述；,一套把问题变换为子问题的操作符；,一套本原问题描述。,问题归约的实质：,从目标,(,要解决的问题,),出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问,题归约为一个平凡的本原问题集合。,2.2,问题规约法,25,2.2.1,问题归约描述（,Problem Reduction Description,）,梵塔难题,1,2,3,C,B,A,2.2,问题规约法,26,解题过程（,3,个圆盘问题）,1,2,3,1,2,3,1,2,3,1,3,2,1,2,3,1,2,3,1,2,3,1,2,3,2.2,问题规约法,27,2.2.2,与或图表示,1.,与图、或图、与或图,2.2,问题规约法,A,B,C,D,与图,A,B,C,或图,28,2.2,问题规约法,B,C,D,E,F,G,A,H,M,B,C,D,E,F,G,A,N,29,2.,一些关于与或图的术语,2.2,问题规约法,H,M,B,C,D,E,F,G,A,N,父节点,与节点,弧线,或节点,子节点,终叶节点,30,3.,定义,2.2,问题规约法,与或图例子,t,t,t,t,t,t,t,t,t,（a）,（b）,有解节点,无解节点,终叶节点,31,不可解节点的一般定义,没有后裔的非终叶节点为不可解节点。,含有或后继节点且全部后裔为不可解的非终叶节点是不可解的。,含有与后继节点且后裔至少有一个为不可解的非终叶节点是不可解的。,2.2,问题规约法,32,梵塔问题归约图,（,113,）（,123,）,（,111,）（,113,）,（,123,）（,122,）,（,111,）（,333,）,（,122,）（,322,）,（,111,）（,122,）,（,322,）（,333,）,（,321,）（,331,）,（,322,）（,321,）,（,331,）（,333,）,2.2,问题规约法,33,2.3,谓词逻辑法,谓词逻辑容许表达那些无法用命题逻辑表达的事情,.,一阶谓词演算是一种形式语言,其根本目的在于把数学中的逻辑论证符号化,.,如果能够采用数学演绎的方式证明一个新语句是从那些已知正确的语句导出的,那么也就能够断定这个新语句也是正确的,.,2.3.1,谓词演算,1.,语法和语义,谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。,34,例,1,表示机器人,(ROBOT),在,1,号房间,用原子公式表示如下,:,INROOM(ROBOT,r1),其中,:ROBOT,和,r1,为常量符号,INROOM,为谓词符号,.,35,连词和量词,(Connective&Quantifiers),连词,与及合取,（,conjunction),或及析取,（,disjunction,）,蕴涵,（,Implication,）,非,（,Not,）,量词,全称量词,（,Universal Quantifiers),存在量词,(Existential Quantifiers),2.3,谓词逻辑法,36,2.3.2,谓词公式,原子公式的的定义：,用,P(x,1,，,x,2,，,，,x,n,),表示一个,n,元谓词公式，其中,P,为,n,元谓词，,x,1,x,2,，,x,n,为客体变量或变元。通常把,P(x,1,x,2,x,n,),叫做谓词演算的原子公式，或原子谓词公式。,分子谓词公式,可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。,2.3,谓词逻辑法,37,合适公式,（,WFF,，,well-formed formulas,）,合适公式的递归定义,合适公式的性质,合适公式的真值,等价（,Equivalence),2.3,谓词逻辑法,38,2.3.3,置换与合一,置换,概念,假元推理,全称化推理,综合推理,定义,就是在该表达式中用置换项置换变量,性质,可结合的,不可交换的,2.3,谓词逻辑法,39,合一（,Unification),合一：寻找项对变量的置换，以使两表达式一致。,可合一：如果一个置换,s,作用于表达式集,Ei,的每个元素，则我们用,Ei,s,来表示置换例的集。我们称表达式集,Ei,是可合一的。,2.3,谓词逻辑法,40,2.4,语义网络法 （,Semantic Network Representation,）,语义网络的结构,定义,组成部分,词法,结构,过程,语义,41,表示占有关系和其它情况,例：小燕是一只燕子，燕子是鸟；巢,-1,是小燕,的巢，巢,-1,是巢中的一个。,选择语义基元,试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识。,2.4,语义网络法,2.4.1,二元语义网络的表示,42,2.