【必修】人工智能原理 学习笔记（二）chapter 2 产生式系统

(零）常用的知识表示方法

1）非结构化方法：
①逻辑表示法： QA3，STRIPS，DART
②产生式系统： DENDEAL,MYCIN (chaper2,3,4)

2）结构化方法：
①框架
②语义网络

3）过程式知识表示法

（一）产生式系统概述

1.定义与部件构成

1.产生式系统：
是人工智能系统常用的一种程序结构，也是一种知识表示系统，通常由 综合数据库、产生式规则和控制系统 三个部分组成。

2.综合数据库：
综合数据库是由问题的状态描述所构成的集合；
【基础数据】
【它是动态变化的】

3.产生式规则：
产生式规则具有IF<前提条件> 和THEN<操作>的形式。当规则的前提条件被某一状态描述满足时，就对该状态实施规则所指出的操作；
【数据关系】

4.控制系统：
对于同一个产生式规则，通常有多个产生式规则可以使用，因此，控制系统决定在这些适用的规则中选出哪一条来使用。
同时，控制系统还具有第二个功能：即，检验状态描述是否满足终止条件。
【是本书的核心】

【预习时我认为这三个部件的运行规则如下】

2.产生式系统运行实例

1）表示问题

把一个实际问题转换成产生式系统，这是一件技术性很强的工作。在用产生式系统解决问题时，选择一种好的表示是非常重要的，好的表示可以使问题有较少的状态，较简单的规则，容易检验的终止条件，从而容易得到问题的解。

2）实例：八数码难题

①问题：
给定一个九宫格，只有最后一行中间的格子被空出，其余八个格子无顺序且不重复地分布着1-8这八个数字，每次只能将数字移动一个位置，希望最后能达到顺序摆放并且只空出中间格的状态。

②使用产生式规则描述对硬纸片的移动：
有很多种描述方式，比如直接移动数字还是移动空格，几种描述的简洁性截然不同。（选择后者）

③产生式系统的基本过程：

Procedure PRODUCTION
1.DATA <- 初始状态描述
2.until DATA 满足终止条件，do:
3.	begin
4.		在规则集合中，选出一条可用于DATA的规则R
5.		DATA <- 把R应用在DATA所得的结果
6.	end

3.产生式系统的优点（比较于通常的分级调用方式）

1）产生式系统具有更强的模块性：
综合数据库，规则集和控制部分相对独立，这使得程序的修改更加容易；而且不同模块之间并不相互交流。

2）各产生式规则是相互独立的，它们不能相互调用。 因此，增加一些产生式规则或删去一些产生式规则都十分方便；

3）产生式规则的形式与人们推理所用的逻辑形式十分接近，容易把人们的只是转换成产生式规则。

综上，产生式系统经常被大型人工智能系统所采用，比如DENDRAL和MYCIN。
———————————

（二）控制策略

Procedure PRODUCTION
1.DATA <- 初始状态描述
2.until DATA 满足终止条件，do:
3.	begin
4.		在规则集合中，选出一条可用于DATA的规则R
5.		DATA <- 把R应用在DATA所得的结果
6.	end

产生式系统中的：“在规则集合中，选出一条可用于DATA的规则R” 就是所谓的
控制策略，即如何从规则集中选出一条。

1.控制策略的分类

控制系统分为两类，一类是不可撤回的，一类是试探性的。试探性的控制策略又可以进一步分为回溯方式和图搜索方式。

1）不可撤回的控制策略（爬山函数）

爬山函数的简单说明：
无论我们正在爬山的哪一个过程中（获得局部知识），我们总是沿着最陡峭的方向向上爬，这样，我们向目标前进的方向就不会错。从而确定一个全局性的解。

在不可撤回的产生式系统中，用爬山函数来确定各状态的优劣。

在整个综合数据库上，爬山函数的函数值是一个实数，代表目标状态有最大的函数值。当有很多条产生式规则适用时，用对应的爬山函数值作为最大函数值进行筛选，这样不断地选取规则，应用规则，最终达到了目标（获得一个全局解）。

爬山函数的缺点在于：一些容易计算的爬山函数会遇到 多个局部最大值 或者 平顶值 ，从而导致爬山过程失败，所以，不可撤回控制策略具有很大的局限性。

其中 ，CF（ ）是爬山函数，So是起始状态，Sq是目标状态，每次都使得CF（）得到一个最大值，直到达到目标状态为止。

如果要使用不可撤回策略，则应当保持爬山函数只增不降。

——————

2）回溯控制策略（类似深度优先）

回溯策略先选定一条规则，如果发现这条规则的选用不能导致产生解，则系统“忘掉”这一规则所涉及的步骤和产生的状态，然后选用另外一条规则。

——遇到以下三种情况则进行回溯——
①当产生了上溯到初始状态的路径上已经出现过的状态时；

②当已经应用了一定数量的规则仍未得到一个解时，这个数量是事先确定的，叫做 深度限制；
这个深度限制指的是一次探索过程中延伸出的最多的“弧”的数量，也就是说假设深度限制是n，则可以探索n+1个结点。

③当已经没有了可用的规则时。

回溯的优点：
当控制系统包括较多解的知识，则回溯的次数比较少，可以很快找到解，而且回溯方式解决了爬山过程中的局部极大值等困难。

回溯的缺点：
当控制系统不包括解的知识，或掌握的解的知识比较少，那么系统的效率是很低的，需要回溯很多次才能找到合适的规则。而且如果深度限制设定的很低，那么爬山过程中很可能找不到解。
————————

3）图搜索控制策略（类似广度优先）

图搜索控制方式可以同时记录多个规则序列的执行效果：作为一种特殊情形，我们可以用树结构记录规则的应用和所产生的状态，这种树结构称为搜索树。
树根：初始状态；
有向弧：规则的使用；
除根以外的各节点：规则应用的结果。

不再选择规则，而是应用所有规则。

图搜索控制方式不断地扩展搜索树，直到它包括了满足终止条件的结点为止。

容易看出，不可撤回控制方式对应搜索树中一条路径，回溯方式只记录从初始状态到当前状态的路径，必要时修改这条路径。

————————————————————————

2.产生式系统的分类

分为正向产生式系统和反向产生式系统。

正向产生式系统： 从初始状态出发，不断应用产生式规则，直到产生目标状态为止；

反向产生式系统： 从目标状态出发，利用反向的产生式规则不断地产生子目标，直到产生出与初始状态相同的子目标为止。

双向产生式系统： 双向产生式系统的综合数据库中既有状态描述也有目标描述，产生式规则集也分为正向和反向。

————习 题————

1.什么叫正向产生式系统？什么叫反向产生式系统？什么叫双向产生式系统？它们各自适用于怎样的实际问题？

（1）正向产生式系统（数据驱动控制） ：
综合数据库：用状态描述
产生式规则：F规则–状态产生新状态
从初始状态出发，不断地应用F规则，直到产生目标状态为止。
适用条件：初始节点数≤目标节点数

（2）反（逆）向产生式系统（目标驱动控制） ：
综合数据库：用目标描述
产生式规则：B规则–目标产生子目标
从目标状态出发，利用反向的产生式规则（ B规则 ）不断地产生子目标，直到产生出与初始状态相同的子目标为止。
适用条件：初始节点数≥目标节点数

（3）双向产生式系统：正向产生式系统和反（逆）向产生式系统结合
综合数据库：既有初始状态描述，又有目标状态描述
产生式规则：既有F规则，又有B规则。正向产生式规则用在初始方向的状态描述上，反向产生式规则用在目标状态描述上。从目标状态出发，利用反向的产生式规则（ B规则 ）不断地产生子目标，直到产生出与初始状态相同的子目标为止。
控制系统：判断选F规则还是B规则；判断已经产生的状态和目标是否能以某种方式匹配，从而满足结束条件。
结束条件：中间汇合时的状态。
适用条件：初始节点数与目标节点数都很多。
特点：效率高；复杂。

2.八数码难题的产生式系统表示：

1） 综合数据库：以状态为结点的有向图；状态描述：3X3矩阵

2） 产生式规则：（更类似于移动限制）
a) IF <空格不在最左边> THEN <左移空格>；
b) IF <空格不在最右边> THEN <右移空格>；
c) IF <空格不在最上边> THEN <上移空格>；
d) IF <空格不在最下边> THEN <下移空格>；

3） 控制系统：
按照“上、下、左、右”的顺序移动空格

————————————————————————

3.其他产生式系统

1）可交换的产生式系统

2.叙述什么样的产生式系统是可交换的产生式系统？（P13）
在某些产生式系统中。规则应用的次序对产生的状态无影响，即从初始状态到目标状态不依赖规则次序，因此可应用不可撤回式控制策略，从而提高了产生式系统的效率，这类产生式系统就是可交换的产生式系统。
例：基于归结方法的产生式系统。

5.叙述可交换产生式系统的主要特征，并说明哪种搜索策略用于可交换产生式系统比较合适？（P84）

主要特征：
（1）每一条对D可应用的规则，对于对D应用一条可应用的规则后所产生的状态描述仍是可应用的 （可应用性）；
（2）如果D满足目标条件，则对D应用任何一条可应用的规则所产生的状态描述也满足目标条件 （可满足性）；
（3）对D应用一个由可应用于D的规则所构成的规则序列所产生的状态描述不因序列的次序不同而改变 (无次序性）。
不可撤回的控制方式比较合适。

2）可分解的产生式系统

3.什么是可分解的产生式系统？试述可分解的产生式系统求解问题的一般步骤？指出控制策略可以在过程中的哪些步骤中使用？（P14）

能够把产生式系统综合数据库的状态描述分解为若干组成部分，产生式规则可以分别用在各组成部分上，并且整个系统的终止条件可以用在各组成部分的终止条件表示出来的产生式系统，称为可分解的产生式系统。

Procedure SPLIT

1. DATA ← 初始状态描述
2. {Di} ← DATA的分解结果；每个Di看成是独立的状态描述
3. until 对所有的Di {Di}， Di都满足终止条件，do:
4. begin
5. 在{Di}中选择一个不满足终止条件的D*
6. 从{Di}中删除D*
7. 从规则集合中选出一个可应用于D*的规则R
8. D ← 把R应用于D*的结果
9. {di} ← D的分解结果
10. 把{di}加入{Di}中
11. End
    控制策略可以在过程的步骤5和步骤7使用。

2.产生式系统由哪几部分组成？各部分的作用是什么？（以八数码问题为例）（P7）
（1）综合数据库：由问题的状态描述构成的集合。
（3×3矩阵）
（2）产生式规则集：当规则的前提条件被某一状态描述满足时，就对该状态施行规则所指出的操作
（如果空格不在左边，则空格左移；如果空格不在上边，则空格上移；
如果空格不在右边，则空格右移；如果空格不在下边，则空格下移）
（3）控制系统：①对同一个状态描述有多个产生式规则可以使用时，决定选择哪一个来使用；②检测状态描述是否满足终止条件，如果满足终止条件，则终止产生式系统的运行，并用使用过的规则序列构造出问题的解。
（各种搜索策略）

2.产生式系统由哪几部分组成？试述产生式系统求解问题的一般步骤。
通常由以下三部分组成：（1）综合数据库（2）产生式规则集（3）控制系统。

一般步骤：
Procedure PRODUCTION
1. DATA←初始状态描述
2. until DATA 满足终止条件 do：
3. begin
4. 在规则集合中，选出一条可用于DATA的规则R
5. DATA←把R应用于DATA所得的结果
6. END

（补充）回答产生式系统控制策略的分类，并说明各自的特点。
或者：产生式系统的控制策略有哪几种方式？（或者：简述各种搜索策略各自的优缺点。）
产生式系统的控制策略分为两类：不可撤回的控制策略
试探性控制策略：回溯方式和图搜索方式

（1）不可撤回的控制策略
优点：只记录当前一个节点，空间复杂性很低；若能找到解，则速度很快。
缺点：爬山函数有多个局部极大值，具有“平顶值”，导致多数情况下找不到解，具有很大局限性。

（2）回溯控制策略
优点：只存储初始节点到当前节点的路径，占用空间较小；应用最广。
缺点：时间复杂性一般，如果系统不包括有关解的知识，则规则选取是盲目的，要多次回溯；如果深度限制制定的很低，可能找不到解。

（3）图搜索控制策略
优点：有解一定能找到（相当于穷举）。
缺点：平均时间复杂性高，占空间大，速度较慢，系统效率低。

二、请用回溯搜索策略BACKTRACK求解四皇后问题，要求规则排序使用对角函数diag(i,j)，如果diag(i,j)< diag(i,k)，则在排序中把R_ij放在R_ik的前面；如果diag(i,j)=diag(i,k)，j<k，则把R_ij放在R_ik的前面。其中diag(i,j)定义为通过单元(i,j)的最长对角线的长度。

*三、一个产生式系统使用下面一组重写规则，这些重写规则把左面的数字转换成右边的字符串。
6→3,3 4→3,1
6→4,2 3→2,1
4→2,2 2→1,1
使用这些规则把6转换成由1组成的数字串。假设k-连接符的费用是k，用数字1标记的节点的h函数是0，用数字n(n≠1)标记的节点的h函数值是n。请用〖AO〗^算法描述解题过程（要求画出各次循环图，标明各点费用q(n)，画出最后的最佳解图，并指明最佳解图的费用）

三、有两个无刻度标志的水壶，分别可装5升和2升的水。设另有一水缸，可用来向水壶灌水或倒出水，两个水壶之间，水也可以相互倾灌。已知5升壶为满壶，2升壶为空壶，问如何通过倒水和灌水操作，使能在2升的壶中量出1升的水来。将此问题用产生式系统描述。

证明题：
一、设可交换产生式系统的一条规则R可应用于综合数据库D来生成出D’，试证明若R存在逆，则可应用于D’的规则集等同于可应用于D的规则集。
设规则R的逆用R’表示。由题意有R应用于D后，得到数据库D’，由可交换系统的性质，有： rule(D) rule(D’)，其中rule(D)表示可应用于D的规则集合。由于R’是R’的逆，所以R’应用于D’后，得到数据库D。同样由可交换系统的性质，有：rule(D’) rule(D)，综合上述两个式子，有rule(D’)＝rule(D)。

二、 一个产生式系统是以整数的集合作为综合数据库，新的数据库可通过把其中任意一对元素的乘积添加到原数据库的操作来产生。设以某一个整数子集的出现作为目标条件，试说明该产生式系统是可交换的。
说明一个产生式系统是可交换的，就是要证明该产生式系统满足可交换产生式系统的三条性质。

（1）该产生式系统以整数的集合为综合数据库，其规则是将集合中的两个整数相乘后加入到数据库中。由于原来数据库是新数据库的子集，所以 原来的规则在新数据库中均可以使用。 所以满足可交换产生式系统的第一条性质。

（2）该产生式系统以某个整数的子集的出现为目标条件，由于规则执行的结果只是向数据库中添加数据，如果原数据库中已经满足目标了，即出现了所需要的整数子集，规则的执行结果不会破坏该整数子集的出现，因此新的数据库仍然会满足目标条件。满足可交换产生式系统的第二个性质。

（3）设D是该产生式系统的一个综合数据库。对D施以一个规则序列后，得到一个新的数据库D’。该规则序列中的有些规则有些是可以应用于D的，这些规则用R1表示。有些规则是不能应用于D的，这些规则用R2表示。由于R1中的规则可以直接应用与D，所以R1中规则的应用与R2中规则的执行结果无关，也与Ｒ1中其他的规则的执行无关。所以可以认为，先将R1中所有的规则对D应用，然后再按照原来的次序应用R2中的规则。因此对于本题的情况，这样得到的综合数据库与D’是相同的。而由于R1中一条规则的执行与其他的规则无关，所以R1中规则的执行顺序不会影响到最终的结果。因此满足可交换产生式系统的第三个条件。
　　因此这样一个产生式系统是一个可交换的产生式系统。

———— 本章作业 ————
1. 研究下面的传教士与食人魔渡河问题：
三个传教士和三个食人魔来到一条河的岸边，他们想渡河到对岸去。河的这边有一条小船，只能供两人乘坐，可以是两个传教士或一传教士和一食人魔，或两个食人魔；但是无论如何在河的此岸和彼岸，如果食人魔的人数超过传教士的人数，食人魔就会把传教士吃掉。问，怎样才能利用这条船把他们全部渡过河去。
设计一个产生式系统解决上述问题，说明产生式系统的状态描述，产生式规则和终止条件，对状态描述给出一个爬山函数，利用这个爬山函数，分别用不可撤回的控制策略和回溯式策略解决上述问题。

4.证明：设D是一个可交换的产生式系统的一个状态描述，R是一条可应用与D的规则，R用于D的结果是D’, 如果R是可逆的，证明可应用于D的规则集于可应用于D的规则集相等。