加速点最快的路径

Question

这只是我自己想出的东西，但它看起来像一个有趣的问题，它让我难倒了。

您在二维空间中有一组点，一个点指定为“开始”和一个“结束”。每个点都有坐标（距离原点的米），还有一个“加速度数”（以米/秒为单位）。在达到一个点（包括开始点）后，您可以在任何方向上加速到该点的加速度数。边缘成本取决于您当前的速度，但您也必须朝正确的方向移动。

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

如果这太容易了，如果您添加了必须停止在终点的要求会怎么样？ （即当你到达最后时，你必须小于加速度值。）

编辑：为了清楚，方向很重要。您在遍历图时维护速度矢量，加速度表示向其添加矢量，其大小限制在该点的加速度数上。这意味着在某些情况下，建立巨大的速度是有害的，因为你将太快以至于不能“转向”其他有价值的点/目的地。

Answer 1

我认为你只需要使用每个点的加速度就可以使这个问题在一般情况下完成。想想看，像这样的输入：

如果最终点和点的其余部分之间的“巨大的距离”大到足以称霸最终解决方案的成本，找到一个最佳的解决方案归结为找到一种方法来从图表的开头尽可能多地提高速度。如果您只允许每个点传递一次，这将相当于哈密尔顿路径问题，这是NP完整的。

也就是说，你的问题有一些额外的规则（距离是欧几里得，图总是完整的），这可能最终导致问题变得更容易。

Answer 2

您可以尝试通过递归地追踪从末端到其他节点的路径来解决此问题，然后指定沿着该线路的最大速度以便能够从该节点转向任何其他节点。如果从当前节点到下一个节点的路径以较低速度存在，并且从末端花费的时间较少，则这将意味着其他路径默认情况下更加优化，因为它可以到达更多节点并且花费更少的时间。一旦路径达到开始节点，应该根据开始时可达到的最大速度重新计算并存储。然后你花费更少的时间收集路径。

您必须在此搜索任何可用路径，因为图上的可用路径依赖于间接机制的过去状态，使用更少的速度允许更多选择。