16

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.

Edward Peters
  • 3,623
  • 2
  • 16
  • 39
  • You will have to provide more details. How would your concept of "acceleration" work? Does it reduce all edge costs along a path by the "acceleration number"? What if you accumulate "acceleration number" well beyond the edge costs? Introducing a concept like "acceleration" suggests that it might be good to introduce a corresponding idea of friction/drag, otherwise you could end up with an "unchecked velocity". So far, I don't think your question is clear enough for us to formulate a proper solution, but do I think it is very interesting. – lightalchemist Jul 02 '16 at 01:11
  • 2
    I doubt there is an analytic solution to this problem. I would start by solving a much simpler problem first: the fastest route that takes the points in a given order. (That search space has a number of dimensions equal to the number of intermediate points, and I can't see an approach better than annealing.) Once you have that method, you can create a modified Dijkstra. – Beta Jul 02 '16 at 01:19
  • @lightalchemist By "Acceleration", I mean "Change in velocity". (So, edge cost = euclidean distance/speed, but only allowed if you're traveling in the right direction... so) Unchecked velocity is fine (it's meant to be a math puzzle, not a simulation... though I did initially envision it for a spacecraft picking up fuel caches, so friction still wouldn't be a thing.) – Edward Peters Jul 02 '16 at 01:21
  • @Beta Hmm... yeah, even if you know the order there's some question of what values you want to take at each point. Good sub-problem. I don't think it would allow for modified Djikstras, though, because you still wouldn't really be able to pick the "closest" point. – Edward Peters Jul 02 '16 at 01:24
  • 3
    If there are only a finite number of different possible acceleration vectors that can be achieved, then this is very similar to the Vector Racetrack game, which I solved here: http://stackoverflow.com/a/6598303/47984. In short, you *can* solve it with Dijkstra, but on a state space where you have a vertex for each (location, entry speed vector) combination instead of just for each location. – j_random_hacker Jul 02 '16 at 14:23
  • 1
    @j_random_hacker I was thinking you would have infinite possible acceleration vectors, but I believe you might be able to break it up into ranges, where each point in a range is purely worse than the point at the top of that range, so you would only have to consider finitely many. It may be a very large finite number, though. – Edward Peters Jul 04 '16 at 02:31
  • I see. It also seems to me that there might turn out to be just a finite number of these "worthwhile-to-consider" vectors, but finding them could be hard. – j_random_hacker Jul 04 '16 at 15:04
  • It is somewhat similar to the Topcoder marathon problem recently asked : https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16703&pm=14268 – uSeemSurprised Jul 05 '16 at 14:05

2 Answers2

3

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:

enter image description here

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.

hugomg
  • 68,213
  • 24
  • 160
  • 246
  • 1
    I don't think it's quite the Hamiltonian path problem (it might be harder, not easier), because there's no guarantee that visiting every point would be best. Acceleration is in velocity, not just picking up speed... so if you have to change directions a lot to hit every point, you might come out of it moving more slowly than if you hit 4 or 5 that were all roughly colinear with your destination. – Edward Peters Jul 02 '16 at 01:21
  • Umm... I think you might need to specify mode clearly how the physics works in your model then. When I read it I understood that the acceleration was a simple "speed boost" that made any future edges cheaper to traverse . – hugomg Jul 02 '16 at 01:23
  • Okay, edited the problem to make it clearer. I'd been thinking that direction mattered (so if your velocity was high enough, it would effectively not be a complete graph). I think I agree that in the problem as you described it, it can come down to a Hamiltonian path in certain situations. – Edward Peters Jul 02 '16 at 01:31
3

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.

Vesper
  • 18,599
  • 6
  • 39
  • 61
  • I'm not sure I understand all of your answer... mind clarifying a couple of things that look like they might be wrong to me? "designate maximum speed along the line to be able to turn from that node to any other" sounds like it loses too much information, because you might be able to reach some nodes and not others, or reach some nodes but only at speed ranges that prevent you from reaching still others, etc. In "The culling rule will be if a path from current to next node exists with less velocity and less time spent from end", what do you mean by "less velocity?" Sometimes velocity is good. – Edward Peters Jul 04 '16 at 02:47
  • About "maximum speed" - it can be per node, a node closer to the vector will allow higher speeds. "Less velocity" means that if you're querying path A-B, determine what velocity can be achieved when turning at A to reach B, find out that there's a path at B that came from A but spent less time reaching B AND was slower at A-B, this means your current path lags behind and can be discarded. – Vesper Jul 04 '16 at 06:14
  • But there's one caveat I've thought about: What if you start at A and are able to visit A to accelerate? This algorithm will fail then, if there's a node behind A. Imagine config: B --- A --- C, source is A, target is C, and you can accelerate for 5 at A, and for 10 at B, with AC being pretty long. The proper path could end up A-B-A-C, say if you travel at 4 from A to B, return at 6 from B to A, and then 11 from A to C, which will be faster than going at 5 from A to C directly, and faster than going A-B-C. – Vesper Jul 04 '16 at 06:16
  • I don't think slower from `A-B` is always better, even if it takes less time to do... what if `A, B, C` are co-linear, and the distance from `B` to `C` dominates?Then you want to be going as fast as possible when you hit `B`, because ability to steer is less important than having speed built up. The other thing is that this isn't just pairwise: I might be able to enter `B` at a speed that gets me to `C`, but not on to `D`, or even that forces me to use almost all of my acceleration at `D` canceling lateral momentum, so I have to go to `E` at a dead crawl. – Edward Peters Jul 04 '16 at 06:25
  • In fact, I'm about to ask a similar question regarding your problem, as a certain combination of data makes calculating optimal time even for a single path a serious problem. You're right at least in that maximum speed from A to B isn't always good. Please consider this answer questionable at least, maybe your problem is indeed not optimizable. – Vesper Jul 04 '16 at 06:29