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

LectureNotesonAI-NNChapter5InformationProcessing&UtilizationCategoriesofInformationProcessing--Problem-Solving--Game-Playing--Theorem-Proving--Logic-DeductionSection5.1Problem-Solving§5-1IntroductionDescriptionofaproblem:Problemdefining:thestart-goalconditionsRuledefining:asetofIF-THENStrategy-finding:rule-applicationcontrollingExampleTheWaterJugProblemInitialBase:Thereare2jugs,a4-kilojuganda3-kilojug.Neitherhasanymeasurementmarksonit.RuleBase:(1)Thereisapumpthatcanbeusedtofillthejugwithwater,or(2)Youcanpourwaterfromjugonthegroundorintoanotherjug.Question:Howtogetexactly2-kiloofwaterintothe4-kilojug?RepresentationandSolution:Kilosin4-kilojugkilosin3-kilojug00033033420220R1R2R13R21R222R2ItisclearthattheProductionSystemissuitablemeansofrepresentationforProblem-Solving.ProcedurePRODUCTION1.DATA←initialdatabase2.UntilDATAsatisfiestheterminationcondition,do:i)beginii)selectsomerule,R,inthesetofrulesthatcanbeappliedtoDATAiii)DATA←resultofapplyingRtoDATAInmostofAIapplications,theinformationavailabletothecontrolstrategyisusuallynotsufficienttopermitselectionofthemostappropriateruleoneverystage.TheoperationofAIproductionsystemcanthusbecharacterizedasaSEARCHPROCESSinwhichrulesaretrieduntilsomesequenceofthemisfoundthatproducesadatabasesatisfyingtheterminationconditionFurther,ifthedatabaseoftheproblemtobesolvedisrepresentedbymeansofgraph,thesearchiscalledGRAPH-SEARCH.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.6.Expandn(Applyaruleton),generatingtheset,M,ofitssuccessorsthatarenotancestorsofn.InstallthesemembersofMassuccessorsofn.7.EstablishapointertonfromthesemembersofMthatwerenotalreadyoneitherOPENorCLOSED.AddtheremembersofMtoOPEN.ForeachmemberofMthatwasalreadyonOPENorCLOSED,decidewhetherornottoredirectitspointerton.ForeachmemberofMalreadyonCLOSED,decideforeachofitsdescendantsinGwhetherornottoredirectitspointer.8.ReorderthelistOPENaccordingtoacertainrule.9.GoLOOPSNodeonCLOSEDNodeonOPEN1=n23546PointersneedtoberedirectedtoRedirectionThecrucialfactorinsearchprocessistheorderingregulationthatdeterminesthefashionoftheselectionofnodesforexpansionnext.Thesearchefficiencyisdependentontheutilityofprobleminformationinnodeselection.Inaccordwiththeutilityofprobleminformationinnodeselection,searchstrategycanbedividedinto:a)BlindSearch,andb)HeuristicSearch§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,addthemsuccessivelytotheendonOPEN,andestablishpointersfromthemton;gotostep2.Example:BFS12384765283164751=S46=g2831647528316475283147652836417523456789101134353637382831476523184765283147652831675419SeeNilssonp.71Fup.37Theshortestsolutionpath4539442033CommentsonBFS: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.Ifnisunexpandable,gotostep2.7.Expandnoden,generatingallitssuccessors.Establishpointersfromthemton.Letd(successor)=d(n)+1.AddthemtothefrontonOPENinanyorder,thengotostep2.BExample:DFSd=5283184765283164751=S28316475283164752831476528364175234567891011283147652376528371476528314765SeeNilssonp.70Fup.42ThesolutionpathB8326417518832641758632417583264175121314151617832148321483214813247651920212223641756841752368417523684175641752864317528364517283674152836741528367415237652836528371465283746152837146512384765123784658423184765123847652425262728293031ComparedwithBFS,DFShasthefollowingfeatures:1)Ifdistoosmall,thegoalnodemaybemissed,iftoolarge,thegreateramountofstorageisneeded.2)DFSmayfindthegoalfasterthanBFS,whilethethesolutionpathmaynotbetheshortestoneiftherearemorethanonegoalnode.3)DFScanoftenbecarriedoutusingareasonablysmallamountofstorage.Bgg§5-1-3Informed(Heuristic)SearchonTree(1)GeneralRemarks--Theweaknessinblindsearch:ignoringtheinformationassociatedwiththeprobleminselectingnodeforexpansionnext.--Solution:TrytousetheheuristicinformationinnodeorderingonOPEN--HeuristicSearch.--TheheuristicinformationisusedintermsofEvaluationFunction,f(.):f(n):nodenRealnumbermappingnodestotheirpromisingvalues.Foranynodenonatree,letg*(n)betheactualcostofami