第6章基于产生式规则的机器推理资料.ppt

* 最早提出产生式系统并把它作为计算手段的是美国数学家Post，大约在1943年。他设计的Post系统，目的是为了构造一种形式化的计算工具，并证明它和图灵机有相同的计算能力。几乎在同一时期，Chomsky在研究自然语言结构时，提出了文法分层的概念，并提出了文法的重写规则，即语言生成规则，语言生成规则实际是特殊的产生式。1960年，Backus提出了著名的BNF，用以描述计算机语言的文法。后来发现，BNF范式实际上就是Chomsky的上下文无关文法。至此，产生式系统的应用范围大大扩展。产生式知识表示方法具有和图灵机一样的表达能力。产生式表示方法容易描述事物、规则以及他们的不确定性度量。 * 利用产生式规则可以实现有前提条件的指令性操作，也可以实现逻辑推理。实现操作的方式是当测试到一条规则的前提条件满足时，就执行其候补的动作，这称为规则被触发或点燃。 这种机遇产生式规则的逻辑推理模式，就是逻辑上所说的假言推理（对常量规则而言）和三段论推理（对变量规则而言） * * 阿三打死得其所 * * 例2：M-C问题（续2） 1，综合数据库 （m, c, b)， 其中：0≤m, c≤3, b ∈{0, 1} 2，初始状态 （3，3，1） ( 简化，只描述左岸的情况即可 ) 3，目标状态（结束状态） （0，0，0） * 例2：M-C问题（续3 ） 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, 0) THEN (m, c+1, 1) 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) 例2：M-C问题（续4） 例2：N=5，k=3为例 * 人工智能 * 例3：猴子摘香蕉问题 一个房间里，天花板上挂有一串香蕉，有一只猴子可在房间里任意活动（到处走动，推移箱子，攀登箱子等）。设房间里还有一只可被猴子移动的箱子，且猴子登上箱子时才能摘到香蕉，问猴子在某一状态下（设猴子位置为c，箱子位置为b，香蕉位置为a），如何行动可摘取到香蕉。 * 人工智能 * a b c 例3：猴子摘香蕉问题 * 人工智能 * 1，综合数据库 定义5元组（M, B, Box, On, H） M：猴子的位置 B：香蕉的位置 Box：箱子的位置 On=0：猴子在地板上 On=1：猴子在箱子上 H=0：猴子没有抓到香蕉 H=1：猴子抓到了香蕉 例4：量水问题 对量水问题给出产生式系统描述，并画出状态空间图。 有两个无刻度标志的水壶，分别可装5升和2升的水。设另有一水缸，可用来向水壶灌水或倒出水，两个水壶之间，水也可以相互倾灌。已知5升壶为满壶，2升壶为空壶，问如何通过倒水或灌水操作，使能在2升的壶中量出一升的水来。 * 人工智能 * 例4：量水问题 * 人工智能 * * 人工智能 * 6.2.3控制策略与常用算法（1） 推理方式 正向推理 ——从初始事实数据出发，正向使用规则进行推理，朝目标方向前进。又称为前向推理、正向链、数据驱动的推理。 反向推理——从目标出发，反向使用规则进行推理，朝初始事实或数据方向前进。又称反向推理、反向链、目标驱动的推理。 * 人工智能 * 6.2.3控制策略与常用算法（2） 正向推理算法一 步1 将初始事实/数据置入动态数据库； 步2 用动态数据库中的事实匹配目标条件，若目标条件满足，推理成功，结束。 步3 用规则库中各规则的前提匹配动态数据库中的事实，将匹配成功的规则组成待用规则集。 步4 若待用规则集为空，则运行失败，退出。 步5 将待用规则集中各规则的结论加入动态数据库，或者执行其动作，转步2。 * 人工智能 * 6.2.3控制策略与常用算法（3） 若把动态数据库的每一个状态作为一个节点的话，则上述推理过程就是一个从初始状态到目标状态的状态图有哪些信誉好的足球投注网站过程。 如果把动态数据库中的每一个事实/数据作为一个节点的话，则上述推理过程就是一个自底向上的与或树有哪些信誉好的足球投注网站过程。 * 人工智能 * 6.2.3控制策略与常用算法（4） 反向推理算法 步1 将初始事实/数据置入动态数据库，将目标条件置入目标链； 步2 若目标链为空，则推理成功，结束。 步3 取出目标链中第一个目标，用动态数据库中的事实同其匹配，若匹配成功，转步2。