人工智能与机器翻译

人工智能与机器翻译主讲：杨宪泽——产生式系统及其搜索方法第3章章产产生式式系统及及其搜索索方法3.1产生式系系统3.2产生式系系统的搜搜索(控制)策略3.3图搜索算算法3.4产生式系系统的规规则问题题3.5应用举例例3.6产生式系系统的不不确定性性问题3.7系统设计计技巧3.1产产生式式系统产生式系系统使用用类似于于文法的的规则,,对对符符号串作作替换运运算。它它是智智能软件件中使用用最普遍遍、最典典型的一一种结构构。为什什么要采采用产生生式系统统作为智智能软件件的主要要结构呢呢?这这可以以有两点理由由:(1)用用产生式式系统结结构求解解问题的的过程和和人类求求解问题题时的思思维过程程很相象象,因因而而可以用用它来模模拟人类类求解问问题时的的思维过过程;(2)可可以把把产生式式系统作作为智能能软件中中的基本本结构单单元或基基本模式式看待,,就就好象是是积木木世界中中的积木木块一样样,因因而研究究产生式式系统的的基本问问题就具具有一般般意义。。3.1产产生式式系统3.1..1产产生式式系统的的组成部部分一个智能能软件用用产生式式系统设设计的基基本组成成是:一个综合合数据库库;一一组组产生式式规则;;一一个个控制系系统。综合数据据库是产产生式系系统所使使用的主主要数据据结构,,用来来表述问问题的状状态或有有关事实实。它它包含求求解问题题的信息息,其其中中有些部部分可以以是不变变的,有有些些部分可可能只与与当前问问题的解解有关。。人们可可以根据据问题的的性质,,用适适当的方方法来构构造综合合数据库库的信息息。3.1产产生式式系统3.1..1产产生式式系统的的组成部部分产生式规规则的一一般形式式为:条件─→→行动或或前前提─→→结论即表示成成为:if┄┄┄then┄┄┄的的形形式。其中,左左边确确定了该该规则可可应用的的先决条条件;右右边边描述了了应用这这条规则则所采取取的行动动或得出出的结论论。一条条产生式式规则满满足了应应用的先先决条件件之后,,就就可对综综合数据据库进行行操作,,使其其发生变变化。如如综合数数据库代代表当前前状态,,则则应用用规则后后就使状状态发生生转换,,生生成新状状态。3.1产产生式式系统3.1..1产产生式式系统的的组成部部分控制系统统是软件件的控制制程序,,也是是规则的的解释((推理))程序。。它规规定了如如何选择择一条可可应用用的规则则对数据据库进行行操作,,即确确定了求求解过程程的推理理路线。。当数数据库满满足结束束条件时时,系系统就就应停止止运行;;还还要使使系统在在求解过过程中记记住应用用过的规规则序列列,以以便最最终能给给出解的的路径。。控制系统统也称控控制策略略,它它也也可以是是从规则则集中选选择规则则并作用用于状态态的一种种广义选选取函数数。确定定某一种种策略后后,可可以以算法的的形式给给出。在在建立产产生式系系统描述述时,还还要要给出初初始状态态和目标标条件,,具具体说说明所求求解的问问题。产产生式式系统中中控制策策略的作作用就是是从初始始状态出出发,寻寻求求一个满满足一定定条件的的问题状状态。目目标条条件也是是产生式式系统结结束条件件的基础础。3.1产产生式式系统3.1..1产产生式式系统的的组成部部分上述产生生式系统统的定义义具有一一般性,,它它可用用来模拟拟任一可可计算过过程。在在研究究人类进进行问题题求解过过程时,,完完全可可用一个个产生式式系统来来模拟求求解过程程,及及可作作为描述述搜索的的一种有有效方法法。作为为智能中中的一种种形式体体系,它它还具具有以下下优点::(1)适适合于于模拟强强数据驱驱动特点点的智能能行为。。当一些些新的数数据数入入时,系系统统的行为为就要改改变;(2)易易于于添加新新规则去去适应新新的情况况,而而不破坏坏系统的的其他部部分。这这是由由于产生生式系统统的各组组成部分分具有相相对的独独立性,,因因而便便于扩展展和修改改。3.1产产生式式系统3.1..1产产生式式系统的的组成部部分用产生式式系统来来求解问问题,首首先必须须建立起起问题的的产生式式系统描描述,即即规定定出数据据库、规规则集合合及其控控制策略略。这种种把一个个问题的的叙述转转化为产产生式系系统的三三个组成成部分,,在在智智能技术术中通常常称为问问题的表表示。一一般来说说一个问问题可有有多种表表示方式式,而而选择择一种较较好的表表示是运运用智能能技术解解决实际际问题首首先要考考虑的,,而且且要有一一定的技技巧。建立了产产生式系系统描述述之后,,通通过控控制策略略,可可求求得实现现目标的的一个规规则序列列,这这就是是所谓问问题的解解,这这个解解序列是是根据控控制系统统记住搜搜索目标标过程中中用过的的所有规规则而构构造出来来的。3.1产生式系系统3.1..1产产生式式系统的的组成部部分在一般情情况下,,问题题可能有有多个解解的序列列,但但有时时会要求求得到有有某些附附加约束束条件的的解,例例如要求求步数最最少、距距离最短短等。这这些约约束条件件通常是是用耗散散或代价价这一概概念来概概括,这这时问题题可称为为寻找具具有最小小耗散的的解。在用产生生式系统统求解问问题时,,有有时引引入状态态空间图图。状态态空间图图是一个个有向图图,其其节点可可表示问问题的各各种状态态(综合合数据库库),节节点之间间的弧线线代表一一些操作作(产生生式规则则),它它们可把把一种状状态导向向另一种种状态。。这样建建立起来来的状态态空间图图,描描述了了问题所所有可能能出现的的状态及及状态和和操作之之间的关关系,因因而可以以较直观观地看出出问题的的解路径径及其性性质。当当然,只只有问问题空间间规模较较小才可可能作出出状态空空间图。。3.1产生式系系统3.1..1产产生式式系统的的组成部部分建立产生生式系统统描述的的过程,,就就是所所谓问题题的表示示。对问问题表示示的好坏坏,往往往对对求解解过程的的效率有有很大的的影响。。一种较较好的表表示法会会简化状状态空间间和规则则集表示示,此此外外,高高效率率的问题题求解过过程与控控制策略略有关,,合合适的的控制策策略可缩缩小状态态空间的的搜索范范围,提提高高求解的的效率。。从以上论论述可知知,用用产产生式系系统来描描述和求求解问题题,就就是在在问题空空间中搜搜索一条条从初始始状态到到达某一一个目标标状态的的路径。。这完全全可以模模拟人的的求解过过程,也也就就是可以以把产生生式系统统作为求求解问题题思考过过程的一一种模拟拟。3.1产生式系系统3.1..2产产生式式系统的的基本算算法E1:DATA←初初始事实实库E2:untilDATA满满足结束束条件以以前,doE3:beginE4:在在规则则集中,,选某一一条可用用于DATA的的规则E5:DATA←规规则应用用到DATA得得到的结结果E6:结结束3.1产生式系系统3.1..3产产生式系系统的类类型正向、逆逆向、双双向产生生式系统统用产生式式系统求求解某一一问题时时,如如果按按照规则则使用的的方式或或者说按按推理方方向来划划分的话话,有有正正向、逆逆向和双双向产生生式系统统。正正向产生生式系统统是从初初始状态态出发朝朝着目标标状态这这个方向向使用规规则,即即正推的的方式工工作,称称这些规规则为F规则;;若若选选目标状状态作为为初始数数据库库逆向进进行求解解,即即逆向使使用规则则,产产生生子目标标状态,,反反方方向一步步一步朝朝着初始始状态方方向求解解,整整个逆逆推方式式工作,,称称逆逆向产生生式系统统,逆逆向应用用的规则则称B规规则;若若以双双向搜索索的方式式(即正正向和逆逆向同时时进行))去求解解问题,,则称称为双向向产生式式系统。。3.1产产生式式系统3.1..3产产生式系系统的类类型可交换的的产生式式系统可交换式式产生式式系统的的可交换换性指几几条规则则的应用用可以任任意交换换次序而而不影响响求解。。一般来说说,当当一一个产生生式系统统对任何何一个数数据库D都具有有如下性性质时,,这这样一一个产生生式系统统是可可交换的的。(1)可可应用于于D的规规则集合合,使使用用了其中中任意一一条规则则之后所所生成的的任何数数据库,,这这样一一个规则则集合还还适用;;(2)满满足目目标条件件的某个个数据库库D,当当应用任任何一个个可应用用于数据据库D的的规则则之后所所生成成的任何何数据库库,任任然满足足目标条条件;(3)若若对D应用某某一规则则序列后后得到的的一个数数据库D'(并并能达到到解),,当当改变这这些规则则次序后后,任任然然可求得得解,即即求得D'与使使用满足足D的可可应用规规则集合合中的规规则次序序无关。。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产产生式系系统的类类型可分解的的产生式式系统先研究一一个重写写问题的的产生式式系统,,初初始数据据库为((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产产生式系系统的类类型可分解的的产生式式系统用图搜索索方式求求解这个个问题时时,搜搜索得到到的部分分状态空空间图见见图26。图图中只给给出两条条达到目目标的路路径和一一条失败败的路径径。实际际搜索时时有可能能去探索索更多的的路径,,往往往往导致效效率降低低。对于个问问题,为为了避免免搜索多多余的路路径,,可可以将将初始数数据库分分解成几几个可以以独立加加以处理理的分量量,分分别对它它们进行行求解。。即即可以分分别对每每一个分分量数据据库,测测试产产生式规规则可以以应用的的条件,,如如此进进行下去去,直直到分量量数据库库满足某某种结束束条件为为止。要要注意意一般结结束条条件应是是所有分分量数据据库都已已满足结结束条件件。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))end下图为分分解方式式((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)图263.2产产生式系系统的搜搜索(控控制)策策略在3..1..2节节的算法法中,如如何何选择一一条可应应用的规规则,作作用用于当前前的综合合数据库库,生生成成新的的状态以以及记住住选用的的规则序序列是构构成控制制策略的的主要内内容。对对大多数数的智能能应用问问题,所所拥有的的控制策策略知识识或信息息并不足足以使每每次通过过算法E4时,,一一下子就就能选出出最合适适的一一条规则则来,因因而产生生式系统统还必须须把E4扩大成成搜索((推理))算法,,以以至于基基本算法法的每一一循环环中选一一条规则则试用,,最最终找找出某一一序列能能产生一一个满足足结束条条件的数数据库为为止。由由此可见见,高高效率的的控制策策略需要要有关被被求解问问题的足足够知识识,这这样才才能在搜搜索过程程减少少盲目性性,比比较快的的找到解解路径。。过去三十十多年中中,人人们研究究了许多多种搜索索算法,,归纳起起来主要要有两类类:一一类类是非启启发式式算法;;另一一类是启启发式算算法。非非启发发式算法法是按预预定的控控制策略略进行搜搜索,在在其其过程中中获得的的中间信信息不用用来改进进控制策策略。由由于搜搜索总是是按预先先规定的的路线进进行,没没有有考虑问问题本身身的特性性,所所以以不容易易选择到到最优的的搜索途途径,效效率率较低,,且且出现""组合爆爆炸"的的频率高高。启启发式算算法是在在搜索中中加入了了与问题题有关的的启发性性信息,,用用以指导导搜索朝朝着最有有希望的的方向前前进,加加速问问题的求求解过程程并找到到最优解解。3.2产产生生式系统统的搜索索(控制制)策略略3.2产产生生式系统统的搜索索(控制制)策略略3.2..1产产生式式系统控控制策略略分类可分解的的产生式式系统控制策略略可划分分为两大大类:┌不可撤撤回方法法┌┌回溯方方法└试探性性方法──┤┤└图搜索索方法3.2产产生生式系统统的搜索索(控制制)策略略3.2..2不不可撤撤回方法法这种方法法相当于于沿着单单独一条条路搜索索下去,,利利用问题题给出的的局部知知识决定定如何选选取规则则,就就是是说根据据当前可可靠的局局部知识识选一条条可应用用规则并并作用于于当前综综合数据据库。接接着再再根据新新状态继继续选取取规则,,搜搜索过程程一直进进行,不不必考考虑撤回回用过的的规则。。这是是由于在在搜索过过程中如如能有效效利用局局部知识识,即即使使使用了了一条不不理想的的规则,,也也不妨碍碍下一步步选得另另一条更更合适的的规则。。这样不不撤消用用过的规规则,并并不影响响求到解解,只只是解解序列中中可能多多了一些些不必要要的规则则。显然然这种策策略具有有控制简简单的优优点。3.2产产生生式系统统的搜索索(控制制)策略略3.2..2不不可撤撤回方法法爬山法不不仅适用用于爬山山问题,,那些些目标为为极大值值,搜搜索过过程是不不断接近近目标的的单值问问题都可可应用这这一方法法。使用用不可撤撤回策略略,虽虽然不不可能对对任何状状态总能能选得最最优的规规则,但但是如如果应用用了一条条不合适适的规则则之后,,不不去撤消消它并不不排除下下一步应应用一条条合适的的规则,,那么么只是解解序列有有些多余余的规则则而已,,求得得的解不不是最优优解,但但控制制较简单单。此外外还应当当指出,,一般般很难对对给定问问题构造造出任何何情况下下都能通通用的爬爬山函数数,因因而不不可撤撤回的方方法具有有一定的的局限性性。3.2产产生生式系统统的搜索索(控制制)策略略3.2..3回回溯方法法在问题求求解过程程中,有有时时会发现现应用一一条不合合适的规规则会阻阻扰或拖拖延达到到目标的的过程。。在这种种情况下下,需需要有这这样的控控制策略略:先先试一试试某一条条规则,,如如果以后后发现这这条规则则不合适适,则则允允许退回回去,另另选一条条规则来来试。回回溯方法法不保留留完整的的搜索树树结构,,只只记住住当前工工作的一一条路径径,回回溯溯就是对对这条路路径进行行修正。。使用回溯溯策略首首要的问问题要研研究在什什么情况况下应该该回溯,,即即要确定定回溯条条件的问问题。其其次就是是如何利利用有用用知识进进行规则则排序,,以减减少回溯溯次数。。回溯溯应发生生在以下下三种情情况:(1)新新生成的的状态在在通向初初始状态态的路径径上已出出现过;;(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.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..2典典型的的非启发发式图搜搜索算法法分析与与改进广度优先先搜索法法该方法从从初始节节点开始始,序序扩展展生成下下一级各各子节点点,OPEN表表中已有有的节点点后面面(实现现先生成成的子节节点先扩扩展),,然然后从从OPEN表表中提取取最前的的一个节节点检查查是否是是目标节节点,否否则则再扩展展,再再重复复上述操操作。这这种种方法认认为同一一级各节节点对问问题求解解的价值值是同等等的,因因而对全全部节点点沿广度度进行横横向扫描描,按按各各节点生生成的先先后次序序,先生生成、先先检查、、先扩展展,沿沿广度度遍历所所有节点点。这种方法法只要问问题有解解,即即若若树图上上存在目目标节点点,经经搜搜索一定定能找到到。所所以,广广度度优先搜搜索法是是完备的的,是是一种推推理算法法。但但是,在在问问题大节节点多,,且且目标节节点距离离初始节节点较远远时将会会产生许许多无用用节点,,搜索索效率低低,还还可能产产生组合合爆炸。。因此此,这这种方法法较适宜宜问题不不大的环环境中3.3图图搜索算算法3.3..2典典型的的非启发发式图搜搜索算法法分析与与改进深度优先先搜索法法该方法从从初始节节点开始始,顺顺序序扩展生生成下一一级各子子节点,,放在OPEN表中已已有的节节点前面面(实现现后生成成的子节节点先扩扩展),,然然后从从OPEN表表中提取取最前的的一个节节点检查查是否是是目标节节点,否否则再扩扩展,再再重复上上述操作作。这这种方法法每一次次扩展最最晚生成成的子节节点,沿沿着着最晚生生成的子子节点分分支,逐逐级纵向向深入发发展。这种方法法搜索一一旦进入入某个分分支,就就将沿沿着该分分支一直直向下搜搜索。如如果果目标节节点恰好好在此此分支上上,则则可较较快地得得到解。。但是是,如如果果目标节节点不在在此分支支上,,不不回溯就就不可能能得到解解。所所以,深深度优先先搜索是是不完备备的,只只是推推理步骤骤。如如果回溯溯,不不难证证明其平平均效效率与广广度优先先搜索法法相同。。因此此,深深度优先先搜索法法如果没没有启发发信息,,很很难有有实用价价值。3.3图图搜索算算法3.3..2典典型的的非启发发式图搜搜索算法法分析与与改进代价驱动动搜索法法该方法考考虑了从从一个节节点经过过一条支支路,转转移到另另一个节节点时所所需要支支付的代代价,如如费费用、时时间等。。该方方法从初初始节点点开始,,扩扩展生生成下一一级各子子节点,,这这些子节节点中若若没有目目标节点点需再扩扩展搜索索。把把它们放放进OPEN表表中,依依据初初始节点点到它们们各自所所付出的的代价大大小进进行排序序,代代价小的的节点放放在前面面扩展,,周而而复始重重复上述述操作,,直直至找到到目标节节点为止止。这种方法法根据各各条支路路所需支支付的代代价有差差别,所所以具有有同样路路径长度度(所所经过的的支路数数)的的搜索过过程,其其搜索索代价((所支付付的总代代价)可可能不同同,优优选最最小代价价的搜索索路径,,进进行推理理求解问问题。代代价驱驱动搜索索无论在在理论研研究方面面还是实实际应用用方面都都很有前前景,例例如最短短路径问问题。进进一步的的研究认认为最短短路径问问题的改改进应为为以下几几点: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..3典典型型的启发发式搜索索算法分分析与改改进搜索过程程中,如果在确确定扩展展那一个个节点时时能充分分利用与与问题求求解有关关的特性性信息,就可以估估计出节节点的重重要性,就能使搜搜索选择择重要性性较高的的节点,以利于求求得最优优解。象象这样样就可可用于指指导搜索索过程,且与具体体问题求求解有关关的控制制性信息息称为启启发性信信息。启启发发性信息息可以用用于估价价节点重重要性,表示为函函数形式式:f(x))=g((x)++h(x)其中,g((x)为初始节节点S。到节点x已经付出出的代价价;h(x)是从节点点x到目标节节点Sg的最优路路径的的估计代代价,它体现了了问题的的启发性性信息,其形式根根据问题题的特性性确定。。3.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..3典典型型的启发发式搜索索算法分分析与改改进A*算法法几个重重要性质质:性质1对对于有限限图,A*算算法一定定会在有有限步内内终止..证明：对对于于有限图图,其其节点个个数是有有限的,,A*算算法在在经过若若干次循循环后会会出现两两种情况况:或或者者搜索到到目标节节点在步步骤5结结束;或或者OPEN表表中的节节点被取取完在步步骤3结结束。不不管管那种种情况,,A*算法法都在有有限步内内终止。。3.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..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..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..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..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典典型型的启发发式搜索索算法分分析与改改进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..3典典型的的启发式式搜索算算法分析析与改进进A*算法法的改进进改进1OPEN表中自自始至终终的排序序,采采用3..3.2.3节节中介绍绍的映射射方法。。改进2h(x)单调调限制::A**算法中中,每每当扩扩展一个个节点时时都要检检查其子子节点是是否已在在OPEN表或或CLOSED表中,,有时时还需调调整指向向父节点点的指针针,这这就增加加了搜索索代价。。如果果对启发发函数h(x))单调限限制,可可减少少检查和和调整的的工作量量,从从而提高高搜索效效率。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典典型的的启发式式搜索算算法分析析与改进进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典典型的的启发式式搜索算算法分析析与改进进A*算法法的改进进改进3引引入感兴兴趣集的的算法::这一一改进的的思路是是这样的的,问问题求解解时,人人们们往往知知道最佳佳路径上上有关节节点的某某些启发发信息。。例如如,在在求城城市A到到城市B的最佳佳路径时时,人人们往往往凭自自己的经经验断定定所要求求的最佳佳路径必必经城市市C和城城市H,,这里里我们称称{C,,H}}是感感兴趣趣集合。。若知知道感兴兴趣集且且启发式式搜索算算法恰当当地应用用感兴趣趣集,则则肯肯定可以以改善算算法的搜搜索效率率。3.3图图搜索算算法3.3..3典典型的的启发式式搜索算算法分析析与改进进A*算法法的改进进算法的改改进使用用OPEN1和和OPEN2,,CLOSED1和和CLOSED2四个个表,对对任一一节点x,若若从s到到节点点x的当当前路径径中不含含感兴趣趣集中的的节点,,则x放入OPEN1中;;否则则放入OPEN2中。。选择择节点点扩展时时,首首先扩展展OPEN2中中的节点点,因因为OPEN2中含有有感兴趣趣集中的的节点,,可可能能比OPEN1中的节节点更有有希望在在最佳路路径上,,而且且所扩展展的节点点数目总总不会多多于原算算法。3.3图图搜索算算法3.3..3典典型的的启发式式搜索算算法分析析与改进进讨论(1)启发式搜搜索算法法在大问问题中一一般优于于非启发发式搜索索算法,,因因此,,有效效地分析析利用启启发信息息尤为重重要。含含有启启发信息息的评价价函数可可写成下下列形式式:f(x))=v··g(x)+w·h((x)其中,v、w为权系系数且≥≥0.当当w↑↑,强强调启发发信息,,搜索索过程沿沿最有希希望的方方向进行行,效效率率肯定高高,但但降低了了完备性性;当当v↑,,强调调历史信信息,搜搜索过过程沿横横向扫描描,有有利于完完备性性,但但降低了了搜索效效率。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..4AND/OR图搜索索算法上节探讨讨的算法法具有重重要的意意义。但但对于于复杂的的问题,,它们们并不是是唯一的的途径,,若若利用它它们直接接求解往往往还比比较困难难。AND//OR图图算法法是用于于表示问问题及其其求解过过程的又又一种种形式化化方法。。定义1AND图及AND图图算法把把一个个复杂的的问题分分解成若若干个较较为简单单的子问问题,每每个子问问题又可可继续分分解为更更为简单单的子问问题,重重复此此过程,,直直到不需需要再分分解或者者不能再再分解为为止。这这个分分解图是是与图,,根据据这个图图对每个个子问题题分别求求解,然然后后把这些些解合并并起来得得到原问问题解的的过程是是AND图算法法。3.3图图搜索算算法3.3..4AND/OR图搜索索算法定义2OR图及及OR图图算法把把一个个复杂问问题利用用同构或或同态的的等价变变换,,使使之成为为若干个个较容易易求解的的新问题题。这这个变换换图是OR图,,根根据这这个图对对新问题题求解,,当当且仅当当新问题题有一一个可解解,就就得到原原问题的的解的解解过程是是AO图图算法。。定义3可可解节点点在AND//OR图图中,满满足下下列条件件之一者者为可解解节点::(1)它它是一一个终止止节点..(2)它它是一一个OR节点,,且子子节点中中至少有有一个是是可解节节点.(3)它它是一一个AND节点点,且且其子节节点全部部是可解解节点。。3.3图图搜索算算法3.3..4AND/OR图搜索索算法定义4不不可解节节点定定义3中中三个条条件全部部不满足足的节点点称为不不可解节节点。下面分析析AND/OR图AO*搜索索算法,,作作一些改改进探讨讨;探探讨讨类比搜搜索方法法.为此此,我我们首先先给出AND//OR图图的一般般搜索过过程:(1)把把原始始问题作作为初始始节点,,并作作为当前前节点。。(2)应应用分分解或等等价变换换算符对对当前节节点进行行扩展。。(3)为为每个个子节点点设置指指向父节节点的指指针。(4)选选择合合适的子子节点作作为当前前节点,,反复复执行((2)和和(3)),直直至找找到可解解节点或或不可解解节点为为止。下班可解解或不可可解的搜搜索过程程都是至至上而下下的。如如果确确定某个个节点是是可解节节点,则则不不可解解的后裔裔节点不不再有用用,可可从搜索索图中删删去;同同样,,如果果确定某某个节点点是不可可解节点点,则则全全部后裔裔节点都都不在有有用,也也可从从搜索图图中删去去。3.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..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..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..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为为空,do3.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..5AO**搜索算算法分析析与改进进分析与改改进算法AO*可以以理解为为两个主主要运算算:A1～A6,完完成自自上而下下的图生生成,通通过有有标记的的连接接符,寻寻找最最好的局