点加速的最快路径 [英] Fastest Path with Acceleration at Points

问题描述

这只是我自己想出的东西，但这似乎是一个有趣的问题，困扰我.

This is just something I came up with on my own, but it seems like a fun problem and it has me stumped.

您在二维空间中有一组点，其中一个点指定为开始"，一个点指定为结束".每个点都有坐标(以距原点的米为单位)，但也有加速度数"(以米/秒为单位的增量V).到达某个点(包括起点)后，您可以在任何方向上以该点的加速数加速.边缘成本取决于您当前的速度，但您还必须朝正确的方向前进.

You have a set of points in two-dimensional space, with one point designated "Start" and one "End". Each point has coordinates (in meters from the origin), but also an "acceleration number" (in meters/second of delta-V). Upon reaching a point (including the start), you may accelerate by up to that point's acceleration number in any direction. Edge cost is dependent on your current speed, but you also have to be moving in the correct direction.

是否有一种有效的算法可以找到到达终点的最快路径?除了尝试每条路径并检查结果"之外，我没有什么比这更好的了. Djikstra的算法和其他简单算法无法正常工作，因为如果您以不同的初始速度到达中间点，您就无法轻易地说出到达中间点的一条路比另一条路好还是差.

Is there an efficient algorithm for finding the fastest path through to the end point? I haven't come up with anything better than "Try every path and check results". Djikstra's and other simple algorithms don't work, because you can't easily say that one path to an intermediate point is better or worse than another, if they have you arriving with different initial velocities.

如果这太容易了，那么如果添加了必须在终点处停止的要求，该怎么办? (即，到达终点时，加速度必须小于加速度值.)

If that's too easy, what if you add the requirement that you have to stop at the end point? (i.e., you must have less than its acceleration value when you reach the end.)

明确地说，方向很重要.在遍历图形时，您要保持一个速度矢量，而加速度意味着向其添加一个矢量，其大小以该点的加速度为上限.这意味着在某些情况下，建立巨大的速度是有害的，因为您将太快地转向"其他有价值的地点/目的地.

To be clear, direction matters. You maintain a velocity vector as you traverse the graph, and acceleration means adding a vector to it, whose magnitude is capped at that point's acceleration number. This means there are situations where building up a huge velocity is detrimental, as you will be going too fast to "steer" towards other valuable points/your destination.

推荐答案

您可以通过递归地跟踪从末端到其他节点的路径来尝试向后解决此问题，然后指定沿线的最大速度以能够从该路径转向节点到任何其他节点.选择规则是，是否存在从当前到下一个节点的路径，速度越小，从末端花费的时间越少，这意味着默认情况下，另一条路径是最优的，因为它可以到达更多的节点并且花费的时间更少.路径到达起始节点后，应根据起始处可达到的最大速度重新计算并存储.然后，您将花费更少的时间来收集路径.

You can try solving this problem backwards by recursively tracing paths from the end to each other node, then designate maximum speed along the line to be able to turn from that node to any other. The culling rule will be if a path from current to next node exists with less velocity and less time spent from end, which will mean that the other path is more optimal by default because it can reach more nodes and takes less time. Once a path reaches start node, it should get recalculated based on the maximum speed achievable at the start and stored. Then you gather the path with less time spent.

您必须在此处搜索任何可用路径，因为图形上的可用路径取决于间接状态的过去状态，因此使用较低的速度可以有更多选择.

You have to search for any available path here, because the available paths on your graph are dependent on past state with an indirect mechanics, using less speed allows more choices.

这篇关于点加速的最快路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！