Algorithm to find most efficient moves to arrive at a given point

Question

(This is not exactly the problem that I have, but it's isomorphic, and I think that this explanation will be easiest for others to understand.)

Suppose that I have a set of points in an n-dimensional space. Using 3 dimensions for example:

A : [1,2,3]
B : [4,5,6]
C : [7,8,9]

I also have a set of vectors that describe possible movements in this space:

V1 : [+1,0,-1]
V2 : [+2,0,0]

Now, given a point dest, I need to find a starting point p and a set of vectors moves that will bring me to dest in the most efficient manner. Efficiency is defined as "fewest number of moves", not necessarily "least linear distance": it's permissible to select a p that's further from dest than other candidates if the move set is such that you can get there in fewer moves. The vectors in moves must be a strict subset of the available vectors; you can't use the same vector more than once unless it appears more than once in the input set.

My input contains ~100 starting points and maybe ~10 vectors, and my number of dimensions is ~20. The starting points and available vectors will be fixed for the lifetime of the app, but I'll be finding paths for many, many different dest points. I want to optimize for speed, not memory. It's acceptable for the algorithm to fail (to find no possible paths to dest).

Update w/ Accepted Solution

I adopted a solution very similar to the one marked below as "accepted". I iterate over all points and vectors and build a list of all reachable points with the routes to reach them. I convert this list into a hash of <dest, p+vectors>, selecting the shortest set of vectors for each destination point. (There is also a little bit of optimization for hash size, which isn't relevant here.) Subsequent dest lookups happen in constant time.

Answer 1

Given that you have the starting points and a fixed set of vectors, can you calculate the list of all reachable destinations and then just look up a given destination?

Answer 2

I believe you would be able to make a generalized application of the A* (aka A star) path finding algorithm. There is no reason why it can't be done in Nth space. It gaurantees the most optimal path, if you can describe the cost of each move.

http://en.wikipedia.org/wiki/A*_search_algorithm

Answer 3

1. Begin at the start.
2. Do for a While
3. Get the distance to the destination
4. Test all possible moves and pick the one that gets you closest to the destination in one move.
5. end do

This may oscillate around the destination, but it will get you close.

Answer 4

Actually, considering that you have around 10 vectors, you can, for a given dest point, calculate only the 1024 "targets" from the subset of vectors -- e.g every reachable space, with the information about what set of moves gets there. That might be "slow", or "fast" depending on context (it's be absurdly fast if implemented on a parallel computing device like the GPU).

Having all the sets that get there you can calculate the paths a lot quicker, then you can pick the point from which to get to dest in the fewest moves, choosing from the subset of the ones that are either your query or further.

(thanks to Strilanc)

Answer 5

So you want to find a subset of your set of vectors such that the subset sums to a given value. In 1 dimension this is called the subset sum problem, and is NP-Complete.

Luckily you only have ~10 vectors, so your problem size is actually quite small and tractable. Start by just trying all 2^10 move combinations for each starting point and picking the best one. Then work from there looking for simple optimizations.

Some easy optimizations that might work:

• Prioritize searching subsets including vectors pointed in the right direction.
• Meet-in-the-middle. Use a hash table to store all points reachable using subsets of the first half of your move set, and see if you can hit any using the second half of your move set starting from the end.
• Go backwards. You only have one endpoint, so hash all reachable start points from there then check against all possible start points.
• Concurrency

Answer 6

As Kornel states, you have at most 2^10 = 1024 reachable destinations. So you could just generate all reachable destinations in 2^N time (where N is the number of vectors) by a simple recursive generation. This is going to be fast enough, of course. However, let's assume you wanted to stretch it.

You could optimise it to O(2^(N/2+1)) time by using a meet-in-the-middle solution. You split the vector set into two subsets and generate all reachable destinations for each subset independently. You then iterate through one set of reachable destinations, and for each location find the difference between it and the target destination. If that difference vector is in the other set of reachable destinations, you have a solution: combine the two and you're done. The difficulty here is in efficiently querying if you have the required vector in the other set: this can be done in O(1) time using a hash table.

That's O(2^(N/2)) time per subset, times two subsets gives O(2^(N/2+1)). To join the two it's O(2^(N/2)) time. So that gives us O(2^(N/2+1)) time overall.