《人工智能》教案第8课启发式搜索策略

点略2课时(90min)知识技能目标： (1)了解启发式搜索策略 (2)掌握A搜索和A*搜索等启发式搜索策略。思政育人目标： (1)了解科技前沿新应用，开阔视野，抓住机遇，展现新作为 (2)关心国家大事，抓住机遇，展现新作为，增强爱党、爱国情感 (3)弘扬精益求精、科学严谨、追求卓越的工匠精神A索A授法、讨论法、问答法计算机、投影仪、多媒体课件、教材课前任务→考勤(2min)→问题导入(3min)→传授新知(50min)→新知导入(3min)→课堂实训(20min)→课堂练习(7min)→课堂小结(3min)→作业布置(2min)主要教学内容及步骤设计意图 (2min) (3min)【教师】布置课前任务，和学生负责人取得联系，让其提醒同学通过APPAPP签到。通过课前学生过问题导入的方法， (50min)4.1推理概述启发式搜索策略2略有A搜索和A*搜索。【教师】讲解卓越创新相关内容发性信息和估价函数 的下一个节点，避免盲目地扩展节点。 (2)在扩展节点的过程中，用于决定生成哪些后继节点，避免盲目地 (3)用于确定应从搜索树中修剪或删除的节点，避免盲目地保留“最估通过教师师结合f(n)=g(n)+h(n)G现【教师】提醒：。A搜索“A搜索”，了解知识解知识在搜索过程中利用估价函数f(n)=g(n)+h(n)对OPEN表中的节点进行【教师】提醒：一个节点的估价函数值f(n)=g(n)+h(n)越小，则作为下一个考察根据启发式搜索过程中选择扩展节点范围的不同，可将A搜索分为全PPT知识讲解全局择优搜索的基本思想是当确定下一个扩展节点时，利用估价函数择一个f(n)值最小的节点作为下一个要考察的节点。由于该搜索是在PPT进行提问f(n)定义为f(n)=g(n)+h(n)，g(n)表示猫从节点A到节点n的实际，“2”表示默认任意两个节点间的体力消耗值都为2。例如，节点K (1)把起始节点A放入OPEN表中，计算估价函数值 (3)把OPEN表中的第一个节点(记为节点n)移出，并放入CLOSED (4)判断节点n是否为目标节点，若是，则求得问题的解，成功退出；否则转向(5)。节点A不是目标节点。 (5)判断节点n是否可扩展，若可扩展转向(6)；否则转向(2)。 (6)扩展节点n，计算所有后继节点的估价函数值f(n)，并提供从这 】展示表格“OPEN表和CLOSED表的状态变化”，讲解过程44GfGPPT举例说明从表4-4可以看出，在第5次循环中，步骤(4)判断的节点n是目标节点O。此时，找到一个解，成功退出。便可得到猫捉老鼠的捕捉路线为PPT进行讲解个后继节点的估价函数值f(n)，并在这些后继节点中选择一个f(n)值最部【教师】提出问题：提出的问题nO (1)把起始节点A放入OPEN表中，计算估价函数值 (3)把OPEN表中的第一个节点(记为节点n)移出，并放入CLOSED 否则转向(5)。节点A不是目标节点。 (5)判断节点n是否可扩展，若可扩展转向(6)；否则转向(2)。 (6)扩展节点n，计算所有后继节点的估价函数值f(n)，并提供从这 入OPEN表的前端，最后转向(2)。对后继节点B和C排序得到的节点顺】展示表格“OPEN表和CLOSED表的状态变化”，讲解过程从表4-5可以看出，在第5次循环中，步骤(4)判断的节点n是目标节点O。此时，找到一个解，成功退出。便可得到猫捉老鼠的捕捉路线为4.3.3A*搜索生扫描二维码“A*搜索”，了解知识fngn+h(n)中的启发函数h(n)加上限定条件，即h(n)h*(n)，对所有节点nA到最优解，保证A*搜索找到最优解 (1)搜索树中存在从起始节点到目标节点的最优路径。 (2)问题域是有限的。 (3)所有节点的后继节点的搜索代价值大于0，即两节点之间弧线的 【教师】提醒：若A搜索中估价函数f(n)=g(n)+h(n)中的启发函数h(n)满足条件6使用A*搜索求解例4-4的步骤如下。其中，估价函数f(n)定义为耗估计值。定义h(n)=1i，其中i表示从节点n到目标节点O的节点个】提醒：启发函数h(n)的设计源于对问题自身特性的认识，依据这些特性加快K A (3)把OPEN表中的第一个节点(记为节点n)移出，并放入CLOSED (4)判断节点n是否为目标节点，若是，则求得问题的解，成功退出；否则转向(5)。节点A不是目标节点。 (5)判断节点n是否可扩展，若可扩展转向(6)；否则转向(2)。 (6)扩展节点n，计算所有后继节点的估价函数值f(n)，并提供从这 大的顺序对OPEN表中的全部节点进行排序，最后转向(2)。将节点B和师】展示表格“OPEN表和CLOSED表的状态变化”，讲解过程点O。此时，找到一个解，成功退出。便可得到猫捉老鼠的捕捉路线为【教师】展示图片*搜索树”，讲解过程7A*搜索具有下列性质。 (1)可采纳性。对于一个可求解的问题，如果一个搜索算法能在有限 (2)单调性。所谓单调性是指在A*搜索中，如果对其估价函数中的启发性函数h(n)加上适当的单调性限制条件，就可以减少对OPEN表或 (3)信息性。所谓信息性就是指比较两个A*搜索的启发函数h(n)1和h(n)，如果对搜索空间中的任一节点n都有h(n)h(n)，就代表212搜索策略h比h具有更多的信息性。21迷宫寻路【教师】展示图片“迷宫地图”，进行提问：， (1)启发式搜索的关键是定义启发式函数，本问题的启发式函数定义ngnhn不考虑路径是否可通行的情况下，当前节点到目标节点所在行的纵向距离。 (2)使用局部择优搜索解决此问题的步骤如下。在行的纵向距离h(A)=4，将节点A放入OPEN表中，计算估价函数值③把OPEN表中的第一个节点(记为节点n)移出，并放入CLOSED】展示表格“OPEN表和CLOSED表的状态变化”，讲解过程8循环执行上述操作，其OPEN表和CLOSED表的状态变化如表所示。 (3min) (20min)K成功退出。便可得到从迷宫入口到出口的最短路径报告4.4本章实训：沙漠寻宝 (1)熟悉状态空间表示法。 2)掌握状态空间图的绘制方法。 理解并掌握基于状态空间图的不同搜索策略的基本思想。 (1)要求每一步都落在方格中。 (2)地图中黑色的格子表示无法通行的障碍，标记叉号的格子表示沙。 过导入趣通过课堂法9 (4)在一些代表特殊地形的格子上行走要花费额外的地形代价。例如， (5)一条路径总的代价为移动代价与地形代价之和。其中，移动代价 (1)简述不同算法求解沙漠寻宝问题的思想。 (2)针对沙漠寻宝问题，比较不同的算法对解题效率的影响。 (3)设置不同的启发函数求解沙漠寻宝问题。 (1)宝藏地图是一个二维平面，可用一个二维数组表示，并将该地图存储在计算机中。其中，用0表示普通地形，用2表示溪流，用4表示沙 (2)采用全局择优搜索算法求解沙漠寻宝的最短路径。定义启发式函fngnhn其中，g(n)代表已走过的真实距离，h(n)表示不考虑路况问题时，当前节点到目标节点的最短距离。【教师】提醒：数时更加看重实证得到的解是最优解。 (3)根据规定的行动规则，开始沙漠寻宝，其主要流程如下。③把OPEN表中的第一个节点(记为节点n)移出，并放入CLOSED⑦把这些后继节点都送入OPEN表中，然后按照估价函数值从小到 图。 (2)编写程序实现迷宫寻路，并提交源代码。 (1)下列说法正确的一项是()。 (7min) (2)在搜索过程中，利用与问题有关的信息，引导搜索朝最有利的方向进行，加快搜索的速度，提高搜索效率是()。通过课堂 的信息，引导搜索朝最有利的方向进行，提高搜索效率。常用的启发式搜索