ПОИСК СО СКОЛЬЖЕНИЕМ В ГЛУБИНУ ДЕРЕВА

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

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

Альтернативой этой процедуре является реализация поиска в глубину с помощью рекурсивной функции, вызывающей саму себя в каждой из дочерних узлов по очереди. Процедура поиска в глубину характеризуется скромными потребностями в памяти – необходимо хранить информацию для единственного пути от корня до листового узла, наряду с оставшимися неразвернутыми сестринскими узлами для каждого узла пути. Поскольку в результате развертывания некоторого узла полностью исследуются все его преемники (рис. 31), он может быть удален из памяти. Процедура поиска в глубину для пространства состояний с коэффициентом ветвления b и максимальной глубиной m требует хранения только bm + 1 узлов. Если узлы на той же глубине, что и целевой, не имеют преемников, то используя такие же предположения, как и в
табл. 13, получаем, что при глубине d = 8 для поиска в глубину требуется 80 Кб вместо 1 Тб, т. е. потребность в пространстве уменьшается примерно в 10 миллионов раз.

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

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

Проблема неограниченных деревьев решается выбором заранее определенного предела глубины l < d, т. е. полагают, что самая поверхностная цель выходит за пределы глубины. Выбор пределов глубины может быть обусловлен лучшим пониманием задачи, например? задачи выбора маршрута движения автомобиля до Бухареста по карте Румынии, при внимательном рассмотрении которой можно установить, что в любой город можно прибыть из любого другого не более чем за 9 этапов. В большинстве задач, однако, предел глубины остается неизвестным до тех пор, пока не будет решена сама задача.

Поиск с итеративным углублением позволяет найти наилучший предел глубины путем постепенного увеличения предела (который вначале устанавливается равным 0, затем 1, затем 2 и т. д.) до тех пор, пока не будет найдена цель. В поиске с итеративным углублением сочетаются преимущества поиска в глубину и поиска в ширину. Аналогично поиску в глубину он характеризуется очень скромными требованиями к памяти, а именно – значением O(bd). Как и поиск в ширину, он является полным, если коэффициент ветвления конечен, и оптимальным, если стоимость пути представляет собой неубывающую функцию глубины узла.

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