Notes on Path Finding problem

Some good sources on Path-finding:

# A* path finding: ( googling for astar c.)

By Patrick Lester (Updated July 18, 2005)  

http://www.policyalmanac.org/games/aStarTutorial.htm

http://www.heyes-jones.com/astar.html

http://stackoverflow.com/questions/3412157/a-implemented-in-c

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

# Path matrix for required length

Create the adjacency matrix where 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.

The theorem that addresses the random walk problem is this:

Let A = [aij] be the adjacency matrix of a graph G having points n1, …, nn.  Let k be any positive integer.  Then the number of distinct n1-nj walks of length k in G is equal to the i, j element of A^k. 

Check 

A) book: Classic Data Structures, by D. Samanta at page 367

http://books.google.com/books?id=_lDjLlasQycC&lpg=PA368&ots=LRtfxKppaq&dq=path%20matrix%20of%20exactly%20length&pg=PA367#v=onepage&q=path%20matrix%20of%20exactly%20length&f=false

B) http://oneweb.utc.edu/~Christopher-Mawata/petersen/lesson7.htm

# Some other related topics:

• maze creator
• find longest distance

The python code for :  Dijkstra to find two points furthest away from each other

# Find the longest path:

http://stackoverflow.com/questions/477591/algorithm-to-find-two-points-furthest-away-from-each-other

From the record:

• 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

http://stackoverflow.com/questions/2111934/algorithm-to-find-most-efficient-moves-to-arrive-at-a-given-point

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

Other links from arizona cs445:

• Animations Of Sorting Algorithms 
  
  
• Animation of Dijkstra's Algorithm 
  
  
• Animation of Prim's Algorithm 
  
  
• Animation of Kruskal's Algorithm 
  
  
• Animation of Flow Graph Algorithm 
  
  
• Animations of Some Ccomputational Geometry Algorithms (including line-sweep)

--

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥