Поиск в глубину

Начиная с исходного состояния уровня 1 графа, строятся все вершины (узлы) уровня 2 графа, связанные с исходной вершиной. Это так называемые дочерние вершины.

Если целевых вершин нет и максимальная глубина К поиска не достигнута, то берется верхняя вершина и строятся связанные с ней вершины

Если максимальная глубина не достигнута, то берется верхняя вершина и строятся все связанные с ней вершины.

При неуспехе и если достигнута максимальная глубина поиска происходит возврат назад на 3 уровень, на котором выбирается самая верхняя нераскрытая вершина

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

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

Для задач с большой или даже с бесконечной глубиной поиск крайне неэффективен: он стремится в глубину, тогда как цель может быть близка к начальному состоянию.