人工智能原理ch3-1and 3-2

《人工智能原理ch3-1and 3-2》由会员分享，可在线阅读，更多相关《人工智能原理ch3-1and 3-2（77页珍藏版）》请在金锄头文库上搜索。

1、第三章 知识表示 知识是人类在改造现实世界的 实践中认识和经验的总和，在计算 机科学智能程序设计中研究的知识 仅仅是有关现实世界的一部分知识 。在AI系统中，用到以下几种类型 的知识： 对象性知识 事实性知识 性能性知识 元知识 对象性知识 最典型的是以我们周围现实世界 中的有关对象事实来考虑知识：例 如：鸟有翅膀；知更鸟是鸟；雪是 白的等。所以必须要有表达这些对 象本身的类型或种类以及对象描述 的方法。 事实性知识：在现实世界中所发生的动作和事 件。例如：明天在五台山体育馆举 行大学生运动会等。知识表示除了 事件自身的记述外，还必须有事实 的类属与特征，同时涉及到对象、 时间过程及其因果关系

2、等。性能性知识 ：表达的是如何做一件事情及其 技巧的性能。它是一类行为所包 含的，超出了对象性和事件性知 识之外的那一部分知识。这类知 识可决定一个人独立工作的能力 ，解决问题的水平以及创造力。 例如：“某人毛笔字写得很好” ，就有“写”的技巧。 元知识 ：在现实世界中使用我们原先已知的知识， 称为元知识。而在研制专家系统时，我们把使 用和控制该系统领域知识的知识称为元知识。 例如，我们通常知道对某个特殊物体知识的了 解程度和来源，或对某种信息的可靠性的估计 ，以及知道现实世界中的特殊事件的相关重要 性。元知识同样包括已知道的我们自身的性能 ：我们的精力、弱点、在不同领域的水平，以 及对解决问

3、题的进展、感觉均可作为元知识来 处理。 计算机要具有智能，知识是必不可少的 。1977年，在第五届国际人工智能联合会 会议上，人工智能的鼻祖费根鲍姆教授作 了一个特约报告，提出了知识工程的概念 。人工智能的研究有了新的转折点，即从 获取智能的基于能力的策略，变成了基于 知识的方法研究。许多研究者获得共识：人工智能系统是 一个知识处理系统。它的三个基本问题是 知识获取、知识表示和知识利用。 知识的获取 ：如何获取知识。知识可能来自多个知 识源。如报告、课本、数据库、实例研 究、经验数据以及个人经验。专家系统 的主要知识源是领域专家。知识工程师 通过与专家的直接交互来获取知识。方 法步骤包括：现场

4、观察、问题讨论、问 题描述、问题分析、问题精化、系统检 查、系统验证。知识表示 ：在AI系统中如何表示知识。在上节 课介绍的两个例子中，我们是用谓词演 算表示知识。（金融投资辅助决策、“ 幸运学生”的故事） 知识的利用：如何利用已获取并已表示出的知识 进行分析、推理、决策。在以前介绍的 一些例子中，我们用了假言推理、消解 否证、自然演绎法。 不可误解，以为知识表示只有谓词 演算方式，知识利用只有假言推理、消 解否证方法。还有很多其它的方法和手 段。在这一章中，我们将较系统地介绍 一些常用的知识表示方法：包括状态空 间法、问题归约法、谓词逻辑法、语义 网络法、框架、剧本和过程表示法等。 对同一问

5、题，可以用不同的表示法，但 效果可能不一样。3.1 状态空间法(State Space Representation)在人工智能的研究中，许多问题求解方法 是采用试探性搜索方法的。也就是说，这些方 法是通过在某个可能的解空间中寻找一个解来 求解问题的。这种基于解答空间的问题表示和 求解方法就是状态空间法。它是以状态和算符 为基础来表示和求解问题的。状态：是为了描述某类不同事物间的差别而 引入的一组最少变量的有序集合。矢量形式 Q=q1，qnTqi称为状态变量。代入一组值代表了一个具体 的状态。 控制系统中，二阶系统，2个变量。二阶 调速系统，位置和速度。在专家系统中，状态描述了我们在推理的 某

6、个阶段对实际问题所掌握的知识。在博弈中，状态就是一个棋局。操作符（算符）：使问题从一种状态变化为另 一种状态的手段称为操作符或算符。操作符可 为走步、过程、规则、数学算子、运算符号或 逻辑符号等。象棋：车5平4，炮2进6。 问题的状态空间：是一个表示该问题全部可能状态及其关 系的图，它包含三种说明的集合，即所有 可能的问题初始状态集合S、操作符集合F 以及目标状态集合G。因此，可把状态空间 记为三元状态（S，F，G）。 要完成某个问题的状态描述，必须确定 3件事： 该状态描述方式，特别是初始状态的描述 。 操作符集合及其对状态描述的作用。 目标状态的描述。 例：8数码难题（重排九宫）8个编有1

7、8，放在3 x 3 方格棋盘上，可移 动，以便变换移动。问题求解。给定初始状态，求移动步骤，最终变成为目标 状态，采用图示方法表示状态。2 8 3 1 2 3 1 4 8 47 6 5 7 6 5 初始状态 目标状态操作（移动）规则的描述：8 x 4=32。但这种 走步规则不好。较好的表示：上下左右移动空 格。4种走步策略。人的习惯有时并不最简。问 题求解的最终答案是某一个空格移动序列。 例：猴子和香蕉问题用来描述一个状态集合的含有变量的表达 式，叫做状态描述模式。 在一个房间里有一只猴子（可看成是一个 机器人），一只箱子和一束香蕉。香蕉挂在天 花板下方。猴子的高度不足以碰到它，那么猴 子怎样

8、才能摘到香蕉呢？如果是人如何实现呢？对猴子或机器人如何找到正确的行动路线 呢？先不管能否找到摘香蕉的路径，首先，在 人工智能系统中如何表示这个问题。 用一个四元表列（W，X，Y，Z） 表示状态W：猴子的水平位置Y：箱子的水平位置X：猴在箱顶为1，否则为0Z：摘到香蕉为1，否则为0。初始状态（a，0，b，0）目标状态（c，1，c，1）操作符集： goto(U)：（W，0，Y，Z） goto(U) （U，0，Y，Z） pushbox(V): （W，0，W，Z）pushbox(V) （V，0，V，Z） climbbox ：（W，0，W，Z） climbbox （W，1，W，Z） grasp ：（c，

9、1，c，0） grasp （c，1，c，1）问题表示：经过什么样的操作序列，可 使系统从初态（a，0，b，0）转变到目 标状态（c，1，c，1）最终求得的操作序列： goto(b)，pushbox(c)，climbbox，grasp(机器人任务规划)三元状态：初局、终局、走步序列初态、终态、操作序列3.2 问题归约法问题归约是另一种问题描述与求 解方法。已知问题的描述，通过一系 列变换把此问题最终变为一个子问题 集合；这些子问题的解可以直接得到 ，从而解决了初始问题。 问题归约表示由下列3部分组成： 一个初始问题描述； 一套把问题转换成子问题的操作符； 一套本原问题描述。 问题归约法的实质：从

10、目标（要解决的问题）出发逆向 推理，建立子问题以及子问题的子问题 ，直至最后把初始问题归约成一个平凡 的本原问题的集合。1.梵塔难题传说印度的主神梵天做了一个梵塔。 在一块黄铜板上插了3根宝石针，在其中 的一根针上从小到大（从上向下）放置 了64个圆盘。盘可自由移动。要求僧侣 们轮流搬动，将64个盘全部移至另一根 针上。有规定，一次一盘，大盘不能压 在小盘上，并说该移动任务完成时，世 界就会在霹雳中毁灭。考虑3圆盘问题。有3个柱子，3个不同 尺寸的盘子，中间有孔，可堆叠。初始3个盘子在柱1，要求最终全移到 柱3上。规定：每次只能移动一个盘，且 大盘不能压到小盘上。各种正当的配置 状态一共有27

11、种： A(6)+AB(6)+AC(6)+BC(6)+ABC(3)。如何移动这3个盘，一般同学都会移。 如果是4个盘，就要想一下，更不要说是 64个盘。最少应移多少次。 用问题归约法怎样来解这个问题：首先把原始问题归约为一个较简单的问 题集合。 全移至柱3，必须先把C移至柱3，且在 此之前，柱3是空的。 只有在移走A、B后，才能移动C，且A、 B最好不要移至柱3，否则C无法移至柱3 。因此应该先把圆盘A、B移至柱2。 然后才能进行关键的一步：把盘C从柱1 移至柱3。并继续解决难题的其它部分。 通过上述论证，我们可以把原始难题归 约到下列3个子难题： 移动A和B至柱2。双圆盘难题。 移动盘C至柱3

12、。单圆盘难题（本原问题 ）。 移动盘A和B至柱3。双圆盘难题。次数计算：双（3），3圆盘（7），4圆 盘（15），64圆盘（264-1） 2.与或图表示可以用一个类似图的结构来表示，把 问题归约为后继问题的替换集合，画出 问题归约图。设想问题A既可由求解问题B和C，也 可由求解问题D、E和F，或者由单独求解 问题G来解决。问题B、C构成一个后继问 题的集合，问题D、E、F构成另一个后继 问题集合，而问题G则为第3个集合。 可引入附加节点，以便使有一个以 上后继问题的每个集合能够聚集在它们 各自的父辈节点之下。为此引入了附加 节点N、M。如果N和M理解为具有问题描述的作 用，那么问题A被归纳成单

13、一替换子问题 N、M、H。因此节点N、M、H称之为或节 点。问题N被归约为子问题B、C的单一集 合，要求解N必须求解所有子问题B、C， 因此节点B和C称为与节点。同样D、E、F 也是与节点。与节点用小圆弧连接。我 们把这种结构图叫做与或图。 3. 圆盘梵塔问题归约图：先用表列形式描述状态:（1 1 1）（3 3 3）习题：用四元数列结构表示四 圆盘梵塔问题，并画出求解该 问题的与或图。(1 1 1 1)(3 3 3 3) 4.问题归约机理问题归约技术：能够成功地把状态空间 搜索问题归约为越来越简单的搜索问题 ，直至所有问题能够被归约为平凡解为 止。关键算符：对问题求解有决定性作用的 算符叫做关

14、键算符。对梵塔难题（3圆盘）：移动圆盘C至柱3 是关键算符。如何根据当前状况选关键算符，以消除差别、 归约求解呢？对猴子和香蕉问题，4个算符的作用结果和适 用条件如下：走f1：（W，0，Y，Z） goto(U) （U，0，Y，Z）推f2：（W，0，W，Z） pushbox(V) （V，0，V，Z）爬f3：（W，0，W，Z） climbbox （W，1，W，Z）抓f4：（c，1，c，0） grasp （c，1，c，1）(a,0,b,0),F,(c,1,c,1) (1)合适的关键算符：抓 (a,0,b,0),F1,(c,1,c,0) (c,1,c,0),f4,(c,1,c,1) 本原问题 (2)

15、合适的关键算符：爬 (a,0,b,0),F2,(c,0,c,0) (c,0,c,0),f3,(c,1,c,0)本原问题 (3) 合适的关键算符：推 (a,0,b,0),F3,(b,0,b,0) (b,0,b,0),f2,(c,0,c,0) 本原问题 (4) 合适的关键算符：走 (a,0,b,0),f1,(b,0,b,0) 本原问题 解答由回溯得到。 第三章 知识表示 3.3 谓词逻辑法表示一个知识库的主要方法是采用一阶谓词 逻辑。使用量词（ ， ）和逻辑连接符（， ， ，=，=）能作出有关对象、特征、场景 和关系的陈述。例如：所有人都有头，可描述为X人(X)=有(X，头)优点：记号简单，描述易于理解。每个事实仅需表示一次。证明过程的推理规则是有效的。缺点：难以表示过程性和启发性知识。 由于缺少结构上统一的规则，致使大 型知识库难以管理，对证明过程进行操 作的能力差。当事实的数量很大时，鉴 于证明过程的每一步都需使用规则，而 有可能导致组合爆炸。第二章中对命题演算和谓词演算的有 关语法、语义、恒等式等作了较详细的 介绍。以下主要通过几个应用例子，以 巩固一下前面所学的知识。 例1：旅游组团问题（原史密斯家族聚会问 题）某市几个老人院联合组团出去旅游度假 。委托旅游公司办理。由于外出时间较 长，故需要考虑安排兴趣爱好和习惯较 一致的老人在一