第四章 可分解产生式系统的搜索策略 学习目标：了解一般的与 或图搜索问题，掌握与 或图的启发式搜索算法 AO*。了解博弈树搜索问题，掌握博弈树搜索中的极小极大方法和 -剪枝搜索方法。重点：AO*算法， -剪枝算法。Date1l 第二章可分解产生式系统中提到的与 或树表示，其中加到每一个节点上 AND
产生式系统的搜索策略.PPTTag内容描述：
1、关系的后继节点；而分量状态经可应用规则作用后，生成一组“或 ”关系的后继节点。
与 /或树是本章介绍的与 /或图的特例。
l 在一般与 /或图中，一个节点可能是复合状态的组成部分，而同时又是一个规则应用的结果，很难说明它是与后继还是或后继因此，不再区别 AND节点或 OR节点但在称谓上沿用习惯，仍把这种结构称作与 /或图。
4.1 与 /或图搜索Date2例 . 一个与 /或图Date3与 /或图搜索l 定义： 与 /或图 是一种超图在超图中父亲节点和一组后继节点用超弧连接 超弧又叫 k-连接符k-连接符 : 一个父节点指向一组 k个有与关系的后继节点， 这样一组弧线称为一个 k-连接符k1时，用一圆弧标记此连接符。
Note:若所有的连接符都是 1-连接符，则得到的就是与 /或图的特例 -普通有向图。
Date4与 /或图搜索l 与 /或树 : 每一个节点最多只有一个父亲的与 /或图l 根节点 : 在 AND/OR树或 AND / OR图中没有父节点的节点 .l 叶节点 : 在 AND/OR树或 AND / OR图中没有后继的节点l 终止节点 : 满。
2、量 常量：NIL: 空表 -LISP语言中的常量，也可用（） 谓词：TERM(DATA): DATA满足结束条件时，为真DEADEND(DATA):DATA不在解路上，为真（往下到达目标的可能性来定义这个谓词：若从 DATA当前状态往下走到达目标的可能性很小时，则放弃这个状态 ）NULL(X): 表 X为空表时，为真 函数：APPRULES(DATA): 将 DATA所有可用规则进行排序所得到的表FIRST(X): 取表的头TAIL(X): 取表的尾CONS(E, X):将加入表前Date4BACKTRACK过程Recursive Procedure BACKTRACK（ DATA）1 if TERM（ DATA）， return NIL；2 if DEADEND（ DATA）， return FAIL；3 RULESAPPRULES （ DATA）；4 LOOP： if NULL（ RULES）， return FAIL；5 RFIRST （ RULES）； 6 RULESTAIL （ R。
