Algorithm A vs Algorithm A*: What's the difference?

Question

I can find quite a bit of literature on A* but very little on A.

What is the difference between the two search algorithms?

Answer 1

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 state and 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 state

If 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 n and 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*.