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