3
$\begingroup$

Dijkstra's algorithm is often quoted as being used to find the shortest path route however I was surprised to know that there exist A* search which is a extension of Dijkstra's algorithm.

How is it that A* search algorithm is able to perform better compared to Dijkstra's algorithm , what sort of technique does it used that Dijkstra's algorithm did not use ???

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/A*_search_algorithm $\endgroup$ – saadtaame Apr 10 '14 at 2:22
  • 1
    $\begingroup$ Who says it performs better? They don't even solve the same problem! $\endgroup$ – Raphael Apr 10 '14 at 7:56
4
$\begingroup$

Consider providing driving directions from an origin to a destination. Although sometimes traveling away from the destination for short distances is required (think highway on ramp), in general it is best to travel toward the destination. In this case A* is likely to outperform Dijkstra's algorithm because it (probably) will traverse less of the graph.

Dijkstra's algorithm uses a single heuristic, $g(n)$, which is the distance from the origin. In selecting the next road to evaluate, the road with the least $g(n)$ is selected; however, this road may travel away from the destination. A* adds an estimate of the remaining distance, $h(n)$, to bias the search towards the destination. The full A* heuristic is $f(n) = g(n) + h(n)$. Note that as the search progresses, $f(n)$ must monotonically increase or else the path found may not be the shortest. Thus, $h(n)$ must be optimistic and never underestimate the remaining distance (in the directions example, assume the remainder of the trip can be a straight line).

$\endgroup$
1
$\begingroup$

First, you have to note that A* is a generalization of Dijkstra's and the two are equivalent when you have a uniform-cost heuristic and your evaluation function $f(n) = g(n) + h(n)$ can be simplified by just using $f(n) = g(n)$ (where $g(n)$ is the actual cost at node $n$) since each node will have the same heuristic estimate. On the other hand, you can specify a non-uniform heuristic function $h$ which allows you to favour expanding certain nodes before others and this is more effective when your heuristic $h(n)$ is more representative of the distance from node $n$ to your goal node. By evaluating certain nodes before others, you can reach the goal node a whole lot sooner, but remember: this depends on your heuristic whose purpose is to provide a fast, representative estimate.

$\endgroup$
1
$\begingroup$

This two algorithms use the same method - choose the best state and expand it by all possible methods, don't use state twice. The problem is - "which one is the best?". Dijksta algorithm solve concrete case of directed graph with positive edges weight. And it's easy to get the best vertex - it have smallest distance from initial vertex and adjacent to one of visited vertexes. So, dijkstra will find the shortest path on every input data.

A* can be used for any task, even when you can't say exactly what state is the best, for example I've solved 15-puzzle with it. In this case there are many table states which can be considered "best" so we choose the first. But found path isn't shortest.

I used obvious heuristic h(state) = manhattan distances between numbers and it final positions (in reverse, it is 0 when puzzle solved). g(state) = number of steps to achieve this state (as always). Priority is f(x) = h(x) + g(x). Of course, there can be much better estimation (mb it's better to don't touch 1 2 3 4 but stay shuffling 5 6 7 8 ... just as first thoughts).

So, when A* used for something (in STRIPS planning system, or simple pathfinding), it's possible to find very good h(x) for concrete case of graph, so perfomance can become really unexpected (for example, "jump point search" for uniform-cost grid map gives optimal soultion and much better perfomance than bfs-like steps + manhattan heuristic).

Anyway, determined solution still stay preffered. There is no need to solve Rubik's cube with A*, as you can solve it by usual algorithms (you can predict steps count then). And proved classic dijkstra is better than A* when you need to find short path in directed graph with positive edges (and it will be the shortest).

$\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.