《人工智能及其应用》第2章知识表示.pptx

第2章 知识表示;2.1 基本概念;2.1.1 知识的概念; 1.知识的要素 知识的要素是指构成知识的必需元素。一般而言，人工智能系统的知识包含事实、规则、控制和元知识。 事实是指有关问题环境的一些事物的知识，包括事物的分类、属性、事物间关系、科学事实、客观事实等。 规则是指有关问题中与事物的行动、动作相联系的因果关系知识。 控制是指当有多个动作同时被激活时，选择哪一个动作来执行的知识。 元知识是指怎样使用规则、解释规则、校验规则、解释程序结构等知识。 ;2.知识的特性 知识具有相对正确性。在一定的条件及环境下，知识一般来说都是正确的，可信任的。 知识具有不确定性。知识有一个逐步完善的过程。在此过程中，或者由于客观事物表露得不够充分，致使人类对它的认识不够完全；或者对充分表露的事物一时抓不住本质，致使对它的认识不准确。另外，世界上的事物并不都是“不为真就一定为假的”。在某些情况下，它可能既不完全为真，也不完全为假，而处于是真与假之间的某个状态上。 知识具有可表示性。知识是用人类所能接受的、理解和处理的形式来表示。 知识具有可利用性。 ;3.知识的分类 按其应用范围可分为常识性知识和领域性知识。 按其确定性来可分为确定性知识和不确定性知识。 按其结构及表现形式分为逻辑性知识和形象性知识。 按其形式可分为显性知识和隐性知识。 按其作用可分为事实性知识、过程性知识和控制性知识。;2.1.2 知识的表示方法;2.1.2 知识的表示方法;2.2 状态空间表示法;2.2.1 状态及状态空间;2.2.2 状态空间图; 例2-1 二阶梵塔问题。假设有三根柱子，在1号柱子上穿有A、B两片空心圆盘，A的直径小于B的直径，且位于B的上面。要求把这两片空心圆盘全部移到另一根柱子上，规定每次只能移动一片，而且任何时刻都不能使B位于A的上面。 解 设用SK=(SK0, SK1)表示问题的状态。其中，SK0表示A所在的柱子号；SK1表示B所在的柱子号，全部可能状态有如下9种： S0=(1,1)，S1=(1,2)，S2=(1,3)，S3=(2,1)，S4=(2,2)，S5=(2,3)，S6=(3,1)，S7=(3,2)，S8=(3,3) 问题的初始状态集合为S={S0}，目标状态集合为G={S4, S8}。操作算子分别为A(i, j)和B(i, j)。A(i, j)表示把A从第i号柱子移到第j号柱子上；B(i, j)表示把B从第i号柱子移到第j号柱子上。; 可知共有如下12个操作算子： A(1, 2)，A(1, 3)，A(2, 1)，A(2, 3)，A(3, 1)，A(3, 2) B(1, 2)，B(1, 3)，B(2, 1)，B(2, 3)，B(3, 1)，B(3, 2) 根据上述9种可能状态及12种操作算子，可构成二阶梵塔问题的一个状态空间图。 ; 例2-2 传教士和野人问题。假设3个传教士带领3个野人划船渡河，其约束条件是船每一次最多只能运载两个人，同时在任何时候野人的数目一定不能比传教士多。 解 设用A和B表示河的两岸，初始状态下传教士、野人和船都在A岸，目标状态下这三者都到达B岸。我们用m表示传教士在A岸的数目，用c表示野人在A岸的数目，那么问题的状态可以表示为三元组（m,c,a）。其中a=1，表示船在A岸；a=0，表示船在B岸。根据这个约束条件，在A岸、B岸和船上，野人的数目都不能比传教士多，除非只有野人的情况。; 问题求解任务可描述为： (3,3,1) →(0,0,0) 在这个简单问题中，状态空间可能的状态总数为 32 ，但由于要遵守问题约束只有20个状态是合法的。鉴于存在不合法状态，还会导致某些合法状态不可达。 因此，这个问题总共只有16个可达的合法状态。渡河问题中的操作算子可以定义2类：L(m, c)和R(m, c)，分别指示从A岸到B岸的划船操作和从B岸返回A岸的划船操作。因为问题的约束条件，m和c取值的可能组合只有5个：1与0、2与0、1与1、0与1和0与2，故而总共有10个操作算子。;渡河问题的状态空间图可参见图2-3 ; 由上述两例可以看出： (1) 用状态空间表示问题时，必须先定义状态的描述形式，通过这种描述形式把问题的一切状态都表示出来。 (2) 状态空间的解答路径有多条。 (3) 一个复杂问题的状态空间一般都是十分庞大的。 对于一个具体问题来说，与解题有关的状态空间往往只是整个状态空间的一部分，因此只要能生成并存储这部分状态空间就可求得问题的解。 如果在搜索解答路径的过程中只画出搜索