principleMinor
Algorithm A vs Algorithm A*: What's the difference?
Viewed 0 times
algorithmdifferencethewhat
Problem
I can find quite a bit of literature on A* but very little on A.
What is the difference between the two search algorithms?
What is the difference between the two search algorithms?
Solution
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*.
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*.
Context
StackExchange Computer Science Q#50722, answer score: 5
Revisions (0)
No revisions yet.