C-盲目搜索-人工智能(AI).ppt

《C-盲目搜索-人工智能(AI).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、盲目（无信息）搜索Blind(Uninformed)Search（系统化的对可能的选择进行探索）R&N:Chap.3,Sect.3.3–51SimpleProblem-Solving-AgentAgentAlgorithms0sense/readinitialstateGOAL?select/readgoaltestSuccreadsuccessorfunctionsolutionsearch(s0,GOAL?,Succ)perform(solution)2大学路明秀路口秀灵路明秀路口明秀路新阳路口新阳路龙腾路口衡阳路北大路口

2、衡阳路秀灵路口衡阳路友爱路口中华路友爱路口北大路中华路口新阳中华路口新阳路北大路口中华路朝阳路口人民路友爱路口人民朝阳路口3Example:route-findingproblemOnholidayinRomania;currentlyinArad.FlightleavestomorrowfromBucharestFormulategoal:beinBucharestFormulateproblem:states:variouscitiesactions:drivebetweencitiesFindsolution:sequenceo

3、fcities,e.g.,Arad,Sibiu,Fagaras,Bucharest4Example:route-findingproblem5Single-stateproblemformulationAproblemisdefinedbyfouritems:initialstatee.g.,“atArad”goaltest,canbeexplicit,e.g.,x=“atBucharest”implicit,e.g.,NoDirt(x)pathcost(additive)e.g.,sumofdistances,numberofaac

4、tionsexecuted,etc.c(x,a,y)isthestepcost,assumedtobe0successorfunctionS(x)=setofaction-statepairse.g.,S(Arad)={,…}Asolutionisasequenceofactionsleadingfromtheinitialstatetoagoalstate6TreesearchexampleSibiuAradFagarasOradeaBucharestRimnicuTimisoaraZeri

5、ndArad7搜索树SearchTreeSearchtree注意一些状态可能会被多次访问Stategraph8搜索节点状态SearchNodesStates1234567812345678123456781356813456782472123456789SearchNodesStates123456781234567812345678135681345678247212345678若状态允许重复访问，则即使状态空间有限，搜索树也将会是无限的10一个节点的数据结构DataStructureofaNode父节点PARENT-NOD

6、E12345678状态STATE一个节点N的深度＝从根节点到N的路径长度（根节点的深度为0）记录5路径耗散5深度右移动作已扩展？yes...子节点CHILDREN11节点扩展Nodeexpansion搜索树的一个节点N的扩展包括：1）评估状态（N）的后继函数2）根据后继函数返回值，每一个状态生成一个子节点节点生成节点扩展nodegenerationnodeexpansion12345678N13568134567824721234567812搜索策略SearchStrategy边缘(fringe)指所有还未扩展的节点边缘用一个优先

7、队列实现INSERT(node,FRINGE)REMOVE(FRINGE)队列FRINGE中节点的排列顺序决定了搜索策略13搜索算法SearchAlgorithm#1SEARCH#1IfGOAL?(initial-state)thenreturninitial-stateINSERT(initial-node,FRINGE)Repeat:Ifempty(FRINGE)thenreturnfailureNREMOVE(FRINGE)sSTATE(N)Foreverystates’inSUCCESSORS(s)Createanewno

8、deN’asachildofNIfGOAL?(s’)thenreturnpathorgoalstateINSERT(N’,FRINGE)ExpansionofN#214搜索算法性能评价PerformanceMeasure