I can find quite a bit of literature on A* but very little on A.
What is the difference between the two search algorithms?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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*.