10.1.4. Алгоритм перебора в глубину
Для полноты изложения следует упомянуть и четвертый метод поиска на графе, известный как метод перебора в глубину. Это название объясняется тем, что метод применяется, когда граф является деревом. Вместо того чтобы прослеживать все варианты одновременно на одну и ту же глубину, в методе перебора в глубину исследуется сначала один путь до конца, затем другой и т. д. В нашем примере поездки по городам алгоритм перебора в глубину мог бы перейти от Сан-Франциско к Портленду, затем к Сиэтлу, Спокану, Рено и попасть снова в Сан-Франциско. Обнаружив этот цикл, алгоритм вернулся бы к Рено и исследовал другие пути, если они существуют. Затем точно так же были бы исследованы различные пути из Спокана.
1. Поместить все узлы множества 
в список ОТКРЫТ в произвольном порядке.
2. Если список ОТКРЫТ пуст, решения нет.
3. Закрыть первый узел в ОТКРЫТ. Если это целевой узел, задача решена.
4. Поместить преемники только что закрытого узла в список ОТКРЫТ перед узлами, уже содержащимися в этом списке. Если какой-то узел из множества преемников уже есть в списке ОТКРЫТ, то аннулировать все записи его в этом списке, кроме последней. Если какой-то узел из множества преемников находится в списке ЗАКРЫТ, тов список ОТКРЫТ его не помещать.
5. Перейти к шагу 2.
Алгоритм перебора в глубину может привести к бесконечному поиску, если граф не конечен. В качестве примера рассмотрим граф, изображенный на рис. 10.2. Пусть цель задачи — найти путь от 
Возможная последовательность состояний, которую дает метод перебора в глубину, такова:
Этот путь никогда не заканчивается и не содержит пути, ведущего к цели. Обычно, чтобы избежать таких ситуаций, при реализации алгоритма в него включают дополнительный шаг (За), согласно которому преемники узла не следует помещать в список ОТКРЫТ, если узел закрывается на расстоянии не менее 
от начального множества. Значение 
определяется отдельно для каждой задачи. Хотя этот шаг, несомненно, необходим во всех случаях, связанных с бесконечными графами, он лишает нас возможности общего анализа получаемой программы.
В общем случае решение, которое дает метод перебора в глубину, не является ни минимальным, ни наиболее выгодным. Чтобы понять это, рассмотрим снова задачу переезда из Сан-Франциско в Лое-Анд-желес (рис. 10.1) и применим алгоритм перебора в глубину, дополненный правилом, предписывающим помещать в список ОТКРЫТ преемники, начиная с самой северной ветви и двигаясь далее против часовой стрелки. Путь, найденный этим алгоритмом, идет из Сан-Франциско в Лос-Анджелес через Портленд, Сиэтл, Спокан, Рено и Лас-Вегас! Это вряд ли оптимальный путь.
Учитывая такие недостатки алгоритма, естественно спросить, зачем его вообще нужно обсуждать. Ответ, в частности, таков: „По историческим причинам". Метод перебора в глубину очень легко программируется, поскольку список ОТКРЫТ можно подходящим образом упорядочить, заталкивая и выталкивая магазин (Кнут, 1969). Поэтому методы перебора в глубину привлекали тех, кто хотел получить хоть какой-нибудь результат. По крайней мере один автор признался в этом совершенно недвусмысленно (Слейгл, 1965). Возможна и другая, более тонкая причина. Людям легче реализовать метод перебора в глубину. При методе перебора в ширину в список ОТКРЫТ часто помещается очень много узлов. Это всегда требует некоторой схемы для фиксации связей между узлами. А при методе перебора в глубину в ОТКРЫТ обычно содержится меньше узлов и они связаны тем порядком, в котором записывались в этот список, а не явными указателями. В современных
теориях человеческой памяти (Норман, 1969; Кинтш, 1970) обращается внимание на то, что люди располагают весьма ограниченным объемом памяти для оперативной информации и поэтому должны применять те стратегии решения задачи, которые не требуют одновременного запоминания многих фактов. Это, конечно, делает метод перебора в глубину более привлекательным.
Довод, что метод перебора в глубину выглядит психологически более естественным, не является чисто теоретическим. Ньюэлл и Саймон (1965) заметили, что при игре в шахматы, которую можно сформулировать как задачу поиска на графе, очень хороший игрок пользуется модифицированным методом перебора в глубину. Мы провели ряд экспериментов, в которых испытуемым задавались в явном виде задачи поиска на графе и предлагалось решить их либо методом перебора в глубину, либо методом перебора в ширину. Испытуемые практически всегда справлялись с методом перебора в глубину, но затруднялись при выполнении даже очень простых заданий по методу перебора в ширину.
