第二章知识表示方法
教学内容
智能系统问题求解所采用的几种主要的知识表示方法(状态空间法.问题归约法.谓词逻辑法.语义网络法)以及基于不同表示法的问题求解方法。
教学重点
1. 状态空间表示法中问题的状态描述.改变状态的操作和问题目标状态的搜索;
2. 问题规约的一般步骤.规约的与或图表示;
3. 谓词逻辑的语法和语义.量词的辖域.谓词公式的置换与合一;
4. 语义网络的构成.语义基元的选择.语义网络的推理等。
教学难点
状态描述与状态空间图示.问题归约机制.置换与合一。
教学方法
课堂教学为主,同时结合《离散数学》等已学的内容实时提问.收集学生学习情况,充分利用网络课程中的多媒体素材来表示抽象概念。
教学要求
1. 重点掌握用状态空间法.问题归约法.谓词逻辑法.语义网络法来描述问题.解决问题;
2. 掌握这些表示方法之间的差别;并对其它表示方法有一般了解
2.1 状态空间法
教学内容本节讨论基于解答空间的问题表示和求解方法,即状态空间法,它以状态和操作符为基础来表示和求解问题。
教学重点问题的状态描述,操作符。
教学难点选择一个好的状态描述与状态空间表示方案。
教学方法以课堂教学为主;充分利用网络课程中的多媒体素材来阐述抽象概念。
教学要求重点掌握对某个问题的状态空间描述,学会组织状态空间图.用搜索图来求解问题。
2.1.1 问题状态描述
1.基本概念
状态(state)
它是为描述某类不同事物间的差别而引入的一组最少变量q0,q1,…,qn的有序集合,其矢量形式如下:
Q=[q0,q1,…,qn]' (2.1)
式中每个元素qi(i=0,1,…,n)为集合的分量,称为状态变量。给定每个分量的一组值就得到一个具体的状态,如
Qk=[q０k,q1k,…,qnk]' (2.2)
操作符(operator)
称使问题从一种状态变化到另一种状态的手段为操作符或算符。
状态空间(state space)
它是表示一个问题全部可能状态及其关系的图,它包含所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。因此,状态空间记为三元状态(S,F,G)。
提问 1.列举已经学习过的“状态”概念,并比较之。
2.列举操作符。
2.状态空间描述
要完成一个问题的状态描述,必须确定3件事:
(1) 状态描述方式,特别是初始状态描述;
(2) 操作符集合及其对状态描述的作用;
(3) 目标状态描述的特性。
举例列举几个日常生活中状态与操作符的例子,如:棋局。讲解初始状态、操作符、中间状态与目标状态之间的关系;讲解三数码难题的状态变化过程。
讨论每走一步后,棋局都变化了,以此来理解问题的状态空间。
2.1.2 状态图示法
图的基本概念
图是一个包含节点(不一定是有限的节点)和节点间弧线的集合。若图中每条弧线均标有方向,则称这种图为有向图(directed graph)。
代价(cost)
是给各弧线指定数值以表示加在相应操作符上的代价。
图的显式说明
是指各节点及其具有代价的弧线由一张表明确给出。
图的隐式说明:
是指各节点及其具有代价的弧线不能由一张表明确给出。
提问举已经学习过的“有向图”、“路径”及“代价”等的概念。
举例针对三数码难题的状态变化过程讲解图的几个基本概念
2.2 问题规约法
教学内容知识表示的归约法,即已知问题的描述,通过一系列变换把此问题最终变为一个子问题集合;这些子问题的解可以直接得到,从而解决了初始问题的方法。
教学重点问题归约的基本思想,问题描述,问题变换的操作符,与或图表示。
教学难点如何把初始问题变换为子问题,与或图表示方法。
教学方法课堂教学为主,充分利用网络课程中的相关多媒体素材来表示抽象概念。
教学要求通过梵塔难题重点掌握问题归约法的机理和问题归约描述方法。学会用与或图表示归约问题。
2.2.1 问题归约描述
1.问题归约法的概念
问题归约是将初始问题变为一个本原问题集合。
2.问题归约法的组成部分
(1) 一个初始问题描述;
(2) 一套把问题变换为子问题的操作符;
(3) 一套本原问题描述。
3.示例:梵塔难题
问题
有3个柱子(1,2,3)和3个不同尺寸的圆盘(A,B,C)。在每个圆盘的中心有个孔,所以圆盘可以堆叠在柱子上。最初,全部3个圆盘都堆在柱子1上:最大的圆盘C在底部,最小的圆盘A 在顶部。要求把所有圆盘都移到柱子3上,每次只许移动一个,而且只能先搬动柱子顶部的圆盘,还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。
归约过程
(1) 移动圆盘A和B至柱子2的双圆盘难题;
(2) 移动圆盘C至柱子3的单圆盘难题;
(3) 移动圆盘A和B至柱子3的双圆盘难题。
讲述梵塔问题的来源。
提问一圆盘问题要走几步?两圆盘问题要走几步?三个.四个．．．等?
2.2.2 与或图
1.与或图的概念
用一个类似图的结构来表示把问题归约为后继问题的替换集合,画出归约问题图。
2.与或图的有关术语
父节点
是一个初始问题或是可分解为子问题的问题节点;
子节点
是一个初始问题或是子问题分解的子问题节点;
或节点
只要解决某个问题就可解决其父辈问题的节点集合;
与节点
只有解决所有子问题,才能解决其父辈问题的节点集合;
