人工智能原理ch.ppt

第三章 知识识表示 知识识是人类类在改造现实现实 世界的实实 践中认识认识 和经验经验 的总总和，在计计算 机科学智能程序设计设计 中研究的知识识 仅仅仅仅 是有关现实现实 世界的一部分知 识识。在AI系统统中，用到以下几种类类 型的知识识： 对对象性知识识 事实实性知识识 性能性知识识 元知识识 对对象性知识识 最典型的是以我们们周围现实围现实 世 界中的有关对对象事实实来考虑虑知识识 ：例如：鸟鸟有翅膀；知更鸟鸟是鸟鸟； 雪是白的等。所以必须须要有表达这这 些对对象本身的类类型或种类类以及对对 象描述的方法。 事实实性知识识： 在现实现实 世界中所发发生的动动作和事 件。例如：明天在五台山体育馆举馆举 行大学生运动动会等。知识识表示除了 事件自身的记记述外，还还必须须有事 实实的类类属与特征，同时时涉及到对对 象、时间过时间过 程及其因果关系等。 性能性知识识 ： 表达的是如何做一件事情及其技 巧的性能。它是一类类行为为所包含 的，超出了对对象性和事件性知识识 之外的那一部分知识识。这类这类 知识识 可决定一个人独立工作的能力， 解决问题问题 的水平以及创创造力。例 如：“某人毛笔字写得很好”，就 有“写”的技巧。 元知识识 ： 在现实现实 世界中使用我们们原先已知的知识识，称 为为元知识识。而在研制专专家系统时统时 ，我们们把使 用和控制该该系统领统领 域知识识的知识识称为为元知识识 。例如，我们们通常知道对对某个特殊物体知识识 的了解程度和来源，或对对某种信息的可靠性的 估计计，以及知道现实现实 世界中的特殊事件的相 关重要性。元知识识同样样包括已知道的我们们自 身的性能：我们们的精力、弱点、在不同领领域 的水平，以及对对解决问题问题 的进进展、感觉觉均可 作为为元知识识来处处理。 计计算机要具有智能，知识识是必不可少的 。1977年，在第五届国际际人工智能联联合会 会议议上，人工智能的鼻祖费费根鲍鲍姆教授作 了一个特约报约报 告，提出了知识识工程的概念 。人工智能的研究有了新的转转折点，即从 获获取智能的基于能力的策略，变变成了基于 知识识的方法研究。 许许多研究者获获得共识识：人工智能系统统是 一个知识处识处 理系统统。它的三个基本问题问题 是 知识获识获 取、知识识表示和知识识利用。 知识识的获获取 ： 如何获获取知识识。知识识可能来自多个知识识 源。如报报告、课课本、数据库库、实实例研究 、经验经验 数据以及个人经验经验 。专专家系统统的 主要知识识源是领领域专专家。知识识工程师师通 过过与专专家的直接交互来获获取知识识。方法 步骤骤包括：现场观现场观 察、问题讨论问题讨论 、问问 题题描述、问题问题 分析、问题问题 精化、系统检统检 查查、系统验证统验证 。 知识识表示 ： 在AI系统统中如何表示知识识。在上节课节课 介绍绍的两个例子中，我们们是用谓词谓词 演算 表示知识识。（金融投资辅资辅 助决策、“幸运 学生”的故事） 知识识的利用： 如何利用已获获取并已表示出的知识进识进 行分析、推理、决策。在以前介绍绍的一 些例子中，我们们用了假言推理、消解否 证证、自然演绎绎法。 不可误误解，以为为知识识表示只有谓词谓词 演 算方式，知识识利用只有假言推理、消解 否证证方法。还还有很多其它的方法和手段 。 在这这一章中，我们们将简单简单 地介绍绍一些 常用的知识识表示方法：包括状态态空间间法 、问题归约问题归约 法、谓词逻辑谓词逻辑 法、语义语义 网 络络法、框架、剧剧本和过过程表示法等。对对 同一问题问题 ，可以用不同的表示法，但效 果可能不一样样。 3.1 状态态空间间法(State Space Representation) 在人工智能的研究中，许许多问题问题 求解方 法是采用试试探性搜索方法的。也就是说说，这这 些方法是通过过在某个可能的解空间间中寻寻找一 个解来求解问题问题 的。这这种基于解答空间间的问问 题题表示和求解方法就是状态态空间间法。它是以 状态态和算符为为基础础来表示和求解问题问题 的。 状态态：是为为了描述某类类不同事物间间的差别别而 引入的一组组最少变变量的有序集合。 矢量形式 Q=q1，qnT qi称为为状态变态变 量。代入一组值组值 代表了一个具体 的状态态。 控制系统统中，二阶阶系统统，2个变变量。二阶阶 调调速系统统，位置和速度。 在专专家系统统中，状态态描述了我们们在推理 的某个阶阶段对实际问题对实际问题 所掌握的知识识。 在博弈中，状态态就是一个棋局。 操作符（算符）：使问题问题 从一种状态变态变 化为为 另一种状态态的手段称为为操作符或算符。操作 符可为为走步、过过程、规则规则 、数学算子、运算 符号或逻辑逻辑 符号等。 象棋：车车5平4，炮2进进6。 问题问题 的状态态空间间： 是一个表示该问题该问题 全部可能状态态及其 关系的图图，它包含三种说说明的集合，即所 有可能的问题问题 初始状态态集合S、操作符集合 F以及目标标状态态集合G。因此，可把状态态空 间记为间记为 三元状态态（S，F，G）。 要完成某个问题问题 的状态态描述，必须须确 定3件事： 该该状态态描述方式，特别别是初始状态态的描述 。 操作符集合及其对对状态态描述的作用。 目标标状态态的描述。 例：8数码难题码难题 （重排九宫宫） 8个编编有18，放在3 x 3 方格棋盘盘上，可移动动 ，以便变换变换 移动动。问题问题 求解。 给给定初始状态态，求移动动步骤骤，最终变终变 成为为目标标 状态态，采用图图示方法表示状态态。 2 8 3 1 2 3 1 4 8 4 7 6 5 7 6 5 初始状态态 目标标状态态 操作（移动动）规则规则 的描述：数字移动动，共有8 x 4=32。较较好的表示：上下左右移动动空格。4种 走步策略。问题问题 求解的最终终答案是某一个空格 移动动序列。 例：猴子和香蕉问题问题 用来描述一个状态态集合的含有变变量的表达 式，叫做状态态描述模式。 在一个房间间里有一只猴子（可看成是一个机 器人），一只箱子和一束香蕉。香蕉挂在天花 板下方。猴子的高度不足以碰到它，那么猴子 怎样样才能摘到香蕉呢？ 如果是人如何实现实现 呢？ 对对猴子或机器人如何找到正确的行动动路线线呢 ？ 先不管能否找到摘香蕉的路径，首先，在人 工智能系统统中如何表示这这个问题问题 。 用一个四元表列（W，X，Y，Z） 表示状态态 W：猴子的水平位置 Y：箱子的水平位置 X：猴在箱顶为顶为 1，否则为则为 0 Z：摘到香蕉为为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，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部分组组成： 一个初始问题问题 描述； 一套把问题转换问题转换 成子问题问题 的操作符； 一套本原问题问题 描述。 问题归约问题归约 法的实质实质 ： 从目标标（要解决的问题问题 ）出发发逆向推 理，建立子问题问题 以及子问题问题 的子问题问题 ， 直至最后把初始问题归约问题归约 成一个平凡的 本原问题问题 的集合。 1.梵塔难题难题 传说传说 印度的主神梵天做了一个梵塔。在 一块块黄铜铜板上插了3根宝石针针，在其中 的一根针针上从小到大（从上向下）放置 了64个圆盘圆盘 。盘盘可自由移动动。要求僧侣侣 们轮们轮 流搬动动，将64个盘盘全部移至另一根 针针上。有规规定，一次一盘盘，大盘盘不能压压 在小盘盘上，并说该说该 移动动任务务完成时时，世 界就会在霹雳雳中毁灭灭。 考虑虑3圆盘问题圆盘问题 。有3个柱子，3个不同 尺寸的盘盘子，中间间有孔，可堆叠。 初始3个盘盘子在柱1，要求最终终全移到柱 3上。规规定：每次只能移动动一个盘盘，且 大盘盘不能压压到小盘盘上。各种正当的配置 状态态一共有27种： 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。单圆盘难题单圆盘难题 （本原问问 题题）。 移动盘动盘 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 、H 。 如果N和M理解为为具有问题问题 描述的作用 ，那么问题问题 A被归纳归纳 成单单一替换换子问题问题 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.问题归约问题归约 机理 问题归约问题归约 技术术：能够够成功地把状态态空间间 搜索问题归约为问题归约为 越来越简单简单 的搜索问问 题题，直至所有问题问题 能够够被归约为归约为 平凡解 为为止。 关键键算符：对问题对问题 求解有决定性作用的 算符叫做关键键算符。 对对梵塔难题难题 （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