And for those wondering when you'd use this algorithm (as even academics don't seem to know!) - it is the go-to algorithm for implementing pathfinding in video games, and robotics.
Yup. The algorithm was first used in planning paths for Shakey The Robot back in the late 1960s, which seems like ancient history in computer terms. (I only know of it because my dad "invented" A-star. :-) )
The most widely-known form of best-first search is called A-start search (pronounced "A-star search"). It evaluates nodes by combining g(n) - the cost to reach the node, and h(n) - the cost to get from the node to the goal:
Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path from n to the goal, we have Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of g(n) + h(n). It turns out that this strategy is more than just reasonable: provided that the heuristic function h(n) satisfies certain conditions, K search is both complete and optimal.So, for the following graph (tree actually):
Where the function g(x) is the depth of the node in the tree, and the heuristic function h(x) is presented next to the node (random values), A-star will search for a solution first in the nodes with smaller values of f(n). So a traversal starting at node A will visit nodes in the following order: {A, B, C, E, D} If there's anything wrong with my explanation please correct me.P.S.: I know my heuristic function is probably not admissible.