选择一对矢量以获得最佳“之字形”轮廓的算法

Question

我有一组不同的二维向量（在实数上），指向不同的方向。我们被允许选择一对向量并构造它们的线性组合，使得系数是正的，它们的总和是1。简而言之，我们被允许对任何两个向量进行“加权平均”。

我的目标是在任意方向上选取一对向量，其“加权平均值”在这个方向上并且最大化。说到代数给定的向量a和b以及方向向量n，我们对最大化这个值感兴趣：

[a交叉b]/[（a-b）交叉n]

即选择最大化该值的a和b。

（此图中的每条线对应于特定的风力大小）。请注意，每个方向的“不可能”前扇区约为30度。

因此，在某些方向上，速度会很高，在某些方向上，速度会很低，而在某些方向上，不可能直接航行(例如，在严格逆风的方向上)。

如果我们需要朝着一个无法直接航行的方向前进（或者速度不是最佳的），那么就有可能以之字形前进。这称为定位。

现在，我的目标是重新计算一个新的图表，它直接或间接地表示任何方向的平均前进速度。例如，对于上述图表，修正后的图表如下：

注意，再也没有“不可能”的方向了。对于某些方向来说，该图类似于原始图，最好是直接前进，不需要任何机动。对于其他的——它显示了在这个方向上的最大平均推进速度，假设周期性地执行最佳机动。

计算这个的最佳算法是什么？假设图表是一组离散的方位-速度对，我们可以从中计算矢量。

到目前为止，我只是检查所有的向量对来选择最好的。嗯，有截止标准，比如只选择前进方向上有正投影的向量，和相反的垂直投影，但复杂度仍然是O（N^2）。我想知道是否有更有效的算法。

编辑

非常感谢@mcdoella。计算机科学和水手的答案！

我也考虑了凸多边形，发现只值得在该船体上探测向量（即，如果您在该船体上叠加 2 个向量，并尝试用不在此船体上的向量替换其中一个，结果会更糟，因为新向量在所需方向上的投影比两个源向量都差）。

然而，我没有意识到任何2个向量的“加权平均”实际上是连接这些向量的直线段，因此最终的图确实是这个凸包！正如我们所见，这也与我用“暴力”算法计算的结果一致。

Answer 1

首先是前激光水手的答案

至少对于顺风或顺风直行来说，最明显的猜测是进行定位，使每一条腿的长度相同，并且对风的方向相同。如果极坐标图围绕上风-下风轴对称，这是正确的。假设逆风是Y轴，可能的支腿是（A，B）、（-A，B），（A，B）和（-A，B）。对称定位移动（A，B）/2（-A，B）/2=（0，B），另一个对称定位给你（0，B）。不对称定位是（-A，B）A/（A A）（A，B）A/（A）=（0，（A/（A））B（A/（A A））B），如果B=B位于B和B之间，所以不如B和B中的哪一个好。

对于位于左舷和右舷大钉之间的任何方向，如果你想逆风前进，最明显的策略是改变这些腿的长度，而不是改变它们的方向，这样平均行进的向量就在所需的方向上。这是最好的策略吗？如果不是，更好的策略是逆风前进的速度比你逆风前进时的左舷和右舷航向更快，我认为这是一个矛盾-因此，对于任何位于左舷与右舷之间的航向，我认为最好的策略确实是进行这些航向，但改变航向长度，使其朝所需方向前进。同样的事情也适用于顺风航行，如果你有一艘船，这是一个好主意。

Answer 2

现在计算机科学的答案

定位策略为您提供来自构成定位的腿的向量的凸组合。

因此，请考虑图表中仅由一个轮廓绘制的轮廓。所有可能的最佳速度和方向的集合是通过将矢量的所有凸组合带到轮廓而形成的凸多边形。所以你要做的是形成轮廓的凸包（https://en.wikipedia.org/wiki/Convex_hull）。要了解如何在任何特定方向上快速行驶，请将该矢量与凸包相交，并使用与相交的凸包边缘两侧的拐角相对应的腿钉。

看你的图表，轮廓是凹形的，顺风直上，顺风直下，这是你所期望的。然而，还有另一个凹形部分，在4点到5点之间，也对称地在7点到8点之间，在你修正后的图表中，它看起来像一条直线——所以我想还有第三个方向需要调整，使用风的同一侧的两条河段，这是我在传统航海中无法识别的。