Hacker News new | past | comments | ask | show | jobs | submit login

The algorithms themselves are almost unaware of a path, they simply visit nodes, check their neighbours, then continue with another node from the queue. Breadth First Search simply does this in a predictable order, but of course it isn't prioritising nodes closest to the goal; that's where the other three come in. Every node has a path cost, how many moves it took to make it to the node. You can also define a distance heuristic, that calculates geometric distance to the goal as a strict underestimate. All these algorithms simply exit when the goal node is reached, and a path has been created by the algorithm.

Dijkstra, or also known as Uniform Cost Search, will pick nodes with the lowest path cost from the queue first. This works well on graphs, but not so well on open spaces. It should be mentioned that this algorithm is complete, and optimal. That is, it will find a path if one exists, and it will find the path of lowest path cost (note there may be many such paths of equal path cost).

Then we have A, which is also complete and optimal. This uses the sum of path cost and distance heuristic. This means it will nodes closer to the goal, but long-windy paths will confuse it.

Finally we have Best First Search. It should be mentioned this is actually a family, of which Dijkstra and A are members. In this program, it only considers distance heuristic. So nodes that are geometrically closer to the goal are evaluated first. It should be mentioned that it isn't optimal - it might not find the path of lowest cost. If the optimal path requires at first winds away form the goal, these nodes aren't considered until later, or maybe never.




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

Search: