I can find quite a bit of literature on A* but very little on A.What is the difference between the two search algorithms?
Algorithm A vs Algorithm A*: What's the difference?
algorithms;graphs;search algorithms;shortest path;heuristics
Both A and A* algorithm use a best-first search to find the least cost path from a start state to a goal state.Best-first search applies a heuristic evaluation on the states to find the 'best' state.Consider the evaluation function f,f(n) = g(n) + h(n)where g(n) measures the cost of reaching any state n from the start stateand h(n) is a heuristic estimate of the cost of going from state n to a goal.f(n) estimates the total cost of the path from the start state throngh n to the goal stateIf this evaluation function is used with best-first search, then the result is Algorithm A.Here h(n) is just an estimate of the cost of going from n to a goal. The actual cost is not known.Now consider the evaluation function f*,f*(n) = g*(n) + h*(n)where g*(n) is the cost of the shortest path from start state to state nand h*(n) is the actual cost of the shortest path from state n to goal.Although f* does not exist for most real problems, we would like f to be a close estimate of f*.In algorithm A, g(n) is a reasonable estimate of g*(n).g(n) >= g*(n)They are equal when the graph search has discovered an optimal path to n.Although we may not compute h*, it is often possible to determine whether or not the heuristic estimate h(n) is always less than or equal to the actual cost of minimum oath, h*(n).If the Algorithm A uses a function f in which h(n) <= h*(n) , it is called algorithm A*.