Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

It's also misleading because nothing optimal is faster than A* . Quote from AIMA:

"A∗ is optimally efficient for any given consistent heuristic. That is, no other optimal algorithm is guaranteed to expand fewer nodes than A∗ (except possibly through tie-breaking among nodes with f(n) = C∗). This is because any algorithm that does not expand all nodes with f(n) < C∗ runs the risk of missing the optimal solution."



In the general setting A-star is optimal. JPS (and JPS+) can speed it up if you have additional information about the topology of the search space: 1) search is on a rectangular grid, and 2) movement between adjacent grid squares has uniform cost. In that case, you can take advantage of certain properties/symmetries of a rectangular grid to safely "skip" parts of the expansion that A-star would normally do, while still being guaranteed to find the optimal solution.

The JPS paper from a few years ago explains in more detail: http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-g...


> nothing optimal is faster than A* .

For what task? The speaker seems to be concerned with the problem of answering repeated path-finding queries for a single static map. With that problem in mind A* is indeed sub-optimal since it redoes all the computations for each query.


In that sense nothing is faster than Dijkstra's. There are problems for which A* heuristic fails completely, and Dijkstra's is better. JPS exploits a more specific structure of pathfinding just like A* exploits structure given by an heuristic. We have to be very careful to the setting when we say something is 'optimal'.


What probably fudges around this, is that all the nodes get looked at before any routing code starts running. A* is coming to the graph cold.




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

Search: