第26课 寻找最短的路径（教学课件）信息科技人教版五年级下册（新教材）

第7单元 了解更多的算法 寻找最短的路径 第26课 人教版·五年级 学习目标 01 课堂导入 02 新知探究 03 知识总结 04 智慧挑战 05 兴趣园地 06 目录 CONTENTS 2 PART 1 学习目标 进一步了解规划算法的思想，体会把全局问 题分解为局部问题的过程。 学习目标 通过寻找最短路径的算法描述，初步了解路 径规划算法的应用。 PART 2 课堂导入 课堂导入 日常生活中，人们出门时，常常用导航软件查询线路并选择到达目的地的方式。本课通过在一个简单地图上寻找最短的路径，体会相关的算法。 寻找最短路径 PART 3 新知探求 新知探究 学习活动1 活动1：用枚举法寻找最短路径 新知探究 学习活动1 用枚举法寻找最短路径 情境分析 有一个街道地图，共有9个地点，路线正好能形成2行2列的网格。其中，每个点可以对应到不同地点。例如，起点是家，终点是学校，中间有超市、体育馆、公园、书店、博物馆等。 每条边上的数代表走这条路需要用的时间，如 3 代表 3 分钟。这些道路都是单行线，在图上只能从左往右走或者从上往下走，不能反方向走。 计算从起点走到终点的最短时间 新知探究 问题分析 用枚举法遍历所有可能的路径 最短路径是 A→B→E→F→I，用时7分钟 A → B → C → F → I 3 + 2 + 2 + 1 = 8 A → B → E → F → I 3 + 1 + 2 + 1 = 7 A → B → E → H → I 3 + 1 + 1 + 3 = 8 A → D → E → F → I 2 + 3 + 2 + 1 = 8 A → D → E → H → I 2 + 3 + 1 + 3 = 9 A → D → G → H → I 2 + 3 + 3 + 3 = 11 学习活动1 用枚举法寻找最短路径 新知探究 更多地点的最短路径 人工用枚举法遍历寻找路径时，随着地点的增加，路径数量会增加更多，逐个枚举就会很耗费时间，而且很容易遗漏一些路径。 用遍历的方法列 举以下路径，你还能完全列举出来吗? 学习活动1 用枚举法寻找最短路径 新知探究 学习活动2 活动2：用分段用时寻找最短路径 新知探究 把计算整个地图最短路径的用时，转变为计算到具体一个点的最短路径的用时。用圆圈中的数表示从起点到该点的最短用时。 学习活动2 用分段用时寻找最短路径 转变思路后，到一个点的用时最多有两个来源： 上方节点用时 + 上方路径用时 左方节点用时 + 左方路径用时 如果一个点有两个来源，那么选其中用时较少的一个。 新知探究 （1）起点A的用时记为0 01 计算第一个局部，A、B、D、E 四个点 学习活动2 用分段用时寻找最短路径 具体操作步骤 （2）B点只能从A点向右，最短路径用时为：左边A点的用时+A点到B点的用时 （3）D 点只能从 A 点向下，最短路径用时为：A +（A → D）= 0 + 2 = 2 （4）E 点可以从 B 点向下，也可以从 D 点向右，分别表示为： 　　 B +（B → E）= 3 + 1 = 4 　　 D +（D → E）= 2 + 3 = 5 2 4 选较短路径用时：B +（B → E）= 3 + 1 = 4 新知探究 （1） C 点只能从 B 点向右，最短路径用时为：B +（B → C）= 3 + 2 = 5 02 计算第二个局部 C 点和 F 点。 学习活动2 用分段用时寻找最短路径 具体操作步骤 （2）F 点可以从 C 点向下，也可以从 E 点向右，分别表示为： 　 C +（C → F）= 5 + 2 = 7 　 E +（E → F）= 4 + 2 = 6 2 4 6 5 选较短路径用时：E +（E → F）= 4 + 2 = 6 新知探究 （1）G点只能从D点向下，最短路径用时为：D +（D→G） = 2 + 3 = 5 03 计算第三个局部 G 点和 H 点 学习活动2 用分段用时寻找最短路径 具体操作步骤 （2）H点可以从E点向下，也可以从G点向右，分别表示为： 　　E +（E→H） = 4 + 1 = 5 　　G +（G→H）= 5 + 3 = 8 2 4 6 选较短路径用时：E +（E→H）= 4 + 1 = 5 5 5 新知探究 I 点可以从 F 点向下或者从 H 点向右。 　 F +（F → I）= 6 + 1 = 7 　 H +（H → I）= 5 + 3 = 8 04 计算第四个局部，只剩下 I 点 学习活动2 用分段用时寻找最短路径 具体操作步骤 2 4 6 选较短路径用时：F +（F → I）= 6 + 1 = 7 5 5 7 新知探究 最后获得结果： 学习活动2 用分段用时寻找最短路径 从起点到终点最短用时为 7 分钟，路径为 A → B → E → F → I 从上述分析可见，动态规划是将全局的大问题转化为局部的小问题，在逐步解决局部小问题的过程中解决全局大问题。 新知探究 学习活动2 用分段用时寻找最短路径 路径规划算法在现实生活中的广泛应用 在物流配送过程中，路径规划算法可以帮助物流人员确定最优的配送路线，从而节约时间和成本；还可以帮助物流企业规划仓库的位置，让仓库与客户的距离更近，提高配送效率。 物流配送管理 电力网络中的电线杆和变电站可以看作是节点，它们之间的电线可以看作是路径，路径规划算法可以帮助确定节点之间的最短电线布局，从而降低电力损耗和成本。 电力网络优化 路径规划算法可以帮助导航系统找到两个地点之间的最短路径，并标注相应的路线，从而提供导航服务。 导航系统应用 PART 4 知识总结 知识总结 计算从起点走到终点的最短时间 用分段用时寻找最短路径 用枚举法寻找最短路径 用枚举法遍历所有可能的路径 用枚举法存在的问题 PART 5 智慧挑战 2.小华要从学校走到图书馆，中间必须经过一个超市。他可以把整个路程分解为两段：从学校到超市，再从超市到图书馆。这种思考方式体现了哪种算法思想？ A. 随机尝试 B. 把大问题分解成小问题 C. 回溯 D. 递归 1.小红的家到学校有两条路：一条是直路但比较拥堵，另一条是弯路但畅通。她想找到一条用时最短的路径，这属于什么问题？ A. 最短路径问题 B. 最多路径问题 C. 最小成本问题 D. 最长路径问题 智慧挑战 智慧挑战 解析：小红的目标是找到“花费时间最少”的路线，这在数学和计算机科学中被称为“最短路径问题”。这里的“最短”不一定指距离最短，也可以指时间最短、成本最低等。 答案：A 解析：这种“化整为零、分步解决”的策略，正是规划算法中最核心的“问题分解”思想。它让复杂的问题变得清晰简单。 答案：B PART 6 兴趣园地 兴趣园地 篮球传球问题 篮球赛中，对方球队有著名的三人组，这三个人之间配合相当默契。假设三人分别为球员A、球员B、球员C，在进攻时他们组成三角形进攻。请帮助我方球队分析，如果在一轮进攻中，球员A拿到球，然后把球传给球员B或球员C，三人之间一共有10次传球。 A B C 传球路线： 球员 A 可以从球员 B、 C 处获得球。 球员 B 可以从球员 A、 C 处获得球。 球员 C 可以从球员 A、 B 处获得球。 某个球员获得球的可能性就是上一次传球时另外两个球员能获得球的数量之和。利用循环结构重复计算指定的传球次数，就可以获得球传到球员 A 手中可能的次数。 第10次传球仍然能传到球员A手中的可能性有多少种？ 谢谢 下节课见！ Thanks！ 人教版·五年级 $