资源简介

(共44张PPT)
2.1 搜索算法
电子工业出版社 第五册
情境描述
在生活中，我们常常会遇到寻找最佳路线的问题。要找到一条最佳路线，需要一定的方法和大量的计算。电子地图能够快速地找到一条最佳路线并推荐给客户，因为它有一套自己的寻找方法，即人工智能搜索算法。本节让我们一起来了解经典的搜索算法吧!
情境描述
教学目标
1、信息意识：能够识别、评估和利用不同来源的信息，包括数字、文本、图像等形式的信息。
2、计算思维：能够通过编程和算法设计，培养逻辑思维和创新能力运用计算思维的方法解决问题。
3、数字化学习与创新：能够在数字化学习和创新中培养批判性思维、解决问题的能力和创造力。
4、信息社会责任：能够理解信息技术对个人、社会和环境的影响，认识到使用信息技术需要遵循道德和法律准则。
活动1
寻求最佳路线
新知讲解
1．外卖的出现给人们的生活带来了极大的便利，外卖员为了尽快把外卖送到客户的手上，一定想走一条最近的路线。
实践探究1
2、列出从 A到G的所有路线。如果不考虑客户之间的距离，仅仅考虑经过客户数的多少，你推荐外卖员走哪条路线
所有路线：
推荐路线：
1 A-B-E-G 4 A-B-D-C-F-G
2 A-C--F-G 5 A-C-D-F-G
3 A-B-D-F-G
A-B-D-F-G 如果不考虑客户之间的距离，仅仅考虑经过客户数的多少，这条路是最合适的。
实践探究2
2.1、请你用数字标出深度优先搜索顺序。
实践探究2
2.2、请你用数字标出广度优先搜索顺序。
实践探究2
3、深度优先搜索算法和广度优先搜索算法的不同之处
不同之处：
DFS和BFS是两种不同的图搜索算法，DFS以深度优先原则进行搜索，使用栈来实现；BFS以广度优先原则进行搜索，使用队列来实现。它们的搜索顺序、存储结构、遍历方式和应用场景都有所不同，因此在具体问题中选择合适的搜索算法可以提高效率和准确性。
1
在进行归纳推理时，如果逐个考察某类事件的所有可能情况，从而得出可靠结论，那么该结论就是可靠的，这种归纳方法叫作穷举法。深度优先搜索算法和个度优先搜索算法属于穷举搜索算法。
穷举搜索算法
助力知识
以深度为优先，对路线进行穷举搜索。 从当前节点开始，先标记当前节点，再寻找与当前节点相邻的未标记的节点，如果当前节点不存在下一个节点，则返回前一个节点进行搜索。
深度优先搜索算法
助力知识
广度优先搜索算法如其名字一样，是以广度为优先，一层一层搜索下去的，它总是先访问同一层的节点，然后才继续访问下一层的节点。广度优先搜索算法的优点之一是搜索完所有节点所用的时间较短。
广度优先搜索算法
助力知识
无论使用深度优先搜索算法，还是广度优先搜索算法，都可以找到最短路线，但是如果我们在一个包含数千个节点的较大地图中搜索路线，使用这两种算法都难以高效地找到最短路线。
活动2
高效寻求最佳路线
新知讲解
1．节点之间都加上距离(单位为米)，求高效搜索最佳路径的方法。
新知讲解
2、贪婪搜索法获取路线
贪婪最佳优先搜索算法搜索得到的路线为：
这条路线的实际行驶距离为：
A-C-F-G
5700米
新知讲解
3、A*搜索算法获取路线
A*最佳优先搜索算法搜索得到的路线为：
这条路线的实际行驶距离为：
A-B-D-F-G
4270米
助力知识
启发式搜索算法是将当前与问题有关的信息作为启发信息的一种搜索方法。启发式搜索能对当前所有待选择的节点进行评估，选出一个最好的、最容易求出解的节点进行搜索。启发式搜索算法包括贪婪最佳优先搜索算法和 A*算法。
启发式搜索算法
助力知识
贪婪最佳优先搜索算法总是做出对当前来说最好的选择，即当进行每一步搜索时，都会查找相邻的节点，计算它们到目标节点的距离，然后选择距目标节点最近的节点作为下一个节点。通俗地说,这是一个“短视”的算法。
客户家 与G直线距离（米） 客户家 与G直线距离（米）
A 3600 E 1760
B 2500 F 1000
C 2400 G 0
D 1900
贪婪最佳优先搜索算法
助力知识
我们仅将每个客户家到 G 的直线距离作为唯一的启发式依据进行计算，贪婪最佳优先搜索算法不断地寻找当前h的最小值，用贪婪最佳优先搜索算法得到的路线为 A-C-F-G。这条路线的实际行驶里程数为2800+1800+1100=5700米。
贪婪最佳优先搜索算法
A*算法
A*算法不停地计算每个当前节点到起点的距离，同时也汲取贪婪最佳优先搜索算法中不断向目标前进的优点，持续计算每个节点到目标节点的距离，以引导搜索队列不断向目标逼近，从而在搜索更少节点的同时保持高效的路线选择。
A*算法
A*算法综合考虑节点几到起始节点的实际路线长度与节点n到目标节点的估计路线长度，我们仍然利用从 A到G的路线规划问题进行计算演示。图 2.1.5 所示为计算过程与结果，每个节点旁边为该节点当前的 F(n)值。
A*算法
小于使用贪婪最佳优先搜索算法搜索得到的实际行驶距离 5600。用A*算法得到的路线为 A-B-D-F-G，这条线路的实际行驶距离为 1400+800+970+1100-4270，而用 A*算法则可以在搜索尽量少的节点的同时保证找到最优路线(最短路线)。
活动3
拓展延伸
拓展延伸
1、讨论完成：现在地图软件用到了哪些算法，有什么作用？
算法 作用
最短路径算法 地图软件中最重要的算法之一，用于找到两点之间的最短路径。
路线规划算法 将起点和终点之间的路径规划为一个连续的路线。
可视化算法 地图软件通常需要将大量的地理数据可视化为易于理解的形式
实时更新算法 地图软件需要能够实时获取并更新交通状况、道路改建等信息
拓展延伸
2、讨论完成：现在地图软件根据什么来推荐路线？
算法 作用
最快路径 地图软件通常根据交通信息和实时数据计算最快的路径
最短路径 地图软件可以通过计算最短路径来满足这些用户的需求
实时交通信息 地图软件会收集实时交通数据，并考虑当前的交通状况来推荐路线
偏好设置 地图软件通常允许用户设置偏好，例如避免高速公路、选择步行或骑行等
项目实施
1、从图 2.1.6 中的A 点出发到达 G 点，请你分别用贪最佳优先搜索算法和A*算法找到最佳路线，并填写表 2.1.2。
算法 最佳路径
贪婪最佳优先搜索算法 A-C-F-G
或者
A-B-E-G
A*算法 A-C-F-G
或者
A-C-D-F-G
阅读材料
1、假设外卖员现在同时给 3 个客户送餐，他有 3 种选择，如图 2.1.7 所示。理想的解法就是在3 种选择里找到一条最近的路线，然后按照这个选择去送餐。
如果同时给 5个客户送餐，路线选择便有 60 种。
阅读材料
2、现在客户增加到10个,路线选择变成了多少种 答案是大于180万种外卖送餐问题实际上是一个典型的旅行商问题。
阅读材料
3．旅行商问题是指一个推销员要去一些城市推销产品，每个城市都去一趟，且不走回头路，他希望规划出一条最短的路线。旅行商问题在我们的生活中很常见，比如集成电路的设计和焊接问题、连锁超市的货物配送问题。
阅读材料
4、旅行商问题很难得到一个最优解。城市数量越多，解的数量更可能呈爆炸式增长。这个问题有解决方法吗 我们看一下动物界是怎么做的。蚂蚁是一种神奇的动物。蚂蚁团队不仅能做到逢山开路、遇水架桥，还能在没有设计师的情况下，建造一座庞大、精美的蚁穴。
阅读材料
5．不管食物和蚁穴之间有多少障碍物，蚂蚁都能找到回家的近路，这是怎么做到的呢 其实一开始，它们是随机选择路线的。蚂蚁在走路的时候会分泌一种叫信息素的物质，后面的蚂蚁会倾向于走信息素浓的那条路线。
阅读材料
6、蚂蚁在这条路线上往返的次数越多，这条路线上的信息素的浓度就越大。时间一长，所有的蚂蚁都自动集中到这条近路上了。不光蚂蚁有这种本领，蜜蜂在各个花朵和蜂巢之间，也会规划出一条比较近的路线，还有鱼群、萤火虫等都有类似的本领。人类模拟了各种各样的动物行为，发明了各种各样的算法。我们把这一类算法叫作智能搜索算法。
巩固练习
1.1 判断下列说法是否正确：
1、搜索算法是利用计算机的高速运算能力有目的地穷举一个问题的部分或者所有可能情况，从而求解问题的一种算法。( )
2、启发式搜索算法是将与当前问题有关的信息作为启发信息的一种搜索算法。( )
×
√
巩固练习
1.2 判断下列说法是否正确：
3、深度优先搜索算法和广度优先搜索算法是启发式搜索算法。( )
4、A*算法是一种启发式搜索算法。（ ）
×
√
巩固练习
2.关于启发式搜索的说法，正确的是：
A、启发式搜索能对所有当前待选择的节点进行评估，选出一个最好的、最容易求出解的节点进行搜索。
B、启发式搜索总是先访问完同一层的节点，然后才继续访问下一层的节点。
C.启发式搜索以深度为优先对图进行搜索。
答案是：C
巩固练习
3.1 画出你认为最佳的路线，说说你选择这条路线的理由。
理由：涉及的节点最少。
巩固练习
3.2 打开电子地图，输入出发地和目的地，选择相应的出行方式，查询电子地图推荐的路线。
巩固练习
3.3 对比你选出的路线与电子地图推荐的路线，找出异同点，找出电子地图的推荐理由。
不同：行进路线，转换方向次数不同。
相同：终点相同
理由：智能选择是没有红绿灯。
课堂总结
通过这门搜索算法课程，我们不仅掌握了多种搜索算法和优化技巧，还培养了分析和解决问题的思维方式。这些知识和技能对我们的学术研究和未来职业发展都有着重要的意义。我们对搜索算法有了更深入的理解，并且相信它会在我们的学习和工作中发挥重要的作用。
板书设计
搜索算法
一、寻求最佳路线
二、高效寻求最佳路线
三、算法演变
课后作业
1、搜索了解穷举算法？
2、搜索了解贪婪最佳优先搜索法？
3、搜索了解A*算法？
谢谢
21世纪教育网（www.21cnjy.com)
中小学教育资源网站
兼职招聘：
https://www.21cnjy.com/recruitment/home/admin中小学教育资源及组卷应用平台
信息技术 2.1 搜索算法
课题 搜索算法 单元 第二单元 学科 信息技术 年级 九年级
教材分析 信息技术是一门知识性、技能性与创新性相结合的学科。现阶段，信息技术教育的理念已发生了质的飞跃，从单纯的技能训练上升为全面的信息素养的培养。教材以提高全体学生信息素养、养成学生自主学习意识和能力、培养学生数字化创新精神，从生活中发现问题、明确任务、确立目标、分析任务。在探究过程中逐步找到解决问题的方法。实用的小技巧，适时点拨关键操作。旨在帮助学生掌握信息时代生存与发展必需的基础知识和基础技能，养成信息意识、计算思维、数字化学习与创新、信息社会责任的核心素养。
教学目标 1、信息意识：能够识别、评估和利用不同来源的信息，包括数字、文本、图像等形式的信息。2、计算思维：能够通过编程和算法设计，培养逻辑思维和创新能力运用计算思维的方法解决问题。3、数字化学习与创新：能够在数字化学习和创新中培养批判性思维、解决问题的能力和创造力。4、信息社会责任：能够理解信息技术对个人、社会和环境的影响，认识到使用信息技术需要遵循道德和法律准则。
重点 一、寻求最佳路线二、高效寻求最佳路线三、算法演变
难点 1、算法演变
教学过程
教学环节 教师活动 学生活动 设计意图
导入新课 在生活中，我们常常会遇到寻找最佳路线的问题。要找到一条最佳路线，需要一定的方法和大量的计算。电子地图能够快速地找到一条最佳路线并推荐给客户，因为它有一套自己的寻找方法，即人工智能搜索算法。本节让我们一起来了解经典的搜索算法吧。 观看视频了解生活中的搜索算法，思考地图如何运行 帮助学生理解人工智能搜索算法的含义打开课堂
讲授新课 一、活动1：寻求最佳路线1、外卖的出现给人们的生活带来了极大的便利，外卖员为了尽快把外卖送到客户的手上，一定想走一条最近的路线2．列出从 A到G的所有路线。如果不考虑客户之间的距离，仅仅考虑经过客户数的多少，你推荐外卖员走哪条路线。2.1 请你用数字标出深度优先搜索顺序2.2、请你用数字标出广度优先搜索顺序深度优先搜索算法和广度优先搜索算法的不同之处。穷举搜索算法：在进行归纳推理时，如果逐个考察某类事件的所有可能情况，从而得出可靠结论，那么该结论就是可靠的，这种归纳方法叫作穷举法。深度优先搜索算法和个度优先搜索算法属于穷举搜索算法。深度优先搜索算法：以深度为优先，对路线进行穷举搜索。 从当前节点开始，先标记当前节点，再寻找与当前节点相邻的未标记的节点，如果当前节点不存在下一个节点，则返回前一个节点进行搜索。广度优先搜索算法：广度优先搜索算法如其名字一样，是以广度为优先，一层一层搜索下去的，它总是先访问同一层的节点，然后才继续访问下一层的节点。广度优先搜索算法的优点之一是搜索完所有节点所用的时间较短。无论使用深度优先搜索算法，还是广度优先搜索算法，都可以找到最短路线，但是如果我们在一个包含数千个节点的较大地图中搜索路线，使用这两种算法都难以高效地找到最短路线二、活动2 高效寻求最佳路线1、节点之间都加上距离(单位为米)，求高效搜索最佳路径的方法。2．贪婪搜索法获取路线。3 ．A*搜索算法获取路线.启发式搜索算法：启发式搜索算法是将当前与问题有关的信息作为启发信息的一种搜索方法。启发式搜索能对当前所有待选择的节点进行评估，选出一个最好的、最容易求出解的节点进行搜索。启发式搜索算法包括贪婪最佳优先搜索算法和 A*算法贪婪最佳优先搜索算法：贪婪最佳优先搜索算法总是做出对当前来说最好的选择，即当进行每一步搜索时，都会查找相邻的节点，计算它们到目标节点的距离，然后选择距目标节点最近的节点作为下一个节点。通俗地说,这是一个“短视”的算法贪婪最佳优先搜索算法：我们仅将每个客户家到 G 的直线距离作为唯一的启发式依据进行计算，贪婪最佳优先搜索算法不断地寻找当前h的最小值，用贪婪最佳优先搜索算法得到的路线为 A-C-F-G。这条路线的实际行驶里程数为2800+1800+1100=5700米A*算法：A*算法不停地计算每个当前节点到起点的距离，同时也汲取贪婪最佳优先搜索算法中不断向目标前进的优点，持续计算每个节点到目标节点的距离，以引导搜索队列不断向目标逼近，从而在搜索更少节点的同时保持高效的路线选择A*算法：A*算法综合考虑节点几到起始节点的实际路线长度与节点n到目标节点的估计路线长度，我们仍然利用从 A到G的路线规划问题进行计算演示。图 2.1.5 所示为计算过程与结果，每个节点旁边为该节点当前的 F(n)值A*算法：小于使用贪婪最佳优先搜索算法搜索得到的实际行驶距离 5600。用A*算法得到的路线为 A-B-D-F-G，这条线路的实际行驶距离为 1400+800+970+1100-4270，而用 A*算法则可以在搜索尽量少的节点的同时保证找到最优路线(最短路线)三、活动3 拓展延伸1、讨论完成：现在地图软件用到了哪些算法，有什么作用？2、讨论完成：现在地图软件根据什么来推荐路线？四、项目实施1、从图 2.1.6 中的A 点出发到达 G 点，请你分别用贪最佳优先搜索算法和A*算法找到最佳路线，并填写表 2.1.2. 五、阅读材料 1、假设外卖员现在同时给 3 个客户送餐，他有 3 种选择，如图 2.1.7 所示。理想的解法就是在3 种选择里找到一条最近的路线，然后按照这个选择去送餐。如果同时给 5个客户送餐，路线选择便有 60 种。 2、现在客户增加到10个,路线选择变成了多少种 答案是大于180万种外卖送餐问题实际上是一个典型的旅行商问题 3、旅行商问题是指一个推销员要去一些城市推销产品，每个城市都去一趟，且不走回头路，他希望规划出一条最短的路线。旅行商问题在我们的生活中很常见，比如集成电路的设计和焊接问题、连锁超市的货物配送问题 4、旅行商问题很难得到一个最优解。城市数量越多，解的数量更可能呈爆炸式增长。这个问题有解决方法吗 我们看一下动物界是怎么做的。蚂蚁是一种神奇的动物。蚂蚁团队不仅能做到逢山开路、遇水架桥，还能在没有设计师的情况下，建造一座庞大、精美的蚁穴 5、不管食物和蚁穴之间有多少障碍物，蚂蚁都能找到回家的近路，这是怎么做到的呢 其实一开始，它们是随机选择路线的。蚂蚁在走路的时候会分泌一种叫信息素的物质，后面的蚂蚁会倾向于走信息素浓的那条路线 6、蚂蚁在这条路线上往返的次数越多，这条路线上的信息素的浓度就越大。时间一长，所有的蚂蚁都自动集中到这条近路上了。不光蚂蚁有这种本领，蜜蜂在各个花朵和蜂巢之间，也会规划出一条比较近的路线，还有鱼群、萤火虫等都有类似的本领。人类模拟了各种各样的动物行为，发明了各种各样的算法。我们把这一类算法叫作智能搜索算法六、巩固练习1.1 判断下列说法是否正确。2关于启发式搜索的说法，正确的是。3.1 画出你认为最佳的路线，说说你选择这条路线的理由？3.2 打开电子地图，输入出发地和目的地，选择相应的出行方式，查询电子地图推荐的路线3.3 对比你选出的路线与电子地图推荐的路线，找出异同点，找出电子地图的推荐理由 学生通过互相讨论，了解深度和广度算法，两者的不知处学生上网查阅资料，搜索对于贪婪和A*等搜索方法原理学生完成任务学生实践并总结实践的感受。学生阅读材料，和小组讨论了解旅行商问题.学生根据巩固练习完成题目，加深对知识的理解 帮助学生更多的思考穷举搜索的方法，以及深度和广度算法。通过网上资源的查找，帮助学生了解这两个搜索方法的执行方式。通过任务的方式，帮助学生养成解决问题能力。培养学生语言组织能力以及对于信息的采集和总结能力帮助学生团结互助，互相讨论进行思想风暴帮助学生记忆课堂知识
布置作业 1、搜索了解穷举算法？2、搜索了解贪婪最佳优先搜索法？3、搜索了解A*算法？ 完成作业 培养学生查阅资料的能力，分析解决问题的能力
课堂小结 通过这门搜索算法课程，我们不仅掌握了多种搜索算法和优化技巧，还培养了分析和解决问题的思维方式。这些知识和技能对我们的学术研究和未来职业发展都有着重要的意义。我们对搜索算法有了更深入的理解，并且相信它会在我们的学习和工作中发挥重要的作用。 分组总结归纳 锻炼学生的总结能力，逻辑思维、语言表达能力。
板书 一、寻求最佳路线二、高效寻求最佳路线三、算法演变 学习、记忆及勾画知识点 明确教学内容及重点和难点
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页）
HYPERLINK "http://www.21cnjy.com/" 21世纪教育网(www.21cnjy.com)

展开更多......

收起↑