Главная arrow Поиск arrow Поиск в глубину
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Поиск в глубину Печать
При поиске в глубину всегда развертывается самый глубокий узел в текущей периферии дерева поиска. Ход такого поиска показан на рисунке. Поиск непосредственно переходит на самый глубокий уровень дерева поиска, на котором узлы не имеют преемников. По мере того как эти узлы развертываются, они удаляются из периферии, поэтому в дальнейшем поиск «возобновляется» со следующего самого поверхностного узла, который все еще имеет неисследованных преемников.


Поиск в глубину в бинарном дереве. Узлы, которые были развернуты и не имеют потомков в этой периферии, могут быть удалены из памяти; эти узлы обозначены черным цветом. Предполагается, что узлы на глубине 3 не имеют преемников и единственным целевым узлом является M

Эта стратегия может быть реализована в процедуре Tree-Search с помощью очереди LIFO (Last-In-First-Out), называемой также стеком. В качестве альтернативы способу реализации на основе процедуры Tree-Search поиск в глубину часто реализуют с помощью рекурсивной функции, вызывающей саму себя в каждом из дочерних узлов по очереди.

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

Для пространства состояний с коэффициентом ветвления b и максимальной глубиной m поиск в глубину требует хранения только bm+1 узлов. Используя такие же предположения, как и в таблице, и допуская, что узлы, находящиеся на той же глубине, что и целевой узел, не имеют преемников, авторы определили, что на глубине d = 12 для поиска в глубину требуется 118 килобайтов вместо 10 петабайтов, т.е. потребность в пространстве уменьшается примерно в 10 миллиардов раз.

В одном из вариантов поиска в глубину, называемом поиском с возвратами, используется еще меньше памяти. При поиске с возвратами каждый раз формируется только один преемник, а не все преемники; в каждом частично развернутом узле запоминается информация о том, какой преемник должен быть сформирован следующим. Таким образом, требуется только O(m) памяти, а не O(bm). При поиске с возвратами применяется еще один прием, позволяющий экономить память (и время); идея его состоит в том, чтобы при формировании преемника должно непосредственно модифицироваться описание текущего состояния, а не осуществляться его предварительное копирование.

При этом потребность в памяти сокращается до объема, необходимого для хранения только одного описания состояния и O(m) действий. Но для успешного применения данного приема нужно иметь возможность отменять каждую модификацию при возврате, выполняемом для формирования следующего преемника.

При решении задач с объемными описаниями состояния, таких как роботизированная сборка, применение указанных методов модификации состояний становится важнейшим фактором успеха.

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

Например, на рисунке поиск в глубину потребовал бы исследования всего левого поддерева, даже если бы целевым узлом был узел C, находящийся в правом поддереве. А если бы целевым узлом был также узел J, менее приемлемый по сравнению с узлом C, то поиск в глубину возвратил бы в качестве решения именно его; это означает, что поиск в глубину не является оптимальным. Кроме того, если бы левое поддерево имело неограниченную глубину, но не содержало бы решений, то поиск в глубину так никогда бы и не закончился; это означает, что данный алгоритм — не полный.

В наихудшем случае поиск в глубину формирует все O(bm) узлов в дереве поиска, где m — максимальная глубина любого узла. Следует отметить, что т может оказаться гораздо больше по сравнению с d (глубиной самого поверхностного решения) и является бесконечным, если дерево имеет неограниченную глубину.

Поиск с ограничением глубины

Проблему неограниченных деревьев можно решить, предусматривая применение во время поиска в глубину заранее определенного предела глубины L. Это означает, что узлы на глубине L рассматриваются таким образом, как если бы они не имели преемников. Такой подход называется поиском с ограничением глубины.

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

Кроме того, поиск с ограничением глубины будет неоптимальным при выборе значения L>d. Его временная сложность равна O(bL), а пространственная сложность — O(bL). Поиск в глубину может рассматриваться как частный случай поиска с ограничением глубины, при котором L = ∞.

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

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


Рекурсивная реализация поиска с ограничением глубины
function Depth-Limited-Search(problem, limit) returns решение result
              или индикатор неудачи failure/cutoff
return Recursive-DLS(Make-Node(Initial-State[problem]),
           problem,1imit)
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 <— Recursive-DLS(successor, problem, limit)
  if result = cutoff then cutoff_occurred? <— истинное значение
  else if result Ф failure then return решение result
  if cutoff_occurred?
  then return индикатор неудачи cutoff
  else return индикатор неудачи failure


Поиск в глубину с итеративным углублением

Поиск с итеративным углублением (или, точнее, поиск в глубину с итеративным углублением) представляет собой общую стратегию, часто применяемую в сочетании с поиском в глубину, которая позволяет найти наилучший предел глубины. Это достигается путем постепенного увеличения предела (который вначале становится равным 0, затем 1, затем 2 и т.д.) до тех пор, пока не будет найдена цель. Такое событие происходит после того, как предел глубины достигает значения d, глубины самого поверхностного целевого узла.

Данный алгоритм приведен в листинге ниже. В поиске с итеративным углублением сочетаются преимущества поиска в глубину и поиска в ширину. Как и поиск в глубину, он характеризуется очень скромными требованиями к памяти, а именно, значением O(bd).

Как и поиск в ширину, он является полным, если коэффициент ветвления конечен, и оптимальным, если стоимость пути представляет собой неубывающую функцию глубины узла. На рисунке показаны четыре итерации применения процедуры Iterative-Deepening-Search к бинарному дереву поиска, где решение найдено в четвертой итерации.


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

function Iterative-Deepening-Search(problem) returns решение result
  или индикатор неудачи failure
  inputs: problem, задача
  for depth f- 0 to w do
    result <— Depth-Limited-Search(problem, depth)
    if result Ф cutoff then return решение result


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

Причина этого состоит в том, что в дереве поиска с одним и тем же (или почти одним и тем же) коэффициентом ветвления на каждом уровне большинство узлов находится на нижнем уровне, поэтому не имеет большого значения то, что узлы на верхних уровнях формируются многократно. В поиске с итеративным углублением узлы на нижнем уровне (с глубиной d) формируются один раз, те узлы, которые находятся на уровне, предшествующем нижнему, формируются дважды, и т.д., вплоть до дочерних узлов корневого узла, которые формируются d раз. Поэтому общее количество формируемых узлов выражается следующей формулой:

N(IDS) = (d)b + (d-1)b2 + … + (1)bd

которая соответствует временной сложности порядка 0(bd). Это количество можно
сравнить с количеством узлов, формируемых при поиске в ширину:

N(BFS) = b + b2 + … + bd + (bd+1-b)

Четыре итерации поиска с итеративным углублением в бинарном дереве

Следует отметить, что при поиске в ширину некоторые узлы формируются на глубине d+1, а при итеративном углублении этого не происходит. Результатом является то, что поиск с итеративным углублением фактически осуществляется быстрее, чем поиск в ширину, несмотря на повторное формирование состояний. Например, если b = 10 и d = 5, то соответствующие оценки количества узлов принимают следующие значения:

W(IDS) = 50 + 400 + 3000 + 20 000 + 100 000 = 123 450
N(BFS) = 10 + 100 + 1000 + 10 000 + 100 000 + 999 990 = 1 111 100

Вообще говоря, итеративное углубление — это предпочтительный метод неинформированного поиска при тех условиях, когда имеется большое пространство поиска, а глубина решения неизвестна.

 

 

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

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