Iterative deepening search (IDS) combines the benefits of breadth-first and depth-first search: it has modest memory requirements (linear space complexity), and it is complete and optimal when the branching factor is finite, with a time complexity comparable to breadth-first ( is the depth of the solution). IDS works in tandem with depth-limited search and finds the best depth limit with a gradually increasing loop, see Figure 1. In general, IDS is the preferred uninformed search method when the search space is large and the depth of the solution is not known.

Figure 1. Iterative deepening search algorithm.

## @deftypefn {Function File} {@var{solution} =} iterative_deepening_search(@var{problem}, @var{start}, @var{finish})
## Iterative deepening search algorithm.
##
## PRE:
## @var{problem} must be the cost-weighted adjacency matrix.
## @var{start} must be the starting node index.
## @var{finish} must be the finishing node index.
##
## POST:
## @var{solution} is the solution path. State set to zero if there
## is no solution.
## @end deftypefn

## Author: Alexandre Trilla <alex@atrilla.net>

function [solution] = iterative_deepening_search(problem, start, ...
  finish)

  limit = 1;
  while (limit)
    solution = depth_limited_search(problem, start, finish, limit);
    limit += 1;
    if (solution.state ~= 1)
      break;
    endif
  endwhile

endfunction

With IDS you have got to the end of the section that deals with uninformed search strategies. What follows is the journey through informed search methods, where environment knowledge is incorporated in the search procedure in order to guide it (and thus make it more effective). Stay tuned!