人工智能与神经网络笔记3

LectureNotesonAI-NN,Chapter5InformationProcessinggotostep2.,Example:BFS,123,84,765,283,164,75,1=S,46=g,283,164,75,283,164,75,283,14,765,283,64,175,2,3,4,5,6,7,8,9,10,11,34,35,36,37,38,283,14,765,23,184,765,283,14,765,283,16,754,19,SeeNilssonp.71Fup.37,Theshortestsolutionpath,45,39,44,20,33,83,264,175,283,64,175,83,214,765,283,714,65,23,184,765,23,184,765,28,143,765,283,145,76,283,16,754,28,163,754,83,264,175,123,84,765,23,684,175,283,64,175,283,674,15,83,214,765,283,714,65,83,264,175,40,41,42,43,234,18,765,28,143,765,283,145,76,28,163,754,23,186,754,283,156,74,16,283,754,21,32,22,23,24,25,26,27,28,29,30,31,CommentsonBFS:Itisguaranteedtofindaoptimalsolutionbecauseofitssystematicsearchfeature.ThemajorweaknesswithBFSisitsinabilitytousetheinformationrelatedtotheproblemandthusa)Itrequiresalargememorytostorethegreatnumberofthenodes;b)Itrequireagreatamountofworktoexaminethegreatnumberofthenodesc)Asresult,BFShaslowefficiencyofsearch.,5-1-2DepthFirstSearch:NodeOrdering:LIFOProcedureDFS1.PutstartnodesonOPEN.Setd(s)=0,P=02.IfOPEN=NIL,F.3.SelectthefirstnodeonOPEN.PutitonCLOSED.Callitnoden.4.Ifn=g,S.5.Ifd(n)=d,gotostep2.6.Ifnisnotexpandable,gotostep2.7.Expandnoden,generatingallitssuccessors.Establishpointersfromthemton.Letd(successor)=d(n)+1.AddthemtothefrontonOPENinanyorder,thengotostep2.,B,Example:DFSd=5,283,184,765,283,164,75,1=S,283,164,75,283,164,75,283,14,765,283,64,175,2,3,4,5,6,7,8,9,10,11,283,14,765,23,765,283,714,765,283,14,765,SeeNilssonp.70Fup.42,Thesolutionpath,B,83,264,175,18,83,264,175,863,24,175,83,264,175,12,13,14,15,16,17,83,214,83,214,83,214,813,24,765,19,20,21,22,23,64,175,684,175,23,684,175,23,684,175,64,175,28,643,175,283,645,17,283,674,15,283,674,15,283,674,15,23,765,283,65,283,714,65,283,74,615,283,714,65,123,84,765,123,784,65,84,23,184,765,123,84,765,24,25,26,27,28,29,30,31,ComparedwithBFS,DFShasthefollowingfeatures:1)Ifdistoosmall,thegoalnodemaybemissed,iftoolarge,thegreateramountofstorageisneeded.2)DFSmayfindthegoalfasterthanBFS,whilethethesolutionpathmaynotbetheshortestoneiftherearemorethanonegoalnode.3)DFScanoftenbecarriedoutusingareasonablysmallamountofstorage.,B,g,g,5-1-3Informed(Heuristic)SearchonTree,(1)GeneralRemarks-Theweaknessinblindsearch:ignoringtheinformationassociatedwiththeprobleminselectingnodeforexpansionnext.-Solution:TrytousetheheuristicinformationinnodeorderingonOPEN-HeuristicSearch.-TheheuristicinformationisusedintermsofEvaluationFunction,f(.):f(n):nodenRealnumbermappingnodestotheirpromisingvalues.,Foranynodenonatree,letg*(n)betheactualcostofaminimalcostpathfromston.h*(n)bethecostofminimalcostpathfromntog.f*(n)=g*(n)+h*(n)bethecostofanoptimalpathfromstogconstrainedtogoingthroughn.Letagaingbeanestimationofg*,hbeanestimationofh*,andf(n)=g(n)+h(n)beanestimationoff*(n),whichcanbeusedasanevaluationfunctionfororderingnodesonOPEN.,Practically,g(n):thesumofthearccostsencounteredwhiletracingthepointersfromntos.h(n):afunctionbasedonheuristicinformationfromtheproblem,henceiscalledHeuristicFunction.ThepracticalregulationisIfh(n)isveryhigh,nodenmaybeignored;Ifh(n)islow,nodenmaybechosentoexpandnext.,(2)AlgorithmAandAlgorithmA*onTreeAlgorithmAisaspecialTree-Searchusingevaluationfunctionf(n)fororderingnodesonOPENandalwaysselectingforexpansionthenodewiththelowestvalueoff(n).ThekeyforAlgorithmAisthesettingsofhandg:Whenh=0,g=d,itreducestoBFS;h=0,g=0,randomsearch;h=1/d,g=0,DFS;hh*,theoptimalpathmaybelost;hh1(n)forallnon-goalnoden.,ExampleofA*:8-PuzzleProblemLetf(n)=g(n)+h(n)=d(n)+w(n)d(n):depthofnodenonsearchtreew(n):numberofmisplaceddigitsatnoden,283,184,283,164,75,283,164,75,164,75,283,14,765,283,14,765,765,283,765,283,14,765,83,184,214,23,23,765,714,65,123,84,765,123,784,65,84,23,184,765,123,84,765,1#,0+4=4,2#,3#,4#,6#,7#,8#,12#,13#,14#,15#,26#,27#,1+5=6,1+3=4,1+5=6,2+3=5,2+3=5,2+4=6,3+3=6,3+4=7,3+2=5,3+4=7,4+1=5,5+0=5,13outof27,AlgorithmA*withh(n)=w(n)ismoreinformedthanBFSwhichusesh(n)=0.h(n)=w(n)isalowerboundontheexactnumberofstepsneededtoreachthegoal,h*(n),henceitisanAlgorithmA*.However,w(n)doesnotprovidegood-enoughestimateofh*(n).Theinformationof“followingorder”isnotutilizedinw(n).,Abetterestimateofh*(n)ish(n)=P(n)+3S(n)P(n):thesumoftheabsolutedistancesthatadigitisfrom“home”;S(n):asequencescore,takingvalue2,foreachnon-centraldigitnotproperfollowed1,ifadigitinthecenter0,forotherdigitsE.g.,fors=andg=,wehave,216,48,753,123,84,765,P(s)=(3x1)+(3x2)+(1x3)+(1x0)=12(1,2,5)(3,4,8)(6)(7)S(s)=8x2=16,Byusingthish(n),wehavef(n)=g(n)+P(n)+3S(n)withg(n)=d(n)andtheaboveproblemwillfindthesameoptimalpathbutwithfewernodesexpanded:,283,184,283,164,75,283,164,75,164,75,283,14,765,283,14,765,765,283,14,765,184,23,23,765,123,84,765,123,784,65,84,23,184,765,123,84,765,11outof13,Since0w(n)h*(n)P(n)+3S(n),thesolutionpathfoundhappenstobeofminimalpath,althoughwewerenotguaranteedoffindinganoptimalpath.Summary:Fromtheexampleabove,wecanseethatthekeyinheuristicsearchistodeterminetheformofestimationfunctionf(n)byutilizingheuristicinformation.Asisseen,thecrucialdifferencebetweenblindsearchandheuristicsearchistheorderingregulation.InHeuristicsearch,thenodewiththesmallestvalueofevaluationfunctionwillbechosentobeexpandedfirst.,(3)AlgorithmA*forGraphSearch1.sOPEN.Setg(s)=0,f(s)=h(s)=whatever,P=0,CLOSED=NIL2.IfOPEN=NIL,F3.TakefirstnodeonOPEN,callitBest-Node(BN),BNCLOSED4.IfBN=g,S5.IfBNnotexpandable,gotostep26.ExpandBN,generatingsuccessors(SUCs)anddo:(1)SetP:SUCBN(2)Computeg(SUC)=g(BN)+g(BN,SUC)(3)IfSUC=oldnode(OLD)onOPEN,addOLDtothelistofBNssuccessors,Ifg(SUC)g(OLD),donothing(4)IfSUC=oldnode(OLD)onCLOSED,addOLDtothelistofBNssuccessors;dothesamethingasinstep6(3),settheparentlinkandgandfvaluesappropriately;However,ifg(SUC)g(OLD),theimprovementmustbepropagatetoOLDssuccessors.7.Gotostep2.,(4)HeuristicPowerThetotalcostofheuristicsearchconsistsoftwoparts:(a)Pathcost=(pathlength)xunitlengthcost(b)Searchcostspentforsearchingthesolutionpath,(a),(b),Costs,Informed-ness,(5)MeasuresofHeuristicPerformance(a)Penetrance,P,ofASearchPistheextenttowhichthesearchhasfocusedtoagoal,ratherthanwanderedoff:P=L/TwhereL:thelengthofthepathfoundtothegoalT:thetotalnumberofnodesgeneratedduringthesearch(includingthegoalnodebutnotincludingthestartnode)Hence,Pcanbeconsideredasameasureofsearchefficiency.,(b)EffectiveBranchingfactor,B,ofASearchBisdefinedbytheequation:B+B+B=T(totalnumberofnodes)HenceT=,2,L,(B-1)B,L,B-1,P=,L,T,L(B-1),B(B-1),L,Wheretheassumptionsaremade:(1)Thedepthofthesearchtree=thelengthofpathL(2)T=thenumberofnodesgeneratedduringsearch(3)Bisaconstantforallnodesinthetree,Home-Works1.Proposetwohfunctionsforthetravelingsalesmanproblem.Iseitherthesehfunctionsalowerboundonh*?Whichofthemwouldresultinmoreefficientsearch?ApplyalgorithmAwiththesehfunctionstotheTSPproblem.2.Usetheevaluationfunctionf(n)=d(n)+w(n)withalgorithmAtosearchbackwardfromthegoaltothestartnodeinthe8-puzzleproblem.3.Discusswaysinwhichanhfunctionmightbeimprovedduringasearch.,5-2Game-Playing:AND/ORGraphSearchI.Game-PlayingandAOGraphTwo-Person-Zero-Sum-PerfectInformationGamesExample:GrundysGameTwoPlayers,MaxandMin,haveapileofpennies.Thefirstplayer,Min,dividestheoriginalpileintotwopilesthatmustbeunequal.Eachplayeralternativelythereafterdoesthesametosomesinglepilewhenitishisturntoplay.Thegameproceedsuntileverypilehaseitherjustonepennyortwo.Theplayerwhofirstcannotplayistheloser.,7;Min,5,2;Max,6,1;Max,4,3;Max,5,1,1;Min,4,2,1;Min,3,2,2;Min,3,3,1;Min,3,2,1,1;Max,4,1,1,1;Max,2,2,2,1;Max,2,2,1,1,1;Min,3,1,1,1,1;Min,2,1,1,1,1,1;Max,WiningpathforMax,AND/ORGraph,FromMaxspointofview,awinmustbeobtainablefromallofMinssuccessorsandfromatleastoneofMaxssuccessors.ItisanAND/ORgraph.InAND/ORgraphs,therearehyper-arcsconnectingaparentnodewithasetofitssuccessors.Thehyper-arcsarecalledconnectors.Eachk-connectorisdirectedfromaparentnodetoasetofksuccessornodes.,II.FeaturesofAND/ORGraphSearchThechoiceofthenodetoexpandnextmustdependnotonlyonthefvalueofthatnodeitself,butalsoonwhetherthatnodeispartofthecurrentbestpathfromtheinitialnode.E.g.,A,B,C,D,h=534,9,A,B,C,D,J,I,H,G,F,E,5,10,3,4,3,4,17,18,9,9,20,Thus,tosearchanAND/ORgraph,itneedstodothreethingsateachstep:1)Traversethegraph,startingattheinitialnodeandfollowingthecurrentbestpath,andaccumulatethesetofnodesthatareonthatpathandhaventbeenexpanded.2)Pickoneofthesenodesandexpandit.Addtothegraphitssuccessors,computefforeachofthem.3)Changethefvalueofthenewlyexpandednodetoreflectthenewinformationprovidedbysuccessors.Propagatethischangebackwardthroughthegraph.Ateachnodethatisvisitedwhilegoingupthegraph,decidewhichofitssuccessorarcsisthemostpromisingandmarkitaspartofthecurrentbestpath.,A,A,B,B,C,D,C,D,E,F,3,4,5,9,6,4,4,10,9,3,4,A,B,C,D,G,H,E,F,5,7,4,4,10,4,6,12,Thismaycausethecurrentbestpathtochange.,Thus,animportantfeatureinAND/ORgraphsearchisthatonemustsearchasolutiongrapheachtimefromthestartnodetotheterminalnodeandneedstofrequentlychecktoseeifthestartnodesolvable.ThedefinitionofsolvablenodeinAND/ORgraph:1)Terminalnodeissolvablenode;2)AnORnodeissolvableiffatleastoneofitssuccessorsissolvable;3)AnANDnodeissolvableiffallitssuccessorssolvable.,III.ProcedureAO*(1)Createasearchgraph,G,consistingsolelyofthestartnode,s.Computeh(s).Ifsisaterminalnode,h(s)=0,labelsSOLVED.(2)UntilsislabeledSOLVED,do:(3)Begin(4)Computeapartialsolutiongraph,G,inGbytracingdownthemarkedconnectorsinGfroms.(5)Selectanynon-terminaltipnode,n,ofG.(6)ExpandngeneratingallitssuccessorsandinstalltheseinGassuccessorsofn.Foreachsuccessor,n,notalreadyoccurringinG,computingh(n).LabelSOLVEDanyofthesesuccessorsthatareterminalnodes.,j,j,(7)Createasingletonsetofnodes,S,consistingjustofnoden.(8)UntilSisempty,do:(9)Begin(10)RemovefromSanodemsuchthatmhasnodescendantsinGoccurringinS.(11)Revisethecosth(m)form,asfollows:Foreachconnectordirectedfrommtoasetofnodesn,n,computeh(m)=c+h(n)+h(n).Seth(m)totheminimumoveralloutgoingconnectorsofh(m)andmarktheconnectorthroughwhichthisminimumisachieved,erasingthepreviousmarkingifdifferent.,li,ki,i,i,1i,ki,i,IfallofthesuccessorsthroughthisconnectorarelabeledSOLVED,thenlabelnodemSOLVED.(12)IfmhasbeenmarkedSOLVED,oriftherevisedcostofmisdifferentthanitsjustpreviouscost,thenaddtoSalltheseparentofmsuchthatmisoneoftheirsuccessorsthroughamarkedconnector.(13)End(14)End,IVSearchTheGameTree:MinMaxProcedure1.LocalizedSolutionItisusuallyimpossibletodecideabestmovebasedonanentiresearchofawholetreeduetothenatureofcombinatorialexplosion.Instead,wemustmerelytrytofindagoodfirstmovebasedonlocalsearchthatissegmentedbytheartificialterminationconditions.Aftersearchartificiallyterminated,theestimationofthe“best”firstmovecanbemadebyapplyingastaticevaluationfunctiontothetipsofthesearchtree.,2.SomeConventionsTwoperson,zero-sum,completeinformationgames:(a)2players:MaxandMin(b)TrytofindawiningstrategyforMax.(c)Maxmovesfirst,andalternativelythereafter.(d)Thetopnodeofagametreeisofdepth0.(e)Nodesateven-numbereddepthsarecalledMaxnodesinwhichitisMaxsmovenext.(f)Theartificialterminationconditionisacertaindepthofsearchgivenpreviously.(g)GamepositionsfavorabletoMaxcauseevaluationfunctiontohavepositivevalues,whilepositionsfavorabletoMincauseftohavenegativevalues.,Rules:(a)IfMaxweretochooseamongtipnodes,hechoosesthenodehavinglargestevaluation.Thus,theMaxnodeisassignedaback-upvalueequaltothemaximumoftheevaluationofthetipnodes.(b)IfMinweretochooseamongtipnodes,hechoosesthenodehavingsmallestevaluation.ThustheMinnodeisassignedaback-upvalueequaltominimumoftheevaluationsofthetipnodes.(c)Aftertheparentsofalltipnodeshavebeenassignedback-upvalues,webackupvaluesanotherlevel.(d)Continuetobackupvalues,levelbylevel,untilallsuccessorsofthestartnodeareassignedbacked-upvalues.,Example:Tic-Tac-ToeGameTheplayerwhofirstplaceshispiecesinastraightlineinthematrixisthewinner.SupposethatMaxismarkedbywhileMinby;Maxplaysfirst.ABFSisconductedwithsomerevisions:-Artificialterminationcondition:depthbound=2;-Astaticevaluationfunctionforpositionpisdefined:N()-N(),ifpisntawiningpositione(p)=0,ifpisawiningpositionforMax-0,ifpisawiningpositionforMinwhereN()isthenumberofcompletelinesopenfor.,0,0,Theprocessisassumedtobeshownbelow:,MaxNode,MinNode,BestMove,-1,-2,1,1,6-5,5-5,6-5,5-5,4-5,5-6,5-5,5-6,6-6,4-6,5-4,6-4,4-3,3-3,5-3,3-3,4-3,4-3,4-2,3-2,5-2,3-2,4-2,3-2,4-3,4-3,3-3,1,1,0,0,1,1,BestMoveforMax,AnotherBestMove,4-2,4-2,5-2,3-2,4-2,4-2,BestMove,1,-o,-o,-o,-o,-o,-o,-o,-o,2-1,3-1,2-1,3-1,3-2,2-2,3-2,ABCD,2-1,3-1,3-1,2-2,3-2,2-2,2-1,2-1,2-1,o,o,o,o,o,o,o,o,4.Thea-bProcedureMinMaxProcedureneedtobeimproved:Itseparatescompletelythetreegenerationprocesswithpositionevaluation.Onlyaftertreegenerationcompleteddoespositionevaluationbegin.Thismayresultinagrosslyinefficientstrategy.Seethelastfigure.Ifatipnodeisevaluatedassoonasitisgenerated,thenafternodeAisgeneratedandevaluated,thereisnoneedingeneratingandevaluatingnodesB,C,D.MinwillchooseAimmediately.WecanassignAsparenttheback-upvalueof-oandproceedwiththesearchwithoutgeneratingB,C,Dandtheirsuccessors.,o,AnotherPossibleSavingConsiderthefirststep:Supposethat-DFSisemployed,Artificialstoppingcondition:d=2.-Wheneveratipnodeisgenerated,itsevaluationiscomputed.-Wheneverapositioncanbegivenaback-upvalue,thisvalueiscomputed.,StartNode(Max),LowerBound,UpperBound,-1,-2,-1,6-5,5-5,6-5,5-5,4-5,4-6,B,NodeA,B,Considerthesituation:AfternodeAandallitssuccessorshavebeengeneratedbutbeforenodeBisgenerated.Thebacked-upvalueofthestartnodeisboundfrombelowby-1,thelowerbound,anavalueforthestartnode.,StartNode(Max),LowerBound,UpperBound,b,-1,6-5,5-5,6-5,5-5,4-5,4-6,NodeA,B,Next,Banditsfirstsuccessoraregenerated.Theback-upvalueofnodeBisboundedfromaboveby-2,anupperbound,abvalue.Becauseba,wecandiscontinuesearchbelowB.,-2,a,Itisobviousthat:(a)TheavaluesofMaxnodescanneverdecrease,and(b)ThebvaluesofMinnodescanneverincrease.Thuswehavetherules:(1)SearchcanbediscontinuedbelowanyMinnodehavingavaluebaofitsMaxnodeancestors.Thefinalbacked-upvalueofthisMinnodecanbesettoitsbvalue.(2)SearchcanbediscontinuedbelowanyMaxnodehavingavalueabofitsMinnodeancestors.Thefinalbacked-upvalueofthisMaxnodecanbesettoitsavalue.,Thevaluesofaandbarecomputed,duringsearch:(1)TheavalueofaMaxnodeissetequaltothecurrentlargestfinalbacked-upvalueofitssuccessors(2)ThebvalueofaMinnodeissetequaltothecurrentsmallestfinalbacked-upvalueofitssuccessors.Whensearchisdiscontinuesunderrule(1),wecallitana-cutoff