资源简介

中小学教育资源及组卷应用平台
快递路线规划师——最短路径的算法
快递路线规划师——最短路径的算法
年级 五年级 章节 七单元
课时安排 本单元共3个课时
执教教师 学校
一、教学内容分析
本课选自五年级下册第七单元《快递路线规划师》的活动二：最短路径的算法。上节课学生学习了路径建模与计算，能读懂路线图并对路径长度进行计算和比较、排序。本课以“最短路径算法”为核心，聚焦迪杰斯特拉算法，主要讲解了迪杰斯特拉算法的应用场景、算法思想及程序实现。其中，理解“迪杰斯特拉算法的实现过程”是本节课的重点，而实现过程中“基于已有最短路径的从起点到其他点的路径的列举”和路径长度的计算与比较是难点。因此教师可以通过动画演示与实践探究相结合的方式，帮助学生一步步推导。
二、教学对象分析
本课面向五年级的学生，学生的认知发展正处于具体运算和形式运算的过渡期，能借助对直观表象的观察进行简单的推理，但归纳总结和演绎推导能力还不成熟。通过上节课的学习学生已能正确理解路线图并进行路径的列举和计算，但基于已有最短路径的从起点到其他点的路径的列举更抽象复杂，需借助可视化动画帮助学生建立抽象逻辑。
三、教学目标
信息意识：1.学生能够借助生活化实例的列举，意识到最短路径算法的适用场景。2.引导学生利用网络自学常见的其他最短路径算法，帮助学生树立利用信息手段解决学习和生活问题的意识。计算思维：1.通过思维导图展示迪杰斯特拉算法的算法思想，帮助学生建立算法逻辑。2.通过观察分析数据表与路线图的映射关系，理解计算机“读图”的过程。3.通过提出问题、分析问题、解决问题、验证结果正确性的流程，帮助学生树立计算思维和科学思维。数字化学习与创新：1.学生借助可视化动画演示，学习迪杰斯特拉算法“找路径、计算、比较、替换、更新”的实现过程。2.学生通过计算软件帮助快递员找到最短路径，感受算法和信息手段解决生活问题的便捷高效。信息社会责任借助生活实例，体验身边的算法，认识算法的重要性。
四、教学重点与难点
教学重点：理解迪杰斯特拉算法的算法思想和实现过程教学难点：理解计算机读图的过程；能用思维导图表示迪杰斯特拉算法的算法思想； 使用迪杰斯特拉算法“找路径、计算、比较、替换、更新”思想找出图中的最短路径；树立利用算法解决生活问题的信息意识
五、教学环境（软、硬件）
多媒体教室、WPS软件、计算软件程序
六、教学过程
教学环节 教师活动 学生活动 设计意图
课题导入 情境导入——快递员小李的烦恼快递员小李在大家的帮助下，快递派送的非常快，受到了附近村民的一致称赞。勤劳的小李想拓展业务，多负责几个村的快递派送。但是如何在复杂的地图中快速找到最短路径呢？1.衔接旧知：在路线相对简单的情况下，使用上节课我们学习的穷举法来寻找最短路径是可行的方法。但如果要在复杂路线中寻找最短路径，还需要更有效的方法和计算机的帮助。2.问题引导：借助计算机解决最短路径问题的前提是计算机能够识别地图，并能正确读图、析图。聪明的人类可以很快读懂路线图，“计算机是如何读图的？计算机又是如何寻找最短路径的？”让我们一起来学习：最短路径算法。 回顾旧知，积极思考 以生活化情境导入，让学生明确本节课的学习内容和用处。联系上一节课的内容，让学生复习路径的列举与计算，更快进入上课状态，为后面计算路径长度和比较做铺垫。
建构新知 计算机读图：用数据表格表示路线图计算机处理图相关的问题需要先将图转化为数据表1.观察发现：展示路线模型图和数据表，引导学生思考分析数据表中数据的具体含义。①交叉点数值表示：两点的直接连接距离②0表示：某点自己到自己的距离③很大的数如999表示：两点没有直接连通的路线④数据表中黄色和蓝色部分对称且意义相同，可以简化。2.讨论交流：组织学生去掉表格中含义相同的数据，将数据进一步简化。二、计算机析图：迪杰斯特拉算法帮助快递员寻找配送快递的最短路径，就是寻找从A点出发，去到B、C、D、E各地点配送快递的最短路径。如何使用迪杰斯特拉算法寻找最短路径？设置初始状态①动画演示：设计两个方框，分别保存已找到的最短路径和当前发现的路线。 ②讨论交流：列举从起点A开始，与起点A相关的路线。③动画演示：将与起点A相关的路线放入橙框。AB=12 AC=3AD=999 AE=999寻找第一条最短路径①组织学生对橙框里的路线排序。 ②动画演示：将最短的路线移入蓝框。寻找第二条最短路径①重新计算路径长度。计算起点A通过已知最短路径“AC=3”到达其他点的长度。ACD=AC+CD=3+999=1002ACE=AC+CE=3+6=9ACB=AC+CB=3+5=8②动画演示：比较新路径与原路径，用更短的新路径代替原路径。用ACB替换AB ACE替换AE③将橙框中的最短路径ACB移到蓝框中，确定为第二条最短路径。组织小组探究：引导学生按同样的方法继续寻找其余最短路径，直到橙框里的路径为空。教师讲解与学生代表发言相结合，找出剩余的最短路径①计算ACBD和ACBE的路径长度，与AD ACE比较，用ACBD替换AD，第三条最短路径是ACE=9;②计算ACED的路径长度与AD进行比较，用ACED替换AD，第四条最短路径是ACED=13。③问题解决：橙框中的路径即为A到各点的最短路径，所以快递员可以按下列路线最快将快递送到各个地址。AC=3 ACB=8ACE=9 ACED=136.总结归纳：用思维导图概括迪杰斯特拉算法的实现过程。7.观察验证：从起点A到目的点D的最短路径是A→C→E→D，长度为13。观察P54路线图并验证这个结论。 1.小组讨论：观察分析数据表与路线图的映射关系，思考数据表中各个数据的具体含义2.简化表格1.列举从起点A开始，与起点A相关的路线。 2.认真学习动画，按照步骤和要求找到第一条最短路径3.重新计算路径长度4.比较新旧路径5.寻找第二条最短路径 小组探究：掌握迪杰斯特拉算法的实现过程，按照学习步骤继续寻找最短路径，直到橙框为空。7.小组代表发言，介绍寻找最短路径的过程8.梳理迪杰斯特拉算法的核心思想9.看图验证使用迪杰斯特拉算法寻找最短路径的正确性 教师抛出问题，学生自主观察探索路线模型图与数据表的映射关系，让学生在主动思考和学习中理解数据表格中各个数据的含义，理解计算机读图的方法。利用wps动画演示找路径、计算、比较、替换、更新的过程，让学生直观的感受迪杰斯特拉算法的实现过程教师重点讲解前两条最短路径的寻找方法，后面两条路径让学生小组合作探究寻找，让学生在自主探究中更深刻的理解迪杰斯特拉算法的核心思想让学生验证最短路径的正确性，让学生在提出问题、分析问题、解决问题、验证结果的流程中树立严谨的科学思维和计算思维。
探究实践 三、体验计算机寻找最短路径——迪杰斯特拉算法的程序实现师：“刚才使用迪杰斯特拉算法找到了由五个地点构成的地图的最短路径。如果地址很多,我们手动列举就会变得很困难且容易出错。该怎么高效找出复杂地图中的最短路径呢？这时候就需要请出我们的‘智能助手’——计算软件！”可视化演示：打开计算软件程序，输入点的数量及各点之间的距离，输入出发点和目的点，点击开始计算。便能得到最短路径的长度和具体路径。计算机程序算法的优势：人工推算最短路径的方法效率低，易出错。通过计算机编程实现算法，可以快速运算出结果，极大地提高效率，解决更复杂的路径查找问题。 按照步骤运行计算软件，寻找不同地图的最短路径2.修改数据并运行程序 让学生在程序中操作，感受使用计算软件寻找最短路径的便捷和高效，感受算法和信息手段给我们生活带来的便利。同时，帮助学生树立遇到问题能思考如何利用算法和信息手段解决的信息意识。
课堂总结，练习提升 练习提升完成P56页习题。开拓视野除了迪杰斯特拉算法之外，还有很多类似的最短路径算法，如：弗洛 伊德算法、贝尔曼-福特算法（Bellman—Ford）和 SPFA 算法等。这些算法各有特点，可满足不同的需要。在现实生活中，最短路径算法的应用非常广泛，比如手机导航、城市道路规划和网络通信等。课堂总结本节课我们在“帮助快递员寻找配送快递的最短路径”这一真实问题情境驱动下，探索了借助迪杰斯特拉算法寻找最短路径的实现过程，并使用计算软件直观体验了迪杰斯特拉算法的程序实现。生活中还有很多“最短路径算法”的应用场景，希望同学们能将算法思维代入真实问题情境，灵活使用迪杰斯特拉算法解决“求最短路径”的问题，并积极探索其他最短路径算法，思考不同算法的不同适用场景和优缺点。课后练习上网查找资料，分析常见的四种最短路径算法的适用场景和优缺点。 1.完成练习提升习题 2.查找资料学习其他最短路径算法，明确最短路径算法的应用场景3.梳理本课学习内容 帮助学生将零散的知识点串联成完整的认知体系，强化对最短路径算法核心思想的理解通过生活场景的联结，引导学生将课堂所学与真实世界建立联系，培养他们用计算思维解决实际问题的意识，体现“从生活中来，到生活中去”的教学理念。拓展视野与课后练习，引导学生去学习其他常见的最短路径算法，有利于拓宽学生视野、提高学生自学能力。
七、板书设计
八、教学反思
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页）
HYPERLINK "http://21世纪教育网(www.21cnjy.com)
" 21世纪教育网(www.21cnjy.com)

展开更多......

收起↑