人工智能与机器翻译 一产生式系统及其搜索方法 主讲:杨宪泽
第3 章 产生式系统及其搜索方法 人工智能与机器翻译 主讲：杨宪泽 ——产生式系统及其搜索方法
第3章产生式系统及其搜索方法 3.1产生式系统 3.2产生式系统的搜索(控制)策略 3.3图搜索算法 3.4产生式系统的规则问题 3.5应用举例 3.6产生式系统的不确定性问题 3.7系统设计技巧 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 第3 章 产生式系统及其搜索方法 3.1 产生式系统 3.2 产生式系统的搜索(控制)策略 3.3 图搜索算法 3.4 产生式系统的规则问题 3.5 应用举例 3.6 产生式系统的不确定性问题 3.7 系统设计技巧
3.1产生式系统 产生式系统使用类似于文法的规则,对符号 串作替换运算。它是智能软件中使用最普遍、最典 型的一种结构。为什么要采用产生式系统作为智能 软件的主要结构呢?这可以有两点理由: (1)用产生式系统结构求解问题的过程和人类求 解问题时的思维过程很相象,因而可以用它来模拟 人类求解问题时的思维过程; (2)可以把产生式系统作为智能软件中的基本结 构单元或基本模式看待,就好象是积木世界中的积 木块一样,因而研究产生式系统的基本问题就具有 一般意义。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 1 产生式系统 产生式系统使用类似于文法的规则, 对符号 串作替换运算。 它是智能软件中使用最普遍、最典 型的一种结构。为什么要采用产生式系统作为智能 软件的主要结构呢? 这可以有两点理由: (1) 用产生式系统结构求解问题的过程和人类求 解问题时的思维过程很相象, 因而可以用它来模拟 人类求解问题时的思维过程; (2) 可以把产生式系统作为智能软件中的基本结 构单元或基本模式看待, 就好象是 积木世界中的积 木块一样, 因而研究产生式系统的基本问题就具有 一般意义
3.1产生式系统 3.1.1产生式系统的组成部分 一个智能软件用产生式系统设计的基本组 成是:一个综合数据库;一组产生式规则; 个控制系统。 综合数据库是产生式系统所使用的主要数 据结构,用来表述问题的状态或有关事实。 它包含求解问题的信息,其中有些部分可以 是不变的,有些部分可能只与当前问题的解 有关。人们可以根据问题的性质,用适当的方 法来构造综合数据库的信息 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 1 产生式系统 3 . 1 . 1 产生式系统的组成部分 一个智能软件用产生式系统设计的基本组 成是: 一个综合数据库; 一组产生式规则; 一个控制系统。 综合数据库是产生式系统所使用的主要数 据结构, 用来表述问题的状态或有关事实。 它包含求解问题的信息 , 其中有些部分可以 是不变的, 有些部分可能只与当前问题的解 有关。人们可以根据问题的性质, 用适当的方 法来构造综合数据库的信息
3.1产生式系统 13.1.1产生式系统的组成部分 产生式规则的一般形式为: 条件一→行动或前提一→结论 即表示成为:if--then 的形式。 其中,左边确定了该规则可应用的先决条件;右边 描述了应用这条规则所采取的行动或得出的结论。 条产生式规则满足了应用的先决条件之后,就可 对综合数据库进行操作,使其发生变化。如综合数 据库代表当前状态,则应用规则后就使状态发生转 换,生成新状态。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 1 产生式系统 3 . 1 . 1 产生式系统的组成部分 产生式规则的一般形式为: 条件─→行动 或 前提─→结论 即表示成为: if┄┄then┄┄ 的形式。 其中, 左边确定了该规则可应用的先决条件; 右边 描述了应用这条规则所采取的行动或得出的结论。 一条产生式规则满足了应用的先决条件之后, 就可 对综合数据库进行操作, 使其发生变化。如综合数 据库代表当前状态, 则应用规则后就使状态发生转 换, 生成新状态
3.1产生式系统 3.1.1产生式系统的组成部分 控制系统是软件的控制程序,也是规则的解释(推理程 序。它规定了如何选择一条可应用的规则对数据库进行操 作,即确定了求解过程的推理路线。当数据库满足结束条件 时,系统就应停止运行;还要使系统在求解过程中记住应用 过的规则序列,以便最终能给出解的路径。 控制系统也称控制策略,它也可以是从规则集中选择规 则并作用于状态的一种广义选取函数。确定某一种策略后, 可以算法的形式给出。在建立产生式系统描述时,还要给出 初始状态和目标条件,具体说明所求解的问题。产生式系 统中控制策略的作用就是从初始状态出发,寻求一个满足 定条件的问题状态。目标条件也是产生式系统结束条件的 基础。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 1 产生式系统 3 . 1 . 1 产生式系统的组成部分 控制系统是软件的控制程序, 也是规则的解释(推理)程 序。 它规定了如何选择一条可应用的规则对数据库进行操 作, 即确定了求解过程的推理路线。当数据库满足结束条件 时, 系统就应停止运行; 还要使系统在求解过程中记住应用 过的规则序列, 以便最终能给出解的路径。 控制系统也称控制策略, 它也可以是从规则集中选择规 则并作用于状态的一种广义选取函数。确定某一种策略后, 可以算法的形式给出。在建立产生式系统描述时, 还要给出 初始状态和目标条件, 具体说明所求解的问题。产生式系 统中控制策略的作用就是从初始状态出发, 寻求一个满足一 定条件的问题状态。目标条件也是产生式系统结束条件的 基础
3.1产生式系统 3.1.1产生式系统的组成部分 上述产生式系统的定义具有一般性,它可用来模拟任 可计算过程。在研究人类进行问题求解过程时,完全可用 个产生式系统来模拟求解过程,及可作为描述搜索的一种有 效方法。作为智能中的一种形式体系,它还具有以下优点: (1)适合于模拟强数据驱动特点的智能行为 当一些新的数据数入时,系统的行为就要改变; (2)易于添加新规则去适应新的情况,而不破 坏系统的其他部分。这是由于产生式系统的各组成 部分具有相对的独立性,因而便于扩展和修改。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 1 产生式系统 3 . 1 . 1 产生式系统的组成部分 上述产生式系统的定义具有一般性, 它可用来模拟任 一可计算过程。在研究人类进行问题求解过程时, 完全可用 一个产生式系统来模拟求解过程, 及可作为描述搜索的一种有 效方法。作为智能中的一种形式体系, 它还具有以下优点: (1) 适合于模拟强数据驱动特点的智能行为。 当一些新的数据数入时, 系统的行为就要改变; (2) 易于添加新规则去适应新的情况, 而不破 坏系统的其他部分。 这是由于产生式系统的各组成 部分具有相对的独立性, 因而便于扩展和修改
3.1产生式系统 3.1.1产生式系统的组成部分 用产生式系统来求解问题,首先必须建立起问题的产生式 系统描述,即规定出数据库、规则集合及其控制策略。这 种把一个问题的叙述转化为产生式系统的三个组成部分, 在智能技术中通常称为问题的表示。一般来说一个问题可有 多种表示方式,而选择一种较好的表示是运用智能技术解决 实际问题首先要考虑的,而且要有一定的技巧。 建立了产生式系统描述之后,通过控制策略,可求得实现 目标的一个规则序列,这就是所谓问题的解,这个解序列是 根据控制系统记住搜索目标过程中用过的所有规则而构造出 来的。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 1 产生式系统 3 . 1 . 1 产生式系统的组成部分 用产生式系统来求解问题, 首先必须建立起问题的产生式 系统描述, 即规定出数据库、规则集合及其控制策略。这 种把一个问题的叙述转化为产生式系统的三个组成部分, 在智能技术中通常称为问题的表示。一般来说一个问题可有 多种表示方式, 而选择一种较好的表示是运用智能技术解决 实际问题首先要考虑的, 而且要有一定的技巧。 建立了产生式系统描述之后, 通过控制策略, 可求得实现 目标的一个规则序列, 这就是所谓问题的解, 这个解序列是 根据控制系统记住搜索目标过程中用过的所有规则而构造出 来的
3.1产生式系统 3.1.1产生式系统的组成部分 在一般情况下,问题可能有多个解的序列,但有时会要 求得到有某些附加约束条件的解,例如要求步数最少、距离 最短等。这些约束条件通常是用耗散或代价这一概念来概 括,这时问题可称为寻找具有最小耗散的解 在用产生式系统求解问题时,有时引入状态空间图。状 态空间图是一个有向图,其节点可表示问题的各种状态(综 合数据库,节点之间的弧线代表一些操作(产生式规则),它 们可把一种状态导向另一种状态。这样建立起来的状态空间 图,描述了问题所有可能出现的状态及状态和操作之间的关 系,因而可以较直观地看出问题的解路径及其性质。当然, 只有问题空间规模较小才可能作出状态空间图。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 1 产生式系统 3 . 1 . 1 产生式系统的组成部分 在一般情况下, 问题可能有多个解的序列, 但有时会要 求得到有某些附加约束条件的解, 例如要求步数最少、距离 最短等。 这些约束条件通常是用耗散或代价这一概念来概 括, 这时问题可称为寻找具有最小耗散的解。 在用产生式系统求解问题时, 有时引入状态空间图。状 态空间图是一个有向图, 其节点可表示问题的各种状态(综 合数据库), 节点之间的弧线代表一些操作(产生式规则), 它 们可把一种状态导向另一种状态。这样建立起来的状态空间 图, 描述了问题所有可能出现的状态及状态和操作之间的关 系, 因而可以较直观地看出问题的解路径及其性质。当然, 只有问题空间规模较小才可能作出状态空间图
3.1产生式系统 13.1.1产生式系统的组成部分 建立产生式系统描述的过程,就是所谓问题的表示。对 问题表示的好坏,往往对求解过程的效率有很大的影响。 种较好的表示法会简化状态空间和规则集表示,此外,高 效率的问题求解过程与控制策略有关,合适的控制策略可缩 小状态空间的搜索范围,提高求解的效率 从以上论述可知,用产生式系统来描述和求解问题,就 是在问题空间中搜索一条从初始状态到达某一个目标状态的 路径。这完全可以模拟人的求解过程,也就是可以把产生式 系统作为求解问题思考过程的一种模拟。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 1 产生式系统 3 . 1 . 1 产生式系统的组成部分 建立产生式系统描述的过程, 就是所谓问题的表示。对 问题表示的好坏, 往往对求 解过程的效率有很大的影响。一 种较好的表示法会简化状态空间和规则集表示, 此外, 高 效率的问题求解过程与控制策略有关, 合适的控制策略可缩 小状态空间的搜索范围, 提高求解的效率。 从以上论述可知, 用产生式系统来描述和求解问题, 就 是在问题空间中搜索一条从初始状态到达某一个目标状态的 路径。这完全可以模拟人的求解过程, 也就是可以把产生式 系统作为求解问题思考过程的一种模拟