人工智能产生式系统.ppt
《人工智能产生式系统.ppt》由会员分享,可在线阅读,更多相关《人工智能产生式系统.ppt(30页珍藏版)》请在优知文库上搜索。
1、第二章第二章 产生式系统产生式系统 2.1 产生式系统概述 2.2 问题的表示 2.3 控制策略分类 2.4 产生式系统的类型 2.1 产生式系统概述 在自然界的各种知识单元之间存在着大量的因果关系。这是前提和结论之间的关系,可用产生式(或称规则)来表示。产生式也称作规则,或产生式规则。 产生式(规则):前提和结论之间的关系式。 表示形式:前提结论 例:1. 如果获得学士学位就有资格考取硕士研究生 2. 如果获得学士学位成绩名列前茅德育优良就有 资格推免上硕士 研究生 事实:无需前提条件的产生式,可用于表示已知的事实。 表示形式:事实2.1.1 产生式系统的基本结构 三个基本部分:综合数据库、
2、产生式规则、控制系统。1、综合数据库是产生式使用的主要数据结构,它用来表述问题状态或有关事实,对应于表示问题的说明式知识。2、一组产生式规则构成了规则库,每一条规则形如: if 条件 then 行动 或 if 前提 then 结论 例如 1: if 某动物有羽毛 then 该动物是鸟类 2: if 某动物是鸟 and 有长脖子 and 有长腿 and 不会 飞 then 该动物是鸵鸟 (前提结论) 3: if 老虎在铁笼中 and 鸡在同一铁笼中 and 老虎饿 了 then 老虎吃掉这只鸡 (条件行动) 3、控制系统是规则的解释程序,它规定了选择一条可用规则的原则和规则使用的方式 (推理方向
3、),并根据综合数据库的信息,控制求解问题的过程。 4、产生式系统的特点: 相对固定的格式:均由左、右两部分组成 知识的模块化:知识元 、元知识 、高阶元知识;知识的模块化使得知识库(规则)的补充和修改变得非常容易 。 相互影响的间接性:“数据驱动”,是通过修改数据库来间接实现 。 机器可读性 :机器识别产生式、语法检查和某种程度上的语义检查 2.1.2 产生式系统的基本过程 基本算法如下 : 过程PRODUCTION 1DATA 初始数据库 2Until DATA 满足结束条件之前,do:(匹配) 3 Begin 4在规则集中,选一条可应用于DATA的规则R(选 择) 5 DATA R 应用到
4、 DATA 得到的结果 (执行) 6 End上述过程是 “匹配、选择、执行”的循环过程。 2.2 问题的表示 用产生式系统求解问题,就是把一个问题的描述转化成产生式系统的三个部分。其中问题的表示(即综合数据库和规则集的描述)对问题的求解有很大的影响。 常用方法有两个:状态空间法和问题归约法。 状态空间法:找出所求问题的各种状态,通过对可能的状态空间的搜索求得一个解。(PRODUCTION过程) 问题归约法:在解决一个较为复杂的问题时,我们可把问题分解为一些较为简单的子问题,通过对各个子问题解答的搜索求得原问题的解答。 (SPLIT过程) 2.2.1 状态空间法 状态空间可用三元组(S,O,G)
5、来描述, S状态集合。状态是某种事实的符号或数据,任何类型的数据结构都可以描述问题的状态。起始状态S0表示S的一个非空子集,它是问题的现状或已知条件;目标状态G也是S的一个非空子集,它可以是一个或多个要达到的目标,也可是对某些状态性质的描述。O是操作算子(规则)集,利用它将一个状态转化为另一个状态. 中间状态:求解过程中的状态;状态空间:所有可能的状态集合;状态转换:靠规则实现 问题求解:从S0出发,经过一系列操作变换,达到G,即状态空间搜索问题。状态空间的一个解是一个有限的规则序列: ,其中, 即为状态空间的一个解,解不一定唯一。GSSSkOOO21021kOO,12.2.2 问题归约法 问
6、题归约法也可用一个三元组(S0,O,P)来描述,其中: S0是初始问题,即要求解的问题;P是本原问题集,其中的每一个问题是不证明的,自然成立的; O操作算子集,通过一个操作算子把一个问题化成若干个子问题。 该方法是由问题出发,运用操作算子产生一些子问题,对子问题再运用操作算子产生子问题的子问题,这样一直进行到产生的问题均为本原问题,则问题得解。 所有问题归约的最终目的是产生本原问题。问题归约法是比状态空间法更一般的问题求解方法,如果在归约法中,每运用一次操作算子,只产生一个子问题,则就是状态空间法。 2.2.3 举例 图2-1、八数码游戏 问题描述:给定一种初始布局(初始状态)和一个目标的布局
7、(目标状态),问如何移动将牌,实现从初始状态到目标状态的转变。问题的解就是给出一个合理的走步序列。 1综合数据库:就是要选择一种数据结构来表示将牌布局。本例中,选用二维数组来表示布局较直观,其数组元素用 表示,其中, 且互不相等,这样数组的每个具体取值矩阵就代表了一个棋局状态。显然,该问题有 个状态。 2834 571612345678ijS8 , 1 , 0, 3,1ijSji362880! 9111213141516171819CCCCCCCCC 2. 规则集:移动一块将牌(即走一步)就使状态发生一次转变。有四种走法:空格左移、空格上移、空格下移、空格右移。当然,每种走法都有条件,且可用如
8、下4条规则来模拟:(设 为数组第i行第j列的数码元素, 为空格所在的行、列数值,即 ),则 规则1: (向左移一格) 规则2: (向上移一格) 规则3: (向右移一格) 规则4: (向下移一格) ijS00, ji000jiS; 0,2)1()1(0000000jijijiSSSthenjif; 0,2000000)1()1(0jijijiSSStheniif; 0,2)1()1(0000000jijijiSSSthenjif; 0,2000000)1()1(0jijijiSSStheniif 3.控制策略:是从规则集中选择规则并作用于状态的一种广义选取函数。确定某一策略后,就可以用算法的形式
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 产生 系统
