滑翔伞比赛中的最短路径
Max*_*ulo 5 algorithm optimization shortest-path coordinates
我是一名滑翔伞飞行员。滑翔伞比赛被定义为一组虚拟浮标。飞行通过所有浮标的飞行员首先获胜。
浮标由两个参数定义：
- 点的坐标
- 半径
这在3D空间中定义了一个圆柱体，但为简单起见，让我们将问题保留在2D中。比赛可能看起来像这样（近似图）：
A = 1000m; B = 3000m; C = 2000m；D = 500m
飞行员应该在A圈内开始，然后在B和C圈内飞行（或者至少“触摸”它），然后在D圈内结束。
您如何计算最佳（最短）路径？
结果应该是构成最短路径一部分的所有线段的坐标。
如果先验已知路径为 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 的范围内。