探索:最短路径问题

问题原型("将军饮马"):直线 $\ell$ 一侧有两点 $A, B$。在 $\ell$ 上求一点 $P$,使 $PA + PB$ 最小。

解题策略 —— 利用轴对称把折线变直线:

1. 作 $A$ 关于 $\ell$ 的对称点 $A'$;
2. 连接 $A'B$,与 $\ell$ 的交点就是要找的 $P$;
3. 最小值 $PA + PB = PA' + PB = A'B$(三点共线,折线最短)。

核心两条原理:

• 轴对称:$A$ 到 $\ell$ 上任一点 $P$ 的距离 $= A'$ 到 $P$ 的距离,即 $PA = PA'$;
• 两点之间线段最短:$PA' + PB \geq A'B$,当且仅当 $P$ 在线段 $A'B$ 上时取等。

这种"把折线拉直"的技巧也可用于:

• $A, B$ 在直线两侧的 "两线之间最短折线"(直接连 $AB$,无需对称);
• 多次反射的最短闭合路径。