Поиск с ограничением глубины
Проблему неограниченных деревьев можно решить, предусматривая применение во время поиска в глубину заранее определенного предела глубины L Это означает, что узлы на глубине ? рассматриваются таким образом, как если бы они не имели преемников. Такой подход называется поиском с ограничением глубины. Применение предела глубины позволяет решить проблему бесконечного пути. К сожалению, в этом подходе также вводится дополнительный источник неполноты, если будет выбрано значение Ј
Иногда выбор пределов глубины может быть основан на лучшем понимании задачи. Например, допустим, что на рассматриваемой карте Румынии имеется 20 городов. Поэтому известно, что если решение существует, то должно иметь длину не больше 19; это означает, что одним из возможных вариантов является ?=19. Но в действительности при внимательном изучении этой карты можно обнаружить, что любой город может быть достигнут из любого другого города не больше чем за 9 этапов. Это число, известное как диаметр пространства состояний, предоставляет нам лучший предел глубины, который ведет к более эффективному поиску с ограничением глубины. Но в большинстве задач приемлемый предел глубины остается неизвестным до тех пор, пока не будет решена сама задача.
Поиск с ограничением глубины может быть реализован как простая модификация общего алгоритма поиска в дереве или рекурсивного алгоритма поиска в глубину. Псевдокод реализации рекурсивного поиска с ограничением глубины приведен в листинге 3.4. Обратите внимание на то, что поиск с ограничением глубины может приводить к неудачным завершениям двух типов: стандартное значение failure указывает на отсутствие решения, а значение cutoff свидетельствует о том, что на заданном пределе глубины решения нет.
Листинг 3.4. Рекурсивная реализация поиска с ограничением глубины
function Depth-Limited-Search(problem, limit) returns решение result или индикатор неудачи failure/cutoff return Recursive-DLS(Make-Node(Initial-State[problem]),
problem,limit)
function Recursive-DLS(node, problem, limit) returns решение result или индикатор неудачи failure/cutoff cutoff_occurred? <— ложное значение
if Goal-Test[problem] (State[node]) then return Solution(node) else if Depth[node] = limit then return индикатор неудачи cutoff else for each преемник successor in Expand(node, problem) do result
Поиск в глубину с итеративным углублением
Поиск с итеративным углублением (или, точнее, поиск в глубину с итеративным углублением) представляет собой общую стратегию, часто применяемую в сочетании с поиском в глубину, которая позволяет найти наилучший предел глубины. Это достигается путем постепенного увеличения предела (который вначале становится равным 0, затем 1, затем 2 и т.д.) до тех пор, пока не будет найдена цель. Такое событие происходит после того, как предел глубины достигает значения d, глубины самого поверхностного целевого узла. Данный алгоритм приведен в листинге 3.5. В поиске с итеративным углублением сочетаются преимущества поиска в глубину и поиска в ширину. Как и поиск в глубину, он характеризуется очень скромными требованиями к памяти, а именно, значением O(bd). Как и поиск в ширину, он является полным, если коэффициент ветвления конечен, и оптимальным, если стоимость пути представляет собой неубывающую функцию глубины узла. На рис. 3.9 показаны четыре итерации применения процедуры Iterative-Deepening-Search к бинарному дереву поиска, где решение найдено в четвертой итерации.
Листинг 3.5. Алгоритм поиска с итеративным углублением, в котором повторно применяется поиск с ограничением глубины при последовательном увеличении пределов. Он завершает свою работу после того, как обнаруживается решение, или процедура поиска с ограничением глубины возвращает значение failure, а это означает, что решение не существует
function Iterative-Deepening-Search{problem) returns решение result или индикатор неудачи failure inputs: problem, задача
for depth (- 0 to o° do
result <— Depth-Limited-Search(problem, depth) if result Ф cutoff then return решение result
Поиск с итеративным углублением может на первый взгляд показаться расточительным, поскольку одни и те же состояния формируются несколько раз. Но, как оказалось, такие повторные операции не являются слишком дорогостоящими. Причина этого состоит в том, что в дереве поиска с одним и тем же (или почти одним и тем же) коэффициентом ветвления на каждом уровне большинство узлов находится на нижнем уровне, поэтому не имеет большого значения то, что узлы на верхних уровнях формируются многократно. В поиске с итеративным углублением узлы на нижнем уровне (с глубиной d) формируются один раз, те узлы, которые находятся на уровне, предшествующем нижнему, формируются дважды, и т.д., вплоть до дочерних узлов корневого узла, которые формируются d раз. Поэтому общее количество формируемых узлов выражается следующей формулой:
tf(IDS) = (d)b + (d-l)b2 + ... + (l)bd
которая соответствует временной сложности порядка 0(bd). Это количество можно сравнить с количеством узлов, формируемых при поиске в ширину:
N(BFS) = Ъ + Ь2 + ... + bd + (bd+1-b)
N(IDS) = 50 + 400 + 3000 + 20 ООО + 100 ООО = 123 450
N(BFS) = 10 + 100 + 1000 + 10 000 + 100 000 + 999 990 = 1 111 100
& Вообще говоря, итеративное углубление — это предпочтительный метод неинформированного поиска при тех условиях, когда имеется большое пространство поиска, а глубина решения неизвестна.
Поиск с итеративным углублением аналогичен поиску в ширину в том отношении, что в нем при каждой итерации перед переходом на следующий уровень исследуется полный уровень новых узлов. На первый взгляд может показаться целесообразным разработка итеративного аналога поиска по критерию стоимости, который унаследовал бы от последнего алгоритма гарантии оптимальности, позволяя вместе с тем исключить его высокие требования к памяти. Идея состоит в том, чтобы вместо увеличивающихся пределов глубины использовались увеличивающиеся пределы стоимости пути. Результирующий алгоритм, получивший название поиска с итеративным удлинением, рассматривается в упр. 3.11. Но, к сожалению, было установлено, что поиск с итеративным удлинением характеризуется более существенными издержками, чем поиск по критерию стоимости.