义务教育版（2024）五年级全一册第26课《寻找最短的路径》课件(共23张PPT)

(课件网) 义务教育信息科技（2024）五年级　　　　　　　　　　 第1课时 第七单元　了解更多的算法 五年级下册 第26课　寻找最短的路径 1 2 进一步了解规划算法的思想，体会把全局问 题分解为局部问题的过程。 通过寻找最短路径的算法描述，初步了解路 径规划算法的应用。 学习目标 第26课　寻找最短路径 日常生活中，人们出门时，常常用导航软件查询线路并选择到达目的地的方式。本课通过在一个简单地图上寻找最短的路径，体会相关的算法。 第26课　课堂导入 问题情境 有一个街道地图，共有9个地点，路线正好能形成2行2列的网格。其中，每个点可以对应到不同地点。例如，起点是家，终点是学校，中间有超市、体育馆、公园、书店、博物馆等。 要求：这些道路都是单行线，在图上只能从左往右走或者从上往下走，不能反方向走。 求解：计算从起点走到终点的最短时间。 学习活动 一 用枚举法寻找最短路径 二 用分段用时寻找最短路径 第26课　学习活动 每条边上的数代表走这条路需要用的时间，如3代表3分钟。 一共有两类描述对象：一类是代表所需时间的边，另一类是用边连接的点，也就是地点。边一共有12条，点共有9个。　　 从起点出发到终点结束，只能走下方或者右侧的边。 一、用枚举法寻找最短路径 任务分析 第26课　学习活动 根据给定的图形，你能够列举出所有可能的路径吗？ 能找出用时最少的路径吗？ 解决问题的关键点是什么呢？ 分析思考 第26课　学习活动 一、用枚举法寻找最短路径 1．解决任务最简单的方法就是列举出所有的行走方法，计算时间后，找到用时最少的路径。 这样做存在的问题：种类多，容易有遗漏。 2．将全局问题转化为局部问题。 计算从起点到每个点的最少时间就是小问题。最终求得到终点的最少时间，即是全局问题的解决。 方法突破 第26课　学习活动 一、用枚举法寻找最短路径 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课　学习活动 一、用枚举法寻找最短路径 因此，要用一个计算次数尽可能少，且确保不会遗漏路径的算法。 　　人工用枚举法遍历寻找路径时，随着地点的增加，路径数量会迅速增加，逐个枚举就会很耗费时间，而且很容易遗漏一些路径。例如，要枚举右图所示的路径，操作起来就非常困难。 枚举法的局限 第26课　学习活动 一、用枚举法寻找最短路径 思考：用枚举法遍历存在什么问题呢？ 　　把计算整个地图最短路径的用时，转变为计算到具体一个点的最短路径的用时。 到一个点的用时最多有两个来源。 　　一是：上方节点用时+上方路径用时 　　二是：左方节点用时+左方路径用时 　　如果一个点有两个来源，那么选用时较少的一个。 问题分解 第26课　学习活动 二、用分段用时寻找最短路径 在圆圈中填写到该点的最短用时 起点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课　学习活动 二、用分段用时寻找最短路径 第二个局部只需计算两个点C和F。 C点只能从B点向右，表示为： 　 B + (B→C) = 3 + 2 = 5 F点可以从C点向下，也可以从E点 ... ...