滑翔比赛中的最短路径

Question

我是一个滑翔伞飞行员。滑翔伞比赛被定义为一组虚拟浮标。第一个飞越所有浮标的飞行员获胜。

一个浮标由两个参数定义：

- 一个点的坐标 - 一个半径

这在3D空间中定义了一个圆柱体，但为简单起见，让我们将问题保留在2D中。比赛可能看起来像这样（近似绘图）： A=1000m; B=3000m; C=2000m; D=500m

飞行员应该从圆A内开始，然后飞入圆B和C（或至少“触摸”它），并应该在圆D内结束。

如何计算最优（最短）路径？

结果应该是构成最短路径的所有线段的坐标。

- Maximiliano Padulo

---

您可以使用一些受限梯度下降算法，或者是某些二阶拟牛顿算法的替代方案。 - Yakov Galka

另一个观察结果，而非解决方案。最短的路径将从A开始，并以E结束，这条路径可视为光线的路径，如果每个圆圈要么是完美反射（在该点折回），要么是透明（穿过一个圆圈朝下一个圆圈前进）。 - btilly

你真的想要最短路径吗？由于其切线不连续，这在物理上是不可实现的。 - Nico Schertler

最短路径不一定是最快的。风向非常重要。 - user58697

@btilly 是的，我明白了，正在尝试弄清楚是否可以通过仅扩展3个圆的解决方案来简化此问题。 - Yonlif

Answer 1

如果路径预先已知为ABCD，只有确切的点未知，则总距离（平方）可以写成4个变量的函数。

当然，点i的一个参数化是：

x(t_i) = x0_i + r_i * cos(t_i)
y(t_i) = y0_i + r_i * sin(t_i)

路径长度的平方为

D^2 = sum_{i = 1, n-1} (x(t_{i+i}) - x(t_i))^2 + (y(t_{i+i}) - y(t_i))^2

你需要解决的四个变量是t_1, ... t_4。代入后，对于D^2的最终表达式是一个相当复杂的正弦和余弦二次方程。你要尽量使该数量最小。

这不太可能有一个解析解。

你还可以尝试有理二次圆形参数化，但你最终会得到一个有理四次方程。不会更简单（吧）。

令人高兴的是，即使是这种复杂的函数也可以通过标准的数值非线性优化算法进行最小化，例如（评论中有人建议的）梯度下降。

在一般情况下，你无法保证由此类算法找到的最小值是全局的。但在这种情况下，解空间似乎是凸的，至少对于大多数问题实例来说，这使得局部最小值也是全局最小值。

还有可能存在很好的启发式方法来选择数值迭代的起始点。例如，沿着圆的中心路径。对于每个圆，选择其与路径相交的两个点之间的中点。

通过类似的逻辑，你可以约束每个t_i的值都小于\pi的一个范围。

- Gene