人工智能 状态空间法 第二章主讲课件.ppt
《人工智能 状态空间法 第二章主讲课件.ppt》由会员分享,可在线阅读,更多相关《人工智能 状态空间法 第二章主讲课件.ppt(76页珍藏版)》请在三一办公上搜索。
1、人工智能,Artificial Intelligence,主讲人:,XXX,目 录,状态空间法,语义网络表示,谓词逻辑表示,问题归约法,第2 章 知识表示方法,(一),目 录,框架表示,小结,过程表示,本体技术,第2 章 知识表示方法,(二),2.1状态空间法(State Space Representation),问题求解技术主要是两个方面:问题的表示求解的方法状态空间法状态(state)算符(operator)状态空间方法,2.1.1 问题状态描述,基本概念状态(state)它是为描述某类不同事物间的差别而引入的一组最少变q0,q1,qn的有序集合,其矢量形式如下: Q=q0,q1,qnT
2、(2.1) 式中每个元素qi(i=0,1,n)为集合的分量,称为状态变量。给定每个分量的一组值就得到一个具体的状态,如 Qk=qk ,q1k,qnkT(2.2)操作符(operator) 称使问题从一种状态变化到另一种状态的手段为操作符或算符。问题的状态空间: 是一个表示该问题全部可能状态及其关系的图,它包含三种说明的集合,即三元状态(S,F,G)。,2.1 状态空间法,2. 状态空间表示概念详释,例如下棋、迷宫及各种游戏。,MiddleState,GoalState,2.1 状态空间法,例:三数码难题(3 puzzle problem),初始棋局,目标棋局,2.1 状态空间法,1.图的基本概
3、念图是一个包含节点(不一定是有限的节点)和节点间弧线的集合。若图中每条弧线均标有方向,则称这种图为有向图(directed graph)。2.代价(cost)是给各弧线指定数值以表示加在相应操作符上的代价。3.图的显式说明是指各节点及其具有代价的弧线由一张表明确给出。4.图的隐式说明:是指各节点及其具有代价的弧线不能由一张表明确给出。,2.1 状态空间法,2.1.2 状态图示法,有向图代价图的显示说明图的隐示说明,2.1.2 状态图示法,A,B,2.1 状态空间法,2.1.3状态空间表示举例,例:猴子和香蕉问题,2.1 状态空间法,猴子和香蕉问题自动演示:,2.1 状态空间法,解题过程,用一个
4、四元表列(W,x,Y,z)来表示这个问题状态.,这个问题的操作(算符)如下:2 goto(U)表示猴子走到水平位置U或者用产生式规则表示为(W,0,Y,z) goto(U) (U,0,Y,z),2.1 状态空间法,2.1.3状态空间表示举例,ushbox(V)猴子把箱子推到水平位置V,即有(W,0,W,z) pushbox(V) (V,0,V,z),climbbox猴子爬上箱顶,即有(W,0,W,z) climbbox (W,1,W,z),2.1 状态空间法,2.1.3状态空间表示举例,grasp猴子摘到香蕉,即有(c,1,c,0) grasp (c,1,c,1),该初始状态变换为目标状态的操
5、作序列为goto(b),pushbox(c),climbbox,grasp,2.1 状态空间法,2.1.3状态空间表示举例,目标状态,猴子和香蕉问题的状态空间图,2.1 状态空间法,2.1.3状态空间表示举例,2.2问题规约法表示,2.2.1问题归约描述1.问题归约法的概念问题归约是将初始问题变为一个本原问题集合。2.问题归约法的组成部分(1)一个初始问题描述;(2)一套把问题变换为子问题的操作符;(3)一套本原问题描述。,2.2问题规约表示,2.2 问题规约法,2.2 问题规约法,问题归约的实质:从目标(要解决的问题)出发逆向推理,建立子问题以及子问题的子问题,直至最后把初始问题归约为一个平
6、凡的本原问题集合。,2.2问题规约表示,梵塔难题,解题过程(3个圆盘问题),2.2 问题规约法,梵塔问题归约图:子问题2可作为本原问题考虑,因为它的解只包含一步移动。 应用一系列相似的推理,子问题1和子问题3也可被归约为本原问题,如下图所示。 这种图式结构,叫做与或图(AND/OR graph)。它能有效地说明如何由问题归约法求得问题的解答。,图 梵塔问题归约图,2.2.2与或图表示,1.与图、或图、与或图,2.2 问题规约法,2.2 问题规约法,2.一些关于与或图的术语,2.2 问题规约法,终叶节点:对应于原问题的本原节点。或节点:只要解决某个问题就可解决其父辈问题的节点集合,如(M,N,H
7、)。与节点:只有解决所有子问题,才能解决其父辈问题的节点集合,如(B,C)和(D,E,F)各个结点之间用一端小圆弧连接标记。,一些关于与或图的术语: 父节点、子(后继)节点、弧线、起始节点。,3.定义,不可解节点的一般定义没有后裔的非终叶节点为不可解节点。全部后裔为不可解的非终叶节点且含有或后继节点,此非终叶节点才是不可解的。后裔至少有一个为不可解的非终叶节点且含有与后继节点,此非终叶节点才是不可解的。与或图构成规则,2.2 问题规约法,2.2 问题规约法,3.定义图解,3.与或图构图规则 (1)与或图中的每个节点代表一个要解决的单一问题或问题集合。图中起始节点对应原始问题。 (2) 对应于本
8、原问题的节点,叫做终叶节点。 (3)有向弧线自A指向后继节点,表示所求得的子问题集合。 (4) 一般对于代表两个或两个以上子问题集合的每个节点,有向弧线从此节点指向集合中的各个节点。 (5) 在特殊情况下,当只有一个算符可应用于问题A,而且这个算符产生具有一个以上子问题的某个集合时,由上述规则(3)和规则(4)所产生的图可以得到简化。,2.3谓词逻辑表示,2.3.1谓词演算1.语法和语义谓词逻辑的基本组成部分是谓词、变量、函数和常量,并用圆括弧、方括弧、花括弧和逗号隔开。 例如,要表示“机器人(ROBOT)在号房间(r1)内”,如下图所示,可以应用原子公式:2.连词和量词连词有(与)、(或),
9、全称量词(),存在量词()。,3.几个有关定义 1.用连词把几个公式连接起来而构成的公式叫做合取,而此合取式的每个组成部分叫做合取项。一些合适公式所构成的任一合取也是一个合适公式。 例:LIKE(I,MUSIC)LIKE(I,PAINTING)(我喜爱音乐和绘画。),2.用连词把几个公式连接起来所构成的公式叫做析取,而此析取式的每一组成部分叫做析取项。一些合适公式所构成的任一析取也是一个合适公式。 例:PLAYS(LILI,BASKETBALL)PLAYS(LILI,FOOTBALL)(李力打篮球或踢足球。),2.3 谓词逻辑法,3.用连词=连接两个公式所构成的公式叫做蕴涵。称蕴涵的左式为前项
10、,右式为后项。如果前项和后项都是合适公式,那么蕴涵也是合适公式 “=”表示“如果-那么”的语句。 IF = THEN 前项 后项 (左式) (右式)例:RUNS(LIUHUA,FASTEST)TWINS(LIUHUA,CHAMPION) (如果刘华跑得最快,那么他取得冠军),2.3 谓词逻辑法,前面具有符号的公式叫做否定。一个合适公式的否定也是合适公式。 例:INROOM(ROBOT,r2)(机器人不在2号房间内。)如果一个合适公式中某个变量是经过量化的,则称这个变量为约束变量,否则为自由变量。称所有变量都是受约束的合适公式为句子。,2.3 谓词逻辑法,2.3 谓词逻辑法,2.3.2 谓词公式
11、原子公式的的定义:用P(x1,x2,xn)表示一个n元谓词公式,其中P为n元谓词,x1,x2,,xn为客体变量或变元。通常把P(x1,x2,xn)叫做谓词演算的原子公式,或原子谓词公式。分子谓词公式可以用连词把原子谓词公式组成复合谓词公式,并把它叫做分子谓词公式。,合适公式(WFF,well-formed formulas)合适公式的递归定义合适公式的性质合适公式的真值等价(Equivalence),2.3 谓词逻辑法,合适公式(WFF ,well-formed formulas)的递归定义:(1) 原子谓词公式是合适公式。(2) 若A为合适公式,则A也是一个合适公式。(3) 若A和B都是合适
12、公式, 则(AB),(AB),(ATB), (AB)也都是合适公式。(4) 若A是合适公式,x为A中的自由变元, 则( x) A ,(Ex) A都是合适公式。(5) 只有按上述规则(1)至(4)求得的那些公式,才是合适公式。,2.3 谓词逻辑法,例题:对于所有的x,如果x是整数,则x或为正的或者为负的。“( x) (I(x)=(P(x) N(x) ) I(x)表示x是整数,P(x)表示x是正数,N(x)表示x是负数。,2.3 谓词逻辑法,2.合适公式的性质,(1) 否定之否定,(2) PQ,(3) 狄摩根定理,(4) 分配律,(5) 交换律,(6) 结合律,(7) 逆否律,在一个量化的表达式中
13、的约束变量是一类虚元,它可以用任何一个不在表达式中出现过的其它变量符号来代替。举例如下:,2.3 谓词逻辑法,2.3.3 置换与合一,置换概念假元推理全称化推理综合推理定义就是在该表达式中用置换项置换变量性质可结合的不可交换的,2.3 谓词逻辑法,置换:用项(A)替换函数表达式中的变量(x),记为ES,即表示一个表达式E (Expression),用一个置换S (Substitution)而得到的表达式的置换。 例1表达式P x, f(y) ,B的4个置换为 :,s1=z/x, w/y,s2=A/y,s3=q(z)/x , A/y,s4=c/x , A/y,我们用Es来表示一个表达式E用置换s
14、所得到的表达式的置换。于是,我们可得到Px,f(y),B的4个置换的例,如下:,Px,f(y),Bs1=Pz, f(w), B,Px,f(y),Bs2=Px, f(A), B,Px,f(y),Bs3=Pq(z), f(A) ,B,Px,f(y),Bs4=Pc,f(A),B2),2.3 谓词逻辑法,合一(Unification)合一:寻找项对变量的置换,以使两表达式一致。可合一:如果一个置换s作用于表达式集Ei的每个元素,则我们用Ei s来表示置换例的集。我们称表达式集Ei是可合一的。,2.3 谓词逻辑法,2.4 语义网络表示 (Semantic Network Representation),
15、语义网络的结构定义组成部分词法结构过程语义,词法部分决定表示词汇表中允许有哪些符号,它涉及各个节点和弧线。 结构部分叙述符号排列的约束条件,指定各弧线连接的节点对。 过程部分说明访问过程,这些过程能用来建立和修正描述,以及回答相关问题。 语义部分确定与描述相关的(联想)意义的方法即确定有关节点的排列及其占有物和对应弧线。,2.4 语义网络法,用两个节点和一条弧线可以表示一个简单的事实,对于表示占有关系的语义网络,是通过允许节点既可以表示一个物体或一组物体,也可以表示情况和动作。每一情况节点可以有一组向外的弧(事例弧),称为事例框,用以说明与该事例有关的各种变量。在选择节点时,首先要弄清节点是用
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 状态空间法 第二章主讲课件 状态 空间 第二 主讲 课件

链接地址:https://www.31ppt.com/p-1621991.html