Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I want to make my A-Star fast, by using heuristics. At the moment it is very slow and even slower than my Dijkstra. I thougt A-Star is in the worst case as fast as Dijkstra. I convert my OSM bounding box wiht osm2po to a postgresql database with postgis support and then I do my routing with java on android. Do I have to consider something in the osm2po configuration file to get the right weight? For the heuristics calculation I use the Manhattan distance.

share|improve this question
    
You should use a different heuristic for the distance otherwise you're overestimating the distance which makes the results inexact - why not use the air distance (which is natural when using OSM data)? And: A* should be faster than Dijkstra otherwise something is wrong. –  Karussell Jun 25 '13 at 6:43
    
You mean Euclidean distance? –  Irgendw Pointer Jun 25 '13 at 7:29
    
yes (necessary fill for SE) –  Karussell Jun 25 '13 at 10:02
add comment

1 Answer

Mostly an AStar is faster than a Dijkstra. But it's a superstition that it is always faster. Imagine an area shaped like a circle. Routing from the center to a border point lets expand a Dijkstra to the worst case whereby an AStar shows its optimal behavior. Driving the reverse route an AStar will expand to almost the same worst case. But in addition, an AStar has to calculate the distance to the target (using at least the Euclidean Distance calculation) which is a very expensive operation. In this case, it would be indeed slower than a Dijkstra. Nevertheless, you cannot use the Manhattan Distance. The Manhattan Distance is a good filter for expensive Distance calculations, but no alternative.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.