3.3. МЕТОД ПЕРЕБОРА В ГЛУБИНУ
В методах перебора в глубину прежде всего раскрываются те вершины, которые были построены последними. Определим глубину вершины в дереве следующим образом:
Глубина корня дерева равна нулю.
Глубина любой последующей вершины равна единице плюс глубина вершины, которая непосредственно ей предшествует.
Таким образом, вершиной, имеющей наибольшую глубину в дереве перебора, в данный момент служит та, которая должна в этот момент быть раскрыта. Такой подход может привести к процессу, разворачивающемуся вдоль некоторого бесполезного пути, поэтому нужно ввести некоторую процедуру возвращения. После того как в ходе процесса строится вершина с глубиной, превышающей некоторую граничную глубину, мы раскрываем вершину наибольшей глубины, не превышающей этой границы, и т. д.
Метод перебора в глубину определяется следующей последовательностью шагов:
(1) Поместить начальную вершину в список, называемый ОТКРЫТ.
(2) Если список ОТКРЫТ пуст, то на выход дается сигнал о неудаче поиска, в противном случае перейти к шагу (3).
(3) Взять первую вершину из списка ОТКРЫТ и перенести ее в список, называемый ЗАКРЫТ. Эту вершину назватьи.
(4) Если глубина вершины 
равна граничной глубине, то переходить к (2), в противном случае — к (5).
(5) Раскрыть вершину 
построив все непосредственно следующие за ней вершины. Поместить их (в произвольном порядке) в начало списка ОТКРЫТ и построить указатели, идущие от них к. вершине 
(6) Если одна из этих вершин целевая, то на выход выдать решение, просматривая для этого соответствующие указатели, в противном случае переходить к шагу (2).
На рис. 3.4 приведена блок-схема для метода перебора в глубину. Дерево, которое получается в результате применения метода перебора в глубину к той же самой игре в восемь, что и прежде, показано на рис. 3.5. Снова нужно найти
(кликните для просмотра скана)
(кликните для просмотра скана)
последовательность ходов для преобразования левой конфигурации в правую:
Вершины здесь занумерованы в том порядке, в котором они были раскрыты, причем граничная глубина выбрана равной 5 (т. е. ищутся пути, ведущие к цели, длина которых не больше пяти).
Мы видим, что в алгоритме поиска в глубину сначала идет перебор вдоль одного пути, пока не будет достигнута максимальная глубина, затем рассматриваются альтернативные пути той же или меньшей глубины, которые отличаются от него лишь последним шагом, после чего рассматриваются пути, отличающиеся последними двумя шагами, и т. д.
