人工智能与机器翻译.pptx
- 文档编号:15118988
- 上传时间:2023-06-30
- 格式:PPTX
- 页数:112
- 大小:680.81KB
人工智能与机器翻译.pptx
《人工智能与机器翻译.pptx》由会员分享,可在线阅读,更多相关《人工智能与机器翻译.pptx(112页珍藏版)》请在冰点文库上搜索。
人工智能与机器翻译,主讲:
杨宪泽,产生式系统及其搜索方法,第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产生式系统的组成部分产生式规则的一般形式为:
条件行动或前提结论即表示成为:
ifthen的形式。
其中,左边确定了该规则可应用的先决条件;右边描述了应用这条规则所采取的行动或得出的结论。
一条产生式规则满足了应用的先决条件之后,就可对综合数据库进行操作,使其发生变化。
如综合数据库代表当前状态,则应用规则后就使状态发生转换,生成新状态。
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:
ifa,b,cthena,b,c,abR2:
ifa,b,cthena,b,c,bcR3:
ifa,b,cthena,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)UntilDi的所有元素都满足结束条件之前,do:
(4)begin(5)从Di中选一个不满足结束条件的D*(6)从Di中删去D*(7)在规则集中选择一条可应用于D*的规则R(8)di:
=R应用于D*的结果(9)在Di上添加di(10)end,下图为分解方式(C,B,Z)初态R2R4R1(B,M,B,Z)(C,B,B,B,M)(D,L,B,Z)R3R2R3(M,M,M,B,Z)(B,M,B,B,B,M)(D,L,M,M,Z)R3R3R4(M,M,M,M,M,Z)(M,M,M,B,B,B,M)(D,L,M,M,B,B,M)R4R3R3(M,M,M,M,M,B,B,M)(D,L,M,M,M,B,M)R3R3(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.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:
记录新状态,对新状态递规调用YX1YX7;,产生式系统求解问题时,如果控制系统保留所有规则应用后生成并链接起来的状态记录图,则称工作在这种方式下的控制系统使用了图搜索策略。
实际上图搜索策略是实现从一个隐含图中,生成一部分确实含有一个目标节点的显式表示的子图搜索过程。
3.3图搜索算法,3.3图搜索算法,3.3.1一般性图搜索算法步骤1GS,OPEN(S);建立一个搜索图G,它只含有初始节点S,建立一个OPEN表(今后它用于存储生成的节点),开始它只含有初始节点S。
步骤2CLOSED();建立一个CLOSED表(今后它用于存储已扩展节点或将要扩展的某个节点),它的初始状态为空表。
步骤3LOOP:
ifOPEN=()thenreturnFAIL;进入循环。
如果OPEN表已空,说明没有节点可扩展,就返回FAIL,即失败。
步骤4nFIRST(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)。
相同代价值的节点落在同一数组元素中,用计数方式可知有几个。
由于数组元素是有序的,50050,数组元素的下标自然把节点一次定好了位置,排序即完成。
这一排序的时间复杂性为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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 机器翻译