符。

状态空间：由表示问题的全部状态及一切可用算符构成的集合成为该问题的状态空间一般都有三部分构成(S,F,G)

问题的解：从问题的初始状态S出发，经过一系列的算符运算，到达目标状态。由初始状态到目标状态所用的算符序列就构成了问题的一个解。 09

表示方法—状态空间法

由15个编有1至15并放在4×4方格棋盘上的可走动的 棋子组成。 初始棋局和目标棋局，对应于该下棋问题的初始状态和目标状态。 棋盘上总有一格是空的，空格的移动可以看作状态的操作。

从初始状态到目标状态的一系列移动空格操作的新状态组成的集合为问题的解空间。 09

表示方法—状态空间法 用状态空间表示问题的步骤 定义状态的描述形式

用所定义的状态描述形式把问题的所有可能状态都表示出来，并确定出问题的初始状态集合描述和目标状态集合描述

定义一组算符，使得利用这组算符可以把问题由一种状态转变为另一种状态。 09

表示方法—状态空间法

例题：猴子和香蕉问题(monkey and banana problem)

在一个房间内有一只猴子(可把这只猴子看做一个机器人)、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢?下图表示出猴子、香蕉和箱子在房间内的相对位置。 猴子和香蕉问题 09

表示方法—状态空间法

用一个四元表列(W,x,Y,z)来表示这个问题的状态，其中 W－猴子的水平位置

x－当猴子在箱子顶上时取x=1；否则取x=0 Y－箱子的水平位置

z－当猴子摘到香蕉时取z=1；否则取z=0 这个问题中的操作(算符)如下：

goto(U)猴子走到水平位置U，用产生式规则表示为：

即应用操作goto(U)，能把状态(W，0，Y，z)变换为状态(U，0，Y，z)。 09

表示方法—状态空间法

(2) pushbox(V)猴子把箱子推到水平位置V，即有

要应用算符pushbox(V)，就要求产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不是在箱子顶上。这种强加于操作的适用性条件，叫做产生式规则的先决条件。 (3) climbbox猴子爬上箱顶，即有

在应用算符climbbox时也必须注意到，猴子和箱子应当在同一位置上，而且猴子不在箱顶上 。 09

表示方法—状态空间法

(4) grasp猴子摘到香蕉，即有

其中，c是香蕉正下方的地板位置，在应用算符grasp时，要求猴子和箱子都在位置c上，并且猴子已在箱子顶上。 从初始状态到目标状态，把所有适用的操作连续应用于每个状态，我们就能够得到状态空间图。得到从初始状态变换为目标状态的操作序列。 09

表示方法—状态空间法

从初始状态到目标状态的操作序列： ｛goto(b),pushbox(c),climbbox,grasp｝ 09

表示方法（各有特点，并存） 谓词逻辑法

产生式规则表示法 语义网络法 状态空间法 问题归约法 框架表示 面向对象表示 脚本方法表示 过程式表示 09

表示方法—问题归约法 09

表示方法—问题归约法 问题归约描述：

先把问题分解为子问题和子-子问题，然后解决较小的问题。对该问题的某个具体子集的解答就意味着对原始问题的一个解答。 问题归约的实质：

从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。 09

表示方法—问题归约法 与或树概念

终叶节点：对应于原问题的本原节点。

或节点：只要解决某个问题就可解决其父辈问题的节点集合，如（M，N，H）。

与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（B,C)和（D,E,F）各个结点之间用一端小圆弧连接标记。

与或树：由与节点及或节点组成的结构树。 09

表示方法—问题归约法 09

表示方法—问题归约法

可解节点

该节点是一个终止节点

该节点是一个“或”节点，且其子节点中至少有一个为可解节点 该节点是一个“与”节点，且其子节点全部为可解节点 不可解节点

该节点是一个端节点，但却不是终止节点

该节点是一个“或”节点，但其子节点中没有一个是可解节点 该节点是一个“与”节点，且其子节点中至少有一个为不可解节点 09

表示方法—问题归约法 例：汉诺塔问题

有3个柱子(1，2和3)和3个不同尺寸的圆盘（A，B和C）。在每个圆盘的中心有一个孔，所以圆盘可以堆叠在柱子上。最初，3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。 09

表示方法—问题归约法

（1）移动圆盘A和B至柱子2的双圆盘难题。 （2）移动圆盘C至柱子3的单圆盘难题。

（3）移动圆盘A和B至柱子3的双圆盘难题。 09 115

表示方法—问题归约法 09

表示方法—问题归约法 09

表示方法（各有特点，并存） 谓词逻辑法

产生式规则表示法 语义网络法 状态空间法 问题归约法 框架表示 面向对象表示 脚本方法表示 过程式表示 09

表示方法—框架表示法 框架理论概述

1975年 明斯基（Minsky）在论文中提出了框架理论。他从心理学的证据出发，认为人的知识以框架结构记存在人脑中。当人们面临新的情况，或对问题的看法有重要变化时，总是从自己的记忆中找出一个合适的框架，然后根据细节加以修改补充，从而形成对新观察到的事物的认识。

框架理论的基本观点是人脑已存储有大量的典型情景，当人们面临新的情景时，就从记忆中选择一个称作框架的基本知识结构，这个框架是以前记忆的一个知识空框，而其具体内容依照新的情景而改变，对这空框的细节加工修改和补充，形成对新情景的认识又记忆于人脑中。 框架理论将框架视作知识的单位，将一组有关的框架连接起来便形成框架系统。系统中的不同框架可以有共同节点，系统的行为有系统内框架的变化来表现。推理过程是由框架间的协调来完成。 09 定义

框架是一种描述所论对象属性的数据结构。所论对象可以是一个事物、一个事件或者一个概念。

由框架名、槽、侧面、值组成。

槽：用于描述所论及对象的某一方面的属性 侧面：用于描述相应属性的一个方面。

值：槽和侧面所具有的属性值分别称为槽值和侧面值。可以是逻辑型或者是数字型，具体的值可以是程序、条件、默认值或者是一个子框架。 表示方法—框架表示法 09

表示方法—框架表示法 框架的一般结构： 09

表示方法—框架表示法

框架结构内容可根据具体问题的具体需要来舍取。 例：描写“计算机主机”概念。

分析：可能有的属性：品牌，生产厂家，CPU，主板，内存，硬盘。 子属性：品牌，型号，容量 P48 09

表示方法—框架表示法 用框架表示知识的步骤

分析表达知识中的对象及其属性，对框架中的槽进行合理设置

对各对象间的各种联系进行考察。使用一些常用的或根据具体需要定义一些表达联系的槽名，来描述上下层框架间的联系 ISA槽 AKO槽 Instance槽 Part-of槽

对各层对象的“槽”及“侧面”进行合理的组织安排，避免信息描述的重复。 09

表示方法—框架表示法 框架举例 优质商品框架

框架名：<优质商品> 生产厂家：

获奖情况：获奖等级：

颁奖部门：

获奖时间：单位（年，月，日） 09

表示方法—框架表示法

例：下面是一则关于地震的报道，请用框架表达这段报道。“今天，一次强度为里氏8.5级的强烈地震袭击了下斯洛文尼亚地区，造成了25人死亡和5亿美元的财产损失。下斯洛文尼亚地区主席说：多年来，靠近萨迪壕金斯断层的重灾区一直是一个危险地区，这是本地区发生的第3号地震。” 09

表示方法—框架表示法

第一步：确定属性——框架的槽。

地震发生的地点、时间、伤亡人数、财产损失数量、地震强度的震级、断层情况。

第二步：分析本报道中各对象间的联系。 地震一件事情，只需一个框架表示 09

表示方法—框架表示法 框架名：<地震3>

地点：下斯洛文尼亚 时间：今天 伤亡人数：25

财产损失：500 000 000 震级：8.5

断层：萨迪壕金斯 09

该框架可以用下图来表示 09 09

自然灾害、地震、洪水、飓风等都可以用框架表示，用框架联系ISA/Instance将它们联系起来，形成了一个框架系统 09

表示方法—框架表示法 框架表示下的推理方法

把待求解问题用一个框架表示出来，其中有的槽是空的，表示待求解的问题，称作未知处 与知识库中已有的框架进行匹配。

这种匹配是通过对相应的槽的槽名及槽值逐个进行比较实现的。 使用一种评价方法对预选框架进行评价，以决定是否接受它。 若可以接受，则于问题框架的未知处相匹配的事实就是问题的解。