这只是我自己想出的东西，但这似乎是一个有趣的问题，它让我难住了。
您在二维空间中有一组点，其中一个点指定为“起点”，一个点指定为“终点”。每个点都有坐标（以米为单位距原点），但也有一个“加速度数”（以米/秒的 delta-V 为单位）。到达某个点（包括起点）后，您可以在任何方向上以该点的加速度数加速。边缘成本取决于您当前的速度，但您也必须朝正确的方向移动。
是否有一种有效的算法来找到到达终点的最快路径？我没有想出比“尝试每条路径并检查结果”更好的方法。 Djikstra 和其他简单的算法不起作用，因为如果你以不同的初始速度到达，你不能轻易地说到达中间点的一条路径比另一条更好或更差。
如果这太简单了，如果添加必须在终点停止的要求怎么办？ （即，当您到达终点时，您的加速度值必须小于其加速度值。）
编辑：要明确的是，方向很重要。当您遍历图形时，您会维护一个速度矢量，而加速度意味着向其添加一个矢量，其大小以该点的加速度数为上限。这意味着在某些情况下，建立巨大的速度是有害的，因为你会开得太快而无法“转向”其他有价值的点/你的目的地。
我认为，只使用每个点的加速度一次的要求使得这个问题在一般情况下 NP 完全。考虑一个如下所示的输入：
如果终点和其余点之间的“巨大距离”足够大，足以主导最终解决方案的成本，那么找到最佳解决方案将归结为找到一种方法，从最终解决方案中获得尽可能多的速度提升。图表的开始。如果只允许每个点通过一次，这相当于哈密顿路径问题，是 NP 完全问题。
也就是说，你的问题有一些额外的规则（距离是欧几里德的，图表总是完整的），这可能最终会让问题变得更容易。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
