第2章. 产生式系统.ppt

人工智能 华中科技大学水电与数字化工程学院 第二章 产生式系统 1 产生式系统概述 2 问题的表示 3 控制策略分类 4 产生式系统的类型 1 产生式系统概述 自然界中各种知识单元间存在着大量的因果关系 产生式（规则）：前提和结论之间的关系式 表示形式：前提?结论 例：1. 如果获得学士学位?就有资格考取硕士研究生 2. 如果获得学士学位?成绩名列前茅?德育优良?就有资格推免上硕士 研究生 事实：无需前提条件，可用于表示已知的事实 表示形式：?事实 1.1 产生式系统的基本结构 三部分：综合数据库、产生式规则、控制系统。 1 综合数据库：数据结构，问题状态或有关事实（表示问题的信息） 2 一组产生式规则构成了规则库（知识） 每一条规则形如: if 条件 then 行动 或 if 前提 then 结论 3 控制系统：解释程序或执行程序，选择规则的原则和规则使用的方式 (推理方向)，并根据综合数据库的信息，控制求解问题的过程（控制策略）（推理引擎） 各组成成分的特点 综合数据库：依据推理情况内容动态变化。 规则：有相对固定的格式。无序性与模块化，易补充和修改。 控制系统：如何应用规则。与问题无关，可分匹配、冲突解决和操作三步。 数据、知识和控制相互独立。 相互影响的间接性：“数据驱动”，是通过修改数据库来间接实现。 关系: 综合数据库是基础，产生式规则是进行推理的依据， 控制系统是中枢。 重要部分: 控制系统用来控制和协调综合数据库、规则库的运行，包含了推理方式和控制策略，故是产生式系统的中枢。 1.2 产生式系统的基本过程 PRODUCTION 过程 1．DATA ? 初始数据库 (初态) 2．Until DATA 满足结束条件之前(目标态)，do： （匹配） 3．?{ 4．在规则集中，选一条可应用于DATA的规则R （选择） 5．?DATA ? R 应用到 DATA 得到的结果 （执行） 6．?} 上述过程是 “匹配、选择、执行”的循环过程 2 问题的表示 产生式运用的方法：把问题的描述转化成系统的三个部分 基础：问题的表示（综合数据库和规则集） 类型：状态空间法和问题归约法 状态空间法：找出所求问题的各种状态，通过对可能的状态空间的有哪些信誉好的足球投注网站求得一个解。（PRODUCTION过程） 问题归约法：在解较复杂的问题时，将问题分解为一些较简单的子问题，通过对各个子问题解答的有哪些信誉好的足球投注网站求得原问题的解答。 （SPLIT过程） 2.1 状态空间法 三元组（S，O，G）来描述， S 状态集合、起始状态S0 、中间状态Si 、目标状态G . O 是操作算子（规则集）. 状态空间：所有可能的状态集合；状态转换：靠规则实现. 问题求解：从S0出发，经过一系列操作变换，达到G，即状态空间有哪些信誉好的足球投注网站问题。状态空间的一个解是一个有限的规则序列： ，其中， 即为状态空间的一个解，解不一定唯一. 2.2 问题归约法 三元组（S0，O，P）来描述，S0是初始问题，即要求解的问题；P是本原问题集； O操作算子集，通过一个操作算子把一个问题化成若干个子问题 思路：由问题出发，运用操作算子产生一些子问题，对子问题再运用操作算子产生子问题的子问题，这样一直进行到产生的问题均为本原问题，则问题得解。 特点：最终目的是产生本原问题。 异同：更一般的问题求解方法。 ( 思考: 如果在归约法中，每运用一次操作算子，只产生一个子问题,那么…. ) 2.3 举例--八数码游戏 问题描述：给定一种初始布局和一个目标布局，问如何移动将牌（合理的走步序列），实现从初始状态到目标状态的转变。 综合数据库：表示将牌布局的一种数据结构。选用二维数组来表示布局较直观，其数组元素用 表示，其中