algorithm - 滑翔伞比赛中的最短路径

Question

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

浮标由两个参数定义:

• 一个点的坐标
• 半径

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

飞行员应从 A 圈内开始，然后在 B 圈和 C 圈内飞行(或者至少只是“触摸”它)，并应在 D 圈内结束。

如何计算最佳(最短)路径？

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

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 的范围内。