第二知识表示

第二知识表示第1页，共35页，2023年，2月20日，星期一2知识是一切智能行为的基础，是人工智能的重要研究对象。一个智能系统的智能性很大程度上取决于知识的数量及其可利用程度。使计算机具有知识，首先必须解决知识的表示问题。两个问题

1.概念

2.表示方法第2页，共35页，2023年，2月20日，星期一32.1什么是知识？知识是人们在改造客观世界的实践中积累起来的认识和经验。

数据：符号或符号的组合

信息：不同数据组成的一种结构

知识：对信息进行智能性加工所形成的对客观世界规律性的认识把有关信息关联在一起所形成的信息结构称为知识。

对客观世界的描述第3页，共35页，2023年，2月20日，星期一4真假性及其相对性

可以通过实践或推理来证明知识为真或为假知识的真与假是相对于一定条件而言的不确定性

不完备，不确定，模糊矛盾性或相容性

不同知识之间相互对立或不一致，或反之可表示性与可利用性

知识可以用适当的形式表示，并用来解决问题

知识的属性第4页，共35页，2023年，2月20日，星期一5按知识的性质概念、命题、公理、定理、规则和方法等按知识的作用范围常识性知识和领域性知识按知识的作用事实性知识、过程性知识和控制性知识按知识的层次

表层知识和深层知识按知识的确定性按知识的结构及表现形式

逻辑性知识和形象性知识知识的类型第5页，共35页，2023年，2月20日，星期一62.2知识表示知识表示是指用一些约定的符号把知识编码成一组计算机可以接受的数据结构。对知识表示方法的要求

1.表示能力知识表示范围的广泛性；领域知识表示的高效性；对非确定性知识表示的支持程度

2.可利用性对推理的适应性和对高效算法的支持性第6页，共35页，2023年，2月20日，星期一73.可组织性与可维护性

知识的组织是指把有关知识按照某种方式组成一种知识结构。知识维护是指在保证知识的一致性与完整性的前提下对知识所进行的增加删除修改等操作。

4.可实现性

便于在计算机上实现

5.自然性与可理解性

符合人们的日常习惯和思维方式，易读，易懂知识表示第7页，共35页，2023年，2月20日，星期一8知识表示观点陈述性观点

以陈述方式把知识用一定的数据结构表示出来，把知识看作一种特殊的数据，知识表示仅说明描述的对象是什么，不涉及如何运用知识的问题。过程性观点

程序（亦称为过程）的方式把知识表示出来，把知识寓于程序之中，把知识表示和运用知识结合起来。第8页，共35页，2023年，2月20日，星期一9状态空间法问题归约法谓词逻辑法语义网络法框架表示法知识表示方法第9页，共35页，2023年，2月20日，星期一102.3状态空间法

对人工智能研究中运用的问题求解方法进行综合分析，可以发现许多问题求解方法是采用试探搜索方法的。也就是说，这种方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法。状态空间法是以状态和算符为基础来表示和求解问题的。第10页，共35页，2023年，2月20日，星期一11实例：十五数码难题一.问题的状态描述如何把初始棋局变换为目标棋局？第11页，共35页，2023年，2月20日，星期一12状态：为描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，其矢量形式如下：

Q=[q0，q1，…，qn]状态变量：状态集合中的每个元素qi（i=0,1,…,n）。具体状态：给定每个分量的一组值。如

Qk=[q0k，q1k，…，qnk]操作符：使问题从一种状态变换到另一种状态的手段，也叫算符。算符可以是走步、过程、规则、数学算子、运算符号或逻辑符号等。问题的状态空间：表示该问题全部可能状态及其关系的图。它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。因此，状态空间可记为三元组（S，F，G）。一.问题的状态描述第12页，共35页，2023年，2月20日，星期一13二、状态空间法状态空间法：从某个初始状态开始，每次加一个操作符，递增地建立起操作符的试验序列，直到达到目标状态为止。状态图：初始状态可达到的各状态所对应的节点组成的图。当用一个图来表示某个状态空间时，图中各节点标上相应的状态描述，而有向弧线旁边标上算符。寻找从一种状态变换为另一种状态的某个算符序列问题等价于寻找图的某一路径问题。第13页，共35页，2023年，2月20日，星期一14图论中的几个术语：

图；有向图；后继节点（后裔）；父辈节点（祖先）；路径（长度为k的路径）；节点nj是从节点ni可达到的路径；代价；两节点间路径的代价。第14页，共35页，2023年，2月20日，星期一15三.状态空间表示举例

实例：猴子摘香蕉问题acb箱子第15页，共35页，2023年，2月20日，星期一16

实例：猴子摘香蕉问题问题状态的表示：四元组（W，x，Y，z）

W：猴子的水平位置。W=a，b，c。

x：当猴子在箱子顶上时取x=1；否则取x=0。

Y：箱子的水平位置。Y=a，b，c。

z：当猴子摘到香蕉时取z=1；否则取z=0。初始状态：（a，0，b，0）目标状态：（c，1，c，1）第16页，共35页，2023年，2月20日，星期一17

算符集合：

goto(U)：猴子走到水平位置U。

（W，0，Y，z）

goto(U)

（U，0，Y，z）

pushbox(V)：猴子把箱子推到水平位置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）算符的适用性条件：强加于操作的实用性条件。

如：应用算符pushbox(V)时，要求猴子与箱子必须在同一位置。第17页，共35页，2023年，2月20日，星期一18操作序列：{goto(b)，pushbox(c)，climbbox，grasp}猴子摘香蕉问题的状态空间图如下图所示。第18页，共35页，2023年，2月20日，星期一19练习题：设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？第19页，共35页，2023年，2月20日，星期一202.4问题归约法问题归约法：在现实生活中，有许多问题可以通过一系列变换而最终变为一个子问题集合；这些子问题的解可以直接得到，通过解决这些子问题，从而就解决了初始问题。这样一种解决问题的思路就称为是问题归约法。第20页，共35页，2023年，2月20日，星期一21实例：梵塔难题一.问题的归约描述如何由初始配置变换为目标配置？ABC123ABC123初始配置目标配置第21页，共35页，2023年，2月20日，星期一22我们把原始问题归约为3个子问题：（1）移动A、B->2双圆盘问题：可进一步归约（2）移动C->3单圆盘问题：可直接求解--本原问题（3）移动A、B->3双圆盘问题：可进一步归约与或图：可以有效说明问题归约法的求解过程。梵塔问题归约图第22页，共35页，2023年，2月20日，星期一23问题归约描述：采用问题归约法描述与求解问题时问题归约表示由三部分组成：（1）一个初始问题描述如：[（111），（333）]（2）一套把问题变换为子问题的操作符—问题归约算符如：移动A、B->2等（3）一套本原问题描述如：[（122），（322）]本原问题：是可直接求解或具有已知解答的问题，出现本原问题即可停止搜索。问题归约法的实质：从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个本原问题集合。问题归约的目的：最终产生具有明显解答的本原问题。第23页，共35页，2023年，2月20日，星期一24二.与或图表示用问题归约法描述和求解问题的过程可以用一个与或图来表示。关于与或图：例如：设想问题A既可由求解问题B和C，也可由求解问题D、E和F，或者由单独求解问题H来解决。这一关系可由下图所示的结构图来表示。第24页，共35页，2023年，2月20日，星期一25说明：

在与或图中，如果一个节点具有任何后继节点，那么这些后继节点既可全为与节点，也可全为或节点。特殊情况下，根本不出现任何与节点，如在状态空间图中就不存在与节点，即状态空间图是普通图，因此可以说问题归约法是比状态空间法更通用的问题求解方法。通过与或图，在某个问题描述中应用问题归约算符，可以依次产生出一个中间或节点和与节点后裔，从而可以用与或图来表示问题归约方法的相关结构。在与或图中，起始节点对应于原始问题描述，叶子节点对应于本原问题描述。第25页，共35页，2023年，2月20日，星期一26

引入与或图后，问题求解过程就转换为与或图上的搜索过程，搜索的目的是要表明起始节点有解，在与或图中一个可解节点的一般定义可以归纳如下：（1）叶子节点是可解节点（本原问题）。（2）如果某个非叶节点含有或后继节点，那么只有当其后继节点至少有一个可解时，该非叶节点才是可解的。（3）如果某个非叶节点含有与后继节点，那么只有当其后继节点全部可解时，该非叶节点才是可解的。在上述定义基础上，可以给出解图的定义，即解图是那些可解节点的子图，这些节点能够证明其初始节点是可解的。问题求解过程实际上就是生成与或图的足够部分，以证明初始节点可解。第26页，共35页，2023年，2月20日，星期一27三.问题归约机理出发点—引入关键算符：对于状态空间的搜索问题，虽然寻求某个解答中的整个算符序列比较困难，但规定这些算符中的一个却往往比较容易。如果某个算符被认为是求解问题的决定性步骤，那么就很容易找到这样一个算符。例如，梵塔难题中“移动C->3”这个算符就是求解问题的决定性步骤，也很容易找到该算符，这种具有决定性作用的算符叫做关键算符。第27页，共35页，2023年，2月20日，星期一28关键算符的作用：可见，一旦确定了某个关键算符f，就可以把问题归约为如下三个子问题：

（1）（S，F，Gf

）；

（2）（{g}，F，{f（g）}）；

（3）（{f（g）}，F，G）。问题（2）是本原问题问题（1）和（3）可以用直接的状态空间搜索技术或进一步的问题归约来求解（寻找子问题的关键算符，进一步归约下去）。第28页，共35页，2023年，2月20日，星期一29关键算符的作用：首先必须寻找任何状态空间搜索问题的候选关键算符集合。如何寻找候选关键算符呢？——计算某个问题的差别。利用候选关键算符集合构建与或图。第29页，共35页，2023年，2月20日，星期一30什么是差别？实例：猴子摘香蕉问题把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={f1，f2，f3，f4}满足目标条件的状态集合：G第30页，共35页，2023年，2月20日，星期一31实例：猴子摘香蕉问题应用关键算符和差别的归约过程如下：首先计算初始问题的差别，（a，0，b，0）不满足目标测试的原因在于其最后一个元素不是1。与归约这个差别相关的关键算符是f4=grasp，用f4来归约初始问题，得到如下子问题：

（1）（{（a，0，b，0）}，F，Gf4）

（2）（S1，F，f4（S1））（本原问题）

（3）（f4（S1），F，G）（本原问题）其中Gf4是适用于算符f4的状态描述集合，S1∈Gf4

。第31页，共35页，2023年，2月20日，星期一32

要求解问题（1），就要先计算其差别。由（a，0，b，0）所描述的状态不在Gf4中，差别如下：箱子不在c处猴子不在c处猴子不在箱子上f2=pushbox（c）f1=goto（c）f3=climbbox

与差别相关的关键算符如右

用关键算符f2归约问题（1），得到如下子问题：（1-1）（{（a，0，b，0）}，F，Gf2）

（1-2）（S11，F，f2（S11））（本原问题）

（1-3）（f2（S11），F，Gf4

）Gf2是适用于算符f2的状态描述集合，S11∈Gf2

第32页，共35页，2023年，2月20日，星期一33

现在必须求解问题（1-1），所以仍需要先计算其差别。此差别为：猴子不在b处f1=goto（b）

与差别相关的关键算符如右用关键算符f1归约问题（1-1），得