4 ms·

I thought A* _was_ Best-first-search. https://en.wikipedia.org/wiki/Best-first_search https://en.wikipedia.org/wiki/Best-first_search Can someone explain the d

• keeperofdakeys 14y ago
  Best-First Search is a family of algorithms. Specifically, it picks the best candidate node that has been discovered. A* and Dijkstra/Uniform Cost Search are in this family. In this website, Best-First Search uses only the heuristic distance function (distance from current node to goal, in terms of coordinates). This means it will prioritise nodes geometrically closest to the target first. In most cases this works well, but paths with lots of twists that are close to the goal will get longer paths. This also means it isn't optimal (returns the path of lowest cost), whereas A* and Dijkstra/Uniform Cost Search are optimal. Now Dijkstra/Uniform Cost Search only considers path cost to prioritise nodes, and A* considers the sum of path cost and heuristic. This means they do find the path of lowest cost.