人工智能与神经网络笔记

人工智能与神经网络笔记第1页/共60页CategoriesofInformationProcessing--Problem-Solving--Game-Playing--Theorem-Proving--Logic-Deduction第2页/共60页Section5.1Problem-Solving§5-1IntroductionDescriptionofaproblem:Problemdefining:thestart-goalconditionsRuledefining:asetofIF-THENStrategy-finding:rule-applicationcontrolling第3页/共60页ExampleTheWaterJugProblemInitialBase:Thereare2jugs,a4-kilojuganda3-kilojug.Neitherhasanymeasurementmarksonit.RuleBase:(1)Thereisapumpthatcanbeusedtofillthejugwithwater,or(2)Youcanpourwaterfromjugonthegroundorintoanotherjug.Question:Howtogetexactly2-kiloofwaterintothe4-kilojug?第4页/共60页RepresentationandSolution:

Kilosin4-kilojugkilosin3-kilojug00033033420220R1R2R13R21R222R2第5页/共60页ItisclearthattheProductionSystemissuitablemeansofrepresentationforProblem-Solving.ProcedurePRODUCTION1.DATA←initialdatabase2.UntilDATAsatisfiestheterminationcondition,do:i)beginii)selectsomerule,R,inthesetofrulesthatcan

beappliedtoDATAiii)DATA←resultofapplyingRtoDATA第6页/共60页InmostofAIapplications,theinformationavailabletothecontrolstrategyisusuallynotsufficienttopermitselectionofthemostappropriateruleoneverystage.TheoperationofAIproductionsystemcanthusbecharacterizedasaSEARCHPROCESSinwhichrulesaretrieduntilsomesequenceofthemisfoundthatproducesadatabasesatisfyingtheterminationconditionFurther,ifthedatabaseoftheproblemtobesolvedisrepresentedbymeansofgraph,thesearchiscalledGRAPH-SEARCH.第7页/共60页ProcedureGRAPH-SEARCH1.Createasearchgraph,G,consistingsoleofthestartnode,S.PutSonOPEN(OPEN:alistofnodesjustgeneratedbutnotexaminedyet).2.Createalist,CLOSED,thatisinitiallyempty.(CLOSEDisalistofnodesexaminedalready)3.LOOP:ifOPENisempty,exitwithfailure.4.SelectthefirstnodeonOPEN,removeitfromOPENtoCLOSED,Callitnoden.5.Examinen:ifnisagoalnode,exitwithsuccess.ThesolutionisobtainedbytracingapathalongthepointersfromnbacktoSinG.第8页/共60页6.Expandn(Applyaruleton),generatingtheset,M,ofitssuccessorsthatarenotancestorsofn.InstallthesemembersofMassuccessorsofn.7.EstablishapointertonfromthesemembersofMthatwerenotalreadyoneitherOPENorCLOSED.AddtheremembersofMtoOPEN.ForeachmemberofMthatwasalreadyonOPENorCLOSED,decidewhetherornottoredirectitspointerton.ForeachmemberofMalreadyonCLOSED,decideforeachofitsdescendantsinGwhetherornottoredirectitspointer.8.ReorderthelistOPENaccordingtoacertainrule.9.GoLOOP第9页/共60页SNodeonCLOSEDNodeonOPEN1=n23546PointersneedtoberedirectedtoRedirection第10页/共60页Thecrucialfactorinsearchprocessistheorderingregulationthatdeterminesthefashionoftheselectionofnodesforexpansionnext.Thesearchefficiencyisdependentontheutilityofprobleminformationinnodeselection.Inaccordwiththeutilityofprobleminformationinnodeselection,searchstrategycanbedividedinto:a)BlindSearch,andb)HeuristicSearch第11页/共60页§5-1-1BlindSearchonTree1)Breadth-FirstSearchNodeordering:FIFOProcedureBFS1.PutstartnodesonOPEN.SetpointerP=02.IfOPEN=NIL,failure.3.SelectthefirstnodeonOPEN.PutitonCLOSED,Callitnoden.4.Ifn=g,successful.ThesolutionisobtainedbytracingapathalongthepointersfromgtosinG.5.Expandn.Ifithasnosuccessors,gotostep2.Or,generateallitssuccessors,addthemsuccessively

totheendonOPEN,andestablishpointersfromthemton;gotostep2.第12页/共60页Example:BFS12384765283164751=S46=g2831647528316475283147652836417523456789101134353637382831476523184765283147652831675419SeeNilssonp.71Fup.37Theshortestsolutionpath4539442033832641752836417583214765283714652318476523184765281437652831457628316754281637548326417512384765

2368417528364175283674158321476528371465832641754041424323418765281437652831457628163754231867542831567416283754213222232425262728293031第13页/共60页CommentsonBFS:Itisguaranteedtofindaoptimalsolutionbecauseofitssystematicsearchfeature.ThemajorweaknesswithBFSisitsinabilitytousetheinformationrelatedtotheproblemandthusa)Itrequiresalargememorytostorethegreatnumberofthenodes;b)Itrequireagreatamountofworktoexaminethegreatnumberofthenodesc)Asresult,BFShaslowefficiencyofsearch.第14页/共60页§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第15页/共60页Example:DFSd=5283184765283164751=S28316475283164752831476528364175234567891011283147652376528371476528314765SeeNilssonp.70Fup.42ThesolutionpathB8326417518832641758632417583264175121314151617832148321483214813247651920212223641756841752368417523684175641752864317528364517283674152836741528367415237652836528371465283746152837146512384765123784658423184765123847652425262728293031第16页/共60页ComparedwithBFS,DFShasthefollowingfeatures:1)Ifdistoosmall,thegoalnodemaybemissed,iftoolarge,thegreateramountofstorageisneeded.2)DFSmayfindthegoalfasterthanBFS,whilethethesolutionpathmaynotbetheshortestoneiftherearemorethanonegoalnode.3)DFScanoftenbecarriedoutusingareasonablysmallamountofstorage.Bgg第17页/共60页§5-1-3Informed(Heuristic)SearchonTree(1)GeneralRemarks--Theweaknessinblindsearch:ignoringtheinformationassociatedwiththeprobleminselectingnodeforexpansionnext.--Solution:TrytousetheheuristicinformationinnodeorderingonOPEN--HeuristicSearch.--TheheuristicinformationisusedintermsofEvaluationFunction,f(.):

f(n):nodenRealnumbermappingnodestotheirpromisingvalues.第18页/共60页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.第19页/共60页Practically,g(n):thesumofthearccostsencounteredwhiletracingthepointersfromntos.h(n):afunctionbasedonheuristicinformationfromtheproblem,henceiscalledHeuristicFunction.ThepracticalregulationisIfh(n)isveryhigh,nodenmaybeignored;Ifh(n)islow,nodenmaybechosentoexpandnext.第20页/共60页(2)AlgorithmAandAlgorithmA*onTreeAlgorithmAisaspecialTree-Searchusingevaluationfunctionf(n)fororderingnodesonOPENandalwaysselectingforexpansionthenodewiththelowestvalueoff(n).ThekeyforAlgorithmAisthesettingsofhandg:Whenh=0,g=d,itreducestoBFS;h=0,g=0,randomsearch;h=1/d,g=0,DFS;h>h*,theoptimalpathmaybelost;h<h*,somesearchmayberedundant,butoptimalpathcanbefound.第21页/共60页AlgorithmAwithh(n)<h*(n),foralln,isAlgorithmA*.ThusBFSisAlgorithmA*andA*canalwaysfindaminimallengthpathtoagoal.Informed-nessofAlgorithmA*:A1*:f1(n)=g1(n)+h1(n)A2*:f2(n)=g2(n)+h2(n)withh1(n)<h*(n),h2(n)<h*(n)A2*ismoreinformedthanA1*,iffh*(n)>h2(n)>h1(n)forallnon-goalnoden.第22页/共60页ExampleofA*:8-PuzzleProblemLetf(n)=g(n)+h(n)=d(n)+w(n)d(n):depthofnodenonsearchtreew(n):numberofmisplaceddigitsatnoden28318428316475283164751647528314765

28314765765283

7652831476583

184214

23

2376571465

12384765123784658423184765123847651#0+4=42#3#4#6#7#8#12#13#14#15#26#27#1+5=61+3=41+5=62+3=52+3=52+4=63+3=63+4=73+2=53+4=74+1=55+0=513outof27第23页/共60页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).第24页/共60页Abetterestimateofh*(n)ish(n)=P(n)+3S(n)P(n):thesumoftheabsolutedistancesthatadigitisfrom“home”;S(n):asequencescore,takingvalue2,foreachnon-centraldigitnotproperfollowed1,ifadigitinthecenter0,forotherdigitsE.g.,fors=andg=,wehave2164875312384765P(s)=(3x1)+(3x2)+(1x3)+(1x0)=12(1,2,5)(3,4,8)(6)(7)S(s)=8x2=16第25页/共60页Byusingthish(n),wehavef(n)=g(n)+P(n)+3S(n)withg(n)=d(n)andtheaboveproblemwillfindthesameoptimalpathbutwithfewernodesexpanded:28318428316475283164751647528314765

28314765765

28314765

184

23

23765

123847651237846584231847651238476511outof13第26页/共60页Since0<w(n)<h*(n)<P(n)+3S(n),thesolutionpathfoundhappenstobeofminimalpath,althoughwewerenotguaranteedoffindinganoptimalpath.Summary:

Fromtheexampleabove,wecanseethatthekeyinheuristicsearchistodeterminetheformofestimationfunctionf(n)byutilizingheuristicinformation.Asisseen,thecrucialdifferencebetweenblindsearchandheuristicsearchistheorderingregulation.InHeuristicsearch,thenodewiththesmallestvalueofevaluationfunctionwillbechosentobeexpandedfirst.第27页/共60页(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,addOLDtothelistofBN’ssuccessors第28页/共60页

Ifg(SUC)<g(OLD),theOLD’sparentlinkshouldberesettopointtoBN,recordg(SUC)intheplaceofg(OLD)Ifg(SUC)>g(OLD),donothing(4)IfSUC=oldnode(OLD)onCLOSED,addOLDtothelistofBN’ssuccessors;dothesamethingasinstep6(3),settheparentlinkandgandfvaluesappropriately;However,ifg(SUC)<g(OLD),theimprovementmustbepropagatetoOLD’ssuccessors.7.Gotostep2.第29页/共60页(4)HeuristicPowerThetotalcostofheuristicsearchconsistsoftwoparts:(a)Pathcost=(pathlength)xunitlengthcost(b)Searchcostspentforsearchingthesolutionpath(a)(b)CostsInformed-ness第30页/共60页(5)MeasuresofHeuristicPerformance(a)Penetrance,P,ofASearchPistheextenttowhichthesearchhasfocusedtoagoal,ratherthanwanderedoff:

P=L/Twhere

L:thelengthofthepathfoundtothegoal

T:thetotalnumberofnodesgeneratedduringthesearch(includingthegoalnodebutnotincludingthestartnode)Hence,

Pcanbeconsideredasameasureofsearchefficiency.第31页/共60页(b)EffectiveBranchingfactor,B,ofASearchBisdefinedbytheequation:

B+B+…+B=T(totalnumberofnodes)HenceT=2L(B-1)BLB-1P==LTL(B-1)B(B-1)LWheretheassumptionsaremade:(1)Thedepthofthesearchtree=thelengthofpathL(2)T=thenumberofnodesgeneratedduringsearch(3)Bisaconstantforallnodesinthetree第32页/共60页Home-Works1.Proposetwohfunctionsforthetravelingsalesmanproblem.Iseitherthesehfunctionsalowerboundonh*?Whichofthemwouldresultinmoreefficientsearch?ApplyalgorithmAwiththesehfunctionstotheTSPproblem.2.Usetheevaluationfunctionf(n)=d(n)+w(n)withalgorithmAtosearchbackwardfromthegoaltothestartnodeinthe8-puzzleproblem.3.Discusswaysinwhichanhfunctionmightbeimprovedduringasearch.第33页/共60页§5-2Game-Playing:AND/ORGraphSearchI.Game-PlayingandAOGraphTwo-Person-Zero-Sum-PerfectInformationGames

Example:Grundy’sGameTwoPlayers,MaxandMin,haveapileofpennies.Thefirstplayer,Min,dividestheoriginalpileintotwopilesthatmustbeunequal.Eachplayeralternativelythereafterdoesthesametosomesinglepilewhenitishisturntoplay.Thegameproceedsuntileverypilehaseitherjustonepennyortwo.Theplayerwhofirstcannotplayistheloser.第34页/共60页7;Min5,2;Max6,1;Max4,3;Max5,1,1;Min4,2,1;Min3,2,2;Min3,3,1;Min3,2,1,1;Max4,1,1,1;Max2,2,2,1;Max2,2,1,1,1;Min3,1,1,1,1;Min2,1,1,1,1,1;MaxWiningpathforMaxAND/ORGraph第35页/共60页FromMax’spointofview,awinmustbeobtainablefromallofMin’ssuccessorsandfromatleastoneofMax’ssuccessors.ItisanAND/ORgraph.InAND/ORgraphs,therearehyper-arcsconnectingaparentnodewithasetofitssuccessors.Thehyper-arcsarecalledconnectors.Eachk-connectorisdirectedfromaparentnodetoasetofksuccessornodes.第36页/共60页II.FeaturesofAND/ORGraphSearchThechoiceofthenodetoexpandnextmustdependnotonlyonthefvalueofthat

nodeitself,butalsoonwhetherthatnodeispartofthe

currentbest

pathfromthe

initialnode.E.g.,ABCDh=5349ABCDJIHGFE510343417189920第37页/共60页Thus,tosearchanAND/ORgraph,itneedstodothreethingsateachstep:1)Traversethegraph,startingattheinitialnodeandfollowingthecurrentbestpath,andaccumulatethesetofnodesthatareonthatpathandhaven’tbeenexpanded.2)Pickoneofthesenodesandexpandit.Addtothegraphitssuccessors,computefforeachofthem.3)

Changethefvalueofthenewlyexpandednodetoreflectthenewinformationprovidedbysuccessors.Propagatethischangebackwardthroughthegraph.Ateachnodethatisvisitedwhilegoingupthegraph,decidewhichofitssuccessorarcsisthemostpromisingandmarkitaspartofthecurrentbestpath.第38页/共60页AABBCDCDEF345964410934ABCDGHEF5744104612Thismaycausethecurrentbestpathtochange.第39页/共60页Thus,animportantfeatureinAND/ORgraphsearchisthatonemustsearchasolutiongrapheachtimefromthestartnodetotheterminalnodeandneedstofrequentlychecktoseeifthestartnodesolvable.ThedefinitionofsolvablenodeinAND/ORgraph:1)Terminalnodeissolvablenode;2)AnORnodeissolvableiffatleastoneofitssuccessorsissolvable;3)AnANDnodeissolvableiffallitssuccessorssolvable.第40页/共60页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.jj第41页/共60页(7)Createasingletonsetofnodes,S,consistingjustofnoden.(8)UntilSisempty,do:(9)Begin(10)RemovefromSanodemsuchthatmhasnodescendantsinGoccurringinS.(11)Revisethecosth(m)form,asfollows:Foreachconnectordirectedfrommtoasetofnodes{n,…,n},computeh(m)=c+h(n)+…+h(n).Seth(m)totheminimumoveralloutgoingconnectorsofh(m)andmarktheconnectorthroughwhichthisminimumisachieved,erasingthepreviousmarkingifdifferent.likiii1ikii第42页/共60页IfallofthesuccessorsthroughthisconnectorarelabeledSOLVED,thenlabelnodemSOLVED.(12)IfmhasbeenmarkedSOLVED,oriftherevisedcostofmisdifferentthanitsjustpreviouscost,thenaddtoSalltheseparentofmsuchthatmisoneoftheirsuccessorsthroughamarkedconnector.(13)End(14)End第43页/共60页IVSearchTheGameTree:MinMaxProcedure1.LocalizedSolutionItisusuallyimpossibletodecideabestmove

basedonan

entiresearchofawholetreeduetothenatureofcombinatorialexplosion.Instead,wemustmerelytrytofindagoodfirstmovebasedonlocalsearchthatissegmentedbytheartificialterminationconditions.Aftersearchartificiallyterminated,theestimationofthe“best”firstmovecanbemadebyapplyingastaticevaluationfunctiontothetipsofthesearchtree.第44页/共60页2.SomeConventionsTwoperson,zero-sum,completeinformationgames:(a)2players:MaxandMin(b)TrytofindawiningstrategyforMax.(c)Maxmovesfirst,andalternativelythereafter.(d)Thetopnodeofagametreeisofdepth0.(e)Nodesateven-numbereddepthsarecalledMaxnodesinwhichitisMax’smovenext.(f)Theartificialterminationconditionisacertaindepthofsearchgivenpreviously.(g)GamepositionsfavorabletoMaxcauseevaluationfunctiontohavepositivevalues,whilepositionsfavorabletoMincauseftohavenegativevalues.第45页/共60页Rules:(a)IfMaxweretochooseamongtipnodes,hechoosesthenodehavinglargestevaluation.Thus,theMaxnodeisassignedaback-upvalueequaltothemaximumoftheevaluationofthetipnodes.(b)IfMinweretochooseamongtipnodes,hechoosesthenodehavingsmallestevaluation.ThustheMinnodeisassignedaback-upvalueequaltominimumoftheevaluationsofthetipnodes.(c)Aftertheparentsofalltipnodeshavebeenassignedback-upvalues,webackupvaluesanotherlevel.(d)Continuetobackupvalues,levelbylevel,untilallsuccessorsofthestartnodeareassignedbacked-upvalues.第46页/共60页Example:Tic-Tac-ToeGameTheplayerwhofirstplaceshispiecesinastraightlineinthematrixisthewinner.SupposethatMaxismarkedbywhileMinby;Maxplaysfirst.ABFSisconductedwithsomerevisions:--Artificialterminationcondition:depthbound=2;--Astaticevaluationfunctionforpositionpisdefined:N()-N(),ifpisn’tawiningpositione(p)=0,ifpisawiningpositionforMax-0,ifpisawiningpositionforMinwhereN()isthenumberofcompletelinesopenfor.00第47页/共60页Theprocessisassumedtobeshownbelow:MaxNodeMinNodeBestMove-1-2116-55-56-55-54-55-65-55-66-64-65-46-4第48页/共60页4-33-35-33-34-34-34-23-25-23-24-23-24-34-33-3110011BestMoveforMaxAnotherBestMove4-24-25-23-24-24-2第49页/共60页BestMove1-o-o-o-o-o-o-o-o2-13-12-13-13-22-23-2ABCD2-13-13-12-23-22-22-12-12-1oooooooo第50页/共60页4.Thea-bProcedure

MinMaxProcedureneedtobeimproved:

Itseparatescompletelythetreegenerationprocesswithpositionevaluation.Onlyaftertreegenerationcompleteddoespositionevaluationbegin.Thismayresultinagrosslyinefficientstrategy.Seethelastfigure.Ifatipnodeisevaluatedassoonasitisgenerated,thenafternodeAisgeneratedandevaluated,thereisnoneedingeneratingandevaluatingnodesB,C,D.MinwillchooseAimmediately.WecanassignA’sparenttheback-upvalueof-oandproceedwiththesearchwithoutgeneratingB,C,Dandtheirsuccessors.o第51页/共60页AnotherPossibleSavingConsiderthefirststep:Supposethat--DFSisemployed,Artificialstoppingcondition:d=2.--Wheneveratipnodeisgenerated,itsevaluationiscomputed.--Wheneverapositioncanbegivenaback-upvalue,thisvalueiscomputed.StartNode(Max)LowerBound

UpperBound-1-2-16-55-56-55-54-54-6BNodeAB第52页/共60页Considerthesituation:AfternodeAandallitssuccessorshavebeengeneratedbutbeforenodeBisgenerated.Thebacked-upvalueofthestartnodeisboundfrombelowby-1,thelowerbound,anavalueforthestartnode.StartNode(Max)LowerBound

UpperBoundb-16-55-56-55-54-54-6NodeABNext,Banditsfirstsuccessoraregenerated.Theback-upvalueofnodeBisboundedfromaboveby-2,anupperbound,abvalue.Becauseb<a,wecandiscontinuesearchbelowB.-2a第53页/共60页Itisobviousthat:(a)TheavaluesofMaxnodescanneverdecrease,and(b)ThebvaluesofMinnodescanneverincrease.Thuswehavetherules:(1)SearchcanbediscontinuedbelowanyMinnodehavingavalueb

aofitsMaxnodeancestors.Thefinalbacked-upvalueofthisMinnodecanbesettoitsbvalue.(2)Searchcanbediscontinuedbelowa