文档介绍：第一章产生式系统
本章主要内容:
产生式系统的三个组成部分及其作用*
产生式系统解题的基本过程
产生式系统的三类控制策略*
问题的计算机表示原则
可分解的产生式系统的意义*
(*为重点内容)
是AI中最典型/最普遍的一种结构,大多数专家系统都用它来构造。
特点:解题过程与人类思维很相似。
(Global Database)
用来描述问题的状态或有关事实。一般随着解题过程不断变化。像棋局一样
(Set of Rules)
一般表示为 if ……. then……形式。
规则使用的条件采取的行动或结论
某规则使用后,可使综合数据库的状态发生变化,形成新的状态。即数据库变化的规则
(Control System of strategies)
即控制如何使用这些规则去搜索解(决定着解题过程或推理路线);还要记住使用过即使用规则的流程
的规则,以便找到解路径。
例题1:八数码游戏(似华容道)
2
8
3
1
6
4
7
5
1
2
3
8
4
7
6
5
让学生课后思考如何
存储,制定规则100min
可以经过思索,看出走步为:上上左下右。问题似怎样让计算机来解。
用产生式系统解题,须先建立问题的产生式系统描述,即给定综合数据库、规则集,
再利用某种控制策略求解。
(1)综合数据库
可见用二维数组较直观:(Sij),1≤i, j≤3, Sij∈{0,1,…,8}且不等《数据结构》中的各
一个具体的矩阵就表示一个棋局状态。对八数码游戏,显然有9!个状态,构成其种结构都可用。
状态空间――解题过程中所有可能出现的状态的集合。
(2)规则集
每一张牌的移动,都可归结为空格的移动(上、下、左、右),用4条规则描述:
if j0-1≥1 then(左移)Si0j0=Si0(j0-1),Si0(j0-1)=0;
if i0-1≥1 then(上移)Si0j0=S(i0-1)j0,S(i0-1)j0=0;
if j0+1≤3 then(右移)Si0j0=Si0(j0+1),Si0(j0+1)=0;
if i0+1≤3 then(下移)Si0j0=S(i0+1)j0,S(i0+1)j0=0.
(3)搜索策略
按某种策略(如爬山法)从规则集中不断选用规则,最终得到解路径。如(上、上、此处以“靠近目标法”
左、下、右)走步序列就是一个解。(其解题思路与人的思维相似) 演示,导出解路。
可见,用产生式系统解题,就是在问题的状态空间中去搜索一条从初态到终态的路径。
例题2:传教士与野人问题
3个传教士与3个野人渡河,船每次只能乘2人。问传教士为安全起见,如何规划
摆渡方案,是的任何时刻两岸及船上野人的数目均不超过传教士的数目。画草图
即
L R L R
M 3 0 M 0 3
C 3 0 C 0 3
B 1 0 B 0 1 1表示有船
约束条件:岸上M≥C,船上M+C≤2
综合数据库
用三元组(ML,CL,BL),其中0≤ML,CL≤3,BL∈{0,1},则问题可简化
为(3,3,3)―>(0,0,0)
状态空间总数:4×4×2=32个(见P19),最终16个。