2
$\begingroup$

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

What is the difference between the two search algorithms?

$\endgroup$
4
$\begingroup$

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*.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.