Проблему неограниченных деревьев можно решить, предусматривая применение во время поиска в глубину заранее определенного предела глубины L Это означает, что узлы на глубине l рассматриваются таким образом, как если бы они не имели преемников. Такой подход называется поиском с ограничением глубины. Применение предела глубины позволяет решить проблему бесконечного пути. К сожалению, в этом подходе также вводится дополнительный источник неполноты, если будет выбрано значение l<d, иными словами, если самая поверхностная цель выходит за пределы глубины. (Такая ситуация вполне вероятна, если значение d неизвестно.) Кроме того, поиск с ограничением глубины будет неоптимальным при выборе значения . Его временная сложность равна , а пространственная сложность — . Поиск в глубину может рассматриваться как частный случай поиска с ограничением глубины, при котором

Иногда выбор пределов глубины может быть основан на лучшем понимании задачи. Например, допустим, что на рассматриваемой карте Румынии имеется 20 городов. Поэтому известно, что если решение существует, то должно иметь длину не больше 19; это означает, что одним из возможных вариантов является j. Но в действительности при внимательном изучении этой карты можно обнаружить, что любой город может быть достигнут из любого другого города не больше чем за 9 этапов. Это число, известное как диаметр пространства состояний, предоставляет нам лучший предел глубины, который ведет к более эффективному поиску с ограничением глубины. Но в большинстве задач приемлемый предел глубины остается неизвестным до тех пор, пока не будет решена сама задача.

Поиск с ограничением глубины может быть реализован как простая модификация общего алгоритма поиска в дереве или рекурсивного алгоритма поиска в глубину. Псевдокод реализации рекурсивного поиска с ограничением глубины приведен в листинге 3.4. Обратите внимание на то, что поиск с ограничением глубины может приводить к неудачным завершениям двух типов: стандартное значение failure указывает на отсутствие решения, а значение cutoff свидетельствует о том, что на заданном пределе глубины решения нет.

Листинг 3.4. Рекурсивная реализация поиска с ограничением глубины