人工智能与模式识别选讲PPT教学课件-第二章 知识表示方法.ppt

第二章知识表示方法,2.1状态空间法2.2问题归约法2.3谓词逻辑法2.4语义网络法2.5其他方法2.6小结,好的开始是成功的一半，好的表示方法是成功的一半,2.1状态空间法(StateSpaceRepresentation),问题求解技术主要是两个方面：问题的表示求解的方法状态空间法状态（state）算符（operator）状态空间方法,2.1.1问题状态描述,定义状态：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。问题的状态空间：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。,2.状态空间表示概念详释,Originalstate,Middlestate,Goalstate,例:三数码难题（3puzzleproblem）,初始棋局,目标棋局,2.1.2状态图示法,有向图路径代价图的显示说明图的隐示说明,A状态,B状态,2.1.3状态空间表示举例,产生式系统（productionsystem）一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。,数据库,控制策略,规则,2.1.3状态空间表示举例,猴子和香蕉问题,我该咋办？,解题过程,用一个四元表列（W，x，Y，z）来表示这个问题状态.其中W猴子的水平位置x当猴子在箱子顶上时取x=1；否则取x=0Y箱子的水平位置z当猴子摘到香蕉时取z=1；否则取z=0这个问题的操作（算符）如下：令goto(U)表示猴子走到水平位置U或者用产生式规则表示为（W，0，Y，z）goto(U)（U，0，Y，z）,解题过程,pushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）pushbox（V）（V，0，V，z）climbbox猴子爬上箱顶，即有（W，0，W，z）climbbox（W，1，W，z）,解题过程,grasp猴子摘到香蕉，即有（c，1，c，0）grasp（c，1，c，1）该初始状态变换为目标状态的操作序列为goto(b),pushbox(c),climbbox,grasp,解题过程,猴子和香蕉问题的状态空间图,初始状态,2.2问题归约法（ProblemReductionRepresentation）,子问题1,子问题n,原始问题,子问题集,本原问题,2.2问题归约法（ProblemReductionRepresentation）,问题归约表示的组成部分：一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述。问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。,2.2.1问题归约描述（ProblemReductionDescription）,梵塔难题,解题过程（3个圆盘问题）,2.2.2与或图表示,1.与图、或图、与或图,A,B,C,D,与图,A,B,C,或图,1.与图、或图、与或图,2.一些关于与或图的术语,3.定义,与或图例子,t,t,t,t,t,t,t,t,t,（a）,（b）,有解节点,无解节点,终叶节点,3.定义,不可解节点的一般定义没有后裔的非终叶节点为不可解节点。全部后裔为不可解的非终叶节点且含有或后继节点，此非终叶节点才是不可解的。后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。与或图构成规则,梵塔问题归约图,（322）（333）,2.3谓词逻辑法,逻辑语句形式语言,2.3.1谓词演算,1.语法和语义基本符号谓词符号、变量符号、函数符号、常量符号、括号和逗号原子公式,2.3.1谓词演算,连词和量词(Connective&Quantifiers)连词与及合取（conjunction)或及析取（disjunction）蕴涵（Implication）非（Not）量词全称量词（UniversalQuantifiers)存在量词(ExistentialQuantifiers),2.3.2谓词公式,原子公式的的定义：用P(x1，x2，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,，xn为客体变量或变元。通常把P(x1,x2,xn)叫做谓词演算的原子公式，或原子谓词公式。分子谓词公式可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。,2.4语义网络法（SemanticNetworkRepresentation）,语义网络的结构定义组成部分词法结构过程语义,2.4.1二元语义网络的表示,表示占有关系和其它情况例：小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。,xiaoyan,swallow,bird,NEST-1,NEST,ISA,ISA,ISA,2.4.1二元语义网络的表示,谓词逻辑与语义网络等效,2.4.2多元语义网络的表示,多元语义网络表示的实质把多元关系转化为一组二元关系的组合，或二元关系的合取。,R(X1，X2，Xn),R12(X1，X2)R13(X1，X3)R1n(X1，Xn).Rn-1n(Xn-1，Xn),可转换为,2.5其他方法（Others),框架（Frame）表示框架是一种结构化表示法，通常采用语义网络中的节点-槽-值表示结构。剧本（Script）表示剧本是框架的一种特殊形式，它用一组槽来描述某些事件的发生序列。过程（Procedure）表示过程式表示就是将有关某一问题领域的知识，连同如何使用这些知识的方法，均隐式