人工智能与机器翻译

人工智能与机器翻译主讲：杨宪泽——产生式系统及其搜索方法第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产生式式系统统产产生生式系系统的的基本本算法法E1:DATA←←初始始事实实库E2:untilDATA满满足足结束束条件件以前前,doE3:beginE4:在在规则则集中中,选选某一一条可可用于于DATA的规规则E5:DATA←←规则则应用用到DATA得得到的的结果果E6:结结束3.1产生式式系统统产产生式式系统统的类类型正向、、逆向向、双双向产产生式式系统统用产生式式系统求求解某一一问题时时,如如果按按照规则则使用的的方式或或者说按按推理方方向来划划分的话话,有有正正向、逆逆向和双双向产生生式系统统。正正向产生生式系统统是从初初始状态态出发朝朝着目标标状态这这个方向向使用规规则,即即正推的的方式工工作,称称这些规规则为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产产生生式系统统的搜索索(控制制)策略略回回溯方法法在问题求求解过程程中,有有时时会发现现应用一一条不合合适的规规则会阻阻扰或拖拖延达到到目标的的过程。。在这种种情况下下,需需要有这这样的控控制策略略:先先试一试试某一条条规则,如如果以后后发现这这条规则则不合适适,则则允允许退回回去,另另选一条条规则来来试。回回溯方法法不保留留完整的的搜索树树结构,只只记住住当前工工作的一一条路径径,回回溯溯就是对对这条路路径进行行修正。。使用回溯溯策略首首要的问问题要研研究在什什么情况况下应该该回溯,即即要确定定回溯条条件的问问题。其其次就是是如何利利用有用用知识进进行规则则排序,以减减少回溯溯次数。。回溯溯应发生生在以下下三种情情况:(1)新新生成的的状态在在通向初初始状态态的路径径上已出出现过;(2)从从初始状状态开始始,应应用的规规则数目目达到所所规定的的数目之之后还未未找到目目标状态态(这一一组规则则的数目目实际上上就是搜搜索深度度范围所所规定的的);(3)对对当前前状态,再没没有可应应用的规规则。3.2产产生生式系统统的搜索索(控制制)策略略回回溯方法法搜索深度度的设置置是一个个值得注注意的问问题,设设置太太浅,有有可能找找不到解解;设设置置太深,有可可能导致致回溯次次数巨增增。因而而应根据据实际情情况来规规定搜索索范围,先先设置适适中的深深度搜索索,失失败时再再逐步加加深。回溯过程程是一种种可试探探的方法法,从从形形式上无无论是否否存在对对选择规规则有用用的知识识,都都可以以采用这这种策略略。即如如果没有有有用的的知识来来引导规规则选取取,那那么么规则可可按任意意方式(固定排排序或随随机)选选取;如如果有好好的选择择规则的的知识可可用,那那么用用这种知知识来引引导规则则选取,就就会减少少盲目性性,降降低回溯溯次数,甚至至不回溯溯就能找找到解,总总之一般般来说有有利于提提高效率率。此外外由于引引入回溯溯机理,可以以避免陷陷入局部部极大值值的情况况,继继续寻寻找其他他达到目目标的路路径。3.2产产生生式系统统的搜索索(控制制)策略略回回溯方法法可用递归归算法描描述回溯溯策略: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图图搜索算算法典典型的的非启发发式图搜搜索算法法分析与与改进广度优先先搜索法法该方法从从初始节节点开始始,序序扩展展生成下下一级各各子节点点,OPEN表表中已有有的节点点后面面(实现现先生成成的子节节点先扩扩展),然然后从从OPEN表表中提取取最前的的一个节节点检查查是否是是目标节节点,否否则则再扩展展,再再重复复上述操操作。这这种种方法认认为同一一级各节节点对问问题求解解的价值值是同等等的,因因而对全全部节点点沿广度度进行横横向扫描描,按按各各节点生生成的先先后次序序,先生生成、先先检查、、先扩展展,沿沿广度度遍历所所有节点点。这种方法法只要问问题有解解,即即若若树图上上存在目目标节点点,经经搜搜索一定定能找到到。所所以,广广度度优先搜搜索法是是完备的的,是是一种推推理算法法。但但是,在在问问题大节节点多,且且目标节节点距离离初始节节点较远远时将会会产生许许多无用用节点,搜索索效率低低,还还可能产产生组合合爆炸。。因此此,这这种方法法较适宜宜问题不不大的环环境中3.3图图搜索算算法典典型的的非启发发式图搜搜索算法法分析与与改进深度优先先搜索法法该方法从从初始节节点开始始,顺顺序序扩展生生成下一一级各子子节点,放在OPEN表中已已有的节节点前面面(实现现后生成成的子节节点先扩扩展),然然后从从OPEN表表中提取取最前的的一个节节点检查查是否是是目标节节点,否否则再扩扩展,再再重复上上述操作作。这这种方法法每一次次扩展最最晚生成成的子节节点,沿沿着着最晚生生成的子子节点分分支,逐逐级纵向向深入发发展。这种方法法搜索一一旦进入入某个分分支,就就将沿沿着该分分支一直直向下搜搜索。如如果果目标节节点恰好好在此此分支上上,则则可较较快地得得到解。。但是是,如如果果目标节节点不在在此分支支上,不不回溯就就不可能能得到解解。所所以,深深度优先先搜索是是不完备备的,只只是推推理步骤骤。如如果回溯溯,不不难证证明其平平均效效率与广广度优先先搜索法法相同。。因此此,深深度优先先搜索法法如果没没有启发发信息,很很难有有实用价价值。3.3图图搜索算算法典典型的的非启发发式图搜搜索算法法分析与与改进代价驱动动搜索法法该方法考考虑了从从一个节节点经过过一条支支路,转转移到另另一个节节点时所所需要支支付的代代价,如如费费用、时时间等。。该方方法从初初始节点点开始,扩扩展生生成下一一级各子子节点,这这些子节节点中若若没有目目标节点点需再扩扩展搜索索。把把它们放放进OPEN表表中,依依据初初始节点点到它们们各自所所付出的的代价大大小进进行排序序,代代价小的的节点放放在前面面扩展,周而而复始重重复上述述操作,直直至找到到目标节节点为止止。这种方法法根据各各条支路路所需支支付的代代价有差差别,所所以具有有同样路路径长度度(所所经过的的支路数数)的的搜索过过程,其其搜索索代价(所支付付的总代代价)可可能不同同,优优选最最小代价价的搜索索路径,进进行推理理求解问问题。代代价驱驱动搜索索无论在在理论研研究方面面还是实实际应用用方面都都很有前前景,例例如最短短路径问问题。进进一步的的研究认认为最短短路径问问题的改改进应为为以下几几点:3.3图图搜索算算法典典型的非非启发式式图搜索索算法分分析与改改进代价驱动动搜索法法1)OPEN表的的节点排排序问题题,特特别别是在问问题节点点多达成成千上万万时尤为为重要.这一排排序应采采用映射射排序，，它是是一个基基于地址址计算的的排序,在在预置置路径最最大代价价dmax后,开开辟一一个数组组P(dmax),就就可把节节点送入入其值与与P数组组下标相相等的对对应元素素中,显显然di=50它对应应P(50);dj=500,对对应应P(500)。相相同代价价值的节节点落在在同一数数组元素素中,用用计数方方式可可知有几几个。由由于数数组元素素是有序序的,500>50,数数组组元素的的下标自自然把节节点一次次定好了了位置,排排序即即完成。。这一一排序的的时间复复杂性为为O(N),对对于于OPEN表面面临的无无数次排排序操作作,极极大大的提高高了效率率.2)搜搜索索过程程中,如如果果到达达某一一节点点的代代价≥≥任一一初始始节点点到目目标节节点的的路径径代价价,这这一一节点点的路路径删删去。。3)搜搜索索过程程中,如如果同同时出出现了了两条条到达达某一一节点点的路路径,代价价大的的那条条路径径即时时删去去。3.3图图搜搜索算算法典典型的的启发发式搜搜索算算法分分析与与改进进搜索过过程中中,如如果在在确定定扩展展那一一个节节点时时能充充分利利用与与问题题求解解有关关的特特性信信息,就就可以以估计计出节节点的的重要要性,就就能能使搜搜索选选择重重要性性较高高的节节点,以以利利于求求得最最优解解。象象这这样就就可可用于于指导导搜索索过程程,且且与具具体问问题求求解有有关的的控制制性信信息称称为启启发性性信息息。启启发性性信息息可以以用于于估价价节点点重要要性,表表示示为函函数形形式:f(x)=g(x)+h(x)其中,g(x)为为初始始节点点S。。到节节点x已经经付出出的代代价;h(x)是是从节节点x到目目标节节点Sg的的最优优路路径的的估计计代价价,它它体体现了了问题题的启启发性性信息息,其其形形式根根据问问题的的特性性确定定。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图图搜搜索算算法典典型的的启发发式搜搜索算算法分分析与与改进进A*算算法几几个重重要性性质:性质1对对于有有限图图,A*算法法一定定会在在有限限步内内终止止.证明：：对对于于有限限图,其其节点点个数数是有有限的的,A*算算法在在经过过若干干次循循环后后会出出现两两种情情况:或或者搜搜索到到目标标节点点在步步骤5结束束;或或者者OPEN表中中的节节点被被取完完在步步骤3结束束。不不管管那种种情况况,A*算算法都都在有有限步步内终终止。。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图图搜搜索算算法典典型的的启发发式搜搜索算算法分分析与与改进进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图图搜搜索算算法典典型的的启发发式搜搜索算算法分分析与与改进进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表中自自始至终终的排序序,采节节中介绍绍的映射射方法。。改进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,完完成自上而下下的图生成,通过有标标记的连接接符,寻找找最好的局部部解图,然然后对其中一一个非终节点点进行扩展,并对其其后继节点赋赋给给耗散值;A7～A12,完成成自下而上的的耗散值修正正、连接符标标记和节点的的能解标记。。(1)耗散散值的修正从从刚被扩展的的节点n开始始,其修正正耗散值q(n)取估计计h*(n)的所有值值中最小的一一个,然后后根据耗散值值递归计算公公式逐级向上上修正先辈节节点的耗散值值,只有有下层节点耗耗散值修正后后,才可能能影响上一层层节点的耗散散值,因因此必须自底底向上一直修修正到初始始节点。(2)在在A6中扩扩展节点n时时,若若不存在后继继节点(即限限入死胡同),则则可在A11中对m(即即n)赋一一个高的q值值,这这个高的q值值会依次传递递到s,使使得含有有节点n的子子图具有高的的q(s),从而而排除了被当当作后选局部部解图的可能能性。3.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.6类类比搜搜索方法探讨讨构思在AO*和A算法中,所所使使用的启发信信息大多是人人们依据具体体领域问题靠靠经验总结得得来的,启启发发信息获取十十分困难,且且精精确性和可靠靠性也难以保保证。此外外,搜搜索算法一一般执行一次次性搜索,将将同同一问题的多多次搜索视为为彼此独立、、毫无相关的的过程。每每次求解问问题时,面面临的都都是全新的搜搜索图,即即使使求解的是相相同问题,算算法法仍然从零开开始,这这显然然与人类求解解问题的方式式不符。人人类求解问题题的一个重要要特点,就就是常常利利用以前求解解相同或相相似问题的经经验来指导新新问题的求解解。这实际际上是一种类类比学习机制制,如果果将这种机制制引入搜索算算法,则则多次次搜索被看成成相互关联的的过程,前前面搜搜索积累的经经验将有助于于提高后面面搜索的效率率。即,利利用用类比获得与与新问题相似似的过去问题题的求解过程程,作作为启发信信息来指导新新问题的求解解,这这样可以缩缩小搜索范围围,降降低问题求求解的复杂性性。也就是是说,如如果算算法设计恰当当,可以以自动获得启启发信息。3.3图搜搜索算法3.3.6类类比搜搜索方法探讨讨方法探讨AO*、A及及其它算法在在问题的求解解过程中利用用与该问题相相关的启发信信息来帮助搜搜索,启启发信息通通常被用于三三种情况:(1)帮帮助确定扩扩展节点。(2)在在扩展节节点的过程中中,帮助决决定产生后继继节点。(3)在在扩展节节点的过程中中,决定定那些节点可可从搜索树上上删除。值得得注意的是,启发信息息是一种局部部信息,只只在搜索索路径的每个个节点上为选选择操作提供供参考。3.3图搜搜索算法3.3.6类类比搜搜索方法探讨讨方法探讨类比搜索方法法把类比推理理技术与状态态空间的启发发式搜索相结结合,实实际上是对人人类求解问问题、积累经经验和增加求求解问题能力力的一种模拟拟。要实现现它,需需要解决如下下一些主要问问题:(1)如如何积累问问题求解的经经验,即在在一个问题的的求解过程中中,需要要记录那些有有用信息。(2)如如何定义义和判断两个个问题的求解解情况是相似似的,如何何高效的进行行检索。(3)如如何有效效地使用类比比结论,即即相似似的过去问题题的求解经验验,作为为特殊的启发发信息指导新新问题的求解解。3.3图搜搜索算法3.3.6类类比