Стратегия поиска в глубину

Пусть некоторая условная задача формализована первым способом. Это означает, что заданы.

• — пространство состояний, в котором указаны начальное состояние и одно или несколько конечных состояний;
• — разрешенные операции над состояниями;
• — целевые условия, если конечные состояния не указаны явно; целевые условия однозначно характеризуют, какие состояния следует считать конечными.

Так, например, в шахматной игре пространство состояний можно считать состоящим из возможных позиций на шахматной доске. Разрешенные операции — это разрешенные в соответствии с правилами шахматной игры ходы, переводящие одну позицию в другую. Если рассматривается обычная партия в шахматы между двумя игроками, то роль начальной позиции (начального состояния) играет известная стандартная начальная позиция. Конечной, целевой, позицией является любая из позиций, соответствующих окончанию партии. Условия окончания партии также описываются в правилах шахматной игры и, по сути, являются целевыми условиями. В частности, к целевым относятся условия, описывающие позиции мата, пата, вечного шаха и т. д.

Возвращаясь к условной задаче, будем считать, что построен ориентированный граф пространства состояний. Припишем каждому ребру этого графа число 1, которое называют «длиной» этого ребра. Иногда это число называют «глубиной» или «расстоянием». Содержательно «длина» может выражать в зависимости от задачи вес (кг), цену (руб.), длину (м), затраченную энергию (кВт) и т. д. Число 1 в рассматриваемой условной задаче интерпретируется как число операций перехода из одного состояния в другое.

Идея алгоритма поиска в глубину состоит в следующем: начальная вершина графа принимается за начало решающего пути; а далее всегда, когда надлежит выбрать из нескольких альтернативных вершин ту, в которую следует перейти из текущей вершины для продолжения поиска решающего пути, нужно выбрать самую «глубокую» из них, т. е. ту, которая расположена дальше других от начальной вершины. Термины «самая глубокая» и «дальше» здесь следует понимать в смысле «длины» ребра, определенной выше.

При поиске в глубину в случае, когда самых глубоких вершин оказывается несколько, можно выбрать любую из них, например, самую «левую». Здесь термин «левый» — условный термин, означающий в одних случаях первую из альтернативных вершин в порядке их обнаружения, в других случаях на самом деле визуально самую левую из альтернативных вершин, если граф реально представлен графически. В иных случаях термин «левый» может означать предпочтения, продиктованные условиями задачи или, вообще, самыми разными соображениями.

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

На рис. 4, а в качестве примера показано, в каком порядке алгоритм поиска в глубину проходит вершины пространства состояний. Здесь вершина а соответствует начальному состоянию, вершины j и/соответствуют конечным состояниям.

Выделенные пути [д, b, e, j] и [a, c, J] — это найденные решающие пути, и [a, c, f — кратчайший решающий путь, отыскиваемый, если продолжать поиск в глубину до полного перебора всех вершин графа.

Поиск в глубину часто работает хорошо, как в рассмотренном примере на рис. 4, а. Но бывает, что он дает сбои, например, зацикливание, если не предусмотрен анализ наличия циклов в ориентированном графе пространства состояний решаемой задачи. На рис. 4, б представлен граф, содержащий циклы [d, h, d и , е, i, Ь. Включение в алгоритм поиска в глубину механизма обнаружения циклов позволит избежать ситуаций зацикливания. Механизм обнаружения циклов должен работать так, чтобы ни одна из вершин, уже содержащихся в построенном пути, не рассматривалась вторично в качестве возможной альтернативы продолжения поиска.

Рис. 4.

Рассмотрим пример использования стратегии поиска в глубину при решении задачи переупорядочивания кубиков. Задача состоит в выработке плана перестановки кубиков, поставленных друг на друга (см. рис. 5). Слева указано начальное состояние, а справа — конечное состояние, к которому следует прийти. На каждом шаге решения можно переставлять только одни кубик. Кубик можно переставлять только тогда, когда на нем не стоит другой кубик. Кубик можно поставить либо на стол, либо на другой кубик.

Рис. 5.

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

Указанный на рис. 6 путь обхода вершин соответствует стратегии поиска в глубину с механизмом обнаружения циклов и дает решение.

Кратчайшее решение выделено на рис. 6 жирными стрелками. Оно будет получено дальнейшим продолжением поиска решений, пока не будут найдены все решения. Это продолжение поиска отмечено на рис. 6 пунктиром.

В отдельных случаях поиск в глубину может приводить к полному перебору, прежде чем будет построен решающий путь. Например, если в предыдущей задаче переупорядочивания кубиков с пространством состояний, изображенным на рис. 6, исходным состоянием является то же самое состояние, а целевым — другое состояние (см. рис. 7), то стратегия поиска в глубину приводит к почти полному перебору, прежде чем будет найдено решение. Кратчайшее решение в таком пространстве состояний будет найдено, действительно, полным перебором всех вершин и путей.

Поиск в глубину прост, легко программируется и наиболее адекватен рекурсивному стилю программирования, принятому в языке программирования Prolog. Последнее объясняется тем, что, обрабатывая цели, пролог-система просматривает альтернативы именно в глубину. Поиск в глубину (без механизма обнаружения циклов) может быть запрограммирован на языке Prolog следующим образом [9]:

решить (В, [В}):—цель (В).

решить (В, [В Реш 1]):—после (В, В]), решить (В1, РешТ).

Рис. 6 Рис. 7.

Этот текст на языке Prolog означает: для того чтобы найти решающий путь Реш (последовательность вершин в виде прологовского списка | В, 5, …, В_к) из начальной вершины В в некоторую целевую вершину В_к (целевые вершины А задаются фактами вида «цель (/4).»), необходимо:

• — если В — это целевая вершина, то положить Реш= [5],
• — если для начальной вершины В существует вершина 51, в которую направлено ребро графа, выходящее из вершины В, то решающий путь Реш= |5 | РешЦ, где Реш 1 — решающий путь, начинающийся из вершины 51 как из исходной вершины.

Факты вида «после (В, В1).» определяют ребра, направленные из вершины В в вершину В1. Предикат решить (В, Реш) описывает взаимосвязь между начальной вершиной В и решающим путем Реш, начинающимся из этой вершины. Прологовская запись Реш= [В Реш 1] означает, что В — голова списка Реш, а Реш 1 — хвост этого списка.