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

人工智能原理2010年春季广西大学计算机学院Dr.Ou1盲目（无信息）搜索Blind(Uninformed)Search（系统化的对可能的选择进行探索）R&N:Chap.3,Sect.3.3–5人工智能原理2010年春季广西大学计算机学院Dr.Ou2SimpleProblem-Solving-AgentAgentAlgorithm1.s0sense/readinitialstate2.GOAL?select/readgoaltest3.Succreadsuccessorfunction4.solutionsearch(s0,GOAL?,Succ)5.perform(solution)人工智能原理2010年春季广西大学计算机学院Dr.Ou3大学路明秀路口秀灵路明秀路口明秀路新阳路口新阳路龙腾路口衡阳路北大路口衡阳路秀灵路口衡阳路友爱路口中华路友爱路口北大路中华路口新阳中华路口新阳路北大路口中华路朝阳路口人民路友爱路口人民朝阳路口人工智能原理2010年春季广西大学计算机学院Dr.Ou4Example:route-findingproblemOnholidayinRomania;currentlyinArad.FlightleavestomorrowfromBucharestFormulategoal:beinBucharestFormulateproblem:states:variouscitiesactions:drivebetweencitiesFindsolution:sequenceofcities,e.g.,Arad,Sibiu,Fagaras,Bucharest人工智能原理2010年春季广西大学计算机学院Dr.Ou5Example:route-findingproblem人工智能原理2010年春季广西大学计算机学院Dr.Ou6Single-stateproblemformulationAproblemisdefinedbyfouritems:initialstatee.g.,“atArad”goaltest,canbeexplicit,e.g.,x=“atBucharest”implicit,e.g.,NoDirt(x)pathcost(additive)e.g.,sumofdistances,numberofaactionsexecuted,etc.c(x,a,y)isthestepcost,assumedtobe0successorfunctionS(x)=setofaction-statepairse.g.,S(Arad)={AradZerind,Zerind,…}Asolutionisasequenceofactionsleadingfromtheinitialstatetoagoalstate人工智能原理2010年春季广西大学计算机学院Dr.Ou7TreesearchexampleSibiuAradFagarasOradeaBucharestRimnicuTimisoaraZerindArad人工智能原理2010年春季广西大学计算机学院Dr.Ou8搜索树SearchTreeSearchtree注意一些状态可能会被多次访问Stategraph人工智能原理2010年春季广西大学计算机学院Dr.Ou9搜索节点状态SearchNodesStates123456781234567812345678135681345678247212345678人工智能原理2010年春季广西大学计算机学院Dr.Ou10SearchNodesStates123456781234567812345678135681345678247212345678若状态允许重复访问，则即使状态空间有限，搜索树也将会是无限的人工智能原理2010年春季广西大学计算机学院Dr.Ou11一个节点的数据结构DataStructureofaNode父节点PARENT-NODE12345678状态STATE一个节点N的深度＝从根节点到N的路径长度（根节点的深度为0）记录5路径耗散5深度右移动作已扩展？yes...子节点CHILDREN人工智能原理2010年春季广西大学计算机学院Dr.Ou12节点扩展Nodeexpansion搜索树的一个节点N的扩展包括：1）评估状态（N）的后继函数2）根据后继函数返回值，每一个状态生成一个子节点节点生成节点扩展nodegenerationnodeexpansion12345678N135681345678247212345678人工智能原理2010年春季广西大学计算机学院Dr.Ou13搜索策略SearchStrategy边缘(fringe)指所有还未扩展的节点边缘用一个优先队列实现•INSERT(node,FRINGE)•REMOVE(FRINGE)队列FRINGE中节点的排列顺序决定了搜索策略人工智能原理2010年春季广西大学计算机学院Dr.Ou14搜索算法SearchAlgorithm#1SEARCH#11.IfGOAL?(initial-state)thenreturninitial-state2.INSERT(initial-node,FRINGE)3.Repeat:a.Ifempty(FRINGE)thenreturnfailureb.NREMOVE(FRINGE)c.sSTATE(N)d.Foreverystates’inSUCCESSORS(s)i.CreateanewnodeN’asachildofNii.IfGOAL?(s’)thenreturnpathorgoalstateiii.INSERT(N’,FRINGE)ExpansionofN#2人工智能原理2010年春季广西大学计算机学院Dr.Ou15搜索算法性能评价PerformanceMeasures完备性Completeness一个搜索问题只要有解，搜索算法就一定能找到解的路径，则称该搜索算法是完备的[那么当问题无解的时候，将会怎样呢?]最优性Optimality只要问题有解，搜索算法就一定能找到路径耗散最小的解，则称该搜索算法是最优的复杂度Complexity复杂度是评价算法所需要的时间及占用的内存空间大小人工智能原理2010年春季广西大学计算机学院Dr.Ou16盲目vs.启发式策略Blindvs.HeuristicStrategies盲目或(无信息)策略没有利用状态的有关描述信息来确定FRINGE队列的排序，而只根据搜索树中节点的位置来进行搜索启发式或(有信息)策略利用状态的有关描述信息来确定FRINGE队列的排序（最有“希望”的节点被放在FRINGE队列的开始）人工智能原理2010年春季广西大学计算机学院Dr.Ou17Example对于盲目策略，N1和N2只是两个节点（在搜索树上的某个位置)，仅此而已GoalstateN1N2STATESTATE123456781234567812345678人工智能原理2010年春季广西大学计算机学院Dr.Ou18Example而启发式策略会计算节点状态与目标状态相比较，不在位的数码牌个数，认为N2比N1更有希望（达到目标）GoalstateN1N2STATESTATE123456781234567812345678人工智能原理2010年春季广西大学计算机学院Dr.Ou19说明一些搜索问题，比如(n2-1)-puzzle，是NP-hard问题这类问题的计算量至少为指数层次，没有人能够将这类问题的计算量降低到方次层次只能是针对具体的问题实例尽可能高效的去求得问题的解答这就是搜索策略的目标人工智能原理2010年春季广西大学计算机学院Dr.Ou20盲目策略BlindStrategies广度优先Breadth-first•双向搜索Bidirectional深度优先Depth-first•深度限制Depth-limited•迭代深入Iterativedeepening代价一致Uniform-Cost(广度优先的一种变化)弧耗散Arccost=1弧耗散Arccost=c(action)0人工智能原理2010年春季广西大学计算机学院Dr.Ou21广度优先策略Breadth-FirstStrategy新生成的节点放到FRINGE队列的最后2345167FRINGE=(1)人工智能原理2010年春季广西大学计算机学院Dr.Ou22新生成的节点放到FRINGE队列的最后FRINGE=(2,3)2345167广度优先策略Breadth-FirstStrategy人工智能原理2010年春季广西大学计算机学院Dr.Ou23新生成的节点放到FRINGE队列的最后FRINGE=(3,4,5)2345167广度优先策略Breadth-FirstStrategy人工智能原理2010年春季广西大学计算机学院Dr.Ou24新生成的节点放到FRINGE队列的最后FRINGE=(4,5,6,7)2345167广度优先策略Breadth-FirstStrategy人工智能原理2010年春季广西大学计算机学院Dr.Ou25一些重要参数ImportantParameters1）所有状态中的最大后继函数个数搜索树的分支因子bbranchingfactorbofthesearchtree2）初始状态与目标状态之间路径的最短长度(≠耗散)搜索树中最浅的目标节点的深度ddepthdoftheshallowestgoalnodeinthesearchtree人工智能原理2010年春季广西大学计算机学院Dr.Ou26评价Evaluationb:分支因子d:最浅目标节点的深度广度优先搜索:•完备Complete•最优若每一步的耗散为1生成的节点个数：???人工智能原理2010年春季广西大学计算机学院Dr.Ou27评价Evaluationb:分支因子d:最浅目标节点的深度广度优先搜索:•完备Complete•最优若每一步的耗散为1生成的节点个数：1+b+b2+…+bd=???人工智能原理2010年春季广西大学计算机学院Dr.Ou28评价Evaluationb:分支因子d:最浅目标节点的深度广度优先搜索:•完备Complete•最优若每一步的耗散为1生成的节点个数：1+b+b2+…+bd=(bd+1-1)/(b-1)=O(bd)人工智能原理2010年春季广西大学计算机学院Dr.Ou29评价Evaluationb:分支因子d:最浅目标节点的深度广度优先搜索:•完备Complete•最优若每一步的耗散为1生成的节点个数：时间和空间的复杂度均为O(bd)1+b+b2+…+bd=(bd+1-1)/(b-1)=O(bd)人工智能原理2010年春季广西大学计算机学院Dr.Ou30大O符号BigONotation称g(n)=O(f(n))，若存在两个正常数a和N，并满足下式：对于所有nN:g(n)af(n)人工智能原理2010年春季广西大学计算机学院Dr.Ou31时间与空间的要求d#NodesTimeMemory2111.01msec11Kbytes411,1111msec1Mbyte6~1061sec100Mb8~108100sec10Gbytes10~10102.8hours1Tbyte12~101211.6days100Tbytes14~10143.2years10,000Tbytes假设:b=10;1,000,000nodes/sec;100bytes/node人工智能原理2010年春季广西大学计算机学院Dr.Ou32d#NodesTimeMemory2111.01msec11Kbytes411,1111msec1Mbyte6~1061sec100Mb8~108100sec10Gbytes10~10102.8hours1Tbyte12~101211.6days100Tbytes14~10143.2years10,000Tbytes时间与空间的要求假设:b=10;