【doc】启发式图搜索算法RA^＊的改进算法IRA^＊及IRA

【doc】启发式图搜索算法RA^＊的改进算法IRA^＊及IRA 启发式图搜索算法RA^,的改进算法IRA^ ,及IRA 991年3月计算机第3期 启发式图搜索算法RA的改进算法 IRA及IRA 王士同 (镇江船舶学院计算机系,镇江21zooz) IMPR0VEDALG0RITHMIRAANDIRA'FORHEURISTIC GRAPHSEARCHALG0RlTHMRA WangShitong (zfniShipbuildingtas~tute,z^tP2Izoo2) Abgtract:TcomparisonbetweentwoRAalgorithmsispresented.Byintroducing interestlngset,improvedal如rithmsIRAandIRA'forheuristicgraphsearchalgorithmRA' areproposed,andtheadmissibllofIRAiSproved.Fromtheviewpointofthenumber ofexpandedBodes.IRAobviouslybetterthanRA.Ifinterestingsetdoesn0cinvolvenod黜 whichareinthebestsolu~onpath,modifiedalgorithmIRA'ofIRAcanbeusedtofind女 bettersolmionpath -【"Words:Artlfitlaliatslliieaee.hmttrllti~graphnearela,|mtereQtlm|set8.#~ll[orltbnt 摘要:本文在文【1】基础上,对两种RA'算法进行7比较研究,通过引八感 兴趣集,给出了RA'算法的改进算法IRA'和IRA,并且 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 7IRA'算法的 可采纳性.从算法所扩展的蛄点数目这一角度来看,IRA算法日月显优于RA IRA, 算法.若感兴趣集并不包含最佳路径上的结点,则IRA'算法的变形—— 算法可用来手找一条较佳的求解路径. 关键饲:人工智能,启发宣圈提素,感兴赶集,算法. 一 ,引言 在人工智能领域中,研究启发式图搜索算法主要有两个目标:一个是根据搜索算法 的可采纳性寻找最佳路径;另一个则要使算法所扩展的结点数最小.M&6已经证明: 率课题受国家自热科学基金资助.本文t989年t月16日收到.作者舟绍见率刊第t期. 一 一 3期王士同:启发式圈搜索算法RA的改进算法IRA及IRA 从搜索算法所扩展的结点数目来看,则不存在一个最优的可采纳性搜索算法.在文[I】中 提出了随机产生式系统这一概念,并据此提出了对应的基于模T和模SEmi的启发式图搜索 算法RA以及推广的A牛算法.在RA算法中,路径的耗散值以模T来运算.文【I】证 明了当^;()?^矿()时,RA算法可采纳.在推广的A算法中,路径的耗散值以模 S来计算.文[I]证明了推广的A牛算法的可采纳性,即当^:()?()时,推广的A 算法可采纳.本文从算法所扩展的结点数目这一角度出发,重点研究RA算珐.按照本 文的思路可以得到有关推广的A算法的类似重要结论. 本文要研究的问题是:若已知最佳求解路径上的某些结点,且路径耗散值用T模度 量运算.试寻求一个算法求出其最佳求解路径.这个问题是新颖的.应该说,解决这个 问题是有实际意义的.这是因为在求解问题时,人们往往并不是对最佳路径一无所知,而 是通常知道最佳路径上有关结点的某些启发信息.譬如说,在求城市A到城市B的最佳 路径即最短路径时,人们往往凭自己的经验断定所要求的最佳路径必定经过城市C和城 市H,换句话说,城市C和城市H必在最佳路径上.这里我们称{城市C,城市H)是感 兴 趣集合.更一般地,感兴趣集(interestingset)是指存在一条最佳路径,该路径至少包 含该集合中某些节点集合.简记感兴趣集为Is.若知道感兴趣集且启发式图搜索算法恰 当地应用感兴趣集,则肯定可以改善算法的搜索效率.注意:感趣集Is本身也是求解 最佳求解路径时所知的启发信息,但它与启发式图搜索中的启发式估价函数有本质的不 同.启发式估价函数反映了对最佳路径耗散值的估计,而感兴趣集Is则反映了人们对最 佳路径结点组成的了解程度.不难看出,这种了解程度越多,则应用感兴趣集的启发式图 搜索算法越能有效地搜索出最佳路径.感兴趣集的确定跟人们对问题领域的了解程度以 及求解经验等有关系.本文所给出的算法IRA就是基于感兴趣集的随机产生式系统的 启发式图搜索算法,它是对算法RA的一种有效改进.按照Pearl的观点,可采纳性 搜索算法为寻找所有好的可选择求解路径而花费了过多的算法搜索时间.应用感兴趣 集,算法IRA可以剪除许多这样的求解路径.由于人们经验估计的偏差,感兴趣集Is 中并不一定包台有最佳路径上的结点.为了找到较佳的求解路径,本文还给出了基于感 兴趣集的启发式图搜索算法IRA.它是算法IRA的变形.运用它可以保证找到一条 较佳的求解路径. 为了叙述方便,将文中所使用的符号及其意义列表如下: ? c(珥,.) .() ^}(^) ^}(珥,) ^(n/i) ,?() f}(),}(),^}(,f) ,() lS tr() oPENt,OPEN2,OPEN CLOSED1,CLOSED2,CLO$ED 初始结点 从结点拼到结点的直接路径的耗散值 从f到的最佳路径的耗散值 从一到耳标结点的最佳路径的耗散值 从掰到的最佳路径的耗散值 从经过结点i到目标结点的最佳路径的耗散值 (聍'(),蚌.()) 是对}'(),}.(,),?(n/i)的估计 最佳路径的耗散值 患趣寨 从经过到达目标结点的路径耗散筐估计 麦 表 194计算机 hm^? h?^? 算法IRA对h的估计 算{击RA对h的估计 二,算法RA的比较研究 本节研究两个RA算法的比较定理. 定义I.对两个RA'算法RA.和RA:,称RA2比RA,有较多的信息,名RAt,RAz各 官所使用的启发式估价函数爵'()和^)满足:蝎(矗)>婿(忭). 定理1.若RA,和RA2是算法RA的两种形式,且RAz比RA的信息多,月?在任一 具有从初始结点到某一目标结点的路径图上,在搜索结束的地方,由RAz所扩展的每一 个结点也是由RA所扩展的结点,由此可知RA,所扩展的结点至少和R所扩展的结点 一 样多. 证明.对RA搜索树中结束处的结点深度用归纳法证明奉定理. (1)归纳基础.若RA:所扩展的搜索树中结点的深度为0,则RA一定也是这样. 但此时一,即是初始结点.若是目标结点,则两个算法都不必扩展任何结点.若 不是目标结点,则这两个算法均要扩展结点L (2)设RA扩展了R搜索树中由RA所扩展的深度为{或小于{的全部结点,现 在就来证明RA:搜索树中由RA所扩展的深度为+1的任意结点也必由RA,加以 扩展. 根据归纳法假设,RA2搜索树中的任一先辈结点都可由RA予以扩展,因此结点 是在RA搜索树中,而且在RA搜索树中有一条从初始结点到*的路径,其耗散值不 会比搜索树RAz中的从到的路径耗散值更小,即 g}()?g)(1) 假定RA,不能扩展由RA所扩展的结点在RA结束的地方,对RA来说结点 必须在OPEN表上,因为RA已扩展了的一个结点.由于RA没有扩展结点而在 最佳路径上结束,所以根据f}()?f;(),有: (聍'(),^}(.))?停) 根据式(1)有: (窖}(),^())?(窖;'(),())?)(2) 根据RA'算法,文【l】中的定理l可以叙述成如下结论:由算法RA'选来扩展的 任一结点,恒有fr()?f{(j).据此,我们有: (g),^())?,;0)(3) 由式(2),(3)得: 丁((),())?丁((),())(4) 根据式(4)及模丁的定义可知:至少在结点,^}()与^()必须一样大,这就 违反了RA比RA具毒更多信息的假设.因此RA.必扩展由R所扩展的结点. 根据结点的任意性知定理1是成立的. 及IRA 期王士同:启发式圈搜索算法RA'的改进算法IRA' 三,IRA'算法及其可采纳性证明 从本质上看,RA算法是从路径耗散值运甩模T来计算这一角度拓广了GRAPHSE— ARCH算法,且RA是可采纳的.为了有效地减少算法搜索的结点数目,必须在搜索 算法中有效地使用感兴趣集Is,为此我们对GRAPHSEARCH作了较大的修改,其结果 称之为IRA算法.设}(/)?(),感兴趣集IS一{,,'一,t)包含着从初始 结点j到目标结点的一个最佳路径上的某些结点.在IRA算法中使用了两个OPEN表 即OPENI,OPEN2,使用了两个CLOSED表即CLOSEDI,CLOSED2.对任一结点 ,若从至结点的当前路径中并不台有Is集中的结点(结点本身除外),则放入 OPEN1中;否则放入OPEN2中.容易看出,在选择结点扩展时,应首先扩展OPEN2 中的结点(IRA算法步骤(6)在(7)前面等),这是因为OPEN2表中含有Is集中的结点, 可能比OPEN1表中的结点更有希望在最佳路径上.把OPEN和CLOSED表各自分 成两个表并且各自采用不同的方法处理结点使得癌兴趣集Is的作用在本算法中得到了 充分体现.亦就是说,本算法不但有效地使用了启发式函数这一启发信息,而且也有效地 使用了癌兴趣集Is.从OPEN1表所扩展的那些不属于IS的结点放入CLOSEDI表 中,而属于OPEN2表或Is所扩展的结点放人CLOSED2表中.具体说来,IRA算法描 述如下: 1.置韧始结点至表OPEN1,OPEN2中;CLOSED1,CLOSED2表韧始为空;感趣集一札, it,…,,^' 圭失败退出. 2.若OPEN1与OPEN2表均为空表,娜本算{ 3.从OPENI或OPEN2表中选取出一个结点,使得()最小.若n属于OPENI表,则将 故人CLOSED1表中,否则将放人CLOSED2表中. ?.若是目标结点,蜀1j算法找到解并且成功退出. 5.扩展结点一(若无后继结点,则转2).对每个后继结点,计算 F々-(}(#),f(,)). 6.若属于集或选择于OPEN2表,则 (6.1)若有一个中间后继结点均不属于OPEN1,OPEN2,CLOSEDI,CLOSED2表,则置 )一 ,T(o,).--r(gg,蚌(一)) 将放人OPEN2表中. (6.2)若有一个中间后继结点属于OPEN1或OPEN2或CLOSED1或CLO~ED2表.刚 (6.2.I)若(?)>,则P(.)一 (6.2.2)IT(-,)(聍(.),坼(一.))? (6.2.)置.到OPEN~-表中.. 7.若不属于ls集且一是从OPEN1表中选取的,则 (7.1)若中间后继结点不属于OPENi,OPEN2,CLOSED1,CLOSED2表,匠9 聍(i)一 fT(j)+—P,MAXh~(?,q)) t 计算机 t 置f到OPENI表中. (7.2)若中间后继结点日?羼于OPEN1或CLOSEDI表,且(f)>g,则 聍(.)一 fT()r(g,MAXh~(/『j)) _ 置到OPENl表中. (7.3)若中间后继结点.属于OPEN2或CLOSED2表,且g()>,剐 聍(一)一 tr(一.>一T(,坼()) 置.到OPEN2表中. B.转步骤2. 定义2.对IRA算法,若感兴趣集Is中台有从初始结点到目标结点的一条最佳路 径上的某些结点,且^()?^(),则称IRA此时为IRA算法. 定理互IRA'算法结束前的任何时刻,存在着一个属于OPEN1或OPEN2表中 的结点,使得()?,0)., 证明.设(一.,???)是一个_从s到目标结点的最佳路径,且该路径上存在 某结点i?I8.设是该序列属于OPEN1或OPEN2表中的第一个结点,很显然有: ;()一g}奉() 1.设在OPEN1中.由于g;()一g()及模的定义,故有 ()一(;(),MAXh~(n/一))(i?IS) , ?(g(),^;(/i))(?ts) 又因^}(/i)?^(/0,故有: ()?((),矗(/)) 再因^(/i)一(^}唪(,),^()),故有 ()?((),((,),矗;())) 一 r(r(g(),^(,i)),^(i))(模定义) 不难看出,T(g(),^矿(,i))一(i)且在这条最佳路径上并且位于结 点后面,故有 ()?r(g(),^P()) 一 ,;()一垮0) 即,r()?,() 2.设属于OPEN2表,则()一(g;(),^}()).根据文【1]中的定理1容 易推知()?,0).综合上述讨论知本定理成立. 定理3.算法IRA是可采纳的. 证明.(1)首先证明IRA'算法一定会找到一个目标结点而结束. 从算法IRA可以看出,算法IRA'既可以在第2步由于用完OPEN1和OPEN2 表而结束,也可以在第4步因找到目标而结束.但若有一条从初始结点到一个目标结 点的路径,结束前OPEN1或OPEN2表永远不至于都空.根据定理2及其证明过程可 知,将总有一个结点在OPEN1或OPEN2表上,且在最佳路径上,因此,IRA?算法 3期王士同:启发式图搜索算法RA'的改进算法IRA及IRA 一 定会找到一个目标结点而结束. (2)再证明IRA'只能由于找到一个通向目标结点的最佳路径而结束. 假设IRA'未找到一条最佳路径而在某一个目标结点}结束,即f)一;.)< f().但由定理2及其证明过程知,结束前刚好在OPEN1或OPEN2上存在一个结点 ,且()?)>0)在一条最佳路径上,因此在此步,无论f是在OPENI表还 是在OPEN2表上,IRA算法将选扩展而不选l,这说明与假设IRA'已结束矛盾. 综台上述讨论知本定理成立. 定理4.算法IRA所扩展的结点数目总不会比RA多, 证明. . f^;(,)若在OPEN1中 ^.一1^}()若在OPEN2中 hR^I一^}() 根据IRA算法假设^}(/)?^()有:hiR^??h.根据定理I易知本定理成 立(注意定理1成立的条件是h-7'()>(),但这不影响本定理的成立). 定理3,4揭示了IRA*算法不仅是可采纳的,而且从所扩展的结点数目来看,算法 . IRA比算法RA'优越 四,IRA'算法 有时侯,感兴趣集Ig并不一定包含有从初始结点到目标结点最佳路径上的某些结 点.例如寻找一条从城市B到城市E的最佳即最短路径,人们在求解前可能断定城市F 必在最佳路径上.但事实上最佳路径上并不包含城市F.这个例子说明人们的经验有时 会发生偏差的.同时人们亦不一定要找到最佳求解路径,而只要找到较为满意的即较佳 路径即可.此时只要对IRA算法稍加修改,就可以得到IRA~算法.IRA算法可以保 证找到一条从结点到目标结点的满足求解要求的较佳求解路径.IRA'算法可通过更 改lRA算法的第7步而得到: (7.1)若中间后继结点并不属于OPENI,OPEN2,CLOSED1,CLOSED2表,则置 }}()一P 若M^x}(/?j)?(}(),),其中E【0,1],则 fT(~O,-T(,MAx(,)), 且置到OPEN1表;否则置 .)一f,(')) 且置刊OPEN2表 定理5.没^}()?(),则IRA算法结束前的任何时刻,存在着一个属于 OPEN1或OPEN2表中的结点?,使得()?T(ft(s),d),d?【0,l】. 证明.选取一个从初始结点s到目标结点的最佳求解路径.设是该路径上的羼 于OPEN1或OPEN2表中的第一个结点,显然有:()一(). (1)设在OPENl表中. 计算机 因MAx时(./ii)?(^}(i),d)且d?【O,1】,故有:r (窖),MAx再;(/))?(g(),r(五;(),) f 即()?(量(),(^(),)) 一 T(T(g(),^()),d) 一 T(,(),d) 一 T(,(),d) (2)设在OPEN2表中.根据文[1]中的定理1很容易推得:/T()?,(,).根 据模的性质有1 ()?,{0)一((),1)?TO芋(f),) 综合上述讨论可知本定理成立. 定理6.算法IRA'绝不会找到这样的一条求解路径,其路径耗散值小于(,{(),d), 如果艟()?^(),且d?【0,l】. 证明.证阴过程类似于定理3,故略. 定理6揭示了IRA'算法总可以找到一条较佳求解路径,较佳程度一般取决于(E [0,1】)的选择. 五,结束语 本文讨论了两个RA'算法之比较,提出了具有较多启发式信息的启发式图搜索算法 RA',则其所扩展的结点数目较少.IRA'算法是基于随机产生式系统的.从本质上看. 它是RA算法的一种基于感兴趣集为另一种启发信息的改进算法.IRA算法不但 是可 采纳的,而且算法所扩展的结点数目总不会比RA'算法多.在客观的现实世界中,也 由 于感兴趣集并不一定包含最佳路径上的结点,寻找一个较佳的求解路径是很有意 义的. IRA'算法的变形——IRA,算法可用来寻找一个较佳的求解路径.IRA',IRA"算法是 建立在随机产生式系统上的两个启发式图搜索算法.应该说,本文的工作在改善 RA'算 法的性能方面散了有益的尝试,其思想方法亦可以类.1El地用于[1】中的推广的 A'算法 参考文献 【1】王士同,虢机产生式系统的启发式圈搜索算法RA及A'的推广,计算 机,ll:5(1988). [2]王士 同,ImprovedAlgorithmIRA'andIRAForHeuristicGrsphSesrchAlgorithmRA.,Pro~. cfIMYCS.1988.l1. [3]N.J?Niluon,PrinciplesofArtificialImelligence.TiogsPublishingCo.1980. [4】 J.Pearl,Heuristic.IntelligentSearchStrategiesforComputerProblemSolviag.Addison-We lsey. PublishingCo.1984. 【5]张文修,模糊数学基础,西安交通太学出版社,1984. [6]L.MerAHeuristicSeaiehAIgorlthmwithModifiableEttlmste.ztrtiJi~iuilnttllig#nce. (1984).