《产生式系统与状态空间图课件》由会员分享，可在线阅读，更多相关《产生式系统与状态空间图课件（43页珍藏版）》请在金锄头文库上搜索。
1、产生式系统与状态空间图,产生式系统（Production System）是1943年Post提出的一种计算形式体系里所使用的术语，主要是使用类似于文法的规则，对符号串作替换运算。从60年代开始，成为认知心理学研究人类心理活动中信息加工过程的基础，并用它来建立人类认知模型。产生式系统形式上很简单，但在一定意义上模仿了人类思考的过程，因此它成为了专家系统的最基本的结构单元或基本模式。,1 产生式系统的基本组成组成三要素：,一个综合数据库(Globle Database） 存放信息 一组产生式规则 (Rules) 知识 一个控制系统 (Control System/Control Strategie
2、s) 规则的解释或执行程序，即控制策略,综合数据库： 是人工智能产生式系统所使用的主要数据结构，它用来表述问题状态或有关事实，即它含有所求解问题的信息。 产生式规则： 其一般形式为“条件 - 行动” 或“前提-结论”即表示成“if.then.”的形式； “前提”规定了规则可应用的先决条件，“结论”描述了应用这条规则所采取的行动或得出的结论。 一条产生式规则满足了应用的先决条件之后，就可对综合数据库进行操作，使其发生变化，更新数据库。 控制系统或控制策略： 是规则的解释程序，规定了如何选择一条可应用的规则对综合数据库进行操作，即决定问题求解过程的推理路径。当数据库满足结束条件时，系统就应停止运行
3、，并给出解的路径。,产生式系统的优点,在研究人类进行问题求解过程时，完全可以用一个产生式系统来模拟求解过程，即作为描述搜索的一种有效方法。 可以用来模拟任一可计算过程，特别适合于模拟强数据驱动特点的智能行为：当一些新的数据输入时，系统的行为就改变 易于添加新规则去适应新的情况，而不破坏系统的其它部分,八数码问题,八数码游戏（Eight-Puzzle) 在3*3组成的九宫棋盘上，摆有8个牌，每个牌都刻有1-8中的某个数码。棋盘中留有一个空格，允许其周围的某个牌向空格移动。给定一种初始布局和一个目标布局，为如何移动牌，实现从初始状态到目标状态的转变，给出走步序列。 如：,2 8 3,1 6 4,7
4、 5,8 4,1 2 3,7 6 5,产生式系统应用示例一：,八数码问题的思考,一、综合数据库的选择，由于棋盘是3*3的方格，所以数据库可以考虑使用3*3的矩阵。 二、对于规则的考虑，使用规则的目的是为了移动牌，最终的结果是让牌到达指定的位置，有两种实现方法：一种是制定对于8张牌的移动方式；一种是制定对于空格牌的移动。 三、控制策略的考虑，使用规则的目的是为了向目标推进。,八数码问题 （续）,一、综合数据库 用二维数组(ij)来表示将牌的布局，其中1 i、j 3，ij0,1.8，且互不相等。,二、规则集：用以下条规则来模拟将牌空格向左、上、右、下移动的走法 1， IF jo-1=1 then
5、Siojo:=Sio(jo-1),Si0(jo-1):=0 （ Siojo向左） 2， IF io-1=1 then Siojo:=S(io-1)jo,S(io-1)jo:=0 （ Siojo向上） 3, IF jo+1=3 then Siojo:=Sio(jo+1),Si0(jo+1):=0 （ Siojo向右） 4, IF io+1=3 then Siojo:=S(io+1)jo,S(io+1)jo:=0 （ Siojo向下）,八数码问题 （续2）,三、搜索策略 是从规则中选取规则并作用于状态的一种广义选 取函数，这个函数的选取要对当前已经到达的状 态和目标状态有充分的考虑。,四、问题的解
6、 即实现目标的一个走步序列（即规则序列），如（上、上、左、下、右）,传教士与野人问题,传教士与野人问题（M-C问题） 问题：N个传教士，N个野人，一条船，可同时乘坐k个人乘渡。 问：传教士为安全起见，应如何规定摆渡方案，使得任何时刻，河两岸以及船上的野人数目总是不超过传教士的数目。 以N=3，k=2为例求解。,产生式系统应用示例二:,M-C问题（续）,图中L和R表示左岸和右岸，B=1或0表示有船或无船，约束条件是：两岸上或者M=C,或者一个岸上只有野人；M和C都可以驾船；船上M+C=2： 左岸 右岸 L R L R m 3 0 m 0 3 c 3 0 c 0 3 B 1 0 B 0 1,（初始
7、状态）,（目标状态）,M-C问题（续）,1，综合数据库 （m, c, b)， 其中：0m, c3, b 0, 1 2，初始状态 （3，3，1） 3，目标状态（结束状态） （0，0，0）,M-C问题（续）,4，规则集 IF (m, c, 1) THEN (m-1, c, 0) IF (m, c, 1) THEN (m, c-1, 0) IF (m, c, 1) THEN (m-1, c-1, 0) IF (m, c, 1) THEN (m-2, c, 0) IF (m, c, 1) THEN (m, c-2, 0) IF (m, c, 0) THEN (m+1, c, 1) IF (m, c,
8、0) THEN (m, c+1, 1),M-C问题（续）,IF (m, c, 0) THEN (m+1, c+1, 1) IF (m, c, 0) THEN (m+2, c, 1) IF (m, c, 0) THEN (m, c+2, 1) 也可以定义为： IF (m, c, 1) AND 1 i+j2 THEN (m-i, c-j, 0) IF (m, c, 0) AND 1 i+j2 THEN (m+i, c+j, 0),5，控制策略：（略）,(001)达不到，(000)，(0 11)，(010)，(02 1)，(0 2 0)，(0 3 1)，(0 3 0)达不到，(1 0 1)不合法，(
9、1 0 0)不合法，(1 1 1)， (1 1 1)，(1 2 1)不合法，(1 2 0)不合法，(1 3 1)不合法，(1 3 0)不合法，(2 0 1)不合法，(2 0 0)不合法，(2 1 1)不合法，(2 1 0)不合法，(2 2 1)，(2 2 0)，(2 3 1)不合法，(2 3 0)不合法，(3 0 1)达不到，(3 0 0)，(3 1 1)，(3 1 0)，(3 2 1)，(3 2 0)，(3 3 1)，(3 3 0)达不到,N3的M-C问题，状态空间的总状态数为4X4X232，根据约束条件的要求，可以看出只有20个合法状态。再进一步分析后，又发现有4个合法状态实际上是不可能达
10、到的。因此实际的问题空间仅由16个状态构成。下表列出分析的结果：,M-C问题（续 5）,M-C问题状态空间图,状态空间图是一个有向图，其节点可表示问题的各种状态(综合数据库)，节点之间的弧线代表一些操作(产生式规则)，它们可把一种状态导向另一种状态。这样建立起来的状态空间图，描述了问题所有可能出现的状态及状态和操作之间的关系，因而可以较直观地看出问题的解路径及其性质。,状态空间图,字符转换,问题：设字符转换规则 ABC ACD BCG BEF DE 已知：A，B 求：F,产生式系统应用示例三:,字符转换 （续）,一、综合数据库 x，其中x为字符 二、规则集,1，IF AB THEN C 2，I
11、F AC THEN D 3，IF BC THEN G 4，IF BE THEN F 5，IF D THEN E,字符转换 （续）,三、控制策略 将能使用的规则按序号顺序排队，按顺序使用。 四、初始条件 A，B 五、结束条件 Fx,求解过程,数据库可使用规则被使用规则,A，B,（1）,（1）,A，B，C,（2）（3）,（2）,A，B，C，D,（3）（5）,（3）,A，B，C，D，G,（5）,（5）,A，B，C，D，G，E,（4）,（4）,A，B，C，D，G，E，F,1，IF AB THEN C 2，IF AC THEN D 3，IF BC THEN G 4，IF BE THEN F 5，IF D
12、 THEN E,猴子摘香蕉问题,a,b,c,产生式系统应用示例四:,猴子摘香蕉问题（续1）,1，综合数据库 （M, B, Box, On, H） M：猴子的位置 B：香蕉的位置 Box：箱子的位置 On=0：猴子在地板上 On=1：猴子在箱子上 H=0：猴子没有抓到香蕉 H=1：猴子抓到了香蕉,猴子摘香蕉问题（续2）,2，初始状态 （c, a, b, 0, 0） 3，结束状态 （x1, x2, x3, x4, 1） 其中x1x4为变量。,猴子摘香蕉问题（续3）,4，规则集 r1: IF (x, y, z, 0, 0) THEN (w, y, z, 0, 0) r2: IF (x, y, x,
13、0, 0) THEN (z, y, z, 0, 0) r3: IF (x, y, x, 0, 0) THEN (x, y, x, 1, 0) r4: IF (x, y, x, 1, 0) THEN (x, y, x, 0, 0) r5: IF (x, x, x, 1, 0) THEN (x, x, x, 1, 1) 其中x, y, z, w为变量,2.2 产生式系统的基本过程,过程PRODUCTION 1，DATA初始数据库 2，until DATA满足结束条件，do 3， 4，在规则集中选择一条可应用于DATA 的规则R 5，DATA R应用到DATA得到的结果 6，,2.3 产生式系统的控
14、制策略,不可撤回方式（Irrevocable) 试探性方式(Tentative) - 回溯方式（Backtracking) - 图搜索方式(Graph-Search),不可撤回方式(瞎子爬山法),这种方式是利用问题给出的局部知识来决定如何选取规则的，就是说根据当前可靠的局部知识选一条可应用规则并作用于当前综合数据库，接着再根据新状态继续选取规则，搜索过程一直进行下去，不必考虑撤回用过的规则。这是由于在搜索过程中如能有效利用局部知识，即使使用了一条不理想的规则，也不妨碍下一步选得另一条更合适的规则。这样不撤消用过的规则，并不影响求到解，只是解序列中可能多了一些不必要的规则。,瞎子爬山法（局部搜索
15、法）,爬山问题,问题介绍 解决爬山问题就是确定如何一步一步前进达到顶峰。也就是一个在“爬山”过程中寻求函数的极大值问题。 利用高度随位置变化的爬山函数h(p)（当前点到目的点的距离）来引导爬山(h(p)-h(p0)大优先)，就可以实现不可撤回的控制方式。 限制：用不可撤回的方式(爬山法)来求解登山问题，只有在登单峰的时才总是有效的(即对单极值的问题可找到解)。对于比较复杂的情况，如碰到多峰、山脊或平顶的情况时，爬山搜索法并不总是有效的。 解题思路 建立一个描述综合数据库变化的函数，如果这个函数具有单极值，且这个极值对应的状态就是目标，则不可撤回的控制策略就是选择使函数值发生最大增长变化的那条规
16、则作用于综合数据库，直到函数值最大，达到目标。,不可撤回方式示例：八数码问题,用“不在位”将牌个数和作为状态描述的函数：W（n)（“不在位”将牌个数是指当前状态与目标状态对应位置逐一比较后有差异的将牌总个数，n表示任一状态）,2 8 3 1 6 4 7 5,（4）,2 8 3 1 4 7 6 5,（3）,2 3 1 8 4 7 6 5,（3）,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,（2）,1 2 3 8 4 7 6 5,1 2 3 8 4 7 6 5,（3）,8 3 2 1 4 7 6 5,（3）,8 3 2 1 4 7 6 5,（3）,，,1 2 3 8 4 7 6 5,（1）,（0）,（0）,目标,目标,八数码游戏各状态的爬山函数值,优缺点,使用不可撤回的策略，虽然不可能对任何状态总能选得
