Editing Iterative deepening depth-first search (section)

== Properties ==
IDDFS achieves breadth-first search's completeness (when the [[branching factor]] is finite) using depth-first search's space-efficiency. If a solution exists, it will find a solution path with the fewest arcs.<ref name=":0">{{cite web |author1=David Poole |author2=Alan Mackworth |title=3.5.3 Iterative Deepening‣ Chapter 3 Searching for Solutions ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition |url=https://artint.info/2e/html/ArtInt2e.Ch3.S5.SS3.html |website=artint.info |access-date=29 November 2018}}</ref>

Iterative deepening visits states multiple times, and it may seem wasteful.  However, if IDDFS explores a search tree to depth <math>d</math>, most of the total effort is in exploring the states at depth <math>d</math>.  Relative to the number of states at depth <math>d</math>, the cost of repeatedly visiting the states above this depth is always small.<ref name="rn3">{{Russell Norvig 2003}}</ref>

The main advantage of IDDFS in [[game tree]] searching is that the earlier searches tend to improve the commonly used heuristics, such as the [[killer heuristic]] and [[alpha–beta pruning]], so that a more accurate estimate of the score of various nodes at the final depth search can occur, and the search completes more quickly since it is done in a better order. For example, alpha–beta pruning is most efficient if it searches the best moves first.<ref name="rn3"/>

A second advantage is the responsiveness of the algorithm. Because early iterations use small values for <math>d</math>, they execute extremely quickly. This allows the algorithm to supply early indications of the result almost immediately, followed by refinements as <math>d</math> increases. When used in an interactive setting, such as in a [[chess]]-playing program, this facility allows the program to play at any time with the current best move found in the search it has completed so far. This can be phrased as each depth of the search [[corecursive|''co''recursively]] producing a better approximation of the solution, though the work done at each step is recursive. This is not possible with a traditional depth-first search, which does not produce intermediate results.