八數碼游戲（1）綜合數據庫：通常用來表示綜合數據庫的數據結構有符號串、向量、集合、數組、樹、表格、文件等。該問題的綜合數據庫可以如下形式表示：(Sij)，其中1≤i、j≤3，Sij∈{0,1,…,8}，且互不相等。（2）規則集合：移動一塊牌（即走一步）就使狀態發生轉變。改變狀態有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*

（