4
$\begingroup$

I was wondering as what are the specific conditions which make the A* algorithm - optimal in terms of the node expansion over the other Unidirectional algorithms:

When the same heuristic information is given to all the algorithms.

$\endgroup$
  • $\begingroup$ Related: cs.stackexchange.com/questions/30778/… $\endgroup$ – user340082710 Aug 1 '15 at 1:41
  • $\begingroup$ I clearly wrote Optimal in terms of node expansion. Dijkstra's algorithm is for finding the shortest path from source node to all other nodes. A* is for one source and destination node. And to avoid evaluation of paths which can be never be optimal it uses heuristic. So, the question is aimed in understanding the necessary conditions in which the to avoid such unnecessary computations where A* triumphs other shortest finding algorithm in terms the number of possible paths considered. $\endgroup$ – letsBeePolite Aug 1 '15 at 18:18
1
$\begingroup$

This is a nice question! Indeed, A* is known to be asymptotically optimal in the number of expansions. This is usually understood by saying that any algorithm solving the same problem should expand the same set of nodes at least. A unique property of A* with regard to its asymptotical behaviour is that, in addition, it never re-expands any nodes ---in contraposition with other algorithms such as IDA* and RBFS.

But first things first. Before addressing why A* is asymptotically optimal let me note in passing that A* is a suitable algorithm not only for the shortest path problem but those problems that actually verify the suboptimal structure, this is, that all the subpaths in the solution are solutions also between their respective start and end nodes. Additionally, A* is asymptotically optimal not only with regard to evaluation functions $f()$ which are scalar values but, in general, with any that verify the so called cost algebras.

In the following I address the question by mentioning the two contributions of A* that address its asymptotically optimal behaviour and also the role played by the heuristic function $h(n)$.

From the preceding paragraph, the first condition is that $f()$ should be non decreasing, i.e., $f(n) \leq f(n')$ where $n'$ is a descendant of $n$. This property is exploited by Raphael, Hart and Nilsson (the authors of A*) to create a CLOSED list that stores all nodes that have been previously expanded: if a node which is about to be expanded is found in CLOSED, then it is not expanded again even if its $f$-value is larger. The reason is simple: If that node was already expanded, a shortest path cannot go through a more expansive subpath (hope you see here how the principle of suboptimal structure applies). The second contribution of A* is that all newly generated nodes are inserted in an OPEN list and they are sorted in increasing order of their $f$-value. This guarantees that no node with a $f$-value strictly larger than the cost of the optimal solution is ever expanded.

In general, both conditions are also satisfied by Dijkstra's algorithm and, from here, by any of the so called Best-first search algorithms. A* is different from those however in the design of the $f$ evaluation function which is defined as $f(n)=g(n)+h(n)$. Now, if $h(n)$ is admissible, i.e., it never overestimates the effort to reach the goal then it is non-decreasing and, from here, optimality of the solutions found can be guaranteed.

Note, however, that some nodes with a $f$-value equal to the optimal cost might be expanded by A* whereas they are not needed at all. Some works, such as EPEA tried to address this issue with the design of specific operator tables.

Hope this helps,

$\endgroup$
  • $\begingroup$ I'm not sure I understand how this proves that A* expand less nodes than any other algorithm. This only proves it will find the shortest path. $\endgroup$ – Celelibi Dec 21 '15 at 9:15
  • 1
    $\begingroup$ yes, if you assume that any algorithm should expand all nodes with $f (n)<C^*$ where $C^*$ is the cost of the optimal solution. The arguments given above prove exactly this. There is caveat, though, and it is that an arbitrary number of nodes with $f(n)=C^*$ might be expanded but, as mentioned, there are techniques to avoid this as well. $\endgroup$ – Carlos Linares López Dec 28 '15 at 13:35

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.