加速点最快的路径
Edw*_*ers 16 algorithm math graph-theory shortest-path
这只是我自己想出来的东西,但它似乎是一个有趣的问题而且让我难过.
在二维空间中有一组点,其中一个点指定为"开始",一个指定为"结束".每个点都有坐标(以距离原点为单位),但也有"加速度数"(以米 - 秒为单位的Δ-V).到达某个点(包括开始点)后,您可以在任何方向上加速到该点的加速度数.边缘成本取决于您当前的速度,但您还必须朝着正确的方向前进.
是否有一种有效的算法来寻找到达终点的最快路径？我没有提出比"尝试每条路径并检查结果"更好的东西.Djikstra和其他简单的算法不起作用,因为你不能轻易地说中间点的一条路径比另一条路径更好或更差,如果它们以不同的初始速度到达.
如果这太简单了,如果你添加了必须在终点停止的要求怎么办？(即,当你到达终点时,你必须小于它的加速度值.)
编辑:要明确,方向很重要.在遍历图形时保持速度矢量,加速意味着向其添加矢量,其大小以该点的加速度数量为上限.这意味着在哪里建造了一个巨大的速度是有害的,因为你会走得太快,以"引导"对其他宝贵的意见/目的地的情况.
我认为，只使用每个点的加速度一次的要求使得这个问题在一般情况下 NP 完全。考虑一个如下所示的输入：
如果终点和其余点之间的“巨大距离”足够大，足以主导最终解决方案的成本，那么寻找最佳解决方案将归结为找到一种方法，从最终解决方案中获得尽可能多的速度提升。图表的开始。如果只允许每个点通过一次，这相当于哈密顿路径问题，是 NP 完全问题。
也就是说，你的问题有一些额外的规则（距离是欧几里德的，图表总是完整的），这可能最终会让问题变得更容易。