最速降线的蒙特卡洛逼近

本文进行了一次尝试，尝试通过简单粗暴的蒙特卡洛方法逼近一条“最速降线”。

本文代码详见我的前端仓库

Estimate the Brachistochrone using Monte Carlo Simulation^[1]

最速降线的蒙特卡洛逼近

问题抽象

最速降线问题是一个经典的变分问题，它的目的是找一条连续曲线，质点沿着这条曲线自由下降时，它达到目标点所需要的时间最短。

这个问题不难，在数学上是有解析解的，它是一条摆线，满足参数方程

那么就产生了一个问题，那就是如何通过计算机量化模拟的方法对该曲线进行求解。一个最简单和最直观的想法是建立一个比较密集的网格状排布的点集。以这样的点集为基础建立一张图

图的节点是网格单元
图的边是风格单元与它周围 8 个邻居之间的连接
边的权重是质点通过该边时所需要的时间

在该条件下，最速降线问题就转化成了从图中源节点到目标节点的最短路径问题。计算机求解这个问题是很快的，我们有 dijkstra 算法可用，它可以在极短的时间内解决问题。

下图中的背景小点就是风格节点，它的颜色代表该点的“速度值”，或者说是质量的动能，颜色越亮代表能量或速度越高。我们的目标是让质点从左上角坠落到右下角。其中的红线是理想的摆线方程所对应的曲线。

它遵循这样一个假设，那就是只受重力做功的物体的动能只与它下降的高度有关，速度的方向可以是任意的。

Setup

失败的尝试

上图中的较粗和较亮的线代表一次失败的尝试，因为我将边的权重，即时间的微分，过度简化了。你可以想象成一个米字格，

如果沿着水平和垂直的边移动，则时间为速度的倒数；
如果沿着倾斜的边移动，则时间为前值的根号 2 倍。

但结果表明，这种简化是有问题的，因为在每个格子内，质点的运动轨迹的微分并非一条直线，因此可能是穿过这个格子的任意一条弧。这就导致每个格子的时间计算都有问题，因此即使单个格子内的时间是微分，但每个格子都差一些的话，就没有道理假设最终的总和影响趋于 0。

成功的尝试

于是我尝试对积分过程进行修正，然而我发现修正太难了。如果要准确计算每个曲线微元的长度几乎是不可能的，因为它显然与质点进入和离开的速度和位置有关，很难实时计算。

因此我就不算了，索性进行 Monte Carlo 模拟，模拟的随机性来自于每个微元的长度。

由于微元的长度是随机的，因此可以假定它是实际时间的无偏估计。

因此，有理由相信这种模拟有希望找到正确的路径，实验结果果然如此。下图是进行了若干次随机模拟的叠加图，点的颜色还是代表该点的速度，叠加的颜色越亮表示经过该点的概率越高。

Mont Carlo simulation

最后，我们可以畅想一下，这个方法不仅适用于重力场，它还将适用于任意“保守”场。

参考资料

[1]

Estimate the Brachistochrone using Monte Carlo Simulation: https://observablehq.com/@listenzcc/estimate-the-brachistochrone-using-monte-carlo-simulatio

分类：

后端

标签：

后端

作者介绍