有向图 后继节点（后裔） 父辈节点（祖先） 代价（cost） c(ni，nj) 图的显示说明（已知） 图的隐示说明（起始点，推论已知，后
继无限）
2.1 状态空间法
A
B
12
2.1 状态空间法
2.1.3 状态空间表示举例
产生式系统（production system） – 一个总数据库：它含有与具体任务有关的信息随着应用情况的不 同，这些数据库可能简单，或许复杂。 – 一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则
状态空间表示法是人工智能中最基本的形 式化方法，是讨论问题求解技术的基础。
7
2.1.1 问题状态描述
Hale Waihona Puke 2.1 状态空间法1 定义
状态：
描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn 的有序集合。
是描述问题求解过程中不同时刻状况的数据 结构。 一般用一组变量的有序集合表示： Q=(q0，q1，...，qn) 其中每个元素qi(i=0，l，2，…，n) 为状态变量。 当给每一个变量以确定的值时，就得到了一个具体的状态。
算符：使问题从一种状态变化为另一种状态的手段称为 操作符或算符。
算符可分为走步、过程、规则、数学算子、运算符号、
逻辑符号等。
8
状态空间：是一个表示该问题全部可能状态及 其关系的图. 由三部分构成：问题的所有可能初始状态构成 的集合S；算符集合F；目标状态集合G。
问题的解 状态空间的问题求解就是从问题的初始状态集 S出发，经过一系列的算符运算，到达目标状 态。 由初始状态到目标状态所用算符的序列就构成 了问题的一个解。
9
2.1 状态空间法
2. 状态空间表示概念详释
Original State
Middle State
Goal State
例如下棋、迷宫及各种游戏。
10
例:三数码难题 （3 puzzle problem）
23 1
23 1
2 13
2.1 状态空间法
2 13
2
11
3
1
初始棋局
12
3
目标棋局
2.1.2 状态图示法 图论术语
过程性知识表示主要用来描述规则性知识和控制结构 知识。将有关某一问题领域的知识，连同如何使用这 些知识的方法，均隐式地表达为一个求解问题的过程 （如程序）
6
2.1状态空间法 （State Space Representation）
状态空间表示法就是以“状态空间’’的 形式来表示问题及其搜索过程的一种方法。
第二章 知识表示方法
2.1 状态空间法 2.2 问题归约法 2.3 谓词逻辑法 2.4 语义网络法 2.5 其他方法 2.6 小结
1
知识表示的基本概念
什么是知识？（专家看法）
Feigenbaum 认 为 知 识 是 经 过 削 减 、 塑 造 、 解 释 和 转换的信息。简单地说，知识是经过加工的信息。
（W，0，W，z） climbbox （W，1，W，z）
16
2.1 状态空间法
grasp猴子摘到香蕉，即有
（c，1，c，0）
grasp
（c，1，c，1）
该初始状态变换为目标状态的操作序列为 {goto(b),pushbox(c),climbbox,grasp}
的适用性或先决条件以及右部描述规则应用时所完成的动作。
– 一个控制策略：它确定应该采用哪一条适用规则，而且当数据库
的终止条件满足时，就停止计算。
13
状态空间表示举例
例：推销员旅行问题（运筹学－图论－最短路径） 例：猴子和香蕉问题
2.1 状态空间法
在一个房间内有一只猴子(可把这只猴子看做一个机器人)、一个箱子和一束香蕉。
知识的特性 相对正确性：在一定前提条件下正确。 不确定性：知识存在“真—假”程度之分。 可表示性：知识可数据化形式表示。 可利用性：知识就是力量。
3
知识的分类 知识可以从不同角度划分，得到不同的分类方法。 ➢ 按照知识的作用范围来划分，知识可以分为常识性知识、领域性
知识。 ➢ 按照知识的作用及表示来划分，知识可以分为事实性知识、规则
Bernstein说知识是由特定领域的描述、关系和过 程组成的。
Hayes-Roth认为知识是事实、信念和启发式规则。 从知识库观点看，知识是某论域中所涉及的各有 关方面、状态的一种符号表示。
2
知识 知识是人们把实践中获得的信息关联在一起所 形成的信息结构，是构成智能的基础。 知识→信息→数据→符号
14
香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到 香蕉呢?上图表示出猴子、香蕉和箱子在房间内的相对位置。
解题过程
2.1 状态空间法
用一个四元表列（W，x，Y，z）来表示这个问题状态.
W－猴子的水平位置 x－当猴子在箱子顶上时取x=1；否则取x=0 Y－箱子的水平位置 z－当猴子摘到香蕉时取z=1；否则取z=0
对知识进行表示的过程就是把知识编码成某种数据结 构的过程。
知识表示研究用机器表示知识的可行性、有效性的一 般方法，是一种数据结构与控制结构的统一体，既考 虑知识的存储，又考虑知识的使用。
5
知识表示方法可以分为陈述性知识表示和过程性知识 表示两大类。
陈述性知识表示主要是用来描述事实性知识。这类表 示法就是将对象的有关事实陈述出来，并以数据的形 式表示。强调事物所涉及的对象是什么，是对事物有 关知识的静态描述，是知识的一种显式表达形式。而 对于如何使用这些知识，则通过控制策略来决定。
性知识、控制性知识和元知识。 ➢ 按照知识的确定性划分，知识可以分为确定性知识和不确定性知
识。 ➢ 按照人类的思维及认识来划分，可分为逻辑性知识和形象性知识。
4
知识的表示就是对人类知识的一种描述，把知识表示 成计算机能够处理的数据结构。
知识表示是研究用机器表示知识的可行性、有效性的 一般方法，是一种数据结构与控制结构的统一体，既 考虑知识的存储又考虑知识的使用。
这个问题的操作（算符）如下： – 2 goto（U）表示猴子走到水平位置U – 或者用产生式规则表示为
（W，0，Y，z） goto（U） （U，0，Y，z）
15
2.1 状态空间法
pushbox（V）猴子把箱子推到水平位置V，即有
（W，0，W，z） pushbox（V） （V，0，V，z）
climbbox猴子爬上箱顶，即有