高级人工智能ppt课件.ppt

1 搜索 2 内容 搜索问题无信息搜索UninformedSearch启发式搜索InformedSearch局部搜索LocalSearch 3 搜索问题 4 搜索问题 搜索问题构成 状态空间Astatespace后继函数Asuccessorfunction withactions costs 初始状态和目标测试Astartstateandagoaltest解是一个行动序列 将初始状态转换成目标状态 N 1 0 E 1 0 5 搜索问题是对原问题的建模 6 例子 罗马尼亚旅行 状态空间 Cities后继函数 Roads Gotoadjacentcitywithcost distance初始状态 Arad目标测试 Isstate Bucharest 解 7 状态空间包含什么 Problem PathingStates x y locationActions NSEWSuccessor updatelocationonlyGoaltest is x y END Problem Eat All DotsStates x y dotbooleans Actions NSEWSuccessor updatelocationandpossiblyadotbooleanGoaltest dotsallfalse 状态空间包含了环境中的每一个细节 搜索状态只保留行动需要的细节 8 状态空间中状态数量 世界状态 Agentpositions 120Foodcount 30Ghostpositions 12Agentfacing NSEW数量世界状态 120 x 230 x 122 x4路线规划状态 120 吃光豆子 状态 120 x 230 9 Quiz 安全通行 Problem eatalldotswhilekeepingtheghostsperma scaredWhatdoesthestatespacehavetospecify agentposition dotbooleans powerpelletbooleans remainingscaredtime 10 状态空间图StateSpaceGraphs搜索树SearchTrees 11 状态空间图 状态空间图 搜索问题的数学表示Nodesare abstracted worldconfigurationsArcsrepresentsuccessors actionresults Thegoaltestisasetofgoalnodes maybeonlyone 状态空间图中 每个状态只出现一次 几乎不在内存中构建完整的状态空间图 太大了 但它是非常有用的 12 状态空间图 Tinysearchgraphforatinysearchproblem 状态空间图 搜索问题的数学表示Nodesare abstracted worldconfigurationsArcsrepresentsuccessors actionresults Thegoaltestisasetofgoalnodes maybeonlyone 状态空间图中 每个状态只出现一次 几乎不在内存中构建完整的状态空间图 太大了 但它是非常有用的 13 搜索树 搜索树 根节点对应了初始状态子节点对应了父节点的后继节点显示状态 但对应的是到达这些状态的行动对大多数问题 实际上不会构建整个树 E 1 0 N 1 0 Thisisnow start Possiblefutures 14 状态空间图vs 搜索树 S a b d p a c e p h f r q q c G a q e p h f r q q c G a Weconstructbothondemand andweconstructaslittleaspossible EachNODEinthesearchtreeisanentirePATHinthestatespacegraph SearchTree StateSpaceGraph 15 Quiz 状态空间图vs 搜索树 S G b a Considerthis4 stategraph Important Lotsofrepeatedstructureinthesearchtree Howbigisitssearchtree fromS 16 树搜索 17 例子 罗马尼亚旅行 18 基于搜索树的搜索 搜索 扩展出潜在的行动 treenodes 维护所考虑行动的边缘 fringe 节点试图扩展尽可能少的树节点 19 一般的树搜索 Importantideas FringeExpansionExplorationstrategyMainquestion whichfringenodestoexplore 20 搜索算法特性 21 搜索算法特性 完备性 当问题有解时 保证能找到一个解 最优性 保证能找到最优解 最小耗散路径 时间复杂度 空间复杂度 例子 b分支因子m最大深度d最浅目标节点的深度整个树的节点数目 1 b b2 bm O bm b 1node bnodes b2nodes bmnodes mtiers 22 例子 树搜索 23 深度优先搜索 Depth FirstSearch 24 深度优先搜索 r Strategy expandadeepestnodefirstImplementation FringeisaLIFOstack 25 深度优先搜索 DFS 特性 DFS扩展哪些节点 Someleftprefixofthetree Couldprocessthewholetree Ifmisfinite takestimeO bm 内存需求 Onlyhassiblingsonpathtoroot soO bm 完备性 mcouldbeinfinite soonlyifwepreventcycles morelater 最优性 No itfindsthe leftmost solution regardlessofdepthorcost 26 广度优先搜索 Breadth FirstSearch 27 广度优先搜索 Strategy expandashallowestnodefirstImplementation FringeisaFIFOqueue 28 广度优先搜索 BFS 特性 BFS扩展哪些节点 ProcessesallnodesaboveshallowestsolutionLetdepthofshallowestsolutionbesSearchtakestimeO bs 内存需求 Hasroughlythelasttier soO bs 完备性 smustbefiniteifasolutionexists soyes 最优性 Onlyifcostsareall1 moreoncostslater b 1node bnodes b2nodes bmnodes stiers bsnodes 29 Quiz DFSvsBFS 30 Quiz DFSvsBFS 什么情况下BFS优于DFS 什么情况下DFS优于BFS 31 迭代深入搜索 IterativeDeepening b Idea 结合DFS的空间优势与BFS的时间优势RunaDFSwithdepthlimit1 Ifnosolution RunaDFSwithdepthlimit2 Ifnosolution RunaDFSwithdepthlimit3 浪费冗余 通常绝大多数的节点都在底层 所以上层的节点生成多次影响不是很大 32 代价敏感搜索 Cost SensitiveSearch BFSfindstheshortestpathintermsofnumberofactions Itdoesnotfindtheleast costpath Wewillnowcoverasimilaralgorithmwhichdoesfindtheleast costpath 33 代价一致搜索 UniformCostSearch 34 代价一致搜索 Strategy expandacheapestnodefirst Fringeisapriorityqueue priority cumulativecost 3 9 1 16 4 11 5 7 13 8 10 11 17 11 0 6 3 9 1 1 2 8 8 2 15 1 2 Costcontours 2 35 代价一致搜索 UCS 特性 UCS扩展哪些节点 Processesallnodeswithcostlessthancheapestsolution IfthatsolutioncostsC andarcscostatleast thenthe effectivedepth isroughlyC TakestimeO bC exponentialineffectivedepth 内存需求 Hasroughlythelasttier soO bC 完备性 Assumingbestsolutionhasafinitecostandminimumarccostispositive yes 最优性 Yes b C tiers c 3 c 2 c 1 36 代价一致搜索 UCS探索了递增的轮廓线优点 完备性 最优性 缺点 在每一个 方向 上进行探索没有关于目标信息 Start Goal 37 搜索算法 所有的搜索算法都是相同的 除了对边缘的处理策略从概念上说 所有的边缘是优先队列 即附加优先级的节点集合 对于DFS BFS 可以通过使用栈或队列代替优先队列 从而减少log n 的开支 38 搜索算法 39 搜索和模型 搜索是在问题世界的模型上操作实际上并不在真实世界上试验所有的规划规划全部是在 模拟中 你的搜索只能和你的模型一样好 40 启发式搜索 InformedSearch 41 搜索的启发策略 启发策略 估计一个状态到目标距离的函数问题给予算法的额外信息 为特定搜索问题而设计例 Manhattandistance Euclideandistanceforpathing 42 例子 启发函数 h x 43 贪婪搜索 GreedySearch 44 例子 罗马尼亚旅行 h x 45 贪婪搜索 扩展离目标最近的节点 46 贪婪搜索 策略 扩展你认为最接近目标状态的节点启发式 对每个状态估计到最近目标的距离只使用启发函数f n h n 来评价节点通常情况 最佳优先使你直接 或很快 到达目标最坏情况 类似DFS b b 47 A 搜索 48 A 搜索 UCS Greedy A 49 结合UCS和Greedy Uniform costordersbypathcost orbackwardcostg n Greedyordersbygoalproximity orforwardcosth n A Searchordersbythesum f n g n h n S a d b G h 5 h 6 h 2 1 8 1 1 2 h 6 h 0 c h 7 3 e h 1 1 S a b c e d d G G g 0h 6 g 1h 5 g 2h 6 g 3h 7 g 4h 2 g 6h 0 g 9h 1 g 10h 2 g 12h 0 50 A 结束条件 当目标入列时 应该停止吗 不 只有目标出列时才停止 S B A G 2 3 2 2 h 1 h 2 h 0 h 3 51 A 最优性 哪错了 实际 差 目标耗散 好 目标耗散的估计需要估计要小于实际耗散 A G S 1 3 h 6 h 0 5 h 7 52 可采纳启发 53 可采纳启发 启发函数h是可采纳的 那么 其中是到最近目标的真实耗散例 想出可采纳的启发函数是A 算法实际使用中的重点 54 A 树搜索的最优性 55 A 树搜索的最优性 假定 A最优目标节点B次优目标节点h可采纳的结论 A在B之前离开边缘集合 56 A 树搜索的最优性 证明 假设B在边缘集合上A的某个祖先节点n也在边缘集合上 maybeA 那么n将在B之前被扩展f n f A Definitionoff cost Admissibilityofh h 0atagoal 57 A 树搜索的最优性 证明 假设B在边缘集合上A的某个祖先节点n也在边缘集合上 maybeA 那么n将在B之前被扩展f n f A f A f B Bissuboptimal h 0atagoal 58 A 树搜索的最优性 证明 假设B在边缘集合上A的某个祖先节点n也在边缘集合上 maybeA 那么n将在B之前被扩展f n islessorequaltof A f A islessthanf B nexpandsbeforeBA的所有祖先在B之前扩展A在B之前扩展A 是最优的 59 A 算法特性 b b Uniform Cost A 60 UCSvsA 代价一致搜索在所有 方向 上等可能的扩展A 搜索主要朝着目标扩展 而且能够保证最优性 Start Goal Start Goal 61 比较 Greedy UniformCost A 62 A 算法应用 VideogamesPathing routingproblemsResourceplanningproblemsRobotmotionplanningLanguageanalysisMachinetranslationSpeechrecognition 63 设定启发函数 64 设定可采纳的启发函数 对于解决难的搜索问题 大部分工作就是想出可采纳的启发函数通常 可采纳启发函数是松弛问题的解的耗散 366 65 例子 八数码游戏 状态空间 状态数量 有哪些行动 从初始状态有多少后继 耗散 StartState GoalState Actions 松弛问题棋子可以从方格A移到B棋子可以从方格A移到B 如果A和B相邻 66 八数码游戏I Heuristic 不在位棋子数可采纳 h start 由松弛问题得到的启发函数 8 StatisticsfromAndrewMoore 67 八数码游戏II 更简单的八数码游戏任何棋子可以在任何时间滑动 而不用考虑其他棋子曼哈顿 Manhattan 距离可采纳 h start 3 1 2 18 68 八数码游戏III 采用实际耗散作为启发函数 可采纳 节点扩展 存在问题 A 算法 估计质量与每个节点计算量间的折衷启发函数越接近真实的耗散 将扩展越少的节点 但通常会在每个节点计算启发函数本身时有更多的计算 69 启发函数 占优势 ha hcif可采纳的启发函数集合 Trivialheuristics底层是零启发式 whatdoesthisgiveus 顶层是精确的启发式 70 图搜索 71 避免重复的状态 如果算法不检测重复状态 线性问题变成了指数问题 SearchTree StateGraph 72 图搜索 例如 BFS中 不应该为圈起来的节点而操心 why 73 图搜索 主要思想 不要扩展一个状态两次执行 树搜索 扩展过的状态集 closedset 按节点扩展搜索树 但 扩展节点之前 检查确保它的状态在之前没有被扩展如果不是新的状态 忽略 如果是新的 加入closed表重点 storetheclosedsetasaset notalist图搜索会破坏完备性吗 Why whynot 最优性 74 A 图搜索 S A B C G 1 1 1 2 3 S 0 2 Statespacegraph Searchtree 75 启发式的一致性 主要思想 estimatedheuristiccosts actualcosts可采纳性 heuristiccost actualcosttogoalh A actualcostfromAtoG一致性 heuristic arc cost actualcostforeacharch A h C cost AtoC 一致性 沿路径的节点估计耗散f值单调递增h A cost AtoC h C A 图搜索具备最优性 3 A C G h 4 h 1 1 h 2 76 A 图搜索的最优性 77 A 图搜索的最优性 A 算法采用一致的启发函数 Fact1 A 算法扩展节点 f值单调增 f contours Fact2 对每个状态s 到达s最优的节点先于次优的节点扩展Result A 图搜索是最优的 f 3 f 2 f 1 78 A 图搜索的最优性 证明 假定到G 的路径上某个n不能进入队列中 因为某个具有相同状态且较差的n 先被扩展了 disaster 找到树中最高的这样的节点n设p是n的祖先 且在n 出列时在队列中f p f n consistencyf n f n n 次优p应该在n 之前被扩展矛盾 79 最优性 树搜索 A isoptimalifheur