人工智能第二章49

9
5/7/2020
三、产生式系统的基本过程
步骤4是不确定的，只要求选出一条可用的规则
R，至于这条规则如何选取，却没有具体说明。
选取规则所依据的原则称为控制策略。
多数人工智能系统控制策略的信息并不足以在
第4步选出最合用的规则，因此，控制策略便成了一
个搜索过程。
高效的系统需要被求解问题足够的知识，以便在
18
5/7/2020
不可撤回控制策略的局限性
多数情况下找不到解。原因： (a) 爬山函数有多个局部极大值
例如： 123 74 865
125 74
863
目标 0
第二章 产生式系统
2.1 产生式系统概述 一、产生式系统的定义 产生式系统是人工智能系统中常用的一种程序 结构，是一种知识表示系统。 通常由以下三部分组成：
综合数据库 产生式规则集 控制系统
3
5/7/2020
一、产生式系统的定义
综合数据库：存放问题的状态描述的数据结构。
Note: ➢综合数据库不是常规意义的数据库，是一种数据结构。 一般数据库所存数据的结构很简单，通常只有数值与字
步骤4选出一条最合用的规则。第三章，第四章
10
5/7/2020
产生式系统的特点
一、模块性强。综合数据库、规则集和控制系统相
对独立，程序的修改更加容易。
二、各产生式规则相互独立，不能互相调用，增加
一些或删去一些产生式规则都十分方便。
三、产生式规则的形式与人们推理所用的逻辑形式
十分接近，人们具有的知识转换成产生式规则
283 164 75
123 84 765
图2.1 八数码难题的初始状态与目标状态
7
5/7/2020
八数码难题的产生式系统表示
综合数据库：以状态为节点的有向图。
状态描述： 3×3矩阵
产生式规则：
IF<空格不在最左边>Then<左移空格>；
IF<空格不在最上边>Then <上移空格> ；
IF<空格不在最右边>Then <右移空格> ；
16
5/7/2020
例：八数码难题 不可撤回式控制
283源自文库164 75
283 14 765
23 1 8 4 -3 765
-4
-3
123 84 765
123 84
765
23 1 8 4 -2 765
0
17
-1
5/7/2020
不可撤回控制策略的优点
1. 只记录当前一个节点，空间复杂性很低。 2. 若能找到解，则速度很快。
5
5/7/2020
一、产生式系统的定义
控制系统：
（1）选择规则： 对同一个状态的多个可用规则排序。
（2）检验状态描述是否满足终止条件。 如果满足终止条件，则终止产生式系统的运行，
并用使用过的规则序列构造出问题的解。
6
5/7/2020
二、产生式系统的例
八数码难题 由8个标有1－8的棋子和一个3×3的棋盘 组成。把8个棋子放在棋盘里，形成一个初始状态，然 后移动棋子，想办法达到规定的目标状态。在移动棋 子时，只能把棋子移进相邻的空格中。
知识表示
知识是一切智能行为的基础，也是软件智能化的重要 研究对象。要使软件具有智能，就必须使它具有知识， 而要使软件具有知识，首先必须解决知识的表示问题。
所谓知识表示实际上就是对知识的一种描述，即用一 些约定的符号把知识编码成一组计算机可以接受的数 据结构。所谓知识表示过程就是把知识编码成某种数 据结构的过程。
符串；综合数据库的数据可以很复杂，其中状态描述可
以为常规的各种数据结构，如表、数组、字符串、集合、
矩阵、 树、图等等。
➢综合数据库是动态变化的。
4
5/7/2020
一、产生式系统的定义
产生式规则形式： IF前提条件 THEN操作
当规则的前提条件被某一状态描述满足时， 就对该状态施行规则所指出的操作。
5/7/2020
一、不可撤回的控制策略
爬山函数：定义在整个综合数据库上的实数值函数， 目标状态有最大的函数值。
目 标：爬到山顶。 控制策略：应用爬山函数选一规则，使得所选下一状态的 爬山函数值不减少且最大（有两个相同的最大值时任选一 个；若无这样的规则，则终止爬山过程）。
14
5/7/2020
例：八数码难题，不可撤回式控制
人爬山过程，是利用关于每一个状态的局部知识
构造全局性解的过程。在盲人爬山过程中，无论
爬到哪一点，他总沿着坡度最陡的方向向上爬，
这是局部性的知识，尽管他事先对爬山路线并不
了解，但只要按照这个原则向上爬，就一定能爬
到某一山顶，于是确定了一条从山脚到山顶的爬
山路线，也可以说构造出一个具有某种意义下全
13 局性的解。
IF<空格不在最下边>Then <下移空格> 。
控制系统：
选择规则:按左、上、右、下的顺序移动空格。
8
终止条件：匹配5/7成/202功0 。
三、产生式系统的基本过程
Procedure PRODUCTION 1. DATA←初始状态描述 2. until DATA 满足终止条件，do： 3. begin 4. 在规则集合中，选出一条可用于DATA的规则R 5. DATA←把R应用于DATA所得的结果 6. End
一般来说，同一知识可以有多种不同的表示形式，而 不同表示形式所产生的效果又可能不一样。
1
5/7/2020
常用的知识表示方法
非结构化方法
– 逻辑表示法 – 产生式系统
结构化方法
– 框架 – 语义网络
QA3,STRIPS,DART,MOMO DENDRAL，MYCIN
过程式知识表示法
2
5/7/2020
很容易，产生式规则也容易被人们读懂。
DENDRAL和MYCIN都采用了产生式系统的结构。
11
5/7/2020
2.2 控制策略
产生式系统的控制策略分为两类： 不可撤回的控制策略 试探性控制策略：回溯方式和图搜索方式
12
5/7/2020
一、不可撤回的控制策略（瞎子爬山法）
➢基本思想
采用不可撤回控制方式的解题过程类似于盲
设爬山函数CF(S) ：不在目标位的数码个数的 负值。
28 3
初始状态S0 1 6 4
7
5
123
8 4 目标状态Sg
765
CF(S0)＝ - 4 CF(Sg)＝ 0
状态描述S：3阶方阵
4条产生式规则使用顺序：空格左、上、右、下移。
15
5/7/2020
例：八数码难题，不可撤回式控制
控制策略：处于任一状态S，系统根据爬 山函数选择一条规则使得这条规则作用 于 S 时，获得的下一状态爬山函数不减 少且最大（亦即距离目标状态最少）。