人工基础智能 8

课堂设计一、基本信息课次第2次（讲）课次学时数2学时主题知识表示与搜索二、设计方案课堂目标（一）知识目标能简述搜索问题的表示方法；能对搜索策略进行分类；能描述先深、先广搜索的搜索顺序；能简述A*算法的基本思想。素质目标：（二）能力目标能用状态空间对待求解决问题进行表示；能选用合适的搜索算法求解相应问题；能将简单现实问题转化为搜索问题，并分析求解方法。（三）素质目标能通过智能求解搜索问题的演化路径，塑造学员求真探索、追求卓越的品质。教学重难点（一）教学重点状态空间表示方法，盲目式搜索、启发式搜索。（二）教学难点启发式搜索策略。教学设计思路（一）教学内容组织1.状态搜索表示2.盲目式搜索3.启发式搜索（二）教学方法策略采用设问引导的方式渐进式引出主要内容。通过直观的问题，引导学员思考如何对搜索问题进行形式化的表示；通过“问题如何进行求解?”“问题总是有解吗？如果找到解，能保证它是最优的吗?”等连贯性问题让学员思考如何使用搜索算法进行求解；通过“搜索算法的时间复杂性如何?空间复杂性如何？”问题引导学员分析盲目式搜索的算法性能及存在的不足，为下节课内容埋下伏笔。基于提升算法性能这一需求，提出“能否更有效的搜索”这一问题，引入启发式信息的定义及启发式搜索。以A*算法为例，讲解启发式搜索算法的工作流程。再通过问题“多方参与的搜索如何进行搜索”引导学生思考实际中多方博弈的问题。介绍博弈树搜索的工作流程，及两种典型的博弈搜索方法：极大极小分析法和蒙特卡洛树搜索。最后总结，梳理课堂教学脉络，在学员脑中建立搜索问题求解的整体流程。。通过本次课学习，让学员领悟到，将来工作中遇到实际问题时，要多思考多分析，将实际问题转化为可求解问题，再利用所学理论知识有针对性的开展工作，达到事半功倍的效果。教学资源1.头歌（EduCoder）平台在线资源2.《人工智能技术及其军事应用》在线课程

内容备注课堂导入引入AlphaGo的“神之一手”。AlphaGo使用的关键技术其中就有我们今天要学习的搜索算法中的一种——启发式搜索算法。搜索问题在人工智能中的作用：搜索是人工智能技术中进行问题求解的基本技术，不管是解决具体应用问题，还是智能行为本身，最终往往都归结为某种搜索，都要用某种搜索算法来实现。搜索问题也是人工智能取得出色表现的一个领域。问题无人机路径规划的搜索本次课，要解决以下问题：如何对搜索问题进行形式化表示？问题如何进行求解?问题总是有解吗？如果找到解，能保证它是最优的吗?搜索算法的时间复杂性如何?空间复杂性如何？能否更有效的搜索？理论讲解一、问题的状态图表示问题1如何对搜索问题进行形式化表示？案例简单搜索问题对比路径规划、下棋等典型问题，找出求解的共性元素，引出问题的状态空间表示：状态空间：状态空间可用三元组(S,F,G)表示：S是状态集合，其中的每一个元素表示一种状态；F是操作符集合，用于把一个状态转换为另一个状态；G是S的一个非空子集，表示目标状态集，它可以是若干具体的状态，也可以是对某些状态性质的描述。举例八数码问题的状态空间表示二、盲目式搜索问题2问题如何进行求解?将问题用状态图的形式表示后，就可以进行求解了，而在状态途中寻找目标或者路径的基本方法就是搜索。（一）搜索策略由于搜索具有探索性，我们总是希望能够尽快找到目标节点或目标路径，所以，要提高搜索的效率，就必须注意搜索效率，目前主流的搜索策略大体可以分为两类：盲目式搜索和启发式搜索。盲目式搜索：也称为穷举式搜索或暴力搜索，是指从初始节点开始，逐个节点或逐条路径考察，从而找到目标状态或目标路径。启发式（heuristic）搜索：利用启发信息，引导式的进行搜索，缩小搜索范围，提高搜索效率。本次课重点讨论盲目搜索，下一次课讨论启发式搜索。（二）搜索算法搜索算法主体框架如下：(1)把初始节点S0放入OPEN表中。(2)若OPEN表为空,则搜索失败,退出。(3)移出OPEN表中第一个节点N放入CLOSED表中,并冠以编号n。(4)若目标节点Sg=N,则搜索成功,结束。(5)若N不可扩展,则转步(2)。(6)扩展N,生成一组子节点,对这组子节点做如下处理：①删除N的先辈节点(如果有的话)。②对已存在于OPEN表的节点(如果有的话)也删除之；但删除之前要比较其返回初始节点的新路径与原路径,如果新路径“短”,则修改这些节点在OPEN表中的原返回指针,使其沿新路返回。③对已存在于CLOSED表的节点(如果有的话),做与②同样的处理,并且再将其移出CLOSED表,放入OPEN表重新扩展(为了重新计算代价)。④对其余子节点配上指向N的返回指针后放入OPEN表中某处,或对OPEN表进行重新排序,转步(2)。搜索算法的框架，是基于两个表结构实现的，其中Open表用来保存待考察的节点，Closed表用来保存已经考察过的节点。这两个表是一种动态表结构，表结构中每一个元素根据实际问题可以灵活采用各种数据结构。示例搜索算法跟踪（三）广度优先搜索开始搜索d+1层的节点之前，需要搜索完d层的所有节点。算法关键：“对其余子节点配上指向N的返回指针后放入OPEN表中尾部,转步(2)”。（学生接受度不足则不提指针）（四）深度优先搜索深度优先搜索就是在搜索树的每一层始终只扩展一个子节点，不断的向纵深前进，指导不能在前进，才从当前节点返回到上一级节点，沿另一方向又继续前进。算法关键：“对其余子节点配上指向N的返回指针后放入OPEN表中头部,转步(2)”。问题3问题总是有解吗?如果能找到解，能保证解是最优的吗?要探讨解的优劣，首先要对解的代价衡量方式进行约定。对于搜索问题，通常可以从解的代价最低、解的路径最短两个方面考察。解的代价最低，例如形如求最短路径的问题，我们最终要找的是一条路径，我们希望路径的总长度或者总代价最短；对于搜索特定状态的情况，这时的最优解，是找到解的最短路径，也就是最快找到解的路径。这两类问题，实际可以上是同一类问题，刚才说的路径长度问题，无非是每一条边都使用一个数值来表示经过该路径的代价，而针对本问题，我们可以认为，每条边的代价都是1，这样处理，就可以当同一类问题来看待了。能否找到最优解呢？通过对广度优先搜索和深度优先搜索的分析可知，广度优先搜索一定能找到最优解，深度优先搜不一定能找到最优解。问题4搜索问题的时空复杂性如何?以下分析均建立在树的深度为d，每个节点的平均子节点数为b的前提下。时间复杂性：盲目搜索最坏情况下均要搜索完整棵树，所以时间复杂性为O(bd)。对于广度优先搜索，平均耗时为b空间复杂性：空间复杂性主要是搜索算法执行过程中所占用的存储空间。对于广度优先搜索，空间复杂性为O(bd)，问题5能否进行更高效的搜索?三、启发式搜索（一）启发信息启发信息：与待求解问题相关的各类信息，合理使用此类信息有助于更加高效、准确地解决问题。在日常工作和生活中，我们在有意识无意识使用启发信息。对于状态图搜索问题，启发性信息有助于决定先扩展哪些节点，确定搜索方向；决定生成哪些子节点，确定搜索规模；决定删除哪些节点，缩小搜索空间。（二）启发式搜索启发式搜索：利用启发信息，引导式的进行搜索，缩小搜索范围，提高搜索效率。启发函数：用来估计搜索树上节点X与目标节点Sg接近程度的一种函数，通常记为h(x)。启发函数设置的参考思路：一个节点到目标节点的某种距离或者差异；一个节点处在最佳路径上的概率；主观经验的打分。（三）贪婪搜索在搜索过程中先扩展当前状态，然后评估它的儿子节点；而后选择最佳的儿子作进一步的扩展；在整个过程中既不保留它的兄弟，也不保留它的父亲节点；当搜索遇到一个比其所有儿子节点都更好的节点状态时或者达到目标状态时，停止搜索。案例2无人机寻径问题课堂练习贪婪方法寻找目标位置提问贪婪算法能不能找到目标点？贪婪算法属于局部最佳优先搜索算法，会导致局部最大化问题。对于加权最短路径搜索问题，可能找不到最优解；对于寻找目标状态类问题，甚至可能找不到解。（四）A*算法算法的可采纳性：如果只要存在到达目标解的最短路径，搜索算法就可找到这样的路径，那么这个算法就是可采纳的。

定义评估函数定义f(n)=g(n)+ℎ(n)，其中ℎn=当前节点到目标节点的估计距离；g(n)从根节点到当前节点n的实际距离如果在A算法中使用的评估函数满足ℎ(n)小于从n到目标的最短路径代价ℎ∗n，那么就把这种算法称为A∗小结通过本次课学习，解答了课前提出的五个问题。搜索是人工智能技术中进行问题求解的基本技术，首先可以将问题转化为状态图的形式表示，然后可以采用不同的策略进行状态图搜索。盲目搜索是最简单的搜索策略，有先深和先广两种搜索策略。在实际应用中，为了进一步提高搜索效率，可以运用启发信息来指导搜索过程。通过启发信息，确定搜索方向，缩小搜索空间，提高搜索效率。启发式搜索中A*算法，该算法是可采纳的，一定能找到最优解。使用搜索算法解决实际问题，应该针对问题特点灵活运用各种方法解决复杂问题。从搜索在无人机路径规划中的应用，引出搜素要解决的基本问题通过简单直观的问题，引导学员思考搜索过程的本质：选择采取具体的动作向目标逼近。此处可进行知识拓展：形式化表示是使用计算机进行自动化问题求解的基础BFS和DFS的区别？堆栈和队列！引导学员回顾算法课程知识点回顾刚才的示例，体会广度优先搜索算法课程思政：科学的探索永无止境，不能仅满足于找到解，更要追求最优解时空复杂度主要通过教学资源由学员课下自学完成。讨论：实际生活中是否总是会使用盲目式搜索求解？是