人工智能与机器翻译课件.ppt

1、第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 产生式系统使用类似于文法的规则产生式系统使用类似于文法的规则,对符号对符号串作替换运算。串作替换运算。它是智能软件中使用最普遍、最典它是智能软件中使用最普遍、最典型的一种结构。为什么要采用产生式系统作为智能型的一种结构。为什么要采用产生式系统作为智能软件的主要结构呢软件的主要结构呢?这可以有这可以有两点理由两点理由:(1)用产生式系统结构求解问题的过程和人类求用产生式系统结构求解问题的过程和人类求解问题时的思维过程很相象解问题时的思维过程很相象,因而可以用它来模拟因而可以用它来

2、模拟人类求解问题时的思维过程人类求解问题时的思维过程;(2)可以把产生式系统作为智能软件中的基本结可以把产生式系统作为智能软件中的基本结构单元或基本模式看待构单元或基本模式看待,就好象是就好象是 积木世界中的积积木世界中的积木块一样木块一样,因而研究产生式系统的基本问题就具有因而研究产生式系统的基本问题就具有一般意义。一般意义。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.1.1 产生式系统的组成部分产生式系统的组成部分一个智能软件用产生式系统设计的基本组一个智能软件用产生式系统设计的基本组成是成是:一个综合数据库一个综合数据库;一组产生式规则一组产生式规则;一个控制系统。一

3、个控制系统。综合数据库是产生式系统所使用的主要数综合数据库是产生式系统所使用的主要数据结构据结构,用来表述问题的状态或有关事实。用来表述问题的状态或有关事实。它包含求解问题的信息它包含求解问题的信息,其中有些部分可以其中有些部分可以是不变的是不变的,有些部分可能只与当前问题的解有些部分可能只与当前问题的解有关。人们可以根据问题的性质有关。人们可以根据问题的性质,用适当的方用适当的方法来构造综合数据库的信息。法来构造综合数据库的信息。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.1.1 产生式系统的组成部分产生式系统的组成部分产生式规则的一般形式为产生式规则的一般形式为:条件条

4、件行动行动 或或 前提前提结论结论 即表示成为即表示成为:ifthen 的形式。的形式。其中其中,左边确定了该规则可应用的先决条件左边确定了该规则可应用的先决条件;右边右边描述了应用这条规则所采取的行动或得出的结论。描述了应用这条规则所采取的行动或得出的结论。一条产生式规则满足了应用的先决条件之后一条产生式规则满足了应用的先决条件之后,就可就可对综合数据库进行操作对综合数据库进行操作,使其发生变化。如综合数使其发生变化。如综合数据库代表当前状态据库代表当前状态,则应用规则后就使状态发生转则应用规则后就使状态发生转换换,生成新状态。生成新状态。第第3 章章 产生式系统及其搜索方法产生式系统及其搜

5、索方法 3.1.1 产生式系统的组成部分产生式系统的组成部分 控制系统是软件的控制程序控制系统是软件的控制程序,也是规则的解释也是规则的解释(推理推理)程程序。序。它规定了如何选择一条它规定了如何选择一条 可应用的规则对数据库进行操可应用的规则对数据库进行操作作,即确定了求解过程的推理路线。即确定了求解过程的推理路线。当数据库满足结束条件当数据库满足结束条件时时,系统就应停止运行系统就应停止运行;还要使系统在求解过程中记住应用还要使系统在求解过程中记住应用过的规则序列过的规则序列,以便最终能给出解的路径。以便最终能给出解的路径。控制系统也称控制策略控制系统也称控制策略,它也可以是从规则集中选择

6、规它也可以是从规则集中选择规则并作用于状态的一种广义选取函数。确定某一种策略后则并作用于状态的一种广义选取函数。确定某一种策略后,可以算法的形式给出。在建立产生式系统描述时可以算法的形式给出。在建立产生式系统描述时,还要给出还要给出初始状态和目标条件初始状态和目标条件,具体说明所求解的问题。具体说明所求解的问题。产生式系产生式系统中控制策略的作用就是从初始状态出发统中控制策略的作用就是从初始状态出发,寻求一个满足一寻求一个满足一定条件的问题状态。定条件的问题状态。目标条件也是产生式系统结束条件的目标条件也是产生式系统结束条件的基础。基础。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方

7、法 3.1.1 产生式系统的组成部分产生式系统的组成部分 上述产生式系统的定义具有一般性上述产生式系统的定义具有一般性,它可用来模拟任它可用来模拟任一可计算过程。一可计算过程。在研究人类进行问题求解过程时在研究人类进行问题求解过程时,完全可用完全可用一个产生式系统来模拟求解过程一个产生式系统来模拟求解过程,及可作为描述搜索的一种有及可作为描述搜索的一种有效方法。作为智能中的一种形式体系效方法。作为智能中的一种形式体系,它还具有以下优点它还具有以下优点:(1)适合于模拟强数据驱动特点的智能行为。适合于模拟强数据驱动特点的智能行为。当一些新的数据数入时当一些新的数据数入时,系统的行为就要改变系统的

8、行为就要改变;(2)易于添加新规则去适应新的情况易于添加新规则去适应新的情况,而不破而不破坏系统的其他部分。坏系统的其他部分。这是由于产生式系统的各组成这是由于产生式系统的各组成部分具有相对的独立性部分具有相对的独立性,因而便于扩展和修改。因而便于扩展和修改。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.1.1 产生式系统的组成部分产生式系统的组成部分 用产生式系统来求解问题用产生式系统来求解问题,首先必须建立起问题的产生式首先必须建立起问题的产生式系统描述系统描述,即规定出数据库、规则集合及其控制策略。这即规定出数据库、规则集合及其控制策略。这种把一个问题的叙述转化为产生式

9、系统的三个组成部分种把一个问题的叙述转化为产生式系统的三个组成部分,在智能技术中通常称为问题的表示。一般来说一个问题可有在智能技术中通常称为问题的表示。一般来说一个问题可有多种表示方式多种表示方式,而选择一种较好的表示是运用智能技术解决而选择一种较好的表示是运用智能技术解决实际问题首先要考虑的实际问题首先要考虑的,而且要有一定的技巧。而且要有一定的技巧。建立了产生式系统描述之后建立了产生式系统描述之后,通过控制策略通过控制策略,可求得实现可求得实现目标的一个规则序列目标的一个规则序列,这就是所谓问题的解这就是所谓问题的解,这个解序列是这个解序列是根据控制系统记住搜索目标过程中用过的所有规则而构

10、造出根据控制系统记住搜索目标过程中用过的所有规则而构造出来的。来的。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.1.1 产生式系统的组成部分产生式系统的组成部分 在一般情况下在一般情况下,问题可能有多个解的序列问题可能有多个解的序列,但有时会要但有时会要求得到有某些附加约束条件的解求得到有某些附加约束条件的解,例如要求步数最少、距离例如要求步数最少、距离最短等。最短等。这些约束条件通常是用耗散或代价这一概念来概这些约束条件通常是用耗散或代价这一概念来概括括,这时问题可称为寻找具有最小耗散的解。这时问题可称为寻找具有最小耗散的解。在用产生式系统求解问题时在用产生式系统求解问题

11、时,有时引入状态空间图。状有时引入状态空间图。状态空间图是一个有向图态空间图是一个有向图,其节点可表示问题的各种状态其节点可表示问题的各种状态(综综合数据库合数据库),节点之间的弧线代表一些操作节点之间的弧线代表一些操作(产生式规则产生式规则),它它们可把一种状态导向另一种状态。这样建立起来的状态空间们可把一种状态导向另一种状态。这样建立起来的状态空间图图,描述了问题所有可能出现的状态及状态和操作之间的关描述了问题所有可能出现的状态及状态和操作之间的关系系,因而可以较直观地看出问题的解路径及其性质。当然因而可以较直观地看出问题的解路径及其性质。当然,只有问题空间规模较小才可能作出状态空间图。只

12、有问题空间规模较小才可能作出状态空间图。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.1.1 产生式系统的组成部分产生式系统的组成部分 建立产生式系统描述的过程建立产生式系统描述的过程,就是所谓问题的表示。对就是所谓问题的表示。对问题表示的好坏问题表示的好坏,往往对求往往对求 解过程的效率有很大的影响。一解过程的效率有很大的影响。一种较好的表示法会简化状态空间和规则集表示种较好的表示法会简化状态空间和规则集表示,此外此外,高高 效率的问题求解过程与控制策略有关效率的问题求解过程与控制策略有关,合适的控制策略可缩合适的控制策略可缩小状态空间的搜索范围小状态空间的搜索范围,提高求

13、解的效率。提高求解的效率。从以上论述可知从以上论述可知,用产生式系统来描述和求解问题用产生式系统来描述和求解问题,就就是在问题空间中搜索一条从初始状态到达某一个目标状态的是在问题空间中搜索一条从初始状态到达某一个目标状态的路径。这完全可以模拟人的求解过程路径。这完全可以模拟人的求解过程,也就是可以把产生式也就是可以把产生式系统作为求解问题思考过程的一种模拟。系统作为求解问题思考过程的一种模拟。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.1.2 产生式系统的基本算法产生式系统的基本算法 E1:DATA初始事实库初始事实库 E2:until DATA 满足结束条件以前满足结束条

14、件以前,do E3:begin E4:在规则集中在规则集中,选某一条可用于选某一条可用于DATA的规则的规则 E5:DATA规则应用到规则应用到DATA得到的结果得到的结果 E6:结束结束第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.1.3 产生式系统的类型产生式系统的类型正向、逆向、双向产生式系统正向、逆向、双向产生式系统 用产生式系统求解某一问题时用产生式系统求解某一问题时,如果按照规则使用的如果按照规则使用的方式或者说按推理方向来划分的话方式或者说按推理方向来划分的话,有正向、逆向和双向产有正向、逆向和双向产生式系统。生式系统。正向产生式系统是从初始状态出发朝着目标状正

15、向产生式系统是从初始状态出发朝着目标状态这个方向使用规则态这个方向使用规则,即正推的方式工作即正推的方式工作,称这些规则为称这些规则为F规则规则;若选目标状态作为初始若选目标状态作为初始 数据库逆向进行求解数据库逆向进行求解,即逆即逆向使用规则向使用规则,产生子目标状态产生子目标状态,反方向一步一步朝着初始反方向一步一步朝着初始状态方向求解状态方向求解,整个逆推方式工作整个逆推方式工作,称逆向产生式系统称逆向产生式系统,逆向应用的规则称逆向应用的规则称B规则规则;若以双向搜索的方式若以双向搜索的方式(即正向和即正向和逆向同时进行逆向同时进行)去求解问题去求解问题,则称为双向产生式系统。则称为双

16、向产生式系统。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.1.3 产生式系统的类型产生式系统的类型可交换的产生式系统可交换的产生式系统 可交换式产生式系统的可交换性指几条规则的应用可可交换式产生式系统的可交换性指几条规则的应用可以任意交换次序而不影响求解。以任意交换次序而不影响求解。一般来说一般来说,当一个产生式系统对任何一个数据库当一个产生式系统对任何一个数据库D都都具有如下性质时具有如下性质时,这样一个产生式系这样一个产生式系 统是可交换的。统是可交换的。(1)可应用于可应用于D的规则集合的规则集合,使用了其中任意一条规则之后所生使用了其中任意一条规则之后所生成的任何数

17、据库成的任何数据库,这样一个规则集合还适用这样一个规则集合还适用;(2)满足目标条件的某个数据库满足目标条件的某个数据库D,当应用任何一个可应用于数当应用任何一个可应用于数据库据库D 的规则之后所的规则之后所 生成的任何数据库生成的任何数据库,任然满足目标条件任然满足目标条件;(3)若对若对D应用某一规则序列后得到的一个数据库应用某一规则序列后得到的一个数据库D(并能达到并能达到解解),当改变这些规则次序后当改变这些规则次序后,任然可求得解任然可求得解,即求得即求得D与使用满足与使用满足D的可应用规则集合中的规则次序无关。的可应用规则集合中的规则次序无关。第第3 章章 产生式系统及其搜索方法产

18、生式系统及其搜索方法 3.1.3 产生式系统的类型产生式系统的类型可交换的产生式系统可交换的产生式系统 例例:给定一个整数集合的初始状态给定一个整数集合的初始状态a,b,c,设目标状态为设目标状态为具有具有a,b,c,ab,bc,ca这六个元素组成的集合。可应用的这六个元素组成的集合。可应用的规则集合为规则集合为 R1:if a,b,c then a,b,c,ab R2:if a,b,c then a,b,c,bc R3:if a,b,c then a,b,c,ca 显然显然,这个产生式实例具有可交换性。这个产生式实例具有可交换性。一个产生式系统具有可交换性一个产生式系统具有可交换性,求解时只

19、需搜索其中求解时只需搜索其中任一条途径任一条途径,只要解存在就一只要解存在就一 定能找到目标定能找到目标,不必探索不必探索多条途径多条途径,因此不可撤回的控制方式因此不可撤回的控制方式(下节论述下节论述)在这种在这种系统中使用很合适系统中使用很合适,因解与最初可应用的规则系列的次因解与最初可应用的规则系列的次序无关序无关,系统不必提供特殊选择规则的机理系统不必提供特殊选择规则的机理。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.1.3 产生式系统的类型产生式系统的类型 先研究一个重写问题的产生式系统先研究一个重写问题的产生式系统,初始数据库为初始数据库为(C,B,Z),产生式

20、规则如下产生式规则如下:R1:C(D,L)R2:C(B,M)R3:B(M,M)R4:Z(B,B,M)结束条件是生成只包含结束条件是生成只包含M组成的数据库组成的数据库,即即(M,M)。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.1.3 产生式系统的类型产生式系统的类型用图搜索方式求解这个问题时用图搜索方式求解这个问题时,搜索得到的部分状态搜索得到的部分状态空间图见图空间图见图26。图中只给出两条达到目标的路径和一条失图中只给出两条达到目标的路径和一条失败的路径。实际搜索时有可能去探索更多的路径败的路径。实际搜索时有可能去探索更多的路径,往往导往往导致效率降低。致效率降低。对

21、于个问题对于个问题,为了避免搜索多余的路径为了避免搜索多余的路径,可以将初可以将初始数据库分解成几个可以独立加以处理的分量始数据库分解成几个可以独立加以处理的分量,分别对它分别对它们进行求解。们进行求解。即可以分别对每一个分量数据库即可以分别对每一个分量数据库,测试产测试产生式规则可以应用的条件生式规则可以应用的条件,如此进行下去如此进行下去,直到分量数据直到分量数据库满足某种结束条件为止。库满足某种结束条件为止。要注意一般结要注意一般结 束条件应是所束条件应是所有分量数据库都已满足结束条件。有分量数据库都已满足结束条件。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.1.3

22、产生式系统的类型产生式系统的类型 能够分解产生式系统的综合数据库和结束条件的产生能够分解产生式系统的综合数据库和结束条件的产生式系统称为可分解的产生式系统。一个可分解的产生式系式系统称为可分解的产生式系统。一个可分解的产生式系统统,其基本算法描述其基本算法描述如下如下:(1)DATA:=初始数据库初始数据库 (2)Di:=DATA的分解式的分解式;每个每个Di元素都看成单独的数据库元素都看成单独的数据库 (3)Until Di的所有元素都满足结束条件之前的所有元素都满足结束条件之前,do:(4)begin (5)从从Di中选一个不满足结束条件的中选一个不满足结束条件的D*(6)从从Di中删去中

23、删去D*(7)在规则集中选择一条可应用于在规则集中选择一条可应用于D*的规则的规则R (8)di:=R应用于应用于D*的结果的结果 (9)在在Di上添加上添加di(10)end第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法下图为分解方式下图为分解方式 (C,B,Z)初态初态 R2 R4 R1 (B,M,B,Z)(C,B,B,B,M)(D,L,B,Z)R3 R2 R3 (M,M,M,B,Z)(B,M,B,B,B,M)(D,L,M,M,Z)R3 R3 R4 (M,M,M,M,M,Z)(M,M,M,B,B,B,M)(D,L,M,M,B,B,M)R4R3 R3 (M,M,M,M,M,B,B

24、,M)(D,L,M,M,M,B,M)R3 R3 (M,M,M,M,M,M,M,B,M)(D,L,M,M,M,M,M,M,M)R3目标目标 (M,M,M,M,M,M,M,M,M,M)图图 26第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 在在3.1.2节的算法中节的算法中,如何选择一条可应用的规则如何选择一条可应用的规则,作用于当前的综合数据库作用于当前的综合数据库,生成新生成新 的状态以及记住选用的的状态以及记住选用的规则序列是构成控制策略的主要内容。对大多数的智能应用规则序列是构成控制策略的主要内容。对大多数的智能应用问题问题,所拥有的控制策略知识或信息并不足以使每次通过算所拥

25、有的控制策略知识或信息并不足以使每次通过算法法E4时时,一下子就能选出最合适的一下子就能选出最合适的 一条规则来一条规则来,因而产生因而产生式系统还必须把式系统还必须把E4扩大成搜索扩大成搜索(推理推理)算法算法,以至于基本算法以至于基本算法的每的每 一循环中选一条规则试用一循环中选一条规则试用,最终找出某一序列能产生最终找出某一序列能产生一个满足结束条件的数据库为止。由此可见一个满足结束条件的数据库为止。由此可见,高效率的控制高效率的控制策略需要有关被求解问题的足够知识策略需要有关被求解问题的足够知识,这样才能在搜索过程这样才能在搜索过程 减少盲目性减少盲目性,比较快的找到解路径。比较快的找

26、到解路径。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 过去三十多年中过去三十多年中,人们研究了许多种搜索算法人们研究了许多种搜索算法,归纳起归纳起来主要有两类来主要有两类:一类是非启发一类是非启发 式算法式算法;另一类是启发式算法。另一类是启发式算法。非启发式算法是按预定的控制策略进行搜索非启发式算法是按预定的控制策略进行搜索,在其过程中获在其过程中获得的中间信息不用来改进控制策略。得的中间信息不用来改进控制策略。由于搜索总是按预先由于搜索总是按预先规定的路线进行规定的路线进行,没有考虑问题本身的特性没有考虑问题本身的特性,所以不容易选所以不容易选择到最优的搜索途径择到最优的搜

27、索途径,效率较低效率较低,且出现且出现组合爆炸组合爆炸的频率的频率高。高。启发式算法是在搜索中加入了与问题有关的启发性信启发式算法是在搜索中加入了与问题有关的启发性信息息,用以指导搜索朝着最有希望的方向前进用以指导搜索朝着最有希望的方向前进,加速问题的求加速问题的求解过程并找到最优解。解过程并找到最优解。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.2.1 产生式系统控制策略分类产生式系统控制策略分类 控制策略可划分为两大类控制策略可划分为两大类:不可撤回方法不可撤回方法 回溯方法回溯方法 试探性方法试探性方法 图搜索方法图搜索方法第第3 章章 产生式系统及其搜索方法产生式系

28、统及其搜索方法 3.2.2 不可撤回方法不可撤回方法 这种方法相当于沿着单独一条路搜索下去这种方法相当于沿着单独一条路搜索下去,利用问题给利用问题给出的局部知识决定如何选取规则出的局部知识决定如何选取规则,就是说根据当前可靠的局就是说根据当前可靠的局部知识选一条可应用规则并作用于当前综合数据库。部知识选一条可应用规则并作用于当前综合数据库。接着接着再根据新状态继续选取规则再根据新状态继续选取规则,搜索过程一直进行搜索过程一直进行,不必考虑不必考虑撤回用过的规则。撤回用过的规则。这是由于在搜索过程中如能有效利用局这是由于在搜索过程中如能有效利用局部知识部知识,即使使用了一条不理想的规则即使使用了

29、一条不理想的规则,也不妨碍下一步选也不妨碍下一步选得另一条更合适的规则。这样不撤消用过的规则得另一条更合适的规则。这样不撤消用过的规则,并不影响并不影响求到解求到解,只是解序列中可能多了一些不必要的规则。显然这只是解序列中可能多了一些不必要的规则。显然这种策略具有控制简单的优点。种策略具有控制简单的优点。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.2.2 不可撤回方法不可撤回方法 爬山法不仅适用于爬山问题爬山法不仅适用于爬山问题,那些目标为极大值那些目标为极大值,搜索搜索过程是不断接近目标的单值问题都可应用这一方法。使用不过程是不断接近目标的单值问题都可应用这一方法。使用不

30、可撤回策略可撤回策略,虽然不可能对任何状态总能选得最优的规则虽然不可能对任何状态总能选得最优的规则,但是如果应用了一条不合适的规则之后但是如果应用了一条不合适的规则之后,不去撤消它并不排不去撤消它并不排除下一步应用一条合适的规则除下一步应用一条合适的规则,那么只是解序列有些多余的那么只是解序列有些多余的规则而已规则而已,求得的解不是最优解求得的解不是最优解,但控制较简单。此外还应当但控制较简单。此外还应当指出指出,一般很难对给定问题构造出任何情况下都能通用的爬一般很难对给定问题构造出任何情况下都能通用的爬山函数山函数,因而不因而不 可撤回的方法具有一定的局限性。可撤回的方法具有一定的局限性。第

31、第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.2.3 回溯方法回溯方法 在问题求解过程中在问题求解过程中,有时会发现应用一条不合适的规则会阻扰或有时会发现应用一条不合适的规则会阻扰或拖延达到目标的过程。在这种情况下拖延达到目标的过程。在这种情况下,需要有这样的控制策略需要有这样的控制策略:先试一试先试一试某一条规则某一条规则,如果以后发现这条规则不合适如果以后发现这条规则不合适,则允许退回去则允许退回去,另选一条另选一条规则来试。回溯方法不保留完整的搜索树结构规则来试。回溯方法不保留完整的搜索树结构,只记住当前工作的一条只记住当前工作的一条路径路径,回溯就是对这条路径进行修正。

32、回溯就是对这条路径进行修正。使用回溯策略首要的问题要研究在什么情况下应该回溯使用回溯策略首要的问题要研究在什么情况下应该回溯,即要确定即要确定回溯条件的问题。其次就是如何利用有用知识进行规则排序回溯条件的问题。其次就是如何利用有用知识进行规则排序,以减少回以减少回溯次数。溯次数。回溯应发生在以下三种情况回溯应发生在以下三种情况:(1)新生成的状态在通向初始状态的路径上已出现过新生成的状态在通向初始状态的路径上已出现过;(2)从初始状态开始从初始状态开始,应用的规则数目达到所规定的数应用的规则数目达到所规定的数目之后还未找到目标状态目之后还未找到目标状态(这一组规则的数目实际上就是这一组规则的数

33、目实际上就是搜索深度范围所规定的搜索深度范围所规定的);(3)对当前状态对当前状态,再没有可应用的规则。再没有可应用的规则。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.2.3 回溯方法回溯方法 搜索深度的设置是一个值得注意的问题搜索深度的设置是一个值得注意的问题,设置太浅设置太浅,有有可能找不到解可能找不到解;设置太深设置太深,有可能导致回溯次数巨增。因而有可能导致回溯次数巨增。因而应根据实际情况来规定搜索范围应根据实际情况来规定搜索范围,先设置适中的深度搜索先设置适中的深度搜索,失败时再逐步加深。失败时再逐步加深。回溯过程是一种可试探的方法回溯过程是一种可试探的方法,从形

34、式上无论是否存从形式上无论是否存在对选择规则有用的知识在对选择规则有用的知识,都可以采用这种策略。即如果没都可以采用这种策略。即如果没有有用的知识来引导规则选取有有用的知识来引导规则选取,那么规则可按任意方式那么规则可按任意方式(固固定排序或随机定排序或随机)选取选取;如果有好的选择规则的知识可用如果有好的选择规则的知识可用,那么那么用这种知识来引导规则选取用这种知识来引导规则选取,就会减少盲目性就会减少盲目性,降低回溯次降低回溯次数数,甚至不回溯就能找到解甚至不回溯就能找到解,总之一般来说有利于提高效率。总之一般来说有利于提高效率。此外由于引入回溯机理此外由于引入回溯机理,可以避免陷入局部极

35、大值的情况可以避免陷入局部极大值的情况,继续寻找其他达到目标的路径。继续寻找其他达到目标的路径。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.2.3 回溯方法回溯方法可用递归算法描述回溯策略可用递归算法描述回溯策略:YX0:选择一条新路径搜索选择一条新路径搜索;YX1:搜索已超出规定指标搜索已超出规定指标(无新路径、超时无新路径、超时,超深度等超深度等),失败退出失败退出;否则搜索继续否则搜索继续;YX2:搜索的状态找不到可用规则搜索的状态找不到可用规则,回溯到回溯到YX0;YX3:搜索的状态依某种原则搜索的状态依某种原则(任意排列或按启发式准则任意排列或按启发式准则)取有用

36、规则取有用规则;YX4:若规则用完未找到目标若规则用完未找到目标,回溯回溯YX0;YX5:取头条可用规则取头条可用规则Ri;YX6:删去头条规则删去头条规则,减少搜索中规则集长度减少搜索中规则集长度(注意注意,这不动原始规则这不动原始规则集集);YX7:规则规则Ri作用于当前状态作用于当前状态,生成新状态生成新状态;YX8:若找到目标若找到目标,成功退出成功退出;若生成的若生成的新状态新状态已出现过已出现过,回溯到回溯到YX0;YX9:记录新状态记录新状态,对新状态递规调用对新状态递规调用YX1YX7;第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 产生式系统求解问题时产生式系统求

37、解问题时,如果控制系统如果控制系统保留所有规则应用后生成并链接起来的状态保留所有规则应用后生成并链接起来的状态记录图记录图,则称工作在这种方式下的控制系统则称工作在这种方式下的控制系统使用了图搜索策略。使用了图搜索策略。实际上图搜索策略是实实际上图搜索策略是实现从一个隐含图中现从一个隐含图中,生成一部分确实含有一个生成一部分确实含有一个目标节点的显式表示的子图搜索过程。目标节点的显式表示的子图搜索过程。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 3.3.1 一般性图搜索算法一般性图搜索算法 步骤步骤1 GS,OPEN(S);建立一个搜索图建立一个搜索图G,它只含有它只含有初始节

38、点初始节点S,建立一个建立一个OPEN表表(今后它用于存储生成的节点今后它用于存储生成的节点),开始它只含有初始节点开始它只含有初始节点S。步骤步骤2 CLOSED();建立一个建立一个CLOSED表表(今后它用今后它用于存储已扩展节点或将要扩展的某个节点于存储已扩展节点或将要扩展的某个节点),它的初始状态它的初始状态为空表。为空表。步骤步骤3 LOOP:if OPEN=()then return FAIL;进入循环。进入循环。如果如果OPEN表已空表已空,说明没有节点可扩展说明没有节点可扩展,就返回就返回FAIL,即即失败。失败。步骤步骤4 nFIRST(OPEN),CLOSED(n,CLO

39、SED);从从OPEN表中取出一个节点表中取出一个节点n,将其将其 放入放入CLOSED表中。表中。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 该方法从初始节点开始该方法从初始节点开始,序扩展生成下一级各子节点序扩展生成下一级各子节点,OPEN 表中已有的节点后表中已有的节点后 面面(实现先生成的子节点先扩展实现先生成的子节点先扩展),然后从然后从OPEN 表中提取最前的一个节点检查是否是目标节表中提取最前的一个节点检查是否是目标节点点,否则再扩展否则再扩展,再重复上述操作。再重复上述操作。这种方法认为同一级这种方法认为同一级各节点对问题求解的价值是同等的各节点对问题求解的价值

40、是同等的,因而对全部节点沿广因而对全部节点沿广度进行横向扫描度进行横向扫描,按各节点生成的先后次序按各节点生成的先后次序,先生成、先检先生成、先检查、先扩展查、先扩展,沿广度遍历所有节点。沿广度遍历所有节点。这种方法只要问题有解这种方法只要问题有解,即若树图上存在目标节点即若树图上存在目标节点,经搜索一定能找到。经搜索一定能找到。所以所以,广度优先搜索法是完备的广度优先搜索法是完备的,是一是一种推理算法。种推理算法。但是但是,在问题大节点多在问题大节点多,且目标节点距离初且目标节点距离初始节点较远时将会产生许多无用节点始节点较远时将会产生许多无用节点,搜索效率低搜索效率低,还可能还可能产生组合

41、爆炸。产生组合爆炸。因此因此,这种方法较适宜问题不大的环境中这种方法较适宜问题不大的环境中第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 该方法从初始节点开始该方法从初始节点开始,顺序扩展生成下一级各子节点顺序扩展生成下一级各子节点,放在放在OPEN表中已有的节点前面表中已有的节点前面(实现后生成的子节点先扩展实现后生成的子节点先扩展),然后从然后从OPEN 表中提取最前的一个节点检查是否是目标节点表中提取最前的一个节点检查是否是目标节点,否则再扩否则再扩展展,再重复上述操作。再重复上述操作。这种方法每一次扩展最晚生成的子节点这种方法每一次扩展最晚生成的子节点,沿着最晚生成的子节点

42、分支沿着最晚生成的子节点分支,逐级纵向深入发展。逐级纵向深入发展。这种方法搜索一旦进入某个分支这种方法搜索一旦进入某个分支,就将沿着该分支一直向下搜就将沿着该分支一直向下搜索。索。如果目标节点恰如果目标节点恰 好在此分支上好在此分支上,则可较快地得到解。则可较快地得到解。但是但是,如果目标节点不在此分支上如果目标节点不在此分支上,不回溯就不可能得到解。不回溯就不可能得到解。所以所以,深深度优先搜索是不完备的度优先搜索是不完备的,只是推理步骤。只是推理步骤。如果回溯如果回溯,不难证明其平不难证明其平 均效率与广度优先搜索法相同。均效率与广度优先搜索法相同。因此因此,深度优先搜索法如果没有深度优先

43、搜索法如果没有启发信息启发信息,很难有实用价值。很难有实用价值。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 该方法考虑了从一个节点经过一条支路该方法考虑了从一个节点经过一条支路,转移到另一个节点时所需转移到另一个节点时所需要支付的代价要支付的代价,如费用、时间等。如费用、时间等。该方法从初始节点开始该方法从初始节点开始,扩展生成下扩展生成下一级各子节点一级各子节点,这些子节点中若没有目标节点需再扩展搜索。这些子节点中若没有目标节点需再扩展搜索。把它们放把它们放进进OPEN表中表中,依据初始节点到它们各自所付出的代价依据初始节点到它们各自所付出的代价 大小进行排序大小进行排序,代

44、代价小的节点放在前面扩展价小的节点放在前面扩展,周而复始重复上述操作周而复始重复上述操作,直至找到目标节点直至找到目标节点为止。为止。这种方法根据各条支路所需支付的代价有差别这种方法根据各条支路所需支付的代价有差别,所以具有同样路径所以具有同样路径长度长度(所经过的支路数所经过的支路数)的搜索过程的搜索过程,其搜索代价其搜索代价(所支付的总代价所支付的总代价)可能可能不同不同,优选最小代价的搜索路径优选最小代价的搜索路径,进行推理求解问题。进行推理求解问题。代价驱动搜索无代价驱动搜索无论在理论研究方面还是实际应用方面都很有前景论在理论研究方面还是实际应用方面都很有前景,例如最短路径问题。例如最

45、短路径问题。进一步的研究认为最短路径问题的改进应为以下几点进一步的研究认为最短路径问题的改进应为以下几点:第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 1)OPEN表的节点排序问题表的节点排序问题,特别是在问题节点多达成千上万时尤特别是在问题节点多达成千上万时尤为重要为重要.这一排序应采用映射排序，这一排序应采用映射排序，它是一个基于地址计算的排序它是一个基于地址计算的排序,在预在预置路径最大代价置路径最大代价dmax后后,开辟一个数组开辟一个数组P(dmax),就可把节点送入其值就可把节点送入其值与与P数组下标相等的对应元素中数组下标相等的对应元素中,显然显然di=50它对应它

46、对应P(50);dj=500,对应对应P(500)。相同代价值的节点落在同一数组元素中相同代价值的节点落在同一数组元素中,用计数方式用计数方式 可知有几可知有几个。个。由于数组元素是有序的由于数组元素是有序的,50050,数组元素的下标自然把节点一数组元素的下标自然把节点一次定好了位置次定好了位置,排序即完成。排序即完成。这一排序的时间复杂性为这一排序的时间复杂性为O(N),对于对于OPEN表面临的无数次排序操作表面临的无数次排序操作,极大的提高了效率极大的提高了效率.2)搜索过程中搜索过程中,如果到达某一节点的代价如果到达某一节点的代价任一初始节点到目标节任一初始节点到目标节点的路径代价点的

47、路径代价,这一节点的路径删去。这一节点的路径删去。3)搜索过程中搜索过程中,如果同时出现了两条到达某一节点的路径如果同时出现了两条到达某一节点的路径 ,代价大代价大的那条路径即时删去。的那条路径即时删去。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 搜索过程中搜索过程中,如果在确定扩展那一个节点时能充分利如果在确定扩展那一个节点时能充分利用与问题求解有关的特性信息用与问题求解有关的特性信息,就可以估计出节点的重就可以估计出节点的重要性要性 ,就能使搜索选择重要性较高的节点就能使搜索选择重要性较高的节点 ,以利于求得以利于求得最优解。最优解。象这样象这样 就可用于指导搜索过程就可用

48、于指导搜索过程,且与具体问且与具体问题求解有关的控制性信息称为启发性信息。题求解有关的控制性信息称为启发性信息。启发性信息启发性信息可以用于估价节点重要性可以用于估价节点重要性,表示为函数形式表示为函数形式:f(x)=g(x)+h(x)f(x)=g(x)+h(x)其中其中,g(x),g(x)为初始节点为初始节点S S。到节点。到节点x x已经付出的代价已经付出的代价;h(x)h(x)是从节点是从节点x x到目标节点到目标节点SgSg的最优的最优 路径的估计代价路径的估计代价,它它体现了问题的启发性信息体现了问题的启发性信息,其形式根据问题的特性确定。其形式根据问题的特性确定。第第3 章章 产生

49、式系统及其搜索方法产生式系统及其搜索方法如果对一般性图搜索算法作以下限制如果对一般性图搜索算法作以下限制,则它成为则它成为A*算法算法:(1)OPEN表中的节点按估价函数表中的节点按估价函数 f(x)=g(x)+h(x)的值的值从小至大进行排序从小至大进行排序.(2)g(x)是到目前为止是到目前为止,从从S。到。到x的一条最小耗散值路的一条最小耗散值路径的耗散值径的耗散值,是作为从是作为从S。到。到 x 最小耗散值路径的耗散值最小耗散值路径的耗散值g*(x)的估计值的估计值,g(x)0。(3)h(x)是是h*(x)的下界的下界,即对所有即对所有x均有均有h(x)h*(x)。而而h*(x)是从节

50、点是从节点x到目标节点的最小代价到目标节点的最小代价,若有多个目标节点若有多个目标节点,则为其中最小的一个。则为其中最小的一个。第第3 章章 产生式系统及其搜索方法产生式系统及其搜索方法 性质性质1 对于有限图对于有限图,A*算法一定会在有限算法一定会在有限步内终止步内终止.证明：证明：对于有限图对于有限图,其节点个数是有限的其节点个数是有限的,A*算法在经过若干次循环后会出现两种情算法在经过若干次循环后会出现两种情况况:或者搜索到目标节点在步骤或者搜索到目标节点在步骤5结束结束;或或者者OPEN表中的节点被取完在步骤表中的节点被取完在步骤3结束。结束。不不 管那种情况管那种情况,A*算法都在