algorithm - 点加速的最快路径

Question

这只是我自己想出的东西，但这似乎是一个有趣的问题，让我感到难过。

您在二维空间中有一组点，一个点指定为“起点”，一个点指定为“终点”。每个点都有坐标(从原点以米为单位)，还有一个“加速度数”(以 delta-V 的米/秒为单位)。到达一个点(包括起点)后，您可以在任何方向上加速到该点的加速度数。边缘成本取决于您当前的速度，但您也必须朝着正确的方向前进。

是否有一种有效的算法可以找到到达终点的最快路径？我没有想出比“尝试每条路径并检查结果”更好的方法。 Djikstra 和其他简单的算法不起作用，因为如果它们让您以不同的初始速度到达，您不能轻易说到中间点的一条路径比另一条路径更好或更差。

如果这太简单了，如果你添加必须在终点停止的要求呢？ (即，当你到达终点时，你必须小于它的加速度值。)

编辑:明确地说，方向很重要。您在遍历图形时保持速度矢量，加速度意味着向其添加一个矢量，其大小上限为该点的加速度数。这意味着在某些情况下建立一个巨大的速度是有害的，因为你会走得太快而无法“转向”其他有值(value)的点/你的目的地。

Answer 1

我认为你只使用一次来自每个点的加速度的要求使得这个问题在一般情况下 NP 完成。考虑如下所示的输入:

如果终点和其余点之间的“巨大距离”大到足以支配最终解决方案的成本，则找到最佳解决方案将归结为找到一种方法来获得尽可能多的速度提升可能从图表的开始。如果只允许每个点通过一次，就相当于哈密顿路径问题，是NP完全的。

也就是说，您的问题有一些额外的规则(距离是欧氏距离，图表总是完整的)，这可能最终会使问题变得更容易。