（2024）人教版信息技术五年级全一册（26）寻找最短的路径-PPT课件

封面--字小魂萌趣 140 尔雅趣宋 60 第26课　学习目标 1 2 进一步了解规划算法的思想，体会把全局问题分解为局部问题的过程。 通过寻找最短路径的算法描述，初步了解路径规划算法的应用。 学习目标 3 第26课　课堂导入 问题情境 有一个街道地图，共有9个地点，路线正好能形成2行2列的网格。其中，每个点可以对应到不同地点。例如，起点是家，终点是学校，中间有超市、体育馆、公园、书店、博物馆等。 要求：这些道路都是单行线，在图上只能从左往右走或者从上往下走，不能反方向走。 求解：计算从起点走到终点的最短时间。 4 学习活动 一 用枚举法寻找最短路径 二 用分段用时寻找最短路径 第26课　学习活动 5 每条边上的数代表走这条路需要用的时间，如3代表3分钟。 一共有两类描述对象：一类是代表所需时间的边，另一类是用边连接的点，也就是地点。边一共有12条，点共有9个。　　 从起点出发到终点结束，只能走下方或者右侧的边。 一、用枚举法寻找最短路径 任务分析 第26课　学习活动 6 根据给定的图形，你能够列举出所有可能的路径吗？ 能找出用时最少的路径吗？ 解决问题的关键点是什么呢？ 分析思考 第26课　学习活动 一、用枚举法寻找最短路径 7 1．解决任务最简单的方法就是列举出所有的行走方法，计算时间后，找到用时最少的路径。 这样做存在的问题：种类多，容易有遗漏。 2．将全局问题转化为局部问题。 计算从起点到每个点的最少时间就是小问题。最终求得到终点的最少时间，即是全局问题的解决。 方法突破 第26课　学习活动 一、用枚举法寻找最短路径 8 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 最短路径是A→B→E→F→I，用时7分钟。 遍历所有路径 第26课　学习活动 一、用枚举法寻找最短路径 9 因此，要用一个计算次数尽可能少，且确保不会遗漏路径的算法。 　　人工用枚举法遍历寻找路径时，随着地点的增加，路径数量会迅速增加，逐个枚举就会很耗费时间，而且很容易遗漏一些路径。例如，要枚举右图所示的路径，操作起来就非常困难。 枚举法的局限 第26课　学习活动 一、用枚举法寻找最短路径 思考：用枚举法遍历存在什么问题呢？ 10 　　把计算整个地图最短路径的用时，转变为计算到具体一个点的最短路径的用时。 到一个点的用时最多有两个来源。 　　一是：上方节点用时+上方路径用时 　　二是：左方节点用时+左方路径用时 　　如果一个点有两个来源，那么选用时较少的一个。 问题分解 第26课　学习活动 二、用分段用时寻找最短路径 在圆圈中填写到该点的最短用时 11 起点A的用时记为0 B点只能从A点向右，最短路径用时为： 　左边A点的用时+A点到B点的用时 　表示为：A +( A→B) = 0 + 3 = 3 D点只能从A点向下，最短路径用时表示为： 　 A + (A→D) = 0 + 2 = 2 E点可以从B点向下，也可以从D点向右，表示为： 　 B +(B→E) = 3 + 1 = 4，D +(D →E) = 2 + 3 = 5 　 选较短的路径用时：B + (B→E) = 3 + 1 = 4 这样，局部的四个点的最短距离得以解决。 第1步：计算第一个局部。 局部问题解决 第26课　学习活动 二、用分段用时寻找最短路径 12 第二个局部只需计算两个点C和F。 C点只能从B点向右，表示为： 　 B + (B→C) = 3 + 2 = 5 F点可以从C点向下，也可以从E点向右，表示为： 　 C + (C→F) = 5 + 2 = 7 　 E +( E→F) = 4 + 2 = 6 　 选较短的路径用时，F点的最短路径用时为： 　 E + (E→F) = 4 + 2 = 6 第2步：计算第二个局部。 局部问题解决 第26课　学习活动 二、用分段用时寻找最短路径 至此，六个点的路径距离得以解决，局部进一步扩大。 13 第三个局部也只需计算两个点G和H。 G点只能从D点向下，表示为： 　 D + (D→G) = 2 + 3 = 5 D点只能从A点向下，表示为： 　 A + (A→D) = 0 + 2 = 2 H点可以从E点向下，也可以从G点向右，表示为： 　E + (E→H) = 4 + 1 = 5 　G + (G→H) = 5 + 3 = 8 选较短的路径用时：E + (E→H) = 4 + 1 = 5 第3步：计算第三个局部。 局部问题解决 第26课　学习活动 二、用分段用时寻找最短路径 14 第四个局部只剩下一个点I。 J点可以从F点向下或者从H点向右。 　F + (F→I) = 6 + 1 = 7 　H + (H→I) = 5 + 3 = 8 　选较短的路径用时，I点的最短路径用时为： 　F + (F→J) = 6 + 1 = 7 第4步：计算第四个局部。 局部问题解决 第26课　学习活动 二、用分段用时寻找最短路径 15 　获得到I点的最短路径用时为7，全局问题得以解决。 　 F + (F→J) = 6 + 1 = 7 局部问题解决 第26课　学习活动 二、用分段用时寻找最短路径 16 问题解决过程 第26课　学习活动 二、用分段用时寻找最短路径 17 导航系统 路径规划算法可以帮助导航系统找到两个地点之间的最短路径，并标注相应的路线，从而提供导航服务。 物流配送 在物流配送过程中，路径规划算法可以帮助物流人员确定最优的配送路线，从而节约时间和成本。还可以帮助物流企业规划仓库的位置，让仓库与客户的距离更近，提高配送效率。 最短路径算法的应用 第26课　学习活动 二、用分段用时寻找最短路径 18 电力网络 　　电力网络中的电线杆和变电站可以看作是节点，它们之间的电线可以看作是路径，路径规划算法可以帮助确定节点之间的最短电线布局，从而降低电力损耗和成本。 　　此外，路径规划算法还常用于城市规划、交通网络优化、通信网络设计等领域，帮助人们找到最优的路径，从而优化资源分配、提高系统效率。 最短路径算法的应用 第26课　学习活动 二、用分段用时寻找最短路径 19 　　 1．动态规划是将全局问题转化为局部问题，随着局部问题的解决逐渐扩大到全局问题的解决。 2．在解决局部问题时，可能会出现多个选择，需要抓住局部问题的关键特征，深入思考，进行局部的最优选择。 3．在现实生活中，路径规划算法应用广泛，它与我们的生活、工作和学习已经息息相关。 第26课　课堂总结 20 　　篮球赛中重要的就是队员互相配合。现在知道对方球队有著名的三人组，这三个人之间配合相当默契。假设三人分别为球员A、球员 B、球员C，在进攻时他们组成三角形进攻。请帮助我方球队分析，如果在一轮进攻中，球员A拿到球，然后把球传给球员 B或球员C，三人之间一共有10次传球，那么第10次传球仍然能传到球员A手中的可能性有多少种？　　 第26课　拓展与提升 打开配套资源中的程序，依据程序的提示，观察、运行程序，分析程序与算法的关系，感受利用算法求解问题的过程。 21 $$