Abstract | ||
---|---|---|
This paper establishes an upper bound on the time complexity of iterative-deepening-A* (IDA*) in terms of the number of states that are surely-expanded by A* during a state space tree search. It is shown that given an admissible evaluation function, IDA* surely-expands in the worst caseN(N+1)/2 states, whereN is the number of states that are surely-expanded by A*. The conditions that give rise to the worst case performance of IDA* on any state space tree are described. Worst case examples are also given for uniform and non-uniform state space trees. |
Year | DOI | Venue |
---|---|---|
1992 | 10.1007/BF01543478 | Ann. Math. Artif. Intell. |
Keywords | DocType | Volume |
Neural Network,Artificial Intelligence,Complex System,State Space,Evaluation Function | Journal | 5 |
Issue | ISSN | Citations |
2-4 | 1012-2443 | 5 |
PageRank | References | Authors |
0.54 | 12 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Brian G. Patrick | 1 | 5 | 1.22 |
Mohammed Almulla | 2 | 147 | 20.60 |
Monroe M. Newborn | 3 | 177 | 47.49 |