Hacker News new | past | comments | ask | show | jobs | submit login
A* (wikipedia.org)
50 points by tosh on Aug 10, 2019 | hide | past | favorite | 6 comments

Contraction hierarchies[0] are a nice extension over which A* works even better and I believe these are used in osrm. I read a paper by Microsoft Research where they optimized the setting to enable shortest path routing in average of 5 memory reads, or something ridiculously unbelievable like that. [1]

0: https://en.wikipedia.org/wiki/Contraction_hierarchies

1: https://www.microsoft.com/en-us/research/wp-content/uploads/...

Related question: do you know how leveraged GPUs are in shortest path implementations and research?

The [1] paper contains a reference to PHAST https://www.microsoft.com/en-us/research/publication/phast-h...

My favorite variant of this is IDA


Iterative Deepening A Star

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact