算法设计与分析课件：Lecture 05 Search

Lecture5

SearchThesearchexampleStatespaceS:allvalidconfigurationsInitialstates(nodes)I={(CSDF,)}⊆SWhere’stheboat?GoalstatesG={(,CSDF)}⊆SSuccessorfunctionsuccs(s)⊆S:statesreachableinonestep(onearc)froms

succs((CSDF,))={(CD,SF)}succs((CDF,S))={(CD,FS),(D,CFS),(C,DFS)}cost(s,s’)=1forallarcs.(weightedlater)Thesearchproblem:findasolutionpathfromastateinItoastateinG.Optionallyminimizethecostofthesolution.ThesearchexampleWaterjugs:howtoget1?Goal?(Howmanygoalstates?)Successorfunction:fillup(fromtaporotherjug),empty(togroundorotherjug)AdirectedgraphinstatespaceIngeneraltherewillbemanygenerated,butun-expandedstatesatanygiventimeOnehastochoosewhichonetoexpandnextDeeporshallow?UninformedsearchUninformedmeansweonlyknow:ThegoaltestThesuccs()functionButnotwhichnon-goalstatesarebetter:thatwouldbeinformedsearch.Fornow,wealsoassumesuccs()graphisatree.Won’tencounterrepeatedstates.Wewilldiscussitlater.Searchstrategies:BFS,UCS,DFS,IDS.Breadth-firstsearch(BFS)Useaqueue(First-inFirst-out)en_queue(Initialstates)While(queuenotempty) s=de_queue() if(s==goal)success! T=succs(s) fortinT:t.prev=s en_queue(T)endWhileWeneedbackpointerstorecoverthesolutionpath.PerformanceofBFSAssume:thegraphmaybeinfinite.Goal(s)existsandisonlyfinitestepsaway.WillBFSfindatleastonegoal?WillBFSfindtheleastcostgoal?Timecomplexity?NumberofstatesgeneratedGoal:dedgesawayBranchingfactor:bSpacecomplexity?NumberofstatesstoredPerformanceofBFSCompleteness:yes,BFSwillfindagoal.Optimality:yes,ifedgescost1(moregenerallypositivenon-decreasingindepth),nootherwise.Timecomplexity(worstcase):goalisthelastnodeatradiusd.Havetogenerateallnodesatradiusd.b+b2+…+bd~O(bd)Spacecomplexity:O(bd)Uniform-costsearchFindtheleast-costgoalEachnodehasapathcostfromstart(=sumofedgecostsalongthepath).Expandtheleastcostnodefirst.UseapriorityqueueinsteadofanormalqueueAlwaystakeouttheleastcostitemRememberheap?time

O(log(numberofitemsinheap))Completeandoptimal(ifedgecosts>=ε>0)Timeandspace:canbemuchworsethanBFSLetC*bethecostoftheleast-costgoalO(bC*/ε),possiblyC*/ε>>dDepth-firstsearchUseastack(First-inLast-out)push(Initialstates)While(stacknotempty) s=pop() if(s==goal)success! T=succs(s) push(T)endWhileThisisnon-recursiveimplementationofDFS,recursiveimplementationismorecommonPerformanceofDFSm=maximumdepthofgraphfromstartSpacecomplexity:O(mb)Infinitetree:maynotfindgoal(incomplete)MaynotbeoptimalFinitetree:mayvisitalmostallnodes,timecomplexityO(bm)Iterativedeepeningsearch1.DFS,butstopifpathlength>1.2.Ifgoalnotfound,repeatDFS,stopifpathlength>2.3.Andsoon…IterativedeepeningsearchBFS+DFSComplete,optimallikeBFSSmallspacecomplexitylikeDFS•Ahugewaste?EachdeepeningrepeatsDFSfromthebeginningNo!db+(d-1)b2+(d-2)b3+…+bd~O(bd)TimecomplexitylikeBFSBidirectionalsearchBreadth-firstsearchfrombothstartandgoalStopwhenfringesmeetThefringes(边缘)areO(bd/2)GeneratesO(bd/2)insteadofO(bd)nodesPerformanceofsearchalgorithmsSearchexampleAlledgesaredirected,pointingdownwardsNodeexpansionDepth-FirstSearch:SADEGSolutionfound:SAGBreadth-FirstSearch:SABCDEGSolutionfound:SAGUniform-CostSearch:SADBCEGSolutionfound:SBG(Thisistheonlyuninformedsearchthatworriesaboutcosts.)Iterative-DeepeningSearch:SABCSADEGSolutionfound:SAGGeneralgraphsearchTheproblem:repeatedstatesWehavetorememberalready-expandedstates(CLOSED).Whenwetakeoutastatefromthefringe(OPEN),checkwhetheritisinCLOSED(alreadyexpanded).Ifyes,throwitaway.Ifno,expandit(addsuccessorstoOPEN),andmoveittoCLOSED.GeneralgraphsearchBFS:StillO(bd)spacecomplexityDFS:MemorizingDFS(MEMDFS):memorizeeveryexpandedstatesPathCheckDFS(PCDFS):rememberonlyexpandedstatesoncurrentpath(fromstarttothecurrentnode)

InformedsearchUninformedsearchKnowstheactualpathcostg(s)fromthestarttoanodes.InformedsearchAlsohasaheuristich(s)ofthecostfromstogoal.

Canbemuchfasterthanuninformedsearch.

Recall:Uniform-costsearchUniform-costsearch:uninformedsearchwhenedgecostsarenotthesame.Complete(willfindagoal).Optimal(willfindtheleast-costgoal).Alwaysexpandthenodewiththeleastg(s)Useapriorityqueue:Pushinstateswiththeirfirst-half-costg(s)Popoutthestatewiththeleastg(s)firstNowwehaveanestimateofthesecond-half-costh(s),howtouseit?Best-firstgreedysearchUseh(s)insteadofg(s)Alwaysexpandthenodewiththeleasth(s)Notoptimal ItwillfollowthepathA->C->GAsearchUsef(s)=g(s)+h(s)Alwaysexpandthenodewiththeleastg(s)+h(s)Asearchisnotalwaysoptimal

A*searchSameasAsearch,buttheheuristicfunctionh()hastosatisfyh(s)<=h*(s),whereh*(s)isthetruecostfromnodestothegoal.Suchheuristicfunctionh()iscalledadmissible.Anadmissibleheuristicneverover-estimatesAsearchwithadmissibleh()iscalledA*search.

Admissibleheuristicfunctionsh8-puzzleexampleWhichofthefollowingareadmissibleheuristics?h(n)=numberoftilesinwrongpositionh(n)=0h(n)=1h(n)=sumofManhattandistancebetweeneachtileanditsgoallocation

AdmissibleheuristicsAheuristicfunctionh2

dominates

h1ifforalls

h1(s)<=h2(s)<=h*(s)d=14,A*(h1)=539nodesA*(h2)=113nodesd=24,A*(h1)=39,135nodesA*(h2)=1,641nodesWepreferheuristicfunctionsasclosetoh*aspossible,butnotoverh*.GoodheuristicfunctionmightneedcomplexcomputationTimemaybebetterspent,ifweuseafaster,simplerheuristicfunctionandexpandmorenodes.SometricksA*shouldterminateonlywhenagoalispoppedfromthepriorityqueueA*canrevisitanexpandedstate,anddiscoverashorterpath

TheA*algorithm1.PutthestartnodeSonthepriorityqueue,calledOPEN

2.IfOPENisempty,exitwithfailure3.RemovefromOPENandplaceonCLOSEDanodenforwhichf(n)isminimum4.Ifnisagoalnode,exit(tracebackpointersfromntoS)5.Expandn,generatingallitssuccessorsandattachtothempointersbackton.Foreachsuccessorn'ofnnotonCLOSED1.Ifn'isnotalreadyonOPEN,estimateh(n'),g(n')=g(n)+c(n,n'),f(n')=g(n')+h(n'),andplaceitonOPEN.2.Ifn'isalreadyonOPEN,thencheckifg(n')islowerforthenewversionofn'.Ifso,then:Redirectpointersbackwardfromn'alongpathyieldinglowerg(n').Putn'onOPEN.Ifg(n')isnotlowerforthenewversion,donothing.6.Goto2.ConsistentheuristicsConsistencyisanalogoustothetriangleinequalityfromEuclidiangeometry.Aheuristicisconsistentif h(n)<=c(n,a,n’)+