**# A* path finding: ( googling for**

`astar c`

.)**# Path matrix for required length**

`matrix[u][v] = 1`

denotes an edge between u and v, and `matrix[u][v] = 0`

denotes no edge between u and v. Then `(matrix)^3`

(just simple matrix exponentiation) is 'magically' the path matrix of exactly length 3.**Classic Data Structures**, by D. Samanta at page 367

**# Some other related topics**:

- An efficient implementation of Dijkstra's algorithm takes O(Elog V) time for a graph with E edges and V vertices.
- Hosam Aly's "flood fill" is a breadth first search, which is O(V). This can be thought of as a special case of Dijkstra's algorithm in which no vertex can have its distance estimate revised.
- The Floyd-Warshall algorithm takes O(V^3) time, is very easy to code, and is still the fastest for dense graphs (those graphs where vertices are typically connected to many other vertices). But it'snot the right choice for the OP's task, which involves very sparse graphs.

Raimund Seidel gives a simple method using matrix multiplication to compute the all-pairs distance matrix on an unweighted, undirected graph (which is exactly what you want) in the first section of his paper On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs [pdf].

**# This one is not exactly the path finding problem, but also very interesting-- like generating the possible move**

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

## No comments:

## Post a Comment