人工智能课件之知识表示方法.pptx

精选ppt
32
2.2 问题规约法
梵塔问题归约图
•数据结构介绍
（111）（333）
•思考题：四圆盘问题
（111）（122） （122）（322）
（）（333）
（111）（113） （113）（123） （123）（122） （322）（321） （321）（331） （331）（333）
精选ppt
精选ppt
19
解题过程
将原始问题归约为一个较简单问题集合 将原始梵塔难题归约（简化）为下列子
难题
– 移动圆盘A和B至柱子2的双圆盘难题 – 移动圆盘C至柱子3的单圆盘难题 – 移动圆盘A和B至柱子3的双圆盘难题
详细过程参看下图
精选ppt
20
2.2 问题规约法
解题过程（3个圆盘问题）
123
123
叫做从节点ni1至节点nik的长度为k的路径
代价 用c（ni，nj）来表示从节点ni指向节点nj
的那段弧线的代价。两点间路径的代价等于连
接该路径上各节点的所有弧线代价之和.
精选ppt
6
图的显示说明 对于显式说明，各节点及其具
有代价的弧线由一张表明确给出。此表可能列出 该图中的每一节点、它的后继节点以及连接弧线 的代价
问题归约的实质：
–从目标(要解决的问题)出发逆向推理，建立 子问题以及子问题的子问题，直至最后把初 始问题归约为一个平凡的本原问题集合。
精选ppt
18
2.2 问题规约法
2.2.1 问题归约描述 （Problem Reduction Description）
梵塔难题
1
2
3
A B C
思考：用状态空间法有多少个节点？为什么？

• 这种图搜索控制策略将在第三章讨论.
推销员旅行问题
• 例2.1 推销员旅行问题（旅行商问题）
•
一个推销员计划出访推销产品。他
从一个城市（如A）出发，访问每个城市
一次，且最多一次，然后返回城市A。要
求寻找最短路线。
推销员旅行问题
• 状态描述：目前为止访问过的城市列表（A…）
•
初始状态： （A）
•
棋局。首先把适用的算符用于初始
状态，以产生新的状态；然后，再
把另一些适用算符用于这些新的状
态；这样继续下去，直至产生目标
状态为止。
八数码难题部分状态图
十五数码难题(思考)
11
9
1
3
7
5
13
2
15
1
2
3
4
12
5
6
7
8
8
6
9
10
11
12
10
14
13
14
15
4
初始状态
目标状态
状态图示法
状态空间的图示形式称为状态空间图。
启发式规则，如果下雨，则出门带伞。
知识的要素
• 控制：当有多个动作同时被激活时，选择哪一个动
作来执行的知识。是有关问题的求解步骤、规划、求
解策略等技巧性知识.
• 元知识：怎样使用规则、解释规则、校验规则、解
释程序结构等知识。是有关知识的知识，是知识库中
的高层知识。元知识与控制知识有时有重叠.
知识的分类
目标状态： （A……A）
推销员旅行问题
图2.4 推销员旅行问题状态空间图
• 算符：下一步走向的城市(a)(b)(c)(d)(e)

产生式的基本形式
（2）规则型知识的产生式表示 规则描述的是事物间的因果关系。含义是：如果…则…，规则型 知识的产生式表示基本形式是：
P→Q 或者 IF P THEN Q 其中，P是生产式的前提，用于指出该生产式是否可用的条件；Q 是一组结论或操作，用于指出当前提P所指示的条件被满足时，应 该得出的结论或应该执行的操作。整个产生式的含义是：如果前 提P被满足，则可推出结论Q或执行Q所规定的操作。
产生式系统
规则集
控制器 匹配排序 冲突裁决
匹配
检索 产生式系统结构与工作过程
综合数据库
产生式系统
【例2.1】 建立一个动物识别系统的规则库，用以识别虎、 豹、斑马、长颈鹿、企鹅、鸵鸟、信天翁等7种动物。
框架表示法
框架
我们无法把过去的经验一一都存在脑子里，而只能以一个通用 的数据结构的形式存储以往的经验。这样的数据结构就是框架 （frame），框架提供了一个结构，一种组织。在这个结构或组织 中，新的资料可以用从过去的经验中得到的概念来分析和解释。 实例框架：对于一个框架，当人们把观察或认识到的具体细节填 入后，就得到了该框架的一个具体实例，框架的这种具体实例被 称为实例框架。 框架系统：在框架理论中，框架是知识的基本单位，把一组有关 的框架连结起来便形成一个框架系统。
人工智能导论
知识表示和知识图谱
2.1知识表示
人类之所以有智能行为是因为他们拥有知识，智能活动过程 其实就是一个获得并运用知识的过程，要使机器系统具有人的智 能能力（人工智能AI），则必须以人的知识为基础，知识是人工 智能的基石。但人类的知识要用适当的模式表示出来，才能够存 储到计算机中并被识别运用，本节将对人工智能中常用的几种知 识表示方法进行介绍，为后续学习奠定基础。

• • • •
对一个问题的状态描述，必须确定3件事： (1) 该状态描述方式，特别是初始状态描述； (2) 操作符集合及其对状态描述的作用； (3) 目标状态描述的特性
状态空间表示
• 典型的例子: • 下棋、迷宫及各种游戏。
三数码难题
• 问题描述: • 三数码难题:有3个编有1-3并放在2X2方格 棋盘上可走动的棋子组成.棋盘上总有一个 空格,以便让空格周围的棋子走进来.直至 从初始状态到达目标状态.
知识的要素
• 控制：当有多个动作同时被激活时，选择哪一个动 作来执行的知识。是有关问题的求解步骤、规划、求 解策略等技巧性知识. • 元知识：怎样使用规则、解释规则、校验规则、解 释程序结构等知识。是有关知识的知识，是知识库中 的高层知识。元知识与控制知识有时有重叠 .
知识的分类
根据知识表达的内容，将其简单地分为如下几类： 事实性知识 知识的一般直接表示，如果事实性知识是批量的、有规律的，则 往往以表格、图册，甚至数据库等形式出现。 这种知识描述一般性的事实，如凡是冷血动物都要冬眠，哺乳动 物都是胎生繁殖后代等。
节知识表示方法
• • • • • • • • • 内容提要：
状态空间法 问题归容之前，我们先了解一 下有关知识及其表示的概念。 人类的智能活动过程主要是一个获得 并运用知识的过程，知识是智能的基础 。为了使计算机具有智能，就必须使它 具有知识。 那什么是知识呢？
三数码难题
八数码难题
初始棋局
目标棋局
表示
•根据问题状态、操作算符和目标条件选择各种 表示，是高效率求解必须的。在问题求解过程中， 会不断取得经验，获得一些简化的表示。 • 制定操作算符集： • * 直观方法——为每个棋牌制定一套可能的走 步：左、上、右、下四种移动。这样就需32个 操作算子。 • * 简易方法——仅为空格制定这4种走步，因 为只有紧靠空格的棋牌才能移动。 • * 空格移动的唯一约束是不能移出棋盘。

将总问题分解为若干子问题。若所有的子问题都解决了， 则总问题也解决了，这是与的逻辑关系。 • 变换—或树：将较难的问题变换为较易的等价或等效的问 题。若一个难问题可以等价变换为几个容易问题，则任何 一个容易问题解决了，也就解决了原有的难问题，这是或 的单）
2.目标：（0，0）；
3.分割操作：每次操作，分割 出一个小长方块，割去一个小黑 格和一个小白格，使状态变量都 减去1，如第一次分割，使原始状 态变成状态（2n2-1，2n2-3）。显 然，经过2n2-2次操作后，状态变 为（2，0），不可能达到所求的 目标状态（0，0）。
初始状态 （2n2，2n2-2）
• 1）、原始问题：在 2n×2n的方格棋盘 中，去掉对顶角上 两个小方格后，如 图（a）所示，问能 否将它分割为若干 1×2的小长方块？ (“组合爆炸”)。
（a）原始问题
Artificial Intelligence
• 2）、同构问题：将棋盘中 小方格相间着色，将其化为 同构问题，如图（b）所示， 由此可见，无论n为何值， 对顶角上两个小方格是同色 的，去掉它们后，小白格和 小黑格的数目之间的差值为 2。
等价问题 （易）
等价问题 （更易）
Artificial Intelligence
三) 产生式系统
• 产生式系统是一种最早被使用且直到现在 仍被广泛使用的知识表示方法.
• 在产生式系统中，知识分为两部分：用事 实表示静态知识; 用产生式规则表示推理过 程和行为.
• 三个基本部分组成：一个综合数据库（事 实库）、一组产生式规则（规则集）和一 个控制系统（控制器）。
• 知识是人们对自然现象的认识和从中总结出来的 规律、经验。
• 表示是使用人造的体系对自然界事物的运算规律 进行概括与抽象的模型。

On（Box，A）（Box在A上）
At(Robot，A)（机器人在A旁边）
EmptyHanded（robot）（机器人手空空）
感 20谢19你-10的-5欣赏
32
例（续）
• 先决条件成立与否的验证可以使用归结法。如将初始状态视作已知条件， 而将要验证的先决条件作为结论，便可使用归结法了。
• 归结过程如下：
达式之一。因此，如果采用谓词逻辑作为系统的理 论背景，则可将数据库系统扩展改造成知识库。
– 一阶谓词逻辑具有完备的逻辑推理算法。如果对逻 辑的某些外延扩展后，则可把大部分的知识表达成 一阶谓词逻辑的形式。（知识易表达）
感 20谢19你-10的-–5欣赏………..
27
表示方法 —逻辑表示法
• 谓词逻辑法是应用最广的方法之一，其原因 是：
陈述性表示
分布表示 过程性表示
逻辑表示 Hale Waihona Puke 生式表示 语义网络表示框架表示
感 20谢19你-10的-5欣赏
脚本表示
17
表示方法
概述 • 直接表示 • 逻辑表示 • 产生式规则表示
法 • 语义网络表示法
感 20谢19你-10的-5欣赏
框架表示法 脚本方法 过程表示 混合型知识表示方法 面向对象的表示方法
第四章 知识表示
• 概述
• 表示方法
感 20谢19你-10的-5欣赏
1
第四章 知识表示方法
• 概述
• 表示方法
感 20谢19你-10的-5欣赏
2
概述
• 人工智能研究中最基本的问题之一
–在知识处理中总要问到：“如何表示知识？”， “知识是用什么来表示的?”。怎样使机器能懂， 能对之进行处理，并能以一种人类能理解的方 式将处理结果告诉人们。