A-算法估价函数的特性分析

18220066JournalofWuhanEngineeringInstiuteVol.18No.2June.2006A3(:430080)A3,,A3:TP183:A:167123524(2006)02200312031A3,(roleplaygame,RPG),RPG,A3,,A3,,,,,A3,,,A3,,2A3,nf(n):f(n)=g(n)+h(n)g(n)n,h(n)n(admissible),A3:n,h(n)=h’(n),h’(n)n,h(n)h(n)A3,Ah(n)h(n1)-h(n2)=c(n1,n2),c(n1,n2)n1n2,h(n),h,h,n1n2,f(n1)=g(n1)+h(n1)f(n2)=g(n2)+h(n2),g(n2)=g(n1)+c(n1,n2)f(n2)=h(n2)+g(n1)+c(n1,n2)h(n),h(n1)=h(n2)+c(n1,n2),g(n1),h(n1)+g(n1)=h(n2)+g(n1)+c(n1,n2),f(n1)=f(n2),,h(n),f(n)A3f,,closed,,:2006201202:,,(1971),,.3,,,:h(n),,h(n),h(n),A3AA,RPG,,h(n),h(n),h(n)h’(n),A3:h(n)0,A3,h(n)h’(n),h(n)=h’(n),,h(n),h(n),,(),,,A3,h(n),h(n),,,h(n),,,h(n)4,h(n),,,,:h=abs(x-endx)+abs(y-endy);(x,y)(endx,endy),,,W:h=abs(x-endx)+abs(y-endy);h=h3WW,810:dx=abs(x-endx),dy=abs(y-endy);if(dxdy)h=103dx+63dy;elseh=103dy+63dx;106,,,,,,,:h(nj)=(ni,nj)+W{D(s,t)d(ni,nj)},ni,nj,(ni,nj)ninj,d(ni,nj)ninj,D(s,t),W,,,,1:A3AK,2(a),h=abs(x-endx)+abs(y-endy)2(b):,(b)8,(a)6,,232006.25,A3,,A3,[1].A3[J].,2005,18(4)[2].A3[J].,2001,9(4)[3]Amit’sA3Pages[4].[M].:,1996[5].[M].:,1995DiscussionofDesigningCostFunctionofA3AlgorithmZhongMinAbstract:ItisakeyissuehowtodesigncostfunctionofA3algorithm.Inthispaper,thecharacteristicsofcostfunctionareanalyzed,severalprinciplesonitsdesigndiscussed.Inaddition,someexperimentalre2sultsandexamplesofcostfunctionareintroduced.Keywords:A3algorithm,costfunction,heuristicfunction,shortestpath(:)33:A3