• 假如规定的搜索深度为6层（表现为：应用了第6条规则之后得到 的状态仍然不是目标状态），回溯策略应用于八数码游戏时的一 部分搜索图如图2-5所示
283 1
164 75
左
左、上、右
283 2 164
75 上
上、右
283 64
175
3
上
上、右、下
83 4 264 175
右、下
右8 3 264 175
• 一个合理的走步序列是问题的一个解。
• 1．综合数据库：选择一种数据结构表示将牌布局。
• 本例选用二维数组来表示布局较直观，其数组元素用 {Sij}表示，其中 1 i, j 3, Sij {0,1,,8}且互不相等。
• 这样每个具体取值矩阵就代表了一个棋局状态。显然，
该问题有 个状态。
2.1.2 产生式系统的基本过程
基本算法如下 ： 过程PRODUCTION
1．DATA 初始数据库 2．Until DATA 满足结束条件(匹配）之前, do:
{ 3．从规则集中选一条可应用于DATA的规则R（选择） 4．综合数据库 R 应用到 DATA 得到结果 （执行） }
上述过程是 “匹配、选择、执行”的循环过程。
• 控制策略分为两类：不可撤回方式（Irrevocable）和试探方 式（Tentative）。
1）不可撤回方式：
• 思想: 利用问题给出的局部知识决定如何选取规则， 已用过的规则不能撤回。优点是控制简单。
• 例：爬山问题。登山过程中，登山人的目标是爬上 峰顶，如何一步一步地向目标前进就是一个策略问 题。通常，人们利用高度随位置变化的函数H(P)来 引导爬山，这是一种不可撤回方式。
– O是规则集合。集合中的每个元素称作操作算子，将一个状态转化为另一个状态。
• 问题求解：从S0出发，经过一系列操作变换达到G，S0 O1 S1 O2 S2 Ok G 即状态空间搜索问题。状态空间的一个解是一个有限的规则序列，O1,, Ok 即为状态空间的一个解，解不一定唯一。
• 冲突解决，选择可调用的规则。
– 从匹配满足的规则集中选择一条规则。
• 执行规则，并在满足结束条件时终止产生式系统的运行 。
– 如果规则的后件是结论，把该结论加入综合数据库； – 如果规则的后件是动作，执行该动作；
4、产生式系统的特点： –数据、知识和控制相互独立。 –知识具有相对固定的格式：均由左、右两部分组成。 –知识无序性与模块化：知识的补充和修改非常容易。 –控制系统与问题无关。
• 问题归约法是比状态空间法更一般的问题求解方法，如果在归约法中， 每运用一次操作算子，只产生一个子问题，则就是状态空间法。
2.2.3 产生式系统举例
28 3 164
7
5
123
8
4
765
图2-1 八数码游戏
• 问题描述：给定一种初始布局（初始状态）和一个目标的布 局（目标状态），问如何移动将牌，实现从初始状态到目标 状态的转变。
• 对当前的状态，只要某一条规则作用之后能生成合法的新状态， 那么，这条规则就是可用规则。
• 产生式系统的运行表现出一种搜索过程，在每一个循环中选一 条规则试用，直到找到某一个序列能产生满足结束条件的状态 为止。
• 不同的控制策略产生不同的解，高效率的控制策略能够走较少 的步骤达到目标，但需要问题求解的足够知识。
执行使测试函数值不减少的规则； – 如果以上两种规则都不存在，则过程停止。
2）试探方式
• 试探方式分为两种：回溯方式和图搜索方式。
• 回溯方式：应用规则后遇到规定的情况时，返回到最 近的回溯点（无特殊规定时，最近的上一状态即是回 溯点），从那里改选另外一条可应用规则。
2）试探方式
• 对八数码问题而言，在3种情况下应考虑回溯： –新生成的状态在通向目标的路径上已经出现过； –从初始状态开始，在应用了指定数目的规则后，仍没有找到 目标状态； –对当前状态，再没有可应用规则。
图2-3 爬山法的三种可能状态
爬山算法缺点：有时到达某一状态后，尽管它不是目标状态，但在测试过 中又找不到比该状态更好的状态，如图2-3。 ⑴ 局部极大点（多峰时处于非主峰）：它比周围邻居状态都好，但不是目标。 ⑵ 平顶：它与全部邻居状态都有同一个值。 ⑶ 山脊：如果搜索方向与山脊的走向不一致，则有可能会停留在山脊处。
2.2.1 状态空间法
• 状态空间可用三元组（S，O，G）来描述
– S是状态集合。状态是表示某种事实的符号或数据。问题的状态可以用任何类型的 数据结构描述。起始状态S0是S的一个非空子集，描述问题的初始状态。
– G是目标状态。 G是S的一个非空子集，它可以是一个或多个要达到的状态，也可 以是对某些状态性质的描述。
5
左、右、下
（1） 左
83 264 175
（3）
右
6
83
264
175
状态6的所有规则 用完，回溯到上一 6 步，到状态 5
左、下
下
863 24 175
6
左、上、右、下
同状态4，回溯到上 一步，到状态5
（1） 左
8 37 264 175
（2） 下 （2）
左
834 7
863 7
26
24
175
175
同状态5，回溯到 上一步，到状态6
if
i0 2
then
S S , S 0; i0j0
( i0 1 ) j0 ( i0 1 ) j0
• 规则3: （空格右移一格）
if
j0 2
then
S S , S 0; i0j0
i0 ( j0 1 ) i0 ( j0 1 )
• 规则4: （空格下移一格）
if
i0 2
空格所在的行、列分别记为i0 , j0，则Si0 j0 0
则空格左移一格、空格上移一格、空格右移一 格、空格下移一格可用如下4条规则来描述：
• 规则1: （空格左移一格）
Hale Waihona Puke ifj0 2then
S S , S 0; i0j0
i0 ( j0 1 ) i0 ( j0 1 )
• 规则2: （空格上移一格）
所以，用不可撤回方式来求解登山问题，需要对状态测试函数进行选择： 这个函数应具有单极值，且这个极值对应目标状态值。
• 测试函数例：以8数码为例，统计“不在位”将牌个数（逐一比 较当前状态与目标状态对应位置,有差异的将牌总个数），并取 其负值作为状态描述的函数.
- W(n)（n为测试状态）
基于该定义，下图所示状态的函数值为-4。显然，目标状态的
2.2.2 问题归约法
• 问题归约法也可用一个三元组（S0，O，P）来描述
– S0是初始问题，即要求解的问题； – P是本原问题集，其中的每一个问题是自然成立的，不需证明的； – O是操作算子集，一个操作算子可把一个问题化成若干个子问题。
• 该方法由问题出发，运用操作算子产生一些子问题，对子问题再运用操 作算子产生子问题的子问题，一直进行到产生的问题均为本原问题，则 问题得解。问题归约的最终目的是产生本原问题。
• 假设登山人当前所处的位置为P0，如果只有四个方向可供选 择 ：[向东（△x）、向西（-△x ）、向北（△y）、向南（△y）]，分别记为规则1、2、3、4。
Z
Y
z0 y0
图2-2
P0(x0,y0,z0)
x0
X
爬山过程示意图
• 利用 H(P)可以计算朝不同方向迈出一步后高度的 变化情况。即
– 向东：△z1=H（P0+△x）-H(P0) – 向西：△z2=H（ P0 -△x）- H(P0) – 向北：△z3=H（ P0+ △y）- H(P0) – 向南：△z4=H（ P0 -△y）- H(P0)
右
123 6
8 4 W=0
283 14
765
上
83 214 765
右
83 214 765
3
W=-3
4
W=-3
5
W=-3
765
上
13 824 765
右
13 824 765
下
123 84 765
8
W=-2
9
W=-1
1 0
W=0
765
图2-4 八数码问题各状态的爬山函数值
• 爬山法的策略
– 执行使新状态的测试函数值有最大增长的规则； – 所有规则都不能使新状态的测试函数值增长时，
用了6条规则，未找
到解，回溯到上一 步，到状态 6
图2-5 利用回溯策略的部分搜索图
• 图搜索方式: 对任一状态，应用其所有可应用规则，并把状态变 化过程用图结构记录下来，一直到得到解为止。图搜索策略求解 问题是一种穷举方式。
图2-6 八数码游戏的部分搜索树
2.2 问题的表示
• 用产生式系统求解问题，就是把一个问题的描述转化成产生式系统的三个部 分。其中问题的表示（即综合数据库和规则集的描述）对问题的求解有很大 的影响。 – 状态空间法。所求问题的已知事实及中间结论，称为状态。状态的集合及 状态间的转移规则构成问题的表示。基于这种表示的问题求解称为状态空 间法。求解过程是，通过对可能的状态空间的搜索求得一个解。 （PRODUCTION过程） – 问题归约法。待求问题分解为一些较为简单的子问题，且子问题也可以分 解，所以可得到若干子问题。包含问题、子问题的集合与问题分解的规则 一起构成问题的表示。基于这种表示的问题求解称为问题归约法。求解过 程是，通过对各个子问题解答的搜索求得原问题的解答。 （SPLIT过程）
then
S S , S 0; i0j0
( i0 1 ) j0 ( i0 1 ) j0
• 3.控制策略：从规则集中选择规则并作用于状 态的一种广义选取函数。 确定某一策略后，可以用算法的形式给出 程序。使用该策略从初始状态出发，通过不断 寻求满足一定条件的问题状态，最后到达目标 状态。