人工智能 第二章 知识表示方法.docx
《人工智能 第二章 知识表示方法.docx》由会员分享,可在线阅读,更多相关《人工智能 第二章 知识表示方法.docx(17页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第二章 学问表示方法教学内容:本章探讨学问表示的各种方法,是人工智能课程三大内容学问表示, 学问推理, 学问应用之一,也是学习人工智能其他内容的根底。教学重点:状态空间法, 问题归约法, 谓词逻辑法, 语义网络法。教学难点:状态描述及状态空间图示, 问题归约机制, 置换及合一。教学方法:课堂教学为主,同时结合离散数学等已学的内容实时提问, 收集学生学习状况,充分利用网络课程中的多媒体素材来表示抽象概念。教学要求:重点驾驭用状态空间法, 问题归约法, 谓词演算法, 语义网络法来描述问题;解决问题;驾驭几种主要方法之间的差异;并对其它几种表示方法有一般了解。2.1 状态空间法教学内容:本节是通过状
2、态空间法来求解问题,它是以状态和算符(operator)为根底来表示和求解问题的。教学重点:问题的状态描述,操作符。教学难点:选择一个好的状态描述及状态空间表示方案。教学方法:以课堂教学为主;充分利用网络课程中的多媒体素材来阐述抽象概念。教学要求:重点驾驭对某个问题的状态空间描述,学会组织状态空间图,用搜寻图来求解问题。 问题状态描述1, 状态State的根本概念状态(state)是为描述某类不同事物间的差异而引入的一组最少变量q0,q1,qn的有序集合,其矢量形式如下:Q=q0,q1,qnT (2.1)式中每个元素qi(i=0,1,n)为集合的重量,称为状态变量。给定每个重量的一组值就得到一
3、个详细的状态,如Qk=qk,q1k,,qnkT (2.2)算符:使问题从一种状态变更为另一种状态的手段称为操作符或算符。操作符可为走步, 过程, 规那么, 数学算子, 运算符号或逻辑符号等。问题的状态空间(state space)是一个表示该问题全部可能状态及其关系的图,它包含三种说明的集合,即全部可能的问题初始状态集合S, 操作符集合F以及目标状态集合G。因此,可把状态空间记为三元状态(S,F,G)。提问: 1. 列举已经学习过的“状态概念,并比拟之。2. 列举算符。举例: 列举几个日常生活中状态及算符的例子,如:棋局。探讨: 每走一步后,棋局都变更了,以此来理解问题的状态空间。2, 状态空
4、间的表示法对一个问题的状态描述,必需确定3件事:(1) 该状态描述方式,特殊是初始状态描述;(2) 操作符集合及其对状态描述的作用;(3) 目标状态描述的特性。举例:讲解初始状态, 算符, 中间状态及目标状态之间的关系;讲解三数码难题的状态变更过程。 状态图示法图的根本概念图由节点(不肯定是有限的节点)的集合构成。一对节点用弧线连接起来,从一个节点指向另一个节点。这种图叫做有向图(directed graph)。某个节点序列(ni1,ni2,nik)当j=2,3,k时,假如对于每一个ni,j-1都有一个后继节点nij存在,那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。代价(
5、cost) 是给各弧线指定数值以表示加在相应算符上的代价。图的显式说明 是指各节点及其具有代价的弧线由一张说明确给出。图的隐式说明 是指各节点及其具有代价的弧线不能由一张说明确给出。提问:举已经学习过的“有向图, “路径及“代价等的概念。举例:针对三数码难题的状态变更过程讲解图的几个根本概念。 状态空间表示举例1, 产生式系统一个产生式系统由以下3局部组成:一个总数据库(global database),它含有及详细任务有关的信息。一套规那么,它对数据库进展操作运算。每条规那么由左右两局部组成,左部鉴别规那么的适用性或先决条件,右部描述规那么应用时所完成的动作。应用规那么来变更数据库。一个限制
6、策略,它确定应当采纳哪一条适用规那么,而且当数据库的终止条件满意时,就停顿计算。2, 状态空间表示举例猴子及香蕉的问题状态空间表示 用四元组W,x,y,z其中:W-猴子的水平位置;x当猴子在箱子顶上时取x=1;否那么取x=0;Y箱子的水平位置;z-当猴子摘到香蕉时取z=1;否那么取z=0。算符(1) goto(U)猴子走到水平位置U; (2) pushbox(V)猴子把箱子推到水平位置V; (3) climbbox猴子爬上箱顶; (4) grasp猴子摘到香蕉。求解过程 令初始状态为(a,0,b,0)。这时,goto(U)是唯一适用的操作,并导致下一状态(U,0,b,0)。现在有3个适用的操作
7、,即goto(U),pushbox(V)和climbbox(假设U=b)。把全部适用的操作 接着应用于每个状态,我们就能够得到状态空间图,如下图。从图不难看出,把该初始状态变换为目标状态的操作序列为:goto(b),pushbox(c),climbbox,grasp举例:针对多媒体上的猴子及香蕉问题的状态空间图,讲解问题的状态空间表示和产生式规那么的应用。2.2 问题归约法教学内容:学问表示的归约法,即问题的描述,通过一系列变换把此问题最终变为一个子问题集合;这些子问题的解可以干脆得到,从而解决了初始问题的方法。教学重点:问题归约的根本思想,问题描述,问题变换的操作符,及或图表示。教学难点:如
8、何把初始问题变换为子问题,及或图表示方法。教学方法:课堂教学为主,充分利用网络课程中的相关多媒体素材来表示抽象概念。教学要求:通过梵塔难题重点驾驭问题归约法的机理和问题归约描述方法。学会用及或图表示归约问题。 问题归约描述1, 问题归约法的概念问题的描述,通过一系列变换把此问题最终变为一个子问题集合;这些子问题的解可以干脆得到,从而解决了初始问题。该方法也就是从目标(要解决的问题)动身逆向推理,建立子问题以及子问题的子问题,直至最终把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。2, 问题归约法的组成局部1一个初始问题描述;2一套把问题变换为子问题的操作符;3一套本原问题描述。3
9、, 例如:梵塔难题问题 有3个柱子(1,2,3)和3个不同尺寸的圆盘(A,B,C)。在每个圆盘的中心有个孔,所以圆盘可以堆叠在柱子上。最初,全部3个圆盘都堆在柱子1上:最大的圆盘C在底部,最小的圆盘A在顶部。要求把全部圆盘都移到柱子3上,每次只许移动一个,而且只能先搬动柱子顶部的圆盘,还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。归约过程1移动圆盘A和B至柱子2的双圆盘难题;2移动圆盘C至柱子3的单圆盘难题;3移动圆盘A和B至柱子3的双圆盘难题。由上可以看出简化了难题每一个都比原始难题简洁,所以问题都会变成易解的本原问题。讲解并描述:梵塔问题的来源。提问:一圆盘问题要走几步?两圆盘问题要走几步
10、?三个, 四个等?4, 归约描述问题归约方法是应用算符来把问题描述变换为子问题描述。可以用状态空间表示的三元组合(S, F, G)来规定及描述问题;对于梵塔问题,子问题111(122),(122)(322)以及(322)(333)规定了最终解答路径将要通过的脚踏石状态(122)和(322)。问题归约方法可以应用状态, 算符和目标这些表示法来描述问题,这并不意味着问题归约法和状态空间法是一样的。 及或图表示1, 及或图的概念用一个类似图的构造来表示把问题归约为后继问题的替换集合,画出归约问题图。例如,设想问题A须要由求解问题B, C和D来确定,那么可以用一个及图来表示;同样,一个问题A或者由求解
11、问题B, 或者由求解问题C来确定,那么可以用一个或图来表示。举例:含有及图及或图的混合图。提问:对于一个及或图如何引入附加节点,使得后继问题的每个集合能够聚集在它们各自的父辈节点之下。2, 及或图的有关术语父节点 是一个初始问题或是可分解为子问题的问题节点;子节点 是一个初始问题或是子问题分解的子问题节点;或节点 只要解决某个问题就可解决其父辈问题的节点集合;及节点 只有解决全部子问题,才能解决其父辈问题的节点集合;弧线 是父辈节点指向子节点的圆弧连线;终叶节点 是对应于原问题的本原节点。举例:对于一个及或图。提问:指出图中的父节点, 子节点, 或节点, 及节点, 弧线和终叶节点。3, 及或图
12、的有关定义可解节点 及或图中一个可解节点的一般定义可以归纳如下:(1) 终叶节点是可解节点(因为它们及本原问题相关连)。(2) 假如某个非终叶节点含有或后继节点,那么只有当其后继节点至少有一个是可解的时,此非终叶节点才是可解的。(3) 假如某个非终叶节点含有及后继节点,那么只要当其后继节点全部为可解时,此非终叶节点才是可解的。举例:对于一个及或图。提问:指出图中的终叶节点, 可解节点, 不行解节点。不行解节点 不行解节点的一般定义归纳于下:(1) 没有后裔的非终叶节点为不行解节点。(2) 假如某个非终叶节点含有或后继节点,那么只有当其全部后裔为不行解时,此非终叶节点才是不行解的。(3) 假如某
13、个非终叶节点含有及后继节点,那么只要当其后裔至少有一个为不行解时,此非终叶节点才是不行解的。举例:对于三圆盘梵塔难题依据构图规那么画出其归约图。提问:指出图中的终叶节点, 可解节点, 不行解节点。课后作业:教材第二章习题22及254, 及或图构图规那么(1) 及或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。(2) 对应于本原问题的节点,叫做终叶节点,它没有后裔。(3)对于把算符应用于问题A的每种可能状况,都把问题变换为一个子问题集合;有向弧线自A指向后继节点,表示所求得的子问题集合。(4) 一般对于代表两个或两个以上子问题集合的每个节点,有向弧线从今节点指
14、向此子问题集合中的各个节点。(5) 在特殊状况下,当只有一个算符可应用于问题A,而且这个算符产生具有一个以上子问题的某个集合时,由上述规那么3和规那么4所产生的图可以得到简化。2.3 谓词逻辑法教学内容:本节主要讲解并描述问题的谓词逻辑表示的根本方法。教学重点:谓词逻辑, 谓词公式, 谓词演算, 置换及合一。教学难点:如何选择谓词,问题的谓词逻辑表示及运算。教学方法:课堂教学为主,充分利用网络课程中的例如程序。教学要求:重点驾驭谓词逻辑表示的语言及方法,驾驭谓词公式的性质及谓词演算,学会谓词公式的置换及合一,运用谓词推理来解决问题。 谓词演算1, 语法和语义谓词逻辑的根本组成局部是谓词符号,
15、变量符号, 函数符号和常量符号,并用圆括弧, 方括弧, 花括弧和逗号隔开,以表示论域内的关系。原子公式是由假设干谓词符号和项组成,只有当其对应的语句在定义域内为真时,才具有值T(真);而当其对应的语句在定义域内为假时,该原子公式才具有值F(假)。2, 连词和量词连词有(及), (或),全称量词(x),存在量词(x)。原子公式是谓词演算的根本积木块,运用连词能够组合多个原子公式以构成比拟困难的相宜公式。3, 几个有关定义用连词把几个公式连接起来而构成的公式叫做合取,而此合取式的每个组成局部叫做合取项。一些相宜公式所构成的任一合取也是一个相宜公式。用连词把几个公式连接起来所构成的公式叫做析取,而此
16、析取式的每一组成局部叫做析取项。由一些相宜公式所构成的任一析取也是一个相宜公式。用连词连接两个公式所构成的公式叫做蕴涵。蕴涵的左式叫做前项,右式叫做后项。假如前项和后项都是相宜公式,那么蕴涵也是相宜公式。前面具有符号的公式叫做否认。一个相宜公式的否认也是相宜公式。量化一个相宜公式中的某个变量所得到的表达式也是相宜公式。假如一个相宜公式中某个变量是经过量化的,就把这个变量叫做约束变量,否那么就叫它为自由变量。在相宜公式中,感爱好的主要是全部变量都是受约束的。这样的相宜公式叫做句子。 谓词公式1, 谓词相宜公式的定义在谓词演算中相宜公式的递归定义如下:(1) 原子谓词公式是相宜公式。(2) 假设A
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 第二章 知识表示方法 第二 知识 表示 方法
限制150内