第26课 寻找最短的路径（教学课件+运行程序）信息科技人教版五年级全一册

该小学信息科技课件聚焦路径规划算法，以“拯救公主”游戏情境导入，引导学生从枚举法尝试所有路径，到用动态规划分解子问题计算各点最短用时，构建从具体操作到抽象算法的学习支架。 其亮点在于游戏化任务驱动与生活应用结合，通过网格地图路径计算培养计算思维，借助程序实践提升数字化学习能力，导航、物流等实例增强信息意识。学生能在探究中掌握算法思想，教师可利用结构化资源高效开展教学。

当前路线A台用时分种 A起点 蘑菇城保历险记！ 游戏说明： 观察地图：左侧是玛丽的冒险地图，每个金币代表一个地 点。 选择路径：点击金币，玛丽会移动到该位置。注意：只能 向右或向下移动： 计算时间：路径上的数字代表所需时间。请在右侧表格中 记录你的探索路线和总用时。 寻找最优：尝试不同的组合，在底部写下你发现的最短路 径。 保存成果：完成后点击“保存研究成果”，将你的报告下载 为图片。 开始探索 经研究报告 五年级第七单元第26课《寻找最短的路径》课后练习 1.小明早上从家出发去学校，他用手机导航找到了花费时间最少的路线。这主要使用了哪种算法思想？（B） A. 枚举法 B. 动态规划 C. 排序算法 D. 加密算法 2.王老师要设计一个校园参观路线，希望每个班级走的路程最短。她决定先计算每个交叉口的最短时间。这种方法体现了什么算法思想？（B） A. 枚举所有路线 B. 将大问题分解为小问题 C. 随机选择路线 D. 只关注终点 3. 如果小区地图从3×3扩大到10×10，小红想用枚举法找最短路径，她可能会遇到什么困难？（C） A. 路径数量减少，很容易找 B. 路径数量不变，仍然简单 C. 路径数量快速增长，容易遗漏 D. 路径时间都变短了 4.小华在计算从家到商场的最短时间时，发现某个路口可以从上方或左方到达。他应该选择哪一条？（B） A. 时间更长的 B. 时间更短的 C. 随便选一条 D. 两条都走 5.快递员小张每天要送很多包裹，公司系统帮他规划了最短送货路线。这体现了路径规划在哪方面的应用？（A） A. 物流配送 B. 社交网络 C. 游戏设计 D. 天气预报 6.小红要去图书馆，她必须先经过一个十字路口，这个路口可以从学校方向来，也可以从超市方向来。她应该怎么选？（A） A. 选更快的来向 B. 选更慢的来向 C. 两个都试试 D. 随便选一个 7.小美的妈妈是物流公司经理，她使用系统为货车规划最短路线。这样做的目的是什么？（C） A. 增加油耗 B. 延长送货时间 C. 节约时间和成本 D. 让司机多走路 8.小华在做最短路径题目时，发现某个点只能从上方到达，不能从左方来。这种情况下，他的最短时间怎么算？（A） A. 只考虑上方来的时间 B. 只考虑左方来的时间 C. 随便选一个 D. 两个都加 9. 在城市交通规划中，工程师使用最短路径算法可以优化什么？（C） A. 公交车的颜色 B. 道路的红绿灯样式 C. 交通路线的布局 D. 车站的名称 10.小红在计算最短路径时，发现到F点可以从C点来，也可以从E点来。如果C点用时5分钟，C→F用2分钟，E点用时4分钟，E→F用2分钟，她应该选哪条？（B） A. 从C来，总时间7分钟 B. 从E来，总时间6分钟 C. 两条都一样 D. 两条都不选 11. 学校组织春游，老师希望从校门口到野餐区用时最少。如果老师先计算每个路口的最短时间，最后再算出总时间。这种方法叫什么？（A） A. 动态规划 B. 枚举法 C. 随机法 D. 倒推法 12.学校组织秋游，景点之间的道路图有2个奇点。老师想设计一条不重复走每条路的路线，应该从哪里出发？（C） A. 任意景点 B. 偶点景点 C. 奇点景点 D. 集合点 13.小红想从家到电影院，她必须先经过一个十字路口。这个路口的最短时间是如何确定的？（B） A. 随机猜测 B. 从可能到达的方向中选择时间最短的 C. 只考虑左边来的 D. 只考虑上边来的 14. 小琪在玩一个手机游戏，游戏里每走一步都会消耗不同的体力值。她想用最少的体力走到终点。这个问题和教材中的什么问题最相似？（A） A. 找最短时间路径 B. 找最长路径 C. 随机走步 D. 走走停停 15.小晨在参加学校组织的定向越野比赛，地图上标出了每个路段需要的时间，他要用最少时间到达终点。他应该采用什么方法？（C） A. 随便选一条路 B. 走最短距离的路 C. 计算每段路的时间总和选最少 D. 走人数最多的路 学科网（北京）股份有限公司 $null活动深究 A起点 用时计过 分段法找路径！ 思路转变：把计算整个地图最短路径的用时，转变为计算 到具体一个点的最短路径的用时。 记录规则：用圆圈中的数表示从起点到该点的最短用时。 计算来源：到一个点的用时最多有两个来源： 一是：上方节点用时+上方路径用时 二是：左方节点用时+左方路径用时 保存成果：完成后点击“保存为图片”，将你的报告下载。 开始探索nullnull 1、 复制连接到浏览器打开：https://turtle.codemao.cn/&wd=&eqid=cef9ea30005068b1000000026576a7ad 2、点击“文件”图标--选择“导入作品(.tur/.py)”按钮 3、选择“1、学生文件 -- 3、三人传球训练【程序体验】--枚举法.py或者分段法.py”点击打开 4、导入成功之后点击右下角的“运行”即可运行程序。 学科网（北京）股份有限公司 $路径研究报告 探索路线 用时（分钟） A-D-E-H-1 9 A-D-E-F-I 8 A-D-G-H-I 11 A-B-C-F-I 8 A-B-E-F-I 7 A-B-E-H-I 8 最短的路径是： A-B-E-F-I 花费的时间是： 7 分钟1、进入问卷星官网，登录进入首页：https:www.wix.cnl 2、点击创建试卷 女问卷型 升级 角我的问5因讯示盟应用0●1847664247 十朗世网卷 N 问卷列表 ★星标同岩 八年级第三单元第一节《数据话信方式和协议》证 1D04156340。片发海答卷010月16日0036 言园收站 厚考试设计·算友这考试~口成6数g 0止口名轴自除口文件头自痘雅 ■文件夹 八年级第三单元第1节《数据通信方式和协议》深前小测⊙考击 D衣41360◆末发布答若010月1右日0阅32 房老试设计，发送考试。口成统8欢驱 。发布口特立除口文行液也英 从人工到白动北 D29952已有的2024127182 斯标 连续安化的数据恒 入门字了 0物止D转立口文件0 3、选择考试 女向若国 应用●184741247 法择应用场骨 创建调查72种概型，强大逻酒设造，支持打包抽奖零功了辉更多 旦直 日考试 从空白创建调查 文本导入调 Exce导入答卷 人工录入服务 口预袋 圆表单流程 为诺入闭白题 360评估 庄 日测评 县AN访谈 提民主评议 龙 复制模板问卷其包见户公世、关过参始回 日收就 全品大学生金业装合中场周盘产品周盘计会需学生有学校汽信行生周音NP5净粗拾油阳当满台应因情：员工继业应商件窝户满向度四种 大学生消捞信况洪有回弄 ■预约 大学生您装观州百 大学生网购问百可卷 大学生课外网陵情况调言 高户件给兰理 用g 9 墨NPS问卷调查 关于大学生况的查 大学生夜情况白 大子生生活共悄况明查 大学生流业向两 户满意皮调 共秘续 用 共 用 共5理 人各户旅程管理 企业员工满度查问岩 企业员工将需求诚问光 员工裤利制资建设情况调查 员工对食满忘瘦的调查问 4、从文本导入考试 女问卷星 升级A我问4调讯灵安用厚单●184764247， 选择应用场景 创建考试支对，实时动名，防作，两第更多 日调查 回考试 从空哈创楚 文本导入专过 Excel导入考试 人工录入服务 日投票 日表单流程 前人考诚标额 ●360度评估 多创电方法 日测萨 马A时谈 发民主评议 接龙 复制模板问卷货太明户公开的可色.过越水4慢回 收款 全学校企业考知完三试证试 ☐预的 制三数学4日一考过者 语文字测考试 化学期中考试 地进考试 =101 盘NPS问#海疮 生物南中传试 初一历史期中考式 企业文化艳老试 新员工入甲考试 是客户满意度网查 共 A客户旅程管理 企组织发展阻关制府考出 企业人力盗江管理考缸试 公司业资知识考过 安全生产灯识考试 5、选择word文档 ☆问卷品 因讯录 ●1847041247 复制War文 复制本 上传Fxne文档 指式示清空文木 在线考试 1.我的火等标中导0？·分 在线考试 OA.110 1我的火报要电话是(C)?甲选 ○B.120 A110 D.120 ⊙D.91 0.911 答案期折：我国的火答报部电话是19。 解析：我四的火等银电是119. 2.四大文朝古西叶的，四大文阴是下选项中的哪四个AB0E)?多选题 2.四大文明古国中的，国大文明显下列法项叶能四个07·6分剑 A及文明 上.印其文明 应A按及文动正海济客 G.中之明 D.希世文明 四众，中国文的（正瑰停案 E,兰李不达米亚文明 口D.希文明 解析：传统认为，四大勇分足中国.埃及印底束两两胞域的关素不达米亚 不达米亚文明正答 3.《出师表》中，先会未半，而中道的册中的先帝“足刘流。《对 符率寒听：传统认为，网大文明盼别是中回，埃及印应和两可流城的关不达米亚。 4.(使》的作者景？随空网 答安：司马注 3,《出表》中，先帝创柴未半，而中道响阳中的先帝是后刘备。·别 6、上传word文档（文件夹已经有本次测试题的word文档，直接导入即可） 女问军 升级角我的可名因延球日豆用09鲁●1B47641247, 复却Mod文本 复ExC文本上传Exce文档 第一步： 第二步 将逐的文档按根区中的格式测整时 上war文猫 格式说 片医片入其中， 要用 4重要提示银据中国相关法规和庄管部门发求，不允许发布与攻治、军束，家放，信和，民法，人权。民主，固家主权。国家统一、外文率件等招关的嫩话远调查，您市解1 7、点击继续编辑 女问装国 角找的因地录应用导84741247 复Nord文本 上传Word文档 制Exce文本上传Exce文档 八年级第三单元第一节《敏据通信方式和协议》 1构物联网的信系统通可分为高量通位系统1分和屋通翠分· 2数造结有不同的分类标准，按传介质类型分类，运还佰方式可以分为有线信：分和无信：份两类” 3有线语供是过物理煤介：分使如网.电聪或光灯传的方式。日有速率高连料定抗干能力强等特点，有线通信通学需 安线：安装济，不利于设的动后者， 4常见的为线通后方式布0·5分 ☑大网位桌 口同电能正请答 庭统垢旗同略 山正事振示：根恤中相关法切和丰管部门唐求，不允许发布与西治军率.六教，信仰，民技，人权民主。国家主极，闲衣统一、外交事件等相关的法话获河吉，诗能本经！ 8、 点击完成编辑 试去8分的分1慰目数：20。迎片他机设适。考试凉用设适白家水统通号卫解白带题号随汉塘少计件公式总览 a ·考生信息 八年级第三单元第一节《数据通信方式和协议》 A姓名 名部门 品 日手机 回其它信则 ⑨落行贺喻 添加问说明 量企业行8 看多试新设塞|效奥示丽 考试型 ●考试讯选 ￥考远判世 √考试够选 日优妈范 工单筑空 《)些项明空 多文件 ·分灭说明 1,构成物联网的通信系统通常可分为高层通信系统1分和底层通信系统1分 分 T设落院明 2,数据通信有不同的分类标准，按传输介质类型分关，数据通信方式可以分为有线通行，份和 无线酒信1分两类 9、发布问卷 八年级第三单元第预卷 88 B 出同飞处于草裤状态，如果您的准备就 可以 发布何 发这考行 自定义成结单 可设成绩单贞面的显示元志，如答冠人得分.韩老.答案篇折.评语等立设 可以进入卷页面，进行问内容的格改和加司齿症资录 导出间#do 可以将绵辑打的问卷内容出到wOd 然控2 可以硬立结选规到，业古为原和济项设置理维 a 维皮设置云 将多个远日绑定到一个维度，名维食权正古比等，可以在报告中豆示名个唯竞的得分 。 10、 复制链接给学生即可 合 八年级纳三单元第，，跑阿港 问卷链接与二维钢 l:/.wx.com/vm/on510.upx 爱制打开设红包品 友成古想 制作海服 四 注义交四之 图以不爱深看器比分开妆欧客。 自定义适速数 亚定义数数 嵌入式部署。 e 荧入页座高宾：自适放问指京府， h-Teossou 三制代码 amc入null活动深究 A起点 用时计过 分段法找路径！ 思路转变：把计算整个地图最短路径的用时，转变为计算 到具体一个点的最短路径的用时。 记录规则：用圆圈中的数表示从起点到该点的最短用时。 计算来源：到一个点的用时最多有两个来源： 一是：上方节点用时+上方路径用时 二是：左方节点用时+左方路径用时 保存成果：完成后点击“保存为图片”，将你的报告下载。 开始探索当前路线A台用时分种 A起点 D 蘑菇城保历险记！ 游戏说明： 观察地图：左侧是玛丽的冒险地图，每个金币代表一个地 点。 选择路径：点击金币，玛丽会移动到该位置。注意：只能 向右或向下移动： 计算时间：路径上的数字代表所需时间。请在右侧表格中 记录你的探索路线和总用时。 寻找最优：尝试不同的组合，在底部写下你发现的最短路 径。 保存成果：完成后点击“保存研究成果”，将你的报告下载 为图片。 开始探索 经研究报告nullnull 第26课 寻找最短的路径 第七单元 了解更多的算法 人教版信息科技五年级 1 目录 /CONTENTS 01 初入蘑菇城堡 【枚举法找路】 02 获得智慧神器 【动态规划法】 03 公主分享妙计 【路径算法应用】 04 终极通关庆典 【路径规划算法】 00 情景导入 拯救公主的蘑菇城堡历险记 在去往城堡的道路被划分成了许多网格，你需要从起点出发，用最短的时间到达城堡，拯救公主 亲爱的玛丽： 当你看到这封信的时候，我已经被坏蛋抓到城堡里，关在了城堡的最深处。 亲爱的玛丽：当你看到这封信的时候，我已经被坏蛋抓到城堡里，关在了城堡的最深处。 在去往城堡的道路被划分成了许多网格，你需要从起点出发，用最短的时间到达城堡，拯救公主。 过渡：我们先来看看通往城堡的道路吧！ 第一部分 01 学会用枚举法列出所有路径，找出最短路线，体会枚举法的局限性。 初入蘑菇城堡 01 初入蘑菇城堡 【枚举法找最短路径】 点 A 起点 B C 想要成功拯救公主，必须先熟悉通往蘑菇城堡的路线图 1 路线地图 左侧是蘑菇城堡的路线图，玛丽的起点在左上角，终点城堡在右下角，每个金币代表一个地点 2 路线选择 点击金币，玛丽就会移动到该位置，但这些道路都是单行线，只能从左往右走或从上往下走，不能反方向走 3 路径用时 路径上的数字表示经过该路径时所花费的时间。 如A→B 花费的时间就是3分钟 了解蘑菇城堡的路线图后，先来看看如何通往蘑菇城堡吧！ 想要成功拯救公主，必须先熟悉通往蘑菇城堡的路线图 左侧是蘑菇城堡的路线图，玛丽的起点在左上角，终点城堡在右下角，每个金币代表一个地点 点击金币，玛丽就会移动到该位置，但这些道路都是单行线，只能从左往右走或从上往下走，不能反方向走； 而路径上的数字表示经过该路径时所花费的时间。如A→B 花费的时间就是3分钟 过渡：了解蘑菇城堡的路线图后，先来看看如何通往蘑菇城堡吧！ 01 初入蘑菇城堡 【枚举法找最短路径】 还有哪些路线可以通往蘑菇城堡呢？一起通过程序找出来吧！ 任 务 目 标 通过”初入蘑菇城堡”程序，尝试找出所有能够通往蘑菇城堡的路线，记录到路径研究报告中，并从中找出用时最短的路径 文 件 位 置 1、学生文件 -- 1、枚举法找路径【程序体验】 -- index.html 我们先通过一个视频看看看如何通往蘑菇城堡吧（点击播放视频） 看完这个视频后，你发现还有哪些路线可以通往蘑菇城堡呢？一起通过程序找出来吧！ 请通过”初入蘑菇城堡”程序，尝试找出所有能够通往蘑菇城堡的路线，记录到路径研究报告中，并从中找出用时最短的路径 请同学们打开1、学生文件 -- 1、枚举法找路径【程序体验】 -- index.html 程序，开始探索吧！（学生实践） 01 初入蘑菇城堡 【枚举法找最短路径】 A 基本定义 把所有可能的路线一条一条全列出来，再比较哪条最快 B 优势特点 路线少时列出所有的路径很简单，不会漏掉 C 不足之处 如果地图变大，路线会多到几百万条，枚举法就太慢了 枚举法 如果蘑菇城堡扩大到100×100的网格！你还能一条条试吗？ 时间到，哪个同学来分享自己的探究成果，并说说你找到的最短的路径是哪一条，用时多久？（邀请学生回答） 通过逐一尝试，相信同学们都找到原来最短的路径是A-B-E-F-I，因此这条路径同时最短，花费了7分钟。 像这种每条路径都列出来的方法，我们成为枚举法。 它指的就是把所有可能的路线一条一条全列出来，再比较哪条最快 一般在路线少时，优势比较明显，列出所有的路径很简单，不会漏掉 但是如果地图变大，路线会多到几百万条，枚举法就太慢了，这也是枚举法的局限性。 如果蘑菇城堡扩大到100×100的网格！你还能一条条试吗？ 能我们试玩全部的路线，公主可能都要在城堡里变成老太婆啦 过渡：因此我们需要一个更加聪明的算法，来帮助我们更加快速得拯救公主！ 第二部分 02 理解“到每个点的最短时间由左边和上边决定”，掌握动态规划算法的方法 获得智慧神器 02 获得智慧神器 【动态规划法找路径】 我们可以把计算整个地图最短路径的用时，转变为计算到具体一个点的最短路径的用时。用圆圈中的数表示从起点到该点的最短用时 每个点的用时来源 一是：上方节点用时+上方路径用时 二是：左方节点用时+左方路径用时 A A为起点 用时统计为0 B 到达B点的路径只能从A→B A + （A→B） = 0 + 3 = 3 D 到达D点的路径只能从A→D A + （A→D） = 0 + 2 = 2 A 起点 B E 到达D点的路径有B→E和D→E B + (B→E) = 3 + 1 = 4 D + (D→E) = 2 + 3 = 5 选较短的路径用时：B+(B→E)=3+1=4 注意：若点有两个来源，选用时较少的一个 (3) (2) (0) (4) 我们可以把计算整个地图最短路径的用时，转变为计算到具体一个点的最短路径的用时。用圆圈中的数表示从起点到该点的最短用时 比如我们截取蘑菇城堡的左上角区域进行分析。 首先我们明确每个点的用时来源，一是：上方节点用时+上方路径用时。二是：左方节点用时+左方路径用时。 我们结合具体的点来看看每个节点的时间改如何计算。 首先看到A点。因为A是起点，所以A点的统计用是为0； 接着看到B点，想要到达B点的话，要怎么走？（邀请同学回答） 从A到往右移动到B点，所有到达B点的时间就是A点用时加上A到B点的路径用时也就是 0 + 3 = 3 在来看看D点，到达D点的路径怎么走？（邀请同学回答） 只能是A点从上往下移动到D点，所以到达D点的最短用时改如何计算？（邀请同学回答） 你举一反三能力真棒！也就是A点用时加上A点到达D点的路径用时：0+2=2 最后我们来看看E点，请同桌之阿金互相讨论，E点的用时应该如何计算（同桌讨论） 谁来说说到达E点的路径有哪些？（邀请同学回答） 想要到达E点可以是B点往下或者D点往右。因为E点就有两个时间，是哪两个时间？（邀请同学回答） B + (B→E) = 3 + 1 = 4 和D + (D→E) = 2 + 3 = 5 哪我们要选择哪一个时间呢？（邀请同学回答） 没错，我们应该选择B+(B→E)=3+1=4，因为她花费的时间比较少。 因此在这里我们需要注意若点有两个来源，选用时较少的一个。最终E点的用时是4。 过渡：在理解了高方法后，下面请同学们结合程序，一起来完成剩下金币地点的用时吧！ 02 获得智慧神器 【动态规划法找路径】 任务目标 以小组为单位，通过程序继续找出剩余三个区域局部的最短用时，并将结果记录到活动探究单上 文件位置 1、学生文件 -- 2、分段法找路径【程序体验】--index.html 以小组为单位，通过程序继续找出剩余三个区域局部的最短用时，并将结果记录到活动探究单上 请同学们打开1、学生文件 -- 2、分段法找路径【程序体验】--index.html 程序，开始体验吧！（学生实践） 02 获得智慧神器 【动态规划法找路径】 C 到达C点的路径只能从B→C B + （B→C） = 3 + 2 = 5 F 到达F点的路径有C→F和E→F C + (C→F) = 5 + 2 = 7 E + (E→F) = 4 + 2 = 6 选较短的路径用时 E + (E→F) = 4 + 2 = 6 5 G 到达G点的路径只能从D→G D + （D→G） = 2 + 3 = 5 H 到达H点的路径有E→H和G→H E + (E→H) = 4 +1 = 5 G + (G→H) = 5 + 3 = 8 选较短的路径用时 E + (E→H) = 4 +1 = 5 I 到达I点的路径有F→I和H→I F + (F→I) = 6 +1 = 7 H + (H→I) = 5 + 3 = 8 选较短的路径用时 F + (F→I) = 6 +1 = 7 6 5 5 (7) 时间到，哪个小组的同学愿意上台分享自己本组的探究成果？（邀请小组上台展示） 听了这组同学的分享，相信同学们跟他们小组的想法不谋而合，下面我们结合这个小组的思路一起来梳理整个过程吧！ 刚才我们已经完成了ABDE这个区域，接下来我们来分析BCEF这个区域。这个区域我们只需要计算GF两个地点的用时即可 首先针对点C到达点C的路径只能是从哪个点多来？（B点） 因此点C的用时就是B + （B→C） = 3 + 2 = 5 而点F我们可以从C往下移动到F或者从E往右移动到F。针对这两点，它们的同时分别是多少？（邀请同学回答） C + (C→F) = 5 + 2 = 7，E + (E→F) = 4 + 2 = 6 。如果一个点有多个路径来源的话，我们应该选择用时少的路径。因此点F最终的用时是：E + (E→F) = 4 + 2 = 6 。 下面我们来分析DEGH这个区域。同样，这个区域我们只需要分析哪两个点？（G和H） 对于点G，到达G点的路径只能从D→G，因此到达点G的用时是？（邀请同学回答） D + （D→G） = 2 + 3 = 5 而点H同样也是有两个路径来源，分别是？（邀请同学回答-E→H和D→H） 所以点H的路径用时就包含了E + (E→H) = 4 +1 = 5和G + (G→H) = 5 + 3 = 8 两种情况，同样我们选择较短路径用时应该是？（E + (E→H) = 4 +1 = 5） 最后我们来分析到达蘑菇城堡的最短路径。 到达蘑菇城堡I点的路径有F→I和H→I，因此用时分别包含了F + (F→I) = 6 +1 = 7和H + (H→I) = 5 + 3 = 8 两种情况，选择较短的路径用时应该是？（F + (F→I) = 6 +1 = 7） 总结：通过梳理，我们发现可以把从起点到终点的全局问题分解成计算从起点到其中每个点的最短用时。这个过程其实就是运用了动态算法 过渡：到底什么是动态规划算法？我们一起来深入探究一下！ 02 获得智慧神器 【动态规划法找路径】 动态规划算法 将全局问题转化为局部问题，随着局部问题的解决逐渐到全局问题的解决。而计算最短路径是动态规划算法最简单的应用场景 基本定义 例如：不急着想“从A到I怎么走最快”，而是先想： ① A→E怎么走最快？ 先考虑A到达最近的两个点B和D： 到B最快3步；到D最快2步（这个时候选择的路径是A→D） 接着考虑B和D到E最快多少 B来是3+1=4步，D来是2+3=5步，选择B→E 路径由原本的A→D转换成了A→B。因为B到E的用时比D到E的用时短，因此路径随着结果实时动态更新为了A→B→E 将全局问题转化为局部问题，随着局部问题的解决逐渐到全局问题的解决。而计算最短路径是动态规划算法最简单的应用场景。 比如结合刚才玛丽要去蘑菇城堡拯救公主的例子。不急着想“从A到I怎么走最快”，而是先想：A→E怎么走最快？ 这个时候我们会先考虑A到达最近的两个点B和D：到B最快3步；到D最快2步（这个时候选择的路径是A→D） 接着考虑B和D到E最快多少，B来是3+1=4步，D来是2+3=5步，选择B→E 最终路径由原本的A→D转换成了A→B。因为B到E的用时比D到E的用时短，因此路径随着结果实时动态更新为了A→B→E。 02 获得智慧神器 【动态规划法找路径】 动态规划算法 ② 接着将局部问题放大到：考虑A→F的最短路径用时。 经过综合分析，A→F的最短路径用时为： A→B→E→F：3+1+2=6 ③ 然后将局部问题换成：考虑A→H的最短用时 最后将局部问题放大到：求A→I的最短路径用时 经过综合分析，A→H的最短路径用时为： A→D→E→H：2+3+1=6 将全局问题转化为局部问题，随着局部问题的解决逐渐到全局问题的解决。而计算最短路径是动态规划算法最简单的应用场景 基本定义 谢谢你们成功拯救了我！其实路径规划算法还有很多妙处，一起去看看吧！ ② 接着将局部问题放大到：考虑A→F的最短路径用时。 经过综合分析，A→F的最短路径用时为：A→B→E→F：3+1+2=6 ③ 然后将局部问题换成：考虑A→H的最短用时 经过综合分析，A→H的最短路径用时为：A→D→E→H：2+3+1=6 最后将局部问题放大到：求A→I的最短路径用时 总结：经过不断求解A点到某个点的最短路径用时，我们成功解决了A点到蘑菇城堡的最短路径用时。这便是动态规划算法中路径规划算法的魅力。 到这里还是要恭喜同学们成功把公主从蘑菇城堡营救出来！而我们的公主也是见多识广，要带我们一起看看路径规划算法的其他应用场景 过渡：下面跟随公主一起去了解路径规划算法的其他应用场景吧！ 第三部分 03 能结合具体情境，了解路径规划算法在显示生活中的应用 公主分享妙计 03 公主分享妙计 【路径算法的应用】 导航系统 路径规划算法可以帮助导航系统找到两个地点之间的最短路径，并标注相应的路线，从而提供导航服务 电力网络 电线杆和变电站看作节点，电线可以看作是路径，路径规划算法可以帮助确定节点之间的最短电线布局 物流配送 帮助物流人员确定最优的配送路线。还可以帮助物流企业规划仓库的位置，让仓库与客户的距离更近 首先就是导航系统。路径规划算法可以帮助导航系统找到两个地点之间的最短路径，并标注相应的路线，从而提供导航服务 其次在物流配送上，路径规划算法可以帮助物流人员确定最优的配送路线。还可以帮助物流企业规划仓库的位置，让仓库与客户的距离更近 最后在电力网络上，我们可以把电线杆和变电站看作节点，电线可以看作是路径，路径规划算法可以帮助确定节点之间的最短电线布局。 过渡：今天我们的探险之旅也接近尾声啦~一起来总结今天都有哪些收获吧! 第四部分 04 比较枚举法与动态规划的优缺点，体会“化整为零”的算法思想。 终极通关庆典 04 终极通关庆典 枚举法 把所有可能的路线一条一条全列出来，再比较哪条最快，适用于路线少的情况 动态规划算法 将全局问题转化为局部问题，随着局部问题的解决逐渐到全局问题的解决。 在现实生活中，路径规划算法应用广泛，它与我们的生活、工作和学习已经息息相关。比如常见的导航系统、物流配送、电力网络等都离不开路径规划算法的帮助 【路径规划算法】 应用场景 首先我们认识了枚举法，其实就是指把所有可能的路线一条一条全列出来，再比较哪条最快，适用于路线少的情况 其次我们还认识了动态规划算法：将全局问题转化为局部问题，随着局部问题的解决逐渐到全局问题的解决。 而路径规划算法是动态规划算法中最简单的应用，它与我们的生活、工作和学习已经息息相关。比如常见的导航系统、物流配送、电力网络等都离不开路径规划算法的帮助 04 终极通关庆典 【路径规划算法】 三人传球 你救出公主后，发现蘑菇城堡军队有三个小兵A、B、C，他们围成三角形训练传球。此时军队的队长下令：每次只能传给相邻的人。 如果一开始球在A手中，传10次后，球再次回到A手中的可能性有多少种？ 1 任务目标 尝试利用不同的程序算法来计算传10次球后再次回到A手中的可能性 2 文件位置 1、学生文件 -- 3、三人传球训练【程序体验】 -- 1、枚举法.py 或2、分段法.py 你救出公主后，发现蘑菇城堡军队有三个小兵A、B、C，他们围成三角形训练传球。此时军队的队长下令：每次只能传给相邻的人。 如果一开始球在A手中，传10次后，球再次回到A手中的可能性有多少种？ 有兴趣的同学可以尝试利用不同的程序算法来计算传10次球后再次回到A手中的可能性 Lavf58.46.101 $