搜索推理技术.ppt

中南大学 智能系统与智能软件研究所 第三章 搜索推理技术 3.1 图搜索策略 图搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。 图搜索过程图 3.2 盲目搜索 特点：不需重排OPEN表 种类：宽度优先、深度优先、等代价搜索等。 例子八数码难题（8-puzzle problem） 3.2.2 深度优先搜索 3.2.3 等代价搜索 3.3 启发式搜索 特点：重排OPEN表，选择最有希望的节点加以扩展 种类：有序搜索、A*算法等 估价函数 为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上 。 f(n)——表示节点n的估价函数值 应用节点“希望”程度（估价函数值）重排OPEN表 例子 3.3.3 A*算法 估价函数的定义：对节点n定义f*(n)=g*(n)+h*(n) ,表示从S开始约束通过节点n的一条最佳路径的代价。希望估价函数f 定义为：f(n)=g(n)+h(n)  —— g是g*的估计 ，h是h*的估计 A*算法的定义：定义1 在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。 定义2 在A算法中，如果对所有的x存在h(x)≤h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。 定义3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。 3.4 消解原理 回顾： 原子公式（atomic formulas） 文字—一个原子公式及其否定。 子句—由文字的析取组成的合适公式。 消解—对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。 例子: 将下列谓词演算公式化为一个子句集 (?x)｛P(x)?｛(?y)［P(y)?P(f(x,y))］∧ ～(?y)［Q(x,y)?P(y)］｝｝ (2) 减少否定符号的辖域 每个否定符号～最多只用到一个谓词符号上，并反复应用狄·摩根定律。 (3) 对变量标准化 对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元。 (4) 消去存在量词 以Skolem函数代替存在量词内的约束变量，然后消去存在量词 化为前束形 把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。 前束形={前缀} {母式} 全称量词串 无量词公式 把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。 (7) 消去全称量词 所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。 (8) 消去连词符号∧ 用{A,B}代替(A∧B)，消去符号∧。最后得到一个有限集，其中每个公式是文字的析取。 (9) 更换变量名称 可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。 3.4.2 消解推理规则 消解式的定义令L1，L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1∨α和～L2∨β,如果L1和L2具有最一般合一σ，那么通过消解可以从这两个父辈子句推导出一个新子句(α∨β)σ。这个新子句叫做消解式。 3.4.3 含有变量的消解式 3.4.4 消解反演求解过程 消解反演 给出{S}，L 否定L，得～L； 把～L添加到S中去； 把新产生的集合｛～L，S｝化成子句集； 应用消解原理，力图推导出一个表示矛盾的空子句 反演求解过程 从反演树求取答案步骤 把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。 按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。 用根部的子句作为一个回答语句。 实质 把一棵根部有NIL的反演树变换为根部带有回 答语句的一棵证明树。 3.5 规则演绎系统 定义 基于规则的问题求解系统运用If→Then规则来建立，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存，then部分用于规定