Jump to content
Posted 24 November 2012 - 12:36 PM
Posted 24 November 2012 - 12:44 PM
Posted 24 November 2012 - 12:51 PM
Posted 24 November 2012 - 12:56 PM
There is no best way. Representation of the search space is orthogonal to functioning of the A* algorithm.
Posted 24 November 2012 - 01:02 PM
Posted 24 November 2012 - 02:23 PM
You're looking at it from the wrong direction. Come up with a situation where you would want to use pathfinding. Create a representation suitable for that situation, and then figure out how to use A* with that representation.
Okay - then perhaps my question should have been - which representation of the search space will make running the A* algorithm on it easiest? What method is most commonly used?
Which is why I think that representation is orthogonal to A*. If you've got a representation where you can't efficiently determine node transitions, then you're representation will also be inefficient for pretty much any operation, not just search algorithms. Obviously, if you're going to choose a representation for the search space which is inefficient for general use, then of course it's going to be sub optimal for A*. The point is to come up with a representation that makes sense for the system being modeled.
In the case of A*, however, all you need from the graph is iterating through the nodes that are connected to a given node, which is the most basic thing you can ask from a graph.
Posted 25 November 2012 - 04:28 AM