5.3. ПОИСК В ГЛУБИНУ
При переборе в глубину делается попытка найти в пределах определенной граничной глубины дерево решения, причем в первую очередь раскрываются только что построенные вершины. Вершины, имеющие большую глубину, чем эта граничная, никогда не будут раскрываться, поэтому незаключительные вершины с глубиной, в точности равной этой границе, отмечаются как неразрешимые. Как и при переборах в пространстве состояний, наличие граничной глубины может воспрепятствовать нахождению решения, но в ходе процесса будет найдено любое решение в пределах этого ограничения. Структура процесса аналогична структуре процесса в методе полного перебора. Она показана на блок-схеме рис. 5.3. Последовательность шагов в процедуре поиска в глубину такова:
(1) Поместить начальную вершину 
в список вершин с названием ОТКРЫТ.
(2) Взять первую вершину из списка ОТКРЫТ и поместить ее в список вершин с названием ЗАКРЫТ; обозначить эту вершину через 
(3) Если глубина вершины 
равна граничной глубине, то отметить вершину 
как неразрешимую и перейти к (5); в противном случае продолжать далее.
(4) Раскрыть вершину 
построив все ее дочерние вершины. Поместить эти дочерние вершины (в произвольном порядке) в начало списка ОТКРЫТ и провести от них указатели к вершине 
Если дочерних вершин не оказалось, то пометить вершину 
как неразрешимую и продолжать; в противном случае перейти к (9).
(5) Применить к дереву поиска процедуру разметки неразрешимых вершин.
(6) Если начальная вершина помечена как неразрешимая, то на выход подается сигнал о неудаче. В противном случае продолжать далее.
(7) Изъять из списка ОТКРЫТ все вершины, имеющие неразрешимые предшествующие им вершины.
(8) Перейти к (2).
(9) Если все дочерние вершины являются заключительными, то пометить их как разрешимые и продолжать. В противном случае перейти к (2).
(10) Применить к дереву перебора процедуру разметки разрешимых вершин.
(11) Если начальная вершина помечена как разрешимая, то на выход выдается дерево решения, которое доказывает, что начальная вершина разрешима. В противном случае продолжать.
(кликните для просмотра скана)
(12) Изъять из списка ОТКРЫТ все вершины, являющиеся разрешимыми или имеющие разрешимые предшествующие им вершины.
(13) Перейти к (2).
Рис. 5.4. «И/ИЛИ» дерево, показывающее порядок, в котором раскрываются вершины при переборе в глубину (предельная глубина равна 4).
Пример последовательности, в которой раскрываются вершины в методе перебора в глубину, приведен на рис. 5.4. В этом примере граничная глубина принята равной 4. Черными кружочками показаны разрешимые вершины, белыми неразрешимые, а дерево решения выделено жирными ветвями.
