Поиск в глубину
При поиске в глубину всегда развертывается самый глубокий узел в текущей периферии дерева поиска. Ход такого поиска показан на рис. 3.8. Поиск непосредственно переходит на самый глубокий уровень дерева поиска, на котором узлы не имеют преемников. По мере того как эти узлы развертываются, они удаляются из периферии, поэтому в дальнейшем поиск "возобновляется" со следующего самого поверхностного узла, который все еще имеет неисследованных преемников.
Эта стратегия может быть реализована в процедуре Tree-Search с помощью очереди LIFO (Last-In-First-Out), называемой также стеком. В качестве альтернативы способу реализации на основе процедуры Tree-Search поиск в глубину часто реализуют с помощью рекурсивной функции, вызывающей саму себя в каждом из дочерних узлов по очереди. (Рекурсивный алгоритм поиска в глубину, в котором предусмотрен предел глубины, приведен в листинге 3.4.)
Поиск в глубину имеет очень скромные потребности в памяти. Он требует хранения только единственного пути от корня до листового узла, наряду с оставшимися неразвернутыми сестринскими узлами для каждого узла пути. После того как был развернут некоторый узел, он может быть удален из памяти, коль скоро будут полностью исследованы все его потомки (см. рис. 3.8). Для пространства состояний с коэффициентом ветвления Ь и максимальной глубиной т поиск в глубину требует хранения только Ьт+1 узлов. Используя такие же предположения, как и в табл. 3.1, и допуская, что узлы, находящиеся на той же глубине, что и целевой узел, не имеют преемников, авторы определили, что на глубине d=12 для поиска в глубину требуется 118 килобайтов вместо 10 петабайтов, т.е. потребность в пространстве уменьшается примерно в 10 миллиардов раз.
В одном из вариантов поиска в глубину, называемом поиском с возвратами, используется еще меньше памяти. При поиске с возвратами каждый раз формируется только один преемник, а не все преемники; в каждом частично развернутом узле запоминается информация о том, какой преемник должен быть сформирован следующим. Таким образом, требуется только 0{т) памяти, а не 0{bm). При поиске с возвратами применяется еще один прием, позволяющий экономить память (и время); идея его состоит в том, чтобы при формировании преемника должно непосредственно модифицироваться описание текущего состояния, а не осуществляться его предварительное копирование. При этом потребность в памяти сокращается до объема, необходимого для хранения только одного описания состояния и О(т) действий. Но для успешного применения данного приема нужно иметь возможность отменять каждую модификацию при возврате, выполняемом для формирования следующего преемника. При решении задач с объемными описаниями состояния, таких как роботизированная сборка, применение указанных методов модификации состояний становится важнейшим фактором успеха.
Недостатком поиска в глубину является то, что в нем может быть сделан неправильный выбор и переход в тупиковую ситуацию, связанную с прохождением вниз по очень длинному (или даже бесконечному) пути, притом что другой вариант мог бы привести к решению, находящемуся недалеко от корня дерева поиска. Например, на рис. 3.8 поиск в глубину потребовал бы исследования всего левого поддерева, даже если бы целевым узлом был узел С, находящийся в правом поддереве. А если бы целевым узлом был также узел J, менее приемлемый по сравнению с узлом С, то поиск в глубину возвратил бы в качестве решения именно его; это означает, что поиск в глубину не является оптимальным. Кроме того, если бы левое поддерево имело неограниченную глубину, но не содержало бы решений, то поиск в глубину так никогда бы и не закончился; это означает, что данный алгоритм — не полный. В наихудшем случае поиск в глубину формирует все О(кГ) узлов в дереве поиска, где т — максимальная глубина любого узла. Следует отметить, что т может оказаться гораздо больше по сравнению с d (глубиной самого поверхностного решения) и является бесконечным, если дерево имеет неограниченную глубину.