拉格朗日解题报告

(思路来源:BZOJ滑行)

题意

在无穷大的水平面上有一个平面直角坐标系。N-1条垂直于x轴的直线将空间分为了N个区域。

你被要求把$(0,0)$处的箱子匀速推到$(x,y)$。

箱子受水平面的摩擦力与正压力正相关,所以在每个区域的摩擦力可以表示为$f_i$。$[0,x]$间的坐标轴在每一块区域内的长度为$d_i$。

那么,你把箱子推到目的地做的最小功是多少呢?(不考虑改变速度时的做功)

拉格朗日乘子法

一个显然的结论是:在每一块区域内的运动成直线,区域间改变方向。这样一定会比走曲线优。

还有一个显然的结论是:箱子的$y$坐标一定单调。

因此,我们可以设箱子$y$坐标在每格内的变化量为$y_i$,那么我们可以列出最优化函数和约束方程:

$$
\begin{align}
F(y_i) &=\sum f_i\sqrt{d_i^2+y_i^2} \
s.t.\ G(y_i) &= \sum f_i – Y = 0
\end{align}
$$

利用拉格朗日乘子法,我们可以知道$F$在何时取到最小值。

该问题的拉格朗日函数为:
$$
L(y_i,\lambda) = F(y_i)-\lambda G(y_i)
$$
对于$y_i$和$\lambda$求偏导,当每个偏导同时为$0$时,函数取到最小值。

$$
\begin{align}
\frac{\partial L}{\partial y_i} &= \frac{f_i y_i}{\sqrt{d_i^2+y_i^2}}-\lambda = 0 \
\frac{\partial L}{\partial \lambda} &= Y-\sum{y_i} = 0
\end{align}
$$

观察这两个方程,我们发现,对于任意一个$\lambda$,第一个方程在正数域内都有唯一解。因此,给定一个$\lambda$,我们可以确定所有的$y$,但是我们又发现,这样得到的$y$不满足第二个偏导为$0$。

因此,我们需要找到一个合适的$\lambda$,使得通过第一个方程解得的$y$满足第二个方程。

注意到第一个方程的$y$在正数域内随$\lambda$单调下降,因此,我们可以通过二分$\lambda$找合适的解。

最后求得的$y_i$带入$F(y_i)$即可求得答案。

光学原理

该方法有关光的折射原理:

设:入射光线与法线的夹角$\theta_1$,出射光线与法线的夹角$\theta_2$,入射面介质内光速$v_1$,出射面介质内光速$v_2$。

$$
\frac{\sin(\theta_1)}{v_1} = \frac{\sin(\theta_2)}{v_2}
$$

以及费马原理:
过两个定点的光走且仅走 光程的一阶变分为零的路径。即光一般走的是邻域内的最快的路线。

有了这两个原理,我们就可以把推箱子和光的传播联系在一起。

我们知道光在空间中传播的耗时为:
$$
\frac{L}{c}
$$
而推箱子的做功为:
$$
Lf
$$
因此,我们令每一段区间的“光速”为$\frac{1}{f}$,则,箱子的最优推行路线就是空间中的光路。确定了箱子初始的运行角度,我们就可以得到箱子最终到达的位置。由于这个位置关于初始角度单调,我们只需要二分这个角度,判断到达位置在$(x,y)$的上方还是下方即可。

但是要注意一点,光在两个介质的光速差异很大,且入射角很大的时候,会发生全反射,推箱子同理。在二分的时候要特殊处理这种情况。

分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *