第二章 产生式系统

八数码游戏（1）综合数据库：通常用来表示综合数据库的数据结构有符号串、向量、集合、数组、树、表格、文件等。该问题的综合数据库可以如下形式表示：(Sij)，其中1≤i、j≤3，Sij∈{0,1,…,8}，且互不相等。（2）规则集合：移动一块牌（即走一步）就使状态发生转变。改变状态有4种走法：空格左移、空格上移、空格右移、空格下移。可用4条产生式规则来模拟

产生式系统的控制策略

控制策略可划分为两大类：

（1）不可撤回方式：爬山法

八数码游戏例:用"不在位"将牌个数并取其负值作为状态描述的函数－W（n）（"不在位"将牌个数是指当前状态与目标状态对应位置逐一比较后有差异的将牌总个数，用W（n）表示，其中n表示任一状态（2）回溯方式：在问题求解过程中，有时会发现应用一条不合适的规则会阻挠或拖延达到目标的过程。在这种情况下，需要有这样的控制策略：先试一试某一条规则，如果以后发现这条规则不合适，则允许退回去，另选一条规则来试。

（3）图搜索方式：如果把问题求解过程用图或树的这种结构来描述，即图中的每一个节点代表问题的状态，节点间的弧代表应用的规则，那么问题的求解空间就可由隐含图来描述。图搜索方式就是用某种策略选择应用规则，并把状态变化过程用图结构记录下来，直到得出解为止。

可交换的产生式系统可交换性是指几条规则可以任意交换次序而不影响求解。但要注意并不是所使用的整个规则序列可以重新排列，只有那些最初可应用于初始数据库的规则才可交换，而对于生成的数据库所添加的其他可应用规则，则不能随意交换。

一般来说，当一个产生式系统对任何一个数据库D都具有如下性质时，这个产生式系统是可交换的：

（1）可应用于D的规则集合，对用了其中任意一条规则之后所生成的任何数据库，这个规则集合还适用；

（2）满足目标条件的某个数据库D，当应用任何一个可应用于数据库D的规则之后所生成的任何数据库，仍然满足目标条件；

（3）若对D应用某一规则序列之后得到一个数据库D′（设有一对应于D→D′的一条解路），则当改变D的可应用规则集合中的规则次序后，仍然可求得解，即求得D′与使用满足D的可应用规则集合中的规则次序无关。

简例：给定一个整数集合{a，b，c}，可通过把集合中任意一对元素的乘积作为新元素添加到集合中的办法来扩大该整数集，要求通过若干次操作后能生成出所需的整数集合来。其综合数据库就可用集合表示，则问题的初始状态为{a，b，c}，设目标条件为具有a，b，c，ab，bc，ca这六个元素组成的集合，初始状态可应用的规则集合为：整数集合生成问题的部分状态空间图如果一个产生式系统可以分解为几个子问题，当子问题得以求解时，则原始问题被求解。这样的产生式系统称为可分解的产生式系统。如果原始问题可以被划分为几个独立的子问题来求解，则可以提高问题求解的效率。但在很多情况下，子问题之间并不是完全独立的，它们之间会有某些方面的联系，这样的可分解产生式系统可以表示为一个与或树（图）。研究一个重写问题的产生式系统，其初始数据库为（C，B，Z），产生式规则的依据是如下的重写规则：

R1：C→（D，L）

R2：C→（B，M）

R3：B→（M，M）

R4：Z→（B，B，M）

结束条件是生成出只包含M组成的数据库，即（M，…，M）。用图搜索方式求解这个问题时，搜索得到的部分状态空间图。图中只给出两条达到目标的路径和一条失败的路径。实际搜索时有可能去探索更多的路径，往往导致效率降低。一个可分解的产生式系统，其基本过程描述如下：

过程SPLIT

（1）DATA:＝初始数据库

（2）{Di}:＝DATA的分解式；每个Di元素都看成单独的数据库

（3）Until{Di}的所有元素都满足结束条件之前，do：

（4）begin

（5）从{Di}中选一个不满足结束条件的D*

（6）从{Di}中删去D*

（