资源描述
,第一级,第二级,第三级,第四级,第五级,*,标题,用搜索解决问题,主讲：张家华,E-mail: zjnuzjh,浙江师范大学教育技术学系,全国高中AI课程研修班,主要内容,搜索及其类型,盲目搜索,宽度优先搜索,深度优先搜索,启发式搜索与博弈,上机实践,搜索及其类型,1、什么是搜索,人工智能所要解决的问题大部分不具备明确的解题步骤，而只能是利用已有的知识一步一步地摸索前进。,根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称之为搜索 。,搜索及其类型,2、可以用搜索解决的问题,8数码问题,猴子和香蕉问题,旅行商问题,走迷宫,博弈问题,规划问题,搜索及其类型,3、常用的搜索技术,盲目搜索,又称无信息/穷举式搜索，只能按照预先规定的搜索控制策略进行搜索，没有任何中间信息来改变这些控制策略。,具有盲目性，效率不高，不便于复杂问题的求解。,具体可以分为宽度优先搜索和深度优先搜索两种。,启发式搜索,在搜索求解过程中，根据问题本身的特性或搜索过程中所产生的一些与问题有关的启发性信息，指导搜索朝着最有希望的推理方向前进，加速问题的求解过程并找到最优解。,盲目搜索,宽度优先搜索,基本思想,从初始节点So开始，逐层地对节点进行扩展并考察它是否为目标节点，在第n层的节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。它是一种,先生成的节点先扩展,的搜索方法。,课件演示,8数码问题的宽度优先搜索过程,盲目搜索,宽度优先搜索示例,求解八数码问题,宽度优先搜索示例,8数码问题的宽度优先搜索树,盲目搜索,OPEN表,用来存放将要扩展的节点。,CLOSE表,在进行子节点的扩展时，为了避免同一个节点被重复扩展，可以把扩展过一次的节点，记录到CLOSED表中，从而使其不再成为以后扩展时的候选对象。,宽度优先搜索算法,盲目搜索,深度优先搜索,深度优先搜索中，搜索树是从树根开始一枝一枝逐渐生成的。它是一种,后生成的节点先扩展,的搜索方法。,基本思想：,从初始节点So开始，在其子节点中选择一个节点进行考察，若不是目标节点，则再在该子节点的子节点中选择一个节点进行考察，如果该子节点可以扩展，则扩展该子节点，依次向下搜索，在搜索树的每一层始终先只扩展一个子节点，如此一直向下搜索，直到某个子节点既不是目标节点又不能继续扩展时，才从当前节点返回上一级节点，沿另一方向又继续前进。,盲目搜索,深度优先搜索示例,求解八数码问题（课件演示）,深度优先搜索示例,8数码问题的,深度优先搜索树,深度优先搜索算法,盲目搜索,有界深度优先搜索,在深度优先搜索的基础上，,给出了搜索树深度限制,，当从初始节点出发沿某一分枝扩展到一限定深度时，就不能再继续向下扩展，而只能改变方向继续搜索。,算法示例,八数码问题(课件演示),启发式搜索,启发式搜索,是指在控制性知识中增加关于被解问题和相应任务的某些特性，利用启发性信息来确定节点的生成、扩展和搜索顺序，指导搜索朝着最有希望的方向前进的一类搜索方法。,启发式搜索的特点,大多是深度优先搜索的改进，即尽量沿着最有希望的路径，向深度方向小范围前进；,在有多条路可走时，会给出该走哪条路径的建议，从而指导搜索过程朝最有利的方向前进；,利用问题求解的先验知识，使之尽快找到问题的解；,可采用估值的方法进行搜索指导；,生成的状态空间小、搜索时间短且效率高、控制性好，易于使问题得到解。,启发式搜索,启发性信息的类型,有效地帮助确定扩展节点的信息，即用于决定应先扩展哪一个节点，以免盲目扩展。,有效地帮助决定哪些后继节点应被生成的信息，即用于决定应生成哪些后继节点，以免盲目地生成过多无用节点。,能决定在扩展一个节点时哪些节点应从搜索树上删除的信息，即用于决定应删除哪些无用节点，以免造成时空浪费。,估价函数,用来估价节点重要性的函数,f (n)=g (n)+h (n),g (n)是从初始节点So到节点n的已经实际付出的代价；,h (n)是从节点n到目标节点Sg的最优路径的估计代价,启发式搜索的算法,启发式搜索算法有很多种，如局部择优搜索、全局择优搜索等等 。右图表示了全局择优的启发式搜索流程 。,启发式搜索示例,设估价函数为,f (n)=g (n)+h (n)，,其中g (n)表示节点n的搜索深度，,h (n)表示节点n与目标节点两个棋局之间位置不相同的棋子数 。,每个节点左边的蓝色数字表示其估价值。,博弈与启发式搜索,博弈,诸如下棋、打牌、战争等一类竞争性的智能活动。,其中最简单的一种称为双方完备博弈。,博弈树,当某一方当前有多个行动方案可供选择时，他总是选择对自己最为有利而对对方最为不利的那个行动方案。,当轮到A方走棋时，则可供A方选择的若干个行动方案之间是“或”的关系。轮到B方走棋时，B方也有若干个可供选择的行动方案，但此时这些行动方案对A方来说它们之间是“与”的关系。,使用与或图（与或树）来表示博弈过程，叫做博弈树。,博弈与启发式搜索,博弈树的特点,博弈的初始格局是初始节点。,在博弈树中，“或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点之间是“或”关系，对方扩展的节点之间是“与”关系。双方轮流扩展节点。,博弈与启发式搜索,极大极小分析法,设博弈的双方分别为A和B，然后为其中的一方（如A）寻找一个最优行动方案。,为了找到当前的最优行动方案，需要对各个方案可能产生的结果进行比较，并计算可能的得分。,为了计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。,当端节点的估值计算出来后，再推算父节点的得分。,如果一个行动方案能获得最大的倒推值，那么它就是当前最好的行动方案。,博弈与启发式搜索,一字棋问题的求解,课件演示：一字棋,博弈与启发式搜索,一字棋问题的求解思路,设A的棋子用“a”表示，B的棋子用“b”表示。并设棋局为P，估价函数为e（P），其中：,（1）若P是A获胜的棋局，则e（P）=。,（2）若P是B获胜的棋局，则e（P）=-。,（3）若P是胜负未定的棋局，则e（P）= e（+P）- e（-P）。,其中e（+P）表示棋局上有可能使a成一线的数目；e（-P）则表示棋局上有可能使b成一线的数目。,博弈与启发式搜索,一字棋的极大极小搜索（第一回合）,博弈与启发式搜索,一字棋的极大极小搜索,综合实践与计算机下棋,与计算机下棋,P102综合实践4,画出博弈树,
展开阅读全文