|
|
|
|
|
|
by Sharlin
5356 days ago
|
|
|
Another useful way to see A* is as the synthesis of two different search algorithms. To compute which untraversed node to choose next, A* uses the function f(n) = g(n) + h(n)
where g(n) is the actual traversed distance from the start to n, and h(n) is an (optimistic) approximation of the distance from n to the goal. Now, without making any other modifications to the algorithm, if we substitute g(n) = 0
what we get is the greedy "best-first" search [1]. If, on the other hand, we select h(n) = 0
we get a single-goal variant of Dijkstra's algorithm [2].[1] http://en.wikipedia.org/wiki/Best-first_search [2] http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm |
|
|