Поиск с ограниченной глубиной. (depth-limited search)
Поиск с ограниченной глубиной позволяет избежать отмеченного недостатка алгоритма поиска "сначала в глубину" путем ограничения максимальной глубины пути. Такое ограничение можно ввести при помощи дополнительного оператора. Например, если при поиске пути из города A в город Z для расширения узлов используется карта, содержащая 20 городов, то ясно, что решение может быть найдено не более, чем за 19 шагов. Следовательно оператор, ограничивающий глубину поиска в этом случае может быть задан при помощи правила:
ЕСЛИ <местонахождение - город X>
И <пройден путь меньше чем 19 шагов>
ТО<сгенерировать множество новых состояний>
Ясно, что правило, ограничивающее глубину, должно быть сформулировано таким образом, чтобы задаваемая им максимальная глубина гарантированно включала решение.
Поиск с итерационным углублением. (iterative deepening search)
Трудной частью алгоритма поиска с ограниченной глубиной является удачный выбор максимальной глубины. В рассмотренном выше примере карта содержала всего 20 городов, поэтому максимальная глубина равна 19. Однако, ясно, что существует и минимальная глубина, (минимально необходимое количество шагов, достаточное для нахождения решения) называемая диаметром (diameter) пространства состояний. Для большинства задач диаметр пространства состояний можно определить только после получения решения задачи.
Поиск с итерационным углублением представляет собой поиск с ограниченной глубиной, в котором максимальная глубина поиска не является фиксированной, а последовательно принимает все возможные значения: 0,1,2 и т.д.
Поиск с итерационным углублением сочетает преимущества поиска "сначала в глубину" и поиска "сначала в ширину". Если решение существует, то гарантируется его нахождение при умеренных расходах памяти. Последовательность расширения узлов при поиске с итерационным углублением похожа на последовательность расширения при поиске "сначала в ширину" за исключением того, что некоторые узлы расширяются несколько раз.
Недостатком алгоритма поиска с итерационным углублением являются дополнительные расходы ресурсов на многократное расширение одних и тех же узлов.