Поиск с ограниченной глубиной. (depth-limited search)

Поиск с ограниченной глубиной позволяет избежать отмеченного недостатка алгоритма поиска "сначала в глубину" путем ограничения максимальной глубины пути. Такое ограничение можно ввести при помощи дополнитель­ного оператора. Например, если при поиске пути из города A в город Z для расширения узлов используется карта, содержащая 20 городов, то ясно, что решение может быть найдено не более, чем за 19 шагов. Следовательно оператор, ограничивающий глубину поиска в этом случае может быть задан при помощи правила:

ЕСЛИ <местонахождение - город X>

И <пройден путь меньше чем 19 шагов>

ТО < сгенерировать множество новых состояний>

Ясно, что правило, ограничивающее глубину, должно быть сформулировано таким образом, чтобы задаваемая им максимальная глубина гарантированно включала решение.

Поиск с итерационным углублением. (iterative deepening search)

Трудной частью алгоритма поиска с ограниченной глубиной является удач­ный выбор максимальной глубины. В рассмотренном выше примере карта содержала всего 20 городов, поэтому максимальная глубина равна 19. Однако, ясно, что существует и минимальная глубина, (минимально не­обходимое количество шагов, достаточное для нахождения решения) назы­ваемая диаметром (diameter) пространства состояний. Для большинства за­дач диаметр пространства состояний можно определить только после полу­чения решения задачи.

Поиск с итерационным углублением представляет собой поиск с ограничен­ной глубиной, в котором максимальная глубина поиска не является фиксиро­ванной, а последовательно принимает все возможные значения: 0,1,2 и т.д.

Поиск с итерационным углублением сочетает преимущества поиска "сначала в глубину" и поиска "сначала в ширину". Если решение существует, то га­рантируется его нахождение при умеренных расходах памяти. Последова­тельность расширения узлов при поиске с итерационным углублением по­хожа на последовательность расширения при поиске "сначала в ширину" за исключением того, что некоторые узлы расширяются несколько раз.

Недостатком алгоритма поиска с итерационным углублением являются до­полнительные расходы ресурсов на многократное расширение одних и тех же узлов.