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.

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.

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.)

EDIT: 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.

回答1:

I think that the requirement that you only use the acceleration from each point once makes this problem NP complete in the general case. Consider an input that looks like this:

If the "huge distance" between the end point and the rest of the points is large enough to dominate the cost of the final solution, finding an optimal solution will boil down to finding a way to pick up as many speed boosts as possible from the start of the graph. If you only allow each point to be passed once, this would be equivalent to to the Hamiltonian path problem, which is NP complete.

That said, your problem has some extra rules on top of it (the distances are euclidean, the graph is always complete) which might end up making the problem easier.

回答2:

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.