Метод полного перебора в глубину

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

Алгоритм перебора в глубину состоит в следующем.

1). Раскрывается начальная вершина соответствующая начальному состоянию Sн.

2) Раскрывается первая вершина, получаемая в результате раскрытия Sн. Ставится указатель.

3) Если она раскрывается, то следующей будет раскрываться вновь порожденная вершина. Если вершина не раскрывается, то процесс возвращается в предыдущую вершину.

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

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