1、第四章 可分解产生式系统的搜索策略 学习目标：了解一般的与 /或图搜索问题，掌握与 /或图的启发式搜索算法 AO*。了解博弈树搜索问题，掌握博弈树搜索中的极小极大方法和 -剪枝搜索方法。重点：AO*算法， -剪枝算法。Date1l 第二章可分解产生式系统中提到的与 /或树表示，其中加到每一个节点上 AND或 OR的标记是取决于该节点对其父节点的关系。如复合状态分解后拥有一组 “与 ”关系的后继节点；而分量状态经可应用规则作用后，生成一组“或 ”关系的后继节点。与 /或树是本章介绍的与 /或图的特例。l 在一般与 /或图中，一个节点可能是复合状态的组成部分，而同时又是一个规则应用的结果，很难说明
2、它是与后继还是或后继因此，不再区别 AND节点或 OR节点但在称谓上沿用习惯，仍把这种结构称作与 /或图。4.1 与 /或图搜索Date2例 . 一个与 /或图Date3与 /或图搜索l 定义： 与 /或图 是一种超图在超图中父亲节点和一组后继节点用超弧连接 超弧又叫 k-连接符k-连接符 : 一个父节点指向一组 k个有与关系的后继节点， 这样一组弧线称为一个 k-连接符k1时，用一圆弧标记此连接符。Note:若所有的连接符都是 1-连接符，则得到的就是与 /或图的特例 -普通有向图。Date4与 /或图搜索l 与 /或树 : 每一个节点最多只有一个父亲的与 /或图l 根节点 : 在 AND/
3、OR树或 AND / OR图中没有父节点的节点 .l 叶节点 : 在 AND/OR树或 AND / OR图中没有后继的节点l 终止节点 : 满足终止条件的节点 Date5与 /或图搜索l 一个可分解的产生式系统定义一个隐含的与 /或图图的根节点表示产生式系统的初始状态描述，连接符表示对一状态描述应用产生式规则或把这一状态描述分解成若干组成部分l 可分解产生式系统的任务 :从隐含的与 /或图出发找出一个从根节点出发到终止节点集的解图。Date6例重写规则：n0 n 1n0 n 5， n4n1 n 2n1 n 3n2 n 3n2 n 5， n4 n3 n 5， n6n4 n 5n4 n 8n5 n
4、 7, n8n5 n 6 n6 n 7, n8Date7练习 1：l 假定我 们 有一个 产 生式系 统 ，基于如下重写 规则 ：R1： n0 n1, n2 R5： n2 n6, n7R2： n0 n2, n3 R6： n3 n5, n6R3： n1 n2 R7： n4 n2R4： n1 n4 R8： n5 n7请 用与 /或 图 表示此 产 生式系 统 。Date8练习 2：一个产生式系统使用下面一组重写规则，这些重写规则把左面的数字转换成右边的数字串。63,3 43,164,2 32,142,2 21,1使用这些规则把 6转换成由 1组成的数字串。请 用与 /或 图 表示此 产 生式系 统 。 Date9与 /或图搜索l 定义 设 N是与 /或图 G的终止节点集合，图 G中无回路，从节点 n出发到 N的一个 解图 是与 /或图 G的一个子图，用 G表示，递归定义如下：1. 若 n是 N中的一个元素，则 G只包括节点 n；Date10
