Strict Standards: Non-static method DB::connect() should not be called statically, assuming \$this from incompatible context in /group/project/aicat/web/lib/database.php on line 32

Strict Standards: Non-static method DB::parseDSN() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB.php on line 520

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB.php on line 557

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /group/project/aicat/web/lib/database.php on line 34

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /group/project/aicat/web/lib/database.php on line 92

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1009

Strict Standards: Non-static method DB::isManip() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 2200

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /group/project/aicat/web/lib/database.php on line 97

Strict Standards: Non-static method DB::connect() should not be called statically, assuming \$this from incompatible context in /group/project/aicat/web/lib/database.php on line 32

Strict Standards: Non-static method DB::parseDSN() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB.php on line 520

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB.php on line 557

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /group/project/aicat/web/lib/database.php on line 34
Catalogue of Artificial Intelligence Techniques

# Catalogue of Artificial Intelligence Techniques

View Maths as: Images | MathML

Strict Standards: Non-static method DB::isManip() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 2200

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1217

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1666

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB.php on line 1387

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1683

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /group/project/aicat/web/lib/database.php on line 113

Strict Standards: Non-static method DB::isManip() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 2200

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1217

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1666

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB.php on line 1387

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1683

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /group/project/aicat/web/lib/database.php on line 113

Strict Standards: Non-static method DB::isManip() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 2200

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1217

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1666

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB.php on line 1387

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1683

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /group/project/aicat/web/lib/database.php on line 113

Strict Standards: Non-static method DB::isManip() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 2200

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1217

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1666

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB.php on line 1387

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1683

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /group/project/aicat/web/lib/database.php on line 113

## Iterative Deepening

### Categories: Search

Author(s): Frank van Harmelen

An uninformed graph search algorithm which is a good compromise between the efficiency of Depth-first Search and the admissibility of Breadth-first Search. Iterative deepening performs a complete search of the Search Space (often using a depth-first search strategy) up to a maximum depth $d$ . If no solutions can be found up to depth $d$ , the maximum search depth is increased to $d+1$ , and the search space is traversed again (starting from the top node). This strategy ensures that iterative deepening, like breadth-first search, always terminates in an optimal path from the start node to a goal node whenever such a path exists (this is called admissibility); but it also allows implementation as an efficient depth-first search. Iterative deepening is optimal in both time and space complexity among all uninformed admissible search strategies. At first sight it might look as if iterative deepening is inefficient, since after increasing the cut-off depth from $d$ to $d+1$ , it redoes all the work up to level $d$ in order to investigate nodes at level$d+1$

. However, since typical search spaces grow exponentially with$d$

(because of a constant branching factor), the cost of searching up to depth $d+1$ is entirely dominated by the search at the deepest level $d+1$ : If $b$ is the average branching rate of the search space, there are ${b}_{}^{\left(d+1\right)}$ nodes at depth $d+1$ , which is the same as the total number of nodes up to depth $d$ . In fact, it can be shown that among all uninformed admissible search strategies, iterative deepening has the lowest asymptotic complexity in both time ($O\left({b}_{}^{d}\right)$ ) and space ($O\left(d\right)$ ). Breadth-first search on the other hand is only asymptotically optimal in time, and is very bad (exponential) in space. The actual time complexity of breadth-first search (as opposed to the asymptotic complexity) is of course lower than that for iterative deepening (namely by the small constant factor $b/b-1$ ), but this is easily offset by the difference in space-complexity in favour of iterative-deepening. Thus, iterative-deepening is asymptotically optimal in both time and space, whereas breadth-first is asymptotically optimal only in time and really bad in space, while the actual complexities of iterative-deepening and breadth-first are very close. Iterative deepening can also be applied to informed search strategies, such as A*. This modified version of A* is again optimal in both time and space among all informed admissible search strategies.

### References:

Strict Standards: Non-static method DB::isManip() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 2200

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1217

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1666

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB.php on line 1387

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1683

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /group/project/aicat/web/lib/database.php on line 113

• Korf, R.E., Search: A Survey of Recent Results, Exploring Artificial Intelligence (Survey talks from the National Conferences on Artificial Intelligence) (Shrobe, H.E. , ed.), Morgan Kaufmann, San Mateo, California, 1988, pp.197--237 (Chapter 6).

Strict Standards: Non-static method DB::isManip() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 2200

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1217

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1666

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB.php on line 1387

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /usr/share/pear/DB/common.php on line 1683

Strict Standards: Non-static method DB::isError() should not be called statically, assuming \$this from incompatible context in /group/project/aicat/web/lib/database.php on line 113