人工智能与机器翻译

人工智能与机器翻译主讲：杨宪泽——产生式系统及其搜索方法第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产生生式式系系统统产产生生式式系系统统的的基基本本算算法法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产产生式系统的的搜索(控制制)策略回回溯方法在问题求解过过程中,有有时会发现现应用一条不不合适的规则则会阻扰或拖拖延达到目标标的过程。在在这种情况下下,需要有有这样的控制制策略:先先试一试某一一条规则,如如果以后后发现这条规规则不合适,则允允许退回去,另选选一条规则来来试。回溯方方法不保留完完整的搜索树树结构,只只记住当当前工作的一一条路径,回回溯就就是对这条路路径进行修正正。使用回溯策略略首要的问题题要研究在什什么情况下应应该回溯,即即要确定定回溯条件的的问题。其次次就是如何利利用有用知识识进行规则排排序,以减减少回溯次数数。回溯应应发生在以下下三种情况:(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图搜搜索算法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,完完成成自自上上而而下下的的图图生生成成,通通过过有有标标记记的的连连接接符符,寻寻找找最最好好的的局局部部解解图图,然然后后对对其其中中一一个个非非终终节节点点进进行行扩扩展展,并并对对其其后后继继节节点点赋赋给给耗耗散散值值;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)与节节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图搜搜索算法类类比比搜索索方法法探讨讨方法探探讨类比搜搜索方方法把把类比比推理理技术术与状状态空空间的的启发发式搜搜索相相结合合,实实际上上是对对人类类求解解问问题、、积累累经验验和增增加求求解问问题能能力的的一种种模拟拟。要要实实现它它,需需要解解决如如下一一些主主要问问题:(1)如如何积积累问问题求求解的的经验验,即即在在一个个问题题的求求解过过程中中,需需要记记录那那些有有用信信息。。(2)如如何何定义义和判判断两两个问问题的的求解解情况况是相相似的的,如如何何高效效的进进行检检索。。(3)如如何何有效效地使使用类类比结结论,即即相相似的的过去去问题题的求求解经经验,作作为为特殊殊的启启发信信息指指导新新问题题的求求解。。3.3图图搜搜索算算法类类比比搜索索方法法探讨讨方法探探讨基于上上述几几点,需需要建建立一一个类类比的的启发发式搜搜索求求解模模型。。它它主主要包包括生生成求求解事事例、、检索索及指指导求求解三三个推推理过过程。。类比比搜索索方法法在每每次求求解一一个新新问题题时,不不是直直接去去搜索索给定定的状状态空空间,而而是首首先在在求解解事例例库中中检索索,查查找与与该问问题相相似的的过去去问题题的求求解事事例。。若若存在在相似似问题题的求求解事事例,则则以此此作为为启发发信息息,指指导导该问问题的的求解解。具具体体地说说,就就是是在新新问题题的求求解过过程中中,对对过去去问题题的求求解事事例中中记录录的成成功搜搜索路路径上上每个个操作作的依依据条条件重重新测测试.如如果依依据条条件仍仍满足足,则则算算法根根随成成功的的求解解路径径。否否则则,对对原原求解解过程程进行行改写写,形形成成的新新问题题求解解过程程作为为一个个新事事例存存储在在事例例库中中,以以便指指导将将来相相似问问题的的求解解。过过去去问题题与新新问题题的相相似性性越高高,求求解过过程需需要的的搜索索就越越少。。在在最理理想的的情况况下,甚甚至不不需要要搜索索。当当没没有检检索到到一个个与新新问题题相似似的过过去问问题的的求解解事例例时,则则使用用A*或AO*等算算法进进行,并并在获获得解解时将将求解解过程程作为为一个个求解解事事例存存储在在事例例库中中。3.3图图搜搜索算算法类类比比搜索索方法法探讨讨方法探探讨系统最最初使使用时时,由由于于事例例库中中缺少少求解解事例例,只只