人工智能与机器翻译课件

人工智能与机器翻译主讲：杨宪泽——产生式系统及其搜索方法人工智能与机器翻译主讲：杨宪泽——产生式系统及其搜索第3章产生式系统及其搜索方法3.1产生式系统3.2产生式系统的搜索(控制)策略3.3图搜索算法3.4产生式系统的规则问题3.5应用举例3.6产生式系统的不确定性问题3.7系统设计技巧第3章产生式系统及其搜索方法3.1产生式系统3.1产生式系统产生式系统使用类似于文法的规则,对符号串作替换运算。它是智能软件中使用最普遍、最典型的一种结构。为什么要采用产生式系统作为智能软件的主要结构呢?这可以有两点理由:

(1)用产生式系统结构求解问题的过程和人类求解问题时的思维过程很相象,因而可以用它来模拟人类求解问题时的思维过程;(2)可以把产生式系统作为智能软件中的基本结构单元或基本模式看待,就好象是积木世界中的积木块一样,因而研究产生式系统的基本问题就具有一般意义。3.1产生式系统产生式系统3.1产生式系统3.1.1产生式系统的组成部分一个智能软件用产生式系统设计的基本组成是:一个综合数据库;一组产生式规则;一个控制系统。综合数据库是产生式系统所使用的主要数据结构,用来表述问题的状态或有关事实。它包含求解问题的信息,其中有些部分可以是不变的,有些部分可能只与当前问题的解有关。人们可以根据问题的性质,用适当的方法来构造综合数据库的信息。3.1产生式系统3.1.13.1产生式系统

3.1.1产生式系统的组成部分产生式规则的一般形式为:条件─→行动或前提─→结论即表示成为:if┄┄then┄┄的形式。其中,左边确定了该规则可应用的先决条件;右边描述了应用这条规则所采取的行动或得出的结论。一条产生式规则满足了应用的先决条件之后,就可对综合数据库进行操作,使其发生变化。如综合数据库代表当前状态,则应用规则后就使状态发生转换,生成新状态。3.1产生式系统3.1.13.1产生式系统

3.1.1产生式系统的组成部分控制系统是软件的控制程序,也是规则的解释(推理)程序。它规定了如何选择一条可应用的规则对数据库进行操作,即确定了求解过程的推理路线。当数据库满足结束条件时,系统就应停止运行;还要使系统在求解过程中记住应用过的规则序列,以便最终能给出解的路径。控制系统也称控制策略,它也可以是从规则集中选择规则并作用于状态的一种广义选取函数。确定某一种策略后,可以算法的形式给出。在建立产生式系统描述时,还要给出初始状态和目标条件,具体说明所求解的问题。产生式系统中控制策略的作用就是从初始状态出发,寻求一个满足一定条件的问题状态。目标条件也是产生式系统结束条件的基础。3.1产生式系统3.1.13.1产生式系统

3.1.1产生式系统的组成部分上述产生式系统的定义具有一般性,它可用来模拟任一可计算过程。在研究人类进行问题求解过程时,完全可用一个产生式系统来模拟求解过程,及可作为描述搜索的一种有效方法。作为智能中的一种形式体系,它还具有以下优点:

(1)适合于模拟强数据驱动特点的智能行为。当一些新的数据数入时,系统的行为就要改变;(2)易于添加新规则去适应新的情况,而不破坏系统的其他部分。这是由于产生式系统的各组成部分具有相对的独立性,因而便于扩展和修改。3.1产生式系统3.1.13.1产生式系统3.1.1产生式系统的组成部分

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

3.1.1产生式系统的组成部分在一般情况下,问题可能有多个解的序列,但有时会要求得到有某些附加约束条件的解,例如要求步数最少、距离最短等。这些约束条件通常是用耗散或代价这一概念来概括,这时问题可称为寻找具有最小耗散的解。在用产生式系统求解问题时,有时引入状态空间图。状态空间图是一个有向图,其节点可表示问题的各种状态(综合数据库),节点之间的弧线代表一些操作(产生式规则),它们可把一种状态导向另一种状态。这样建立起来的状态空间图,描述了问题所有可能出现的状态及状态和操作之间的关系,因而可以较直观地看出问题的解路径及其性质。当然,只有问题空间规模较小才可能作出状态空间图。3.1产生式系统3.1.1产3.1产生式系统

3.1.1产生式系统的组成部分

建立产生式系统描述的过程,就是所谓问题的表示。对问题表示的好坏,往往对求解过程的效率有很大的影响。一种较好的表示法会简化状态空间和规则集表示,此外,高效率的问题求解过程与控制策略有关,合适的控制策略可缩小状态空间的搜索范围,提高求解的效率。从以上论述可知,用产生式系统来描述和求解问题,就是在问题空间中搜索一条从初始状态到达某一个目标状态的路径。这完全可以模拟人的求解过程,也就是可以把产生式系统作为求解问题思考过程的一种模拟。3.1产生式系统3.1.13.1产生式系统

3.1.2产生式系统的基本算法E1:DATA←初始事实库E2:untilDATA满足结束条件以前,doE3:beginE4:在规则集中,选某一条可用于DATA的规则E5:DATA←规则应用到DATA得到的结果E6:结束3.1产生式系统3.1.2产3.1产生式系统

3.1.3产生式系统的类型正向、逆向、双向产生式系统

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

3.1.3产生式系统的类型可交换的产生式系统可交换式产生式系统的可交换性指几条规则的应用可以任意交换次序而不影响求解。一般来说,当一个产生式系统对任何一个数据库D都具有如下性质时,这样一个产生式系统是可交换的。

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

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}显然,这个产生式实例具有可交换性。一个产生式系统具有可交换性,求解时只需搜索其中任一条途径,只要解存在就一定能找到目标,不必探索多条途径,因此不可撤回的控制方式(下节论述)在这种系统中使用很合适,因解与最初可应用的规则系列的次序无关,系统不必提供特殊选择规则的机理。3.1产生式系统3.1.3产3.1产生式系统

3.1.3产生式系统的类型可分解的产生式系统先研究一个重写问题的产生式系统,初始数据库为(C,B,Z),产生式规则如下:R1:C→(D,L)R2:C→(B,M)R3:B→(M,M)R4:Z→(B,B,M)结束条件是生成只包含M组成的数据库,即(M,…,M)。3.1产生式系统3.1.3产3.1产生式系统

3.1.3产生式系统的类型可分解的产生式系统用图搜索方式求解这个问题时,搜索得到的部分状态空间图见图26。图中只给出两条达到目标的路径和一条失败的路径。实际搜索时有可能去探索更多的路径,往往导致效率降低。对于个问题,为了避免搜索多余的路径,可以将初始数据库分解成几个可以独立加以处理的分量,分别对它们进行求解。即可以分别对每一个分量数据库,测试产生式规则可以应用的条件,如此进行下去,直到分量数据库满足某种结束条件为止。要注意一般结束条件应是所有分量数据库都已满足结束条件。3.1产生式系统3.1.3产3.1产生式系统

3.1.3产生式系统的类型可分解的产生式系统能够分解产生式系统的综合数据库和结束条件的产生式系统称为可分解的产生式系统。一个可分解的产生式系统,其基本算法描述如下:

(1)DATA:=初始数据库(2){Di}:=DATA的分解式;每个Di元素都看成单独的数据库(3)Until{Di}的所有元素都满足结束条件之前,do:(4)begin(5)从{Di}中选一个不满足结束条件的D*(6)从{Di}中删去D*(7)在规则集中选择一条可应用于D*的规则R(8){di}:=R应用于D*的结果(9)在{Di}上添加di(10)end3.1产生式系统3.1.3产下图为分解方式(C,B,Z)初态┌──────┼──────┐↓R2↓R4R1↓(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)│┌─────┘│↓R4↓R3↓R3(M,M,M,M,M,B,B,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.2产生式系统的搜索(控制)策略

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

过去三十多年中,人们研究了许多种搜索算法,归纳起来主要有两类:一类是非启发式算法;另一类是启发式算法。非启发式算法是按预定的控制策略进行搜索,在其过程中获得的中间信息不用来改进控制策略。由于搜索总是按预先规定的路线进行,没有考虑问题本身的特性,所以不容易选择到最优的搜索途径,效率较低,且出现"组合爆炸"的频率高。启发式算法是在搜索中加入了与问题有关的启发性信息,用以指导搜索朝着最有希望的方向前进,加速问题的求解过程并找到最优解。

3.2产生式系统的搜索(控制)策略过去三十多年中,人们研究了许多种搜索3.2产生式系统的搜索(控制)策略

3.2.1产生式系统控制策略分类可分解的产生式系统控制策略可划分为两大类:┌不可撤回方法┌回溯方法└试探性方法─┤└图搜索方法3.2产生式系统的搜索(控制)策略3.23.2产生式系统的搜索(控制)策略

3.2.2不可撤回方法

这种方法相当于沿着单独一条路搜索下去,利用问题给出的局部知识决定如何选取规则,就是说根据当前可靠的局部知识选一条可应用规则并作用于当前综合数据库。接着再根据新状态继续选取规则,搜索过程一直进行,不必考虑撤回用过的规则。这是由于在搜索过程中如能有效利用局部知识,即使使用了一条不理想的规则,也不妨碍下一步选得另一条更合适的规则。这样不撤消用过的规则,并不影响求到解,只是解序列中可能多了一些不必要的规则。显然这种策略具有控制简单的优点。3.2产生式系统的搜索(控制)策略3.23.2产生式系统的搜索(控制)策略3.2.2不可撤回方法

爬山法不仅适用于爬山问题,那些目标为极大值,搜索过程是不断接近目标的单值问题都可应用这一方法。使用不可撤回策略,虽然不可能对任何状态总能选得最优的规则,但是如果应用了一条不合适的规则之后,不去撤消它并不排除下一步应用一条合适的规则,那么只是解序列有些多余的规则而已,求得的解不是最优解,但控制较简单。此外还应当指出,一般很难对给定问题构造出任何情况下都能通用的爬山函数,因而不可撤回的方法具有一定的局限性。3.2产生式系统的搜索(控制)策略3.23.2产生式系统的搜索(控制)策略

3.2.3回溯方法

在问题求解过程中,有时会发现应用一条不合适的规则会阻扰或拖延达到目标的过程。在这种情况下,需要有这样的控制策略:先试一试某一条规则,如果以后发现这条规则不合适,则允许退回去,另选一条规则来试。回溯方法不保留完整的搜索树结构,只记住当前工作的一条路径,回溯就是对这条路径进行修正。使用回溯策略首要的问题要研究在什么情况下应该回溯,即要确定回溯条件的问题。其次就是如何利用有用知识进行规则排序,以减少回溯次数。回溯应发生在以下三种情况:

(1)新生成的状态在通向初始状态的路径上已出现过;(2)从初始状态开始,应用的规则数目达到所规定的数目之后还未找到目标状态(这一组规则的数目实际上就是搜索深度范围所规定的);(3)对当前状态,再没有可应用的规则。3.2产生式系统的搜索(控制)策略3.2.3回3.2产生式系统的搜索(控制)策略

3.2.3回溯方法搜索深度的设置是一个值得注意的问题,设置太浅,有可能找不到解;设置太深,有可能导致回溯次数巨增。因而应根据实际情况来规定搜索范围,先设置适中的深度搜索,失败时再逐步加深。回溯过程是一种可试探的方法,从形式上无论是否存在对选择规则有用的知识,都可以采用这种策略。即如果没有有用的知识来引导规则选取,那么规则可按任意方式(固定排序或随机)选取;如果有好的选择规则的知识可用,那么用这种知识来引导规则选取,就会减少盲目性,降低回溯次数,甚至不回溯就能找到解,总之一般来说有利于提高效率。此外由于引入回溯机理,可以避免陷入局部极大值的情况,继续寻找其他达到目标的路径。3.2产生式系统的搜索(控制)策略3.2.3回3.2产生式系统的搜索(控制)策略

3.2.3回溯方法可用递归算法描述回溯策略:YX0:选择一条新路径搜索;YX1:搜索已超出规定指标(无新路径、超时,超深度等),失败退出;否则搜索继续;YX2:搜索的状态找不到可用规则,回溯到YX0;YX3:搜索的状态依某种原则(任意排列或按启发式准则)取有用规则;YX4:若规则用完未找到目标,回溯YX0;YX5:取头条可用规则Ri;YX6:删去头条规则,减少搜索中规则集长度(注意,这不动原始规则集);YX7:规则Ri作用于当前状态,生成新状态;YX8:若找到目标,成功退出;若生成的"新状态"已出现过,回溯到YX0;YX9:记录新状态,对新状态递规调用YX1～YX7;3.2产生式系统的搜索(控制)策略3.2.3回产生式系统求解问题时,如果控制系统保留所有规则应用后生成并链接起来的状态记录图,则称工作在这种方式下的控制系统使用了图搜索策略。实际上图搜索策略是实现从一个隐含图中,生成一部分确实含有一个目标节点的显式表示的子图搜索过程。3.3图搜索算法产生式系统求解问题时,如果控制系统3.3图搜索算法3.3.1一般性图搜索算法步骤1G←S,OPEN←(S);建立一个搜索图G,它只含有初始节点S,建立一个OPEN表(今后它用于存储生成的节点),开始它只含有初始节点S。步骤2CLOSED←();建立一个CLOSED表(今后它用于存储已扩展节点或将要扩展的某个节点),它的初始状态为空表。步骤3LOOP:ifOPEN=()thenreturnFAIL;进入循环。如果OPEN表已空,说明没有节点可扩展,就返回FAIL,即失败。步骤4n←FIRST(OPEN),CLOSED←(n,CLOSED);从OPEN表中取出一个节点n,将其放入CLOSED表中。3.3图搜索算法3.3.1一般3.3图搜索算法3.3.2典型的非启发式图搜索算法分析与改进广度优先搜索法

该方法从初始节点开始,序扩展生成下一级各子节点,OPEN表中已有的节点后面(实现先生成的子节点先扩展),然后从OPEN表中提取最前的一个节点检查是否是目标节点,否则再扩展,再重复上述操作。这种方法认为同一级各节点对问题求解的价值是同等的,因而对全部节点沿广度进行横向扫描,按各节点生成的先后次序,先生成、先检查、先扩展,沿广度遍历所有节点。这种方法只要问题有解,即若树图上存在目标节点,经搜索一定能找到。所以,广度优先搜索法是完备的,是一种推理算法。但是,在问题大节点多,且目标节点距离初始节点较远时将会产生许多无用节点,搜索效率低,还可能产生组合爆炸。因此,这种方法较适宜问题不大的环境中3.3图搜索算法3.3.2典型的非启发3.3图搜索算法3.3.2典型的非启发式图搜索算法分析与改进深度优先搜索法

该方法从初始节点开始,顺序扩展生成下一级各子节点,放在OPEN表中已有的节点前面(实现后生成的子节点先扩展),然后从OPEN表中提取最前的一个节点检查是否是目标节点,否则再扩展,再重复上述操作。这种方法每一次扩展最晚生成的子节点,沿着最晚生成的子节点分支,逐级纵向深入发展。这种方法搜索一旦进入某个分支,就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上,则可较快地得到解。但是,如果目标节点不在此分支上,不回溯就不可能得到解。所以,深度优先搜索是不完备的,只是推理步骤。如果回溯,不难证明其平均效率与广度优先搜索法相同。因此,深度优先搜索法如果没有启发信息,很难有实用价值。3.3图搜索算法3.3.2典型的非启发3.3图搜索算法3.3.2典型的非启发式图搜索算法分析与改进代价驱动搜索法

该方法考虑了从一个节点经过一条支路,转移到另一个节点时所需要支付的代价,如费用、时间等。该方法从初始节点开始,扩展生成下一级各子节点,这些子节点中若没有目标节点需再扩展搜索。把它们放进OPEN表中,依据初始节点到它们各自所付出的代价大小进行排序,代价小的节点放在前面扩展,周而复始重复上述操作,直至找到目标节点为止。这种方法根据各条支路所需支付的代价有差别,所以具有同样路径长度(所经过的支路数)的搜索过程,其搜索代价(所支付的总代价)可能不同,优选最小代价的搜索路径,进行推理求解问题。代价驱动搜索无论在理论研究方面还是实际应用方面都很有前景,例如最短路径问题。进一步的研究认为最短路径问题的改进应为以下几点:3.3图搜索算法3.3.2典型的非启发3.3图搜索算法

3.3.2典型的非启发式图搜索算法分析与改进代价驱动搜索法1)OPEN表的节点排序问题,特别是在问题节点多达成千上万时尤为重要.这一排序应采用映射排序，它是一个基于地址计算的排序,在预置路径最大代价dmax后,开辟一个数组P(dmax),就可把节点送入其值与P数组下标相等的对应元素中,显然di=50它对应P(50);dj=500,对应P(500)。相同代价值的节点落在同一数组元素中,用计数方式可知有几个。由于数组元素是有序的,500>50,数组元素的下标自然把节点一次定好了位置,排序即完成。这一排序的时间复杂性为O(N),对于OPEN表面临的无数次排序操作,极大的提高了效率.2)搜索过程中,如果到达某一节点的代价≥任一初始节点到目标节点的路径代价,这一节点的路径删去。3)搜索过程中,如果同时出现了两条到达某一节点的路径,代价大的那条路径即时删去。3.3图搜索算法3.3.2典型的非启发式图3.3图搜索算法

3.3.3典型的启发式搜索算法分析与改进

搜索过程中,如果在确定扩展那一个节点时能充分利用与问题求解有关的特性信息,就可以估计出节点的重要性,就能使搜索选择重要性较高的节点,以利于求得最优解。象这样就可用于指导搜索过程,且与具体问题求解有关的控制性信息称为启发性信息。启发性信息可以用于估价节点重要性,表示为函数形式:f(x)=g(x)+h(x)其中,g(x)为初始节点S。到节点x已经付出的代价;h(x)是从节点x到目标节点Sg的最优路径的估计代价,它体现了问题的启发性信息,其形式根据问题的特性确定。3.3图搜索算法3.3.33.3图搜索算法3.3.3典型的启发式搜索算法分析与改进A*算法如果对一般性图搜索算法作以下限制,则它成为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)是从节点x到目标节点的最小代价,若有多个目标节点,则为其中最小的一个。3.3图搜索算法3.3.33.3图搜索算法3.3.3典型的启发式搜索算法分析与改进

A*算法几个重要性质:性质1对于有限图,A*算法一定会在有限步内终止.证明：对于有限图,其节点个数是有限的,A*算法在经过若干次循环后会出现两种情况:或者搜索到目标节点在步骤5结束;或者OPEN表中的节点被取完在步骤3结束。不管那种情况,A*算法都在有限步内终止。3.3图搜索算法3.3.33.3图搜索算法3.3.3典型的启发式搜索算法分析与改进A*算法几个重要性质:性质2对于无限图,只要从初始节点到目标节点有路径存在,A*算法也必然终止。证明:分两步.第一步证明A*算法结束前,OPEN表中存在节点x‘,它是最优路径上的一个节点,且满足f(x')≤f*(s).。设最优路径是S。x1,x2,…,S*g由于A*算法中的h(x)满足h(x)≤h*(x)所以f(s0),f(x1),f(x2),…,f(xm)均不大于f(sg*)=f*(s0).又因为A*算法是广度代价择优,所以在它结束之前,OPEN表中一定含有S。x1,x2,…,S*g中的一些节点,设x'是其中最前面的一个,则它必然满足f(x')≤f*(S0)至此,第一步证明结束;3.3图搜索算法3.3.33.3图搜索算法3.3.3典型的启发式搜索算法分析与改进A*算法几个重要性质:性质2对于无限图,只要从初始节点到目标节点有路径存在,A*算法也必然终止。第二步证明：用反证法,假设A*算法不终止,并设e是图中各条边的最小代价,d*(xn)是从S。到节点xn的最短路径长度,则显然有g*(xn)≥d*(xn)×e又因为g(xn)≥g*(xn)所以有g(xn)≥d*(xn)×e再因h(xn)≥0,f(xn)≥g(xn)故得到f(xn)≥d*(xn)×e由于A*算法不终止,随着搜索的进行,d*(xn)会无限增大,从而使f(xn)也无限增大。这与第一步证明得出的结论矛盾,因对可解状态空间来说,f*(s0)一定是有限值。所以,只要从初始节点到目标节点有路径存在,即使对于无限图,A*算法也一定会终止。3.3图搜索算法3.3.33.3图搜索算法3.3.3典型的启发式搜索算法分析与改进

A*算法几个重要性质:

性质3A*算法一定终止在最佳路径上证明:假设A*算法不是在最优路径上终止,而是在某个目标节点t处终止,则f(t)=g(t)>f*(s0)。但是由性质2证明可知,在A*算法结束之前,OPEN表中存在着节点x‘,它应该在最优路径上,且满足f(x')≤f*(s0)此时,A*算法一定会选择x'来扩展而不会选择t,这就与假设矛盾,所以,A*算法一定会终止在最优路径上。3.3图搜索算法3.3.33.3图搜索算法3.3.3典型的启发式搜索算法分析与改进

A*算法几个重要性质:性质4A*算法是最优的证明:A*算法的搜索效率很大程度上取决h(x),在满足h(x)≤h*(x)的前提下,h(x)的值越大越好。h(x)值越大,表明它携带的启发信息越多,搜索时扩展的节点数越少,搜索的效率越高。设f1(x)与f2(x)是对同一问题的两个估价函数f1(x)=g1(x)+h1(x)f2(x)=g2(x)+h2(x)A1*和A2*分别是以f1(x)及f2(x)为估价函数的A*算法,且对于所有的非目标节点x均有h1(x)<h2(x)。3.3图搜索算法3.3.33.3图搜索算法3.3.3典型的启发式搜索算法分析与改进A*算法几个重要性质:性质4A*算法是最优的证明（接前页):

此情况下证明A1*扩展的节点数不会比A*2扩展的节点数少,用归纳法:设K表示搜索树的深度当K=0时,结论显然成立;设当搜索树的深度为K-1时结论成立,即A*2扩展了的节点,A*1也扩展了;现仅证明A*2扩展的第K代的任一节点xk也被A*1扩展:3.3图搜索算法3.3.3典3.3图搜索算法3.3.3典型的启发式搜索算法分析与改进A*算法几个重要性质:性质4A*算法是最优的证明（接前页):由假设可知,A*2扩展的前K-1代节点A*1也都扩展了,因此A1*搜索树中有一条从初始节点S。到xk的路径,其费用不会比A*2搜索树从S。到xk的费用更大。即g1(xk)≤g2(xk)假设A*1不扩展节点xk,这表示A*1能找到另一个具有更小估价值的节点进行扩展并找到最优解,此时有f1(xk)≥f*(S0)即g1(xk)+h1(xk)≥f*(S0)应用关系式g1(xk)≤g2(xk)到上列不等式中,得h1(xk)≥f*(S0)-g2(xk),由于h2(xk)=f*(S0)-g2(xk),这就得到h1(xk)≥h2(xk)这与最初的假设h1(x)<h2(x)相矛盾证毕。3.3图搜索算法3.3.33.3图搜索算法

3.3.3典型的启发式搜索算法分析与改进

A*算法的改进改进1OPEN表中自始至终的排序,采用3.3.2.3节中介绍的映射方法。改进2h(x)单调限制:A*算法中,每当扩展一个节点时都要检查其子节点是否已在OPEN表或CLOSED表中,有时还需调整指向父节点的指针,这就增加了搜索代价。如果对启发函数h(x)单调限制,可减少检查和调整的工作量,从而提高搜索效率。3.3图搜索算法3.3.3典型3.3图搜索算法3.3.3典型的启发式搜索算法分析与改进

A*算法的改进所谓单调限制h(x)应满足两个条件:(1)h(Sg)=0(2)设xj是节点xi的任一子节点,则有h(xi)-h(xj)≤c(xi,xj)其中,Sg是目标节点;c(xi,xj)是节点xi到其子节点xj的边代价。若把上式改写h(xi)≤h(xj)+c(xi,xj),可看出节点xi到目标节点的估价不会超过xi到其子节点xj边代价加从xj到目标节点的估价。3.3图搜索算法3.3.3典型3.3图搜索算法3.3.3典型的启发式搜索算法分析与改进A*算法的改进

当A*算法的启发函数h(x)满足单调限制时,可得出以下两个结论:(1)若A*算法选择节点xn进行扩展,则g(xn)=g*(xn)(2)由A*算法所扩展的节点序列其f值是非递减的。这两个结论都是在h(x)满足单调限制时才成立.对于第2个结论,当h(x)不满足单调限制时,有可能某个要扩展的节点比以前扩展的节点具有较小的f值.3.3图搜索算法3.3.3典型3.3图搜索算法3.3.3典型的启发式搜索算法分析与改进A*算法的改进改进3引入感兴趣集的算法:这一改进的思路是这样的,问题求解时,人们往往知道最佳路径上有关节点的某些启发信息。例如,在求城市A到城市B的最佳路径时,人们往往凭自己的经验断定所要求的最佳路径必经城市C和城市H,这里我们称{C,H}是感兴趣集合。若知道感兴趣集且启发式搜索算法恰当地应用感兴趣集,则肯定可以改善算法的搜索效率。3.3图搜索算法3.3.3典型3.3图搜索算法3.3.3典型的启发式搜索算法分析与改进

A*算法的改进算法的改进使用OPEN1和OPEN2,CLOSED1和CLOSED2四个表,对任一节点x,若从s到节点x的当前路径中不含感兴趣集中的节点,则x放入OPEN1中;否则放入OPEN2中。选择节点扩展时,首先扩展OPEN2中的节点,因为OPEN2中含有感兴趣集中的节点,可能比OPEN1中的节点更有希望在最佳路径上,而且所扩展的节点数目总不会多于原算法。

3.3图搜索算法3.3.3典型3.3图搜索算法

3.3.3典型的启发式搜索算法分析与改进

讨论(1)启发式搜索算法在大问题中一般优于非启发式搜索算法,因此,有效地分析利用启发信息尤为重要。含有启发信息的评价函数可写成下列形式:f(x)=v·g(x)+w·h(x)其中,v、w为权系数且≥0.当w↑,强调启发信息,搜索过程沿最有希望的方向进行,效率肯定高,但降低了完备性;当v↑,强调历史信息,搜索过程沿横向扫描,有利于完备性,但降低了搜索效率。

3.3图搜索算法3.3.3典型3.3图搜索算法3.3.3典型的启发式搜索算法分析与改进

讨论(2)根据启发信息,可将复杂的、规模大的问题分解为简单的规模小的若干子问题。那么各子问题的搜索过程A1,A2,…,An是完备的,则搜索过程A也是完备的。A=A1∩A2∩…∩An根据启发信息,可将原始的问题进行同构或同态的等价变换,转换为若干等价问题。那么等价问题的搜索过程A1,A2,…,An是完备的,则搜索过程A也是完备的。A=A1∪A2∪…∪An.

3.3图搜索算法3.3.3典型3.3图搜索算法3.3.4AND/OR图搜索算法上节探讨的算法具有重要的意义。但对于复杂的问题,它们并不是唯一的途径,若利用它们直接求解往往还比较困难。AND/OR图算法是用于表示问题及其求解过程的又一种形式化方法。定义1AND图及AND图算法把一个复杂的问题分解成若干个较为简单的子问题,每个子问题又可继续分解为更为简单的子问题,重复此过程,直到不需要再分解或者不能再分解为止。这个分解图是与图,根据这个图对每个子问题分别求解,然后把这些解合并起来得到原问题解的过程是AND图算法。3.3图搜索算法3.3.4AN3.3图搜索算法3.3.4AND/OR图搜索算法定义2OR图及OR图算法把一个复杂问题利用同构或同态的等价变换,使之成为若干个较容易求解的新问题。这个变换图是OR图,根据这个图对新问题求解,当且仅当新问题有一个可解,就得到原问题的解的解过程是AO图算法。定义3可解节点在AND/OR图中,满足下列条件之一者为可解节点:(1)它是一个终止节点.(2)它是一个OR节点,且子节点中至少有一个是可解节点.(3)它是一个AND节点,且其子节点全部是可解节点。3.3图搜索算法3.3.4AN3.3图搜索算法3.3.4AND/OR图搜索算法定义4不可解节点定义3中三个条件全部不满足的节点称为不可解节点。下面分析AND/OR图AO*搜索算法,作一些改进探讨;探讨类比搜索方法.为此,我们首先给出AND/OR图的一般搜索过程:(1)把原始问题作为初始节点,并作为当前节点。(2)应用分解或等价变换算符对当前节点进行扩展。(3)为每个子节点设置指向父节点的指针。(4)选择合适的子节点作为当前节点,反复执行(2)和(3),直至找到可解节点或不可解节点为止。下班可解或不可解的搜索过程都是至上而下的。如果确定某个节点是可解节点,则不可解的后裔节点不再有用,可从搜索图中删去;同样,如果确定某个节点是不可解节点,则全部后裔节点都不在有用,也可从搜索图中删去。3.3图搜索算法3.3.4AN3.3图搜索算法3.3.5AO*搜索算法分析与改进定义定义5设AND/OR图G,则从节点n到一立即可解的叶节点集合N的一解图G'定义为:(1)G'是G的子图;(2)若节点n是集合N中的元素,则G'是由单一节点n组成的;(3)若节点n有一个指向节点{n1,n2,…,nk}的k-连接符,使得从每个后继节点ni到集合N有一个解图(i=1,2,…,k),则G'由节点n、k-连接符、节点{n1,n2,…,nk}以及从{n1,n2,…,nk}中的每个节点到集合N的解图组成。(4)否则,从节点n到集合N不存在解图。3.3图搜索算法3.3.5AO3.3图搜索算法3.3.5AO*搜索算法分析与改进定义定义6从AND/OR图任意节点n到一立即可解的叶节点集合N的解图耗散值k(n,N)可递归地定义为：(1)若节点n是集合N中的元素,则k(n,N)=0;(2)否则,节点n有一个通到解图中后继节点集合{n1,n2,…,ni}的连接符.令该连接符的耗散值为Cn,则k(n,N)=Cn+k(n1,N)+k(n2,N)+…+k(ni,N)3.3图搜索算法3.3.5AO3.3图搜索算法3.3.5AO*搜索算法分析与改进定义定义7AND/OR图求解中,从起始节点到一可解叶节点集合具有最小耗散值的一个解图称为最佳解图。令函数h*(n)表示从AND/OR图中的节点n到一可解的叶节点集合的最佳解图的耗散值;启发式估价函数h(n)是h*(n)的估计。定义8若启发式估价函数h满足单调限制,即对AND/OR图中任意节点n及其适用于n的任一k-连接符,有h(n)≤Ck+h(n1)+…+h(nk)其中,Ck为k-连接符的耗散值,n1,n2,…,nk是应用k-连接符于节点n所得的全部后继节点。3.3图搜索算法3.3.5AO3.3图搜索算法3.3.5AO*搜索算法分析与改进AO*算法A1:建立一个搜索图G,G:=s,计算q(s)=h(s),IFGOAL(s)THENM(s,SOLVED);开始时图G只包含s,耗散值估计为h(s),若s是终节点,则标记能解.A2:Untils已标记上SOLVED,do:A3:beginA4:G':=FIND(G);根据连接符标记(指针)找出一个待扩展的局部解图G'.A5:n:=G'中的任一非终节点;选一个非终节点作为当前节点.A6:EXPAND(n),生成子节点集{nj},G:=ADD({nj},G),计算q(nj)=h(nj),其中nj∈G,IFGOAL(nj)THENM(nj,SOLVED);把n的子节点添加到G中,对G中未出现的子节点计算耗散值,若有终节点则加能解标记.A7:S:={n};建立含n的单一节点集合S.A8:UntilS为空,do

3.3图搜索算法3.3.5AO3.3图搜索算法3.3.5AO*搜索算法分析与改进AO*算法(接前页)A9:beginA10:REMOVE(m,S),mc∈{S};这个m的子节点mc应不在S中.A11:(1)修改m的耗散值q(m):对m指向节点集{n1i,n2i,…,nki}的每一个连接符i分别计算qi,qi(m)=Ci+q(n1i)+…+q(nki),q(m):=minqi(m);对m个的i个连接符,取计算结果最小的那个耗散值为q(m).(2)加指针到minqi(m)的连接符上,或把指针修改到minqi(m)的连接符上,即原来指针与新确定的不一致时应删去.(3)IFM(nji,SOLVED)THENM(m,SOLVED);若该连接符的所有子节点都是能解的,则m也标上能解.A12:IFM(m,SOLVED)∨(q(m)≠q0(m))THENADD(ma,S);m能解或修正的耗散值与原先估算q0不同,则把m的所有先辈节点ma添加到S中.A13:endA14:end3.3图搜索算法3.3.5AO3.3图搜索算法

3.3.5AO*搜索算法分析与改进分析与改进算法AO*可以理解为两个主要运算:A1～A6,完成自上而下的图生成,通过有标记的连接符,寻找最好的局部解图,然后对其中一个非终节点进行扩展,并对其后继节点赋给耗散值;A7～A12,完成自下而上的耗散值修正、连接符标记和节点的能解标记。(1)耗散值的修正从刚被扩展的节点n开始,其修正耗散值q(n)取估计h*(n)的所有值中最小的一个,然后根据耗散值递归计算公式逐级向上修正先辈节点的耗散值,只有下层节点耗散值修正后,才可能影响上一层节点的耗散值,因此必须自底向上一直修正到初始节点。(2)在A6中扩展节点n时,若不存在后继节点(即限入死胡同),则可在A11中对m(即n)赋一个高的q值,这个高的q值会依次传递到s,使得含有节点n的子图具有高的q(s),从而排除了被当作后选局部解图的可能性。3.3图搜索算法3.3.5AO3.3图搜索算法3.3.5AO*搜索算法分析与改进分析与改进(3)A5中怎样选G'中的一个非终节点扩展值得研究:一般可以选一个最可能导致该局部解图耗散值发生较大变化的那个节点先扩展,因为选这个节点先扩展,会促使及时修改局部解图的标记。(4)与3.3.3.2节A算法类似,应让h(n)满足单调限制条件,这样,当h(n)≤h*(n)则AO*一定能找到最佳解图。当h(n)≡0时,AO*成宽度优先算法。(5)AO*中评价函数只考虑h(n)分量,计算g没有必要也不可能。其次由于k-连接符连接的有关子节点,对于父节点能解与否以及耗散值都有影响,因而不能象A算法那样优先扩展其中具有最小耗散值的节点。3.3图搜索算法3.3.5AO3.3图搜索算法3.3.6类比搜索方法探讨构思在AO*和A算法中,所使用的启发信息大多是人们依据具体领域问题靠经验总结得来的,启发信息获取十分困难,且精确性和可靠性也难以保证。此外,搜索算法一般执行一次性搜索,将同一问题的多次搜索视为彼此独立、毫无相关的过程。每次求解问题时,面临的都是全新的搜索图,即使求解的是相同问题,算法仍然从零开始,这显然与人类求解问题的方式不符。人类求解问题的一个重要特点,就是常常利用以前求解相同或相似问题的经验来指导新问题的求解。这实际上是一种类比学习机制,如果将这种机制引入搜索算法,则多次搜索被看成相互关联的过程,前面搜索积累的经验将有助于提高后面搜索的效率。即,利用类比获得与新问题相似的过去问题的求解过程,作为启发信息来指导新问题的求解,这样可以缩小搜索范围,降低问题求解的复杂性。也就是说,如果算法设计恰当,可以自动获得启发信息。3.3图搜索算法3.3.6类比3.3图搜索算法3.3.6类比搜索方法探讨方法探讨AO*、A及其它算法在问题的求解过程中利用与该问题相关的启发信息来帮助搜索,启发信息通常被用于三种情况:(1)帮助确定扩展节点。(2)在扩展节点的过程中,帮助决定产生后继节点。(3)在扩展节点的过程中,决定那些节点可从搜索树上删除。值得注意的是,启发信息是一种局部信息,只在搜索路径的每个节点上为选择操作提供参考。3.3图搜索算法3.3.6类比3.3图搜索算法3.3.6类比搜索方法探讨方法探讨类比搜索方法把类比推理技术与状态空间的启发式搜索相结合,实际上是对人类求解问题、积累经验和增加求解问题能力的一种模拟。要实现它,需要解决如下一些主要问题:(1)如何积累问题求解的经验,即在一个问题的求解过程中,需要记录那些有用信息。(2)如何定义和判断两个问题的求解情况是相似的,如何高效的进行检索。(3)如何有效地使用类比结论,即相似的过去问题的求解经验,作为特殊的启发信息指导新问题的求解。3.3图搜索算法3.3.6类比3.3图搜索算法3.3.6类比搜索方法探讨方法探讨

基于上述几点,需要建立一个类比的启发式搜索求解模型。它主要包括生成求解事例、检索及指导求解三个推理过程。类比搜索方法在每次求解一个新问题时,不是直接去搜索给定的状态空间,而是首先在求解事例库中检索,查找与该问题相似的过去问题的求解事例。若存在相似问题的求解事例,则以此作为启发信息,指导该问题的求解。具体地说,就是在新问题的求解过程中,对过去问题的求解事例中记录的成功搜索路径上每个操作的依据条件重新测试.如果依据条件仍满足,则算法根随成功的求解路径。否则,对原求解过程进行改写,形成的新问题求解过程作为一个新事例存储在事例库中,以便指导将来相似问题的求解。过去问题与新问题的相似性越高,求解过程需要的搜索就越少。在最理想的情况下,甚至不需要搜索。当没有检索到一个与新问题相似的过去问题的求解事例时,则使用A*或AO*等算法进行,并在获得解时将求解过程作为一个求解事例存储在事例库中。3.3图搜索算法3.3.6类比3.3图搜索算法3.3.6类比搜索方法探讨方法探讨系统最初使用时,由于事例库中缺少求解事例,只有使用A*或AO*等算法。随着求解次数的增加,求解事例将不断积累,类比的资料增多(启发信息增多),从而使求解问题的效率不断提高。由此可知,类比搜索方法的特点是:类比启发信息不仅包含了局部信息,而且提供了指导求解的搜索方向,这样就可以将一个庞大空间的搜索压缩为对一个或数个很小空间的搜索,极大地提高了求解效率。3.3图搜索算法3.3.6类比3.3图搜索算法3.3.7讨论用AND/OR图算法求解问题时,求解过程就是对一个隐含的AND/OR图进行搜索。初始数据库对应于AND/OR图的根节点,规则对应于k-连接符,结束条件的数据库对应于一组终节点集合,搜索算法的任务就是找到从初始节点到一组终节点集的一个解图。AND/OR图的启发式搜索算法AO*是通过评价函数f(n)=h(n)来引导搜索过程,适用于分解得到的子问题不存在相互作用的情况。若S→N集存在解图,当h(n)≤h*(n)且h(n)满足单调限制条件时,AO*算法一定能找到最佳解图,在这种情况下,AO*具有可采纳性。3.3图搜索算法3.3.7讨3.3图搜索算法3.3.7讨论

类比搜索方法实施的关键技术在于生成求解事例、相似性度量和检索、以及指导求解。生成求解事例就是积累问题的求解经验,其生成过程主要解决的问题是对于一个求解事例需要记录和保存问题求解过程中的那些特征信息,以及如何进行表示、抽取和存储这些信息。求解一个复杂问题时,经常面临庞大的搜索。大量被搜索的节点中,有成功的、也有失败的。为了给相似问题的求解提供有用信息,就要确定保存搜索过程中的哪些有用特征信息。显然,走两个极端最简单:第一是记下整个搜索过程;第二是只记问题的最终解。这两个极端都不圆满,具体地作法除了保留问题的最终解外,还应该记录有关选择这些操作的情境和依据条件。这是一个很有意义的研究课题。相似性的度量也是类比搜索方法的一个关键问题。相似程度越高,度量方法恰当,相似问题的检索俞易获得。关于这方面,目前还是主要根据新、老问题的特征和关系来确定它们之间的相似性。此外,还可设置相似度阀值，检索采用直接映射式方法。3.3图搜索算法3.3.7讨3.3图搜索算法3.3.7讨论指导求解是类比搜索方法的控制程序,主要考虑灵活的处理策略。一般要考虑以下几点:(1)当检索没有类比启发信息时,程序能转向常规搜索方法。(2)当检索到一个与新问题完全相似的过去问题的求解事例时,程序能直接转换解。(3)当检索到一个与新问题部分相似的过去问题的求解事例时,程序能提取相似部分解过程,还能组织部分搜索、衔接新的解过程。此外,应有裁剪过去问题多余解过程的功能。3.3图搜索算法3.3.7讨3.4产生式系统的规则问题3.4.1规则不一致原因及解决方法

规则集中存在的不一致是影响系统性能的重要因素之一。系统建立初期,由于规则集较小,内容也比较简单,设计人员能对每一条规则的条件和结论部分反复推敲和精心构造,这类问题容易防止。但随着时间的推移,新的规则不断加入,规则集合越来越大,内容也越来越丰富,这时规则间的相互影响和相互联系就随之变得复杂。在此情况下,规则的不一致就将自然产生,当然,对它的认识和解决也就显得很重要。3.4产生式系统的规则问题3.4.3.4产生式系统的规则问题3.4.1规则不一致原因及解决方法主要的不一致规则种类(1)循环规则:由数个规则的前提和结论形成一个循环链,最终由末尾规则的结果子句推出起始规则的前提部分;(2)冲突规则:两个规则的前提条件等价,但一个或多个结果子句有矛盾或者前提子句有矛盾而结论部分完全等价;也有可能由多条规则链形成冲突规则集;(3)冗余规则:两个规则的前提条件等价,一个或多个子结果子句也等价;(4)从属规则:两个规则有相同的结果,但其中一个包含有多余的约束条件。3.4产生式系统的规则问题3.4.3.4产生式系统的规则问题3.4.1规则不一致原因及解决方法不一致规则的检查解决方法(1)对于循环规则,可构造规则集的IF---THEN图,从起始规则的条件部分开始搜索,如果搜索过程中遇到的THEN部分已在前面出现,就可以中断搜索,规则集中包含的循环规则子集合需设计人员检查,解决;(2)对于冲突规则,构造IF---IF表,对规则集内有相同的IF规则子句构造规则树,形成推理图。同时建立THEN---THEN表用以判断是否有冲突规则出现。对相同IF部分的规则继续用它的各自THEN部分作为其它可以匹配的IF前提条件,递归地构造,如发现两个推理图上分别有节点在THEN---THEN表上是矛盾的,则检测出冲突规则,人工予以解决。(3)对冗余规则和从属规则的检查类似于冲突规则链的方法.不同之处是前者在推理图中的遍历是试图发现有THEN部分等价的两条规则。3.4产生式系统的规则问题3.4.3.4产生式系统的规则问题3.4.2规则排序算法排序算法原则依赖规则：如果Ri的结论部份包含有Rj的条件部份，则Rj是一个依赖规则，即Rj依赖规则Ri，或称Ri是一个被依赖规则。优先规则:如果Ri被Pi个其它规则所依赖次数pi越大,Ri被援引的可能性越大。静态规则排列：亦是在原文分析、原文译文转换、译文生成之前，对规则集中已有的规则按优先次序排列。动态规则排列：这相当于自学习能力，即某些句子分析、转换、生成时，会增加一条或几条规则。这些规则有可能还与未完成的其它语句有关。因此，在对其它语句和完成速度影晌不大的情况下，同时再排列规则称之为动态规则排列。3.4产生式系统的规则问题3.4.23.4产生式系统的规则问题3.4.2规则排序算法

排序算法原则映射排列：是一个基于地址计算的排序。例如，求出上述Pi(i=1，2,...，N）的最大值后，若开辟一个数组D（Pmax）,就可把数据送入数据值下标相等的对应元素中。显然Pi=50，对应D(50);Pj=500,对应D(500)。相同数据落在同一数组元素中，用计数方式可知有几个。由于数组元素是有序的，500>50，数组元素的下标自然把数据一次定好位置，最后只要按规定的方式调非零元秦，相同元素按计数值次数调动，排序即完成。枚举计数：如果规则Ri被规则Rj依赖(j=1，2,...,N)，则Pi=pi+1（Pi初值赋1)。显然，对于N条规则，每一条都将确定与其它规则的依赖关系并计算，这一过程称之为枚举计数。3.4产生式系统的规则问题3.4.23.4产生式系统的规则问题3.4.2规则排序算法

排序算法描述与分析静态算法（上）B1:[初始化]，有N条规则，置P1至PN皆为1。B2:〔对i循环〕对i=N，N—1，N-2，…，2执行B3;然后转B5。B3:〔对j循环〕对j=i-1，i-2，…，1执行B4;然后转B2。B4:〔寻求Ri被Rj依赖次数〕若Ri被Rj依赖，Pi←Pi＋1；否则转B3。B5:一遍扫描Pi（i=1，2,...，N)，求Pmax。3.4产生式系统的规则问题3.4.23.4产生式系统的规则问题3.4.2规则排序算法排序算法描述与分析静态算法（上）静态算法进行到这里，求出了任一规则Ri被依赖次数Pi。Pi对应于Ri，相当于Ri被依赖次数Pi。Pi对应Ri，相当于Ri的关键字。其中，很可能出现Pi=Pj(i≠j),这说明Ri和Rj被其它规则依赖的条数相同。怎样快速地按关键字Pi(i=1，2，...,N)大小把规则快速地排列起来，并满足动态需要，我们采用高效算法——映射排序算法初始按关键字值以映射关系作一次扫描，基本排定规则位置，Ri→Pi→D（Pi）。对相同关键字的处理，算法附加了三个数组空间：每一记录的链指针空间L（i），链首指针空间Q，链当前指针空间W。3.4产生式系统的规则问题3.4.23.4产生式系统的规则问题3.4.2规则排序算法排序算法描述与分析静