课题学习 最短路径问题

官官方数学老师·19 页·进阶（有基础，想深入原理）·0 次浏览·2 天前
✦ 课题学习 最短路径问题数学课题学习 最短路径问题平移
最短路径图形变换费马原理经典题型

课题学习 最短路径问题

从镜像反射到费马原理，三类经典题一图贯通

按 空格/→ 演示下一步

1 / 19 页

全部页面点击任意一页，跳回舞台从这页播放

最短路径图形变换费马原理经典题型

课题学习 最短路径问题

从镜像反射到费马原理，三类经典题一图贯通

1第 1 页 · 课题学习 最短路径问题

什么是最短路径问题

蚂蚁找食物时，走短路的蚂蚁更早回来、信息素更浓，整个蚁群最终汇聚到最短那条路；为新建小区选饮水点，要让所有住户走来的总距离最小。这些场景背后藏着同一类问题，今天我们来拆开看。

最短路径
在所有连通路线中，总代价最小的那一条
三个要素
起点、终点，以及路径上每段的代价（距离/时间/费用）
难点所在
节点一多，路径数爆炸式增长，暴力枚举不可行
核心思路
不一步求最优，而是逐步逼近，每步利用已知最优更新邻居
GPS导航为司机选路线对应 →最短路径问题的求解

导航把路网建模为图，'快'对应边上的权重，求最短就是找总权重最小的路径

d(v)=min⁡(u,v)∈E{d(u)+w(u,v)}d(v) = \min_{(u,v) \in E} \left\{ d(u) + w(u,v) \right\}
2第 2 页 · 什么是最短路径问题

最短路径的核心思想

最短路径问题看起来复杂——河流挡道、墙壁拦路，路径被迫拐弯。但所有'弯弯绕绕'的最短路径，背后都有一个共同的核心思想：把'弯的路'变成'直的路'，回到'两点之间线段最短'这个最朴素的原理。

线段最短原理
两点之间所有连线中，线段最短——整个最短路径问题的基石
化折为直：轴对称
路径必须碰某条直线时，将一端点关于该直线作对称，连接新两点即为最短折线
化曲为直：对称＋垂直
穿越曲线区域（如河岸）时，先转化为折线问题，再让连线垂直河岸以最短穿越
等距变换：长度不变
轴对称是等距变换，反射前后对应线段长度相等，所以直线长度可代折线长度
打台球碰库边入袋对应 →化折为直的反射变换

想让球碰库一次进袋？把袋口关于库边作镜像，反射点就是瞄准直线与库边的交点

3第 3 页 · 最短路径的核心思想

轴对称变换

上一步我们把'走直线'变成'走折线'，关键操作是把一个点'翻'到对面去。这个'翻'的几何动作，就是轴对称变换。

对称轴
一条选定的直线，所有'翻'的动作都围绕它发生
点点对应
原图形上每个点，在对称轴另一侧都有唯一的对应点
距离守恒
对应点到对称轴的距离相等，连线被对称轴垂直平分
照镜子对应 →轴对称变换

镜前的人和镜中的像左右互换，但一一对应

4第 4 页 · 轴对称变换

平移变换

轴对称用"翻"把折线摊直，但当两点处于平行位置——比如河的两岸、马路的两侧——镜像就用不上了。这时需要平移变换：把图形平着"挪"到新位置。

平移方向
移动的指向，可以是水平、垂直或任意斜向
平移距离
沿方向移动的远近长度
形状大小不变
移动后图形与原图全等，仅位置改变
两要素唯一确定
给定方向和距离，平移就唯一确定
桌面上推一本书对应 →平移变换

推的方向决定书往哪走，推的距离决定书走多远，书本身没变形

(x,y)→(x+a,y+b)(x, y) \to (x + a, y + b)
5第 5 页 · 平移变换

轴对称 vs 平移对比

两种变换都能把折线走法变直线走法，但选错了就求不出真正的最短路径。

轴对称变换
  • 关于某条直线把点镜像翻转
  • 起点与终点在障碍同一侧
  • 障碍通常是一条直线（如墙）
  • 一次翻转后路径即为直线段
平移变换
  • 沿某方向把图形整体移动一段距离
  • 起点与终点各在一条平行线侧
  • 障碍通常是两条平行线（如河岸）
  • 常需多次平移，路径才化为直线
同侧障碍选轴对称，平行线障碍选平移——先看起终点和障碍的位置关系。
6第 6 页 · 轴对称 vs 平移对比

轴对称法的解题步骤

轴对称法把'折线最短'变成'直线最短'，按四步走就能落地。

1
定对称轴
先看清题目要求，锁定那条不能走的中轴线
2
作对称点
把一侧端点关于中轴线翻折到另一侧
3
连线交轴
连接对称点与另一端点，与中轴的交点就是拐点
4
化折为直
由轴对称性质得拐点两段等长，最短路径即直线长
7第 7 页 · 轴对称法的解题步骤

将军饮马模型

从问题场景出发，看轴对称如何把折线最短变成线段最短。

图解渲染中…
c：M是河岸上任意一点，路径必经此处e：B'是B关于河岸的对称点g：M是直线AB'与河岸的交点h：由对称性，MB=MB'
8第 8 页 · 将军饮马模型

轴对称法例题精讲

按解题顺序，从上往下读，对应例题的几何构造与推理过程。

图解渲染中…
a1：A、B都在直线l的同一侧a2：A'是A关于l的轴对称点a4：利用PA=PA'，距离和化为线段A'B
9第 9 页 · 轴对称法例题精讲

为什么轴对称能找到最短路径

上一页说轴对称是核心技巧——但凭什么对一下就能找到最短路？这一页揭开原理：保距 + 直线最短，折线就能被「拉直」。

对称保距
A 到对称轴上任一点 P 的距离，等于 A' 到 P 的距离
折线 ≥ 直线
AP+PB = A'P+PB ≥ A'B，由三角形不等式保证
等号条件
P 恰为 A'B 与对称轴的交点时取等，折线最短
翻折纸张对应 →反射后路径等价

沿对称轴对折后，AP 与 A'P 重合等长，折线就被「拉直」成 A'P + PB

∣AP∣+∣PB∣=∣A′P∣+∣PB∣≥∣A′B∣，等号当 P∈A′B|AP|+|PB|=|A'P|+|PB|\geq|A'B|\text{，等号当 }P\in A'B
10第 10 页 · 为什么轴对称能找到最短路径

平移法的解题步骤

平移法三步化折为直：动一点、连一线、靠公理。

1
沿条件方向平移点
按题目给定的方向与距离，把折线中可动的端点挪到新位置
2
新点连旧点构造
把新点和未动的那个端点相连，得到一组平行四边形的对角线
3
化折为直求最短
对角线即两定点间线段，长度就是折线段的最小值
11第 11 页 · 平移法的解题步骤

两河交汇问题

两河交汇＝平移＋对称的组合：①平移处理甲乙河之间的跨河段，②轴对称处理乙河到B的出河段。沿流程从左到右读。

图解渲染中…
q1：Q沿河距平移后的虚像，与甲河重合于同一直线bb：B关于乙河的镜像点，恒有QB=QB't1：平移变换：把乙河沿垂直方向平移到甲河位置r1：轴对称变换：把B沿乙河镜像到B'
12第 12 页 · 两河交汇问题

平移法例题精讲

沿箭头看六步：从棱柱原图到平移展平，再到画直线求最短路径。

图解渲染中…
a1：原立体：蚂蚁在侧棱一端A，要到B点a5：A'B'是展开后直线，即最短距离
13第 13 页 · 平移法例题精讲

平移法的适用条件

当路径需经过多个约束点时的平移策略

平移法的适用条件
当路径需经过多个约束点时的平移策略
14第 14 页 · 平移法的适用条件

方法选择决策树

从约束出发，先看障碍物形状，再看点的位置，决定用哪种方法。

图解渲染中…
A：先识别题目中的障碍与起止点B：障碍是单条直线还是两条平行线G：轴对称关键：对端点作镜像H：平移关键：把异侧点挪到同侧
15第 15 页 · 方法选择决策树

轴对称法与平移法对比

两种方法的异同、优势与局限对照

轴对称法与平移法对比
两种方法的异同、优势与局限对照
16第 16 页 · 轴对称法与平移法对比

本节知识梳理

  • ✓原理统一：变换保持距离不变，变换后直连即为最短
  • ✓方法分支：障碍在中间用平移，端点在中间用轴对称
  • ✓将军饮马与两河汇流是同一思想的两种应用
  • ✓深层逻辑：最短路径问题都是'绕路变直路'的变换游戏
延伸主题：费马点问题立体最短路径最短网络问题
17第 17 页 · 本节知识梳理

核心概念自测

点击作答

在'将军饮马'问题中，把点A关于直线l作对称点A'后，连接A'与B得到线段A'B，与l的交点M即为最短饮马点。这一做法能找到最短路径，本质上依赖的基本事实是？

18第 18 页 · 核心概念自测

课后思考

先自己想，再看参考答案。三个问题从核心走向边界，琢磨透才算真懂。

1为什么「两点之间线段最短」这么简单的公理，要先做一次轴对称才用得上？

参考答案关键在「最短路径必须经过河岸」这个限制——直接连的两点分居两岸，路径不自由。对称把限制消掉，变成同侧自由点，公理才用得上。

2如果两条河不是平行直线（比如其中一条弯了），平移法还管用吗？该怎么改？

参考答案平移的核心是「等距对齐」，要求两河形状相同。弯河时需要先构造等距曲线，思路一样但操作更繁——本质没变，只是「对齐」变难了。

3如果最短路径还要绕过一个障碍物（比如水塘），前面的方法要怎么调整？

参考答案每个障碍都可以「反射一次」绕开。把约束一个个叠加进变换里，多障碍就是多次反射——这是反射法在更复杂场景下的自然推广方向。

19第 19 页 · 课后思考
课题学习 最短路径问题 · 知识图解