第 03 章 - 用搜索法对问题求解.ppt

《第 03 章 - 用搜索法对问题求解.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、SolvingproblemsbysearchingChapter31OutlineProblem-solvingagentsProblemtypesProblemformulationExampleproblemsBasicsearchalgorithms2Problem-solvingagents3Example:RomaniaOnholidayinRomania;currentlyinArad.FlightleavestomorrowfromBucharestFormulategoal:beinBuchares

2、tFormulateproblem:states:variouscitiesactions:drivebetweencitiesFindsolution:sequenceofcities,e.g.,Arad,Sibiu,Fagaras,Bucharest4Example:Romania5Well-definedproblemsandsolutionsAproblemcanbedefinedbyfouritems:initialstatee.g.,"atArad"actionsorsuccessorfunctionS(

3、x)=setofaction–statepairse.g.,S(Arad)={,…}goaltest,canbeexplicit,e.g.,x="atBucharest"implicit,e.g.,Checkmate(x)pathcost(additive)e.g.,sumofdistances,numberofactionsexecuted,etc.c(x,a,y)isthestepcost,assumedtobe≥0Asolutionisasequenceofactions

4、leadingfromtheinitialstatetoagoalstate6FormulatingproblemsRealworldisabsurdlycomplexstatespacemustbeabstractedforproblemsolving(Abstract)state=setofrealstates(Abstract)action=complexcombinationofrealactionse.g.,"AradZerind"representsacomplexsetofpossibleroute

5、s,detours,reststops,etc.(Abstract)solution=setofrealpathsthataresolutionsintherealworld7Vacuumworldstatespacegraphstates?actions?goaltest?pathcost?8Vacuumworldstatespacegraphstates?integerdirtandrobotlocationactions?Left,Right,Suckgoaltest?nodirtatalllocationsp

6、athcost?1peraction9Example:The8-puzzlestates?actions?goaltest?pathcost?10Example:The8-puzzlestates?locationsoftilesactions?moveblankleft,right,up,downgoaltest?=goalstate(given)pathcost?1permove[Note:optimalsolutionofn-PuzzlefamilyisNP-hard]11Example:roboticasse

7、mblystates?:real-valuedcoordinatesofrobotjointanglespartsoftheobjecttobeassembledactions?:continuousmotionsofrobotjointsgoaltest?:completeassemblypathcost?:timetoexecute12TreesearchalgorithmsBasicidea:offline,simulatedexplorationofstatespacebygeneratingsuccesso

8、rsofalready-exploredstates(a.k.a.~expandingstates)13Treesearchexample14Treesearchexample15Treesearchexample16Implementation:generaltreesearch17Implementation:statesvs.nodesA