Performance of A* and IDA*-a worst case analysis
Ambuj Mahanti, A.K. Pal, S. Ghosh, Laveen N. Kanal, Dana S. Nau · 2002
Summary form only given. The paper presents a detailed comparison between algorithms A* and IDA*. A* is a best first search algorithm which at each node n in the graph uses a node evaluation function f(n)=g(n)+h(n), where g(n) is the cost of the currently known best path from the start node s to n and h(n) is an estimate of h*(n) (cost of the minimum cost path from n to a goal node). At each iteration, A* selects a node with minimum f-value for expansion. A* is known to be optimal in terms of number of node expansions. However, the storage requirement of A* is very high-it is exponential in the depth of the solution found. The other algorithm, IDA*, unfolds a graph into a tree. In every iteration, IDA* starts the search from the start node and makes a depth first search within the current threshold. The paper presents a necessary and sufficient condition for the O(N) time complexity of IDA*. It shows that IDA* can have O(N) time complexity under a more general condition than that was originally felt. Moreover, it illustrates through examples, that the different conditions imposed in the analysis of IDA* are neither sufficient nor necessary. It also shows that the worst case time complexity of IDA* can become O(N/sup 2/) for tree searches.>