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

При поиске в глубину последовательно достраивается единственное частичное решение. В этом и состоит сущность поиска в глубину: продолжать расширение исследуемого решения до тех пор, пока это возможно, и когда решение нельзя расширить, возвращаться по нему и пытаться сделать другой выбор на самом близком шаге, где имеется такая возможность. Если нужно найти все решения, то после нахождения очередного из них также производится возврат. Благодаря такой стратегии, поиск в глубину называют также поиском с возвратом. Идею поиска в глубину легче всего понять на примере следующей задачи прохода через лабиринт.

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

Например, в этом лабиринте требуется попасть из левого нижнего угла в правый верхний угол. Один из способов прохода через лабиринт – двигаться из начальной клетки в соответствии с двумя правилами:

· в каждой клетке выбирать еще не исследованный путь.

· если из текущей клетки нет неисследованных путей, то нужно вернуться назад на ту клетку, из которой пришли в текущую клетку.

Первое правило говорит о том, как расширить исследуемый путь, если это возможно, а второе правило – о том, как выходить из тупика.

Сущность поиска в глубину состоит в следующем: последовательно выстраивается единственное частичное решение путем расширения исследуемого решения до тех пор, пока это возможно, и когда решение нельзя расширить, возвращаться по нему и пытаться сделать другой выбор на самом близком шаге, где имеется такая возможность. Если нужно найти все решения, то после нахождения очередного из них также производится возврат. Благодаря такой стратегии, поиск в глубину называют также поиском с возвратом.

В общем случае решение задачи состоит из вектора (a₁, a₂, …) конечной, но не определенной длины, удовлетворяющего некоторым ограничениям. Каждое ai является элементом конечного линейно упорядоченного множества A_i. При полном переборе должны рассматриваться элементы множества A₁´ A₂ ´ …´ A_i для i =1, 2, …Здесь символ ‘´ ’ обозначает декартовое произведение множеств.

В качестве исходного частичного решения выбирается пустой вектор (), и на основе имеющихся ограничений выясняется, какие элементы из A₁ являются кандидатами в a₁; обозначим это подмножество через S₁. В качестве a₁ выбирается первый элемент множества S₁. В результате получается частичное решение (a₁). Далее в соответствии с ограничениями и выбранным элементом a₁ выбирается элемент a₂ из множества S₂ и т. д. Если на шаге k частичное решение (a₁, a₂, …, a_k-1) не представляет возможностей для выбора элемента a_k, то выбирается новый элемент a_k-1. Если a_k-1 выбрать нельзя, возвращаемся еще дальше и выбирается новый элемент a_k-2 и т. д.

Этот процесс удобно описать с помощью дерева.

Начало

Выборы для a₁

Выборы для a₂ при данном a₁

Выборы для a₃ при данных a₁ и a₂

………………….

Обход дерева в порядке сверху вниз соответствует схеме поиска с возвратом.

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

Идею поиска в глубину легче всего понять на примере следующей задачи прохода через лабиринт.

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

Рассмотрим другую распространенную задачу, для решения которой используется поиск в глубину.

Грядки. Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:

· из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;

· никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).

Подсчитайте количество грядок на садовом участке.

Ввод из файла INPUT.TXT. В первой строке находятся числа N и M через пробел, далее идут N строк по M символов. Символ #обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет.

Вывод в файл OUTPUT.TXT. Вывести одно число - количество грядок на участке.

Ограничения: 1 ≤ N, M ≤ 40, время 1 с.

Пример

Ввод

5 10

Вывод

Следует в любом порядке пройти по всем клеткам поля. Если клетка содержит символ ‘#’ (начало новой грядки), нужно заполнить всю 4-связную область символами ‘.’. Как и раньше, удобно организовать барьер, объявив массив клеток с запасом на 1 в каждую сторону и заполнив его перед чтением файла символами ‘.’. Ответом задачи будет количество вызовов извне процедуры перекраски, которая в простейшем случае выглядит так:

Procedure Metka (i, j: integer); {окраска (пометка грядки) символами '.'}

Begin

if C[i, j] = ’#’ then

begin

C[i, j]: = ‘.’; {пометка клетки (i, j) как пройденной}

Metka (i+1, j);

Metka (i-1, j);

Metka (i, j+1);

Metka (i, j-1);

end;

End.

Можно применять явный стек вместо рекурсивного. Приведем этот вариант программы. Использование динамической памяти позволяет даже в среде Турбо Паскаля увеличить в несколько раз размер поля.

Program Beds; {заливка с явным стеком}

Const Max=200;

Type

Stack = array[1..Max*Max] of byte; {чтобы хватило памяти}

Var X, Y: ^Stack; {для координат клеток}

i, j: integer;

Top: word; {счетчик для стека}

Fin, Fout: text;

N, M: integer; {размер участка}

C: array[0..Max+1, 0..Max+1] of char; {карта поля (с барьерами по краям)}

Count: integer; {счетчик количества грядок}

Procedure Pop(Var i, j: integer); {извлечение из стека очередной клетки грядки}

Begin

i: =X^[Top];

j: =Y^[Top];

Top: =Top-1;

End;

Procedure Push(i, j: integer); {занесение в стек очередной клетки грядки и ее перекраска}

Begin

if C[i, j]='#' then {чтобы не проверять 4 раза в вызывающей процедуре Paint}

begin

Top: =Top+1;

X^[Top]: =i;

Y^[Top]: =j;

C[i, j]: ='.'; {пометка клетки (i, j) как пройденной}

end;

End;

Procedure Metka(i, j: integer); {окраска (пометка) грядки символами '.'}

Begin

Top: =0; {начало окраски клеток новой грядки}

Push(i, j); {занесение клетки (i, j) в стек и перекраска}

While Top> 0 do {пока стек не пуст}

begin

Pop(i, j); {извлечение из стека очередной клетки грядки (Pop)}

Push(i+1, j);

Push(i-1, j);

Push(i, j+1);

Push(i, j-1);

end

End;

Begin

For i: =0 to N+1 do {для барьера}

For j: =0 to M+1 do

C[i, j]: ='.';

Assign(Fin, 'input.txt');

Reset(Fin);

ReadLn(Fin, N, M);

For i: =1 to N do

begin

For j: =1 to M do Read(Fin, C[i, j]);

ReadLn(Fin); {перевод строки}

end;

Close(Fin);

New(X); New(Y);

Count: =0;

For i: =1 to N do

For j: =1 to M do

if C[i, j]='#' then {встретили новую грядку}

begin

Count: =Count+1;

Metka(i, j)

end;

Dispose(X);

Dispose(Y);

Assign(Fout, 'output.txt');

Rewrite(Fout);

WriteLn(Fout, Count);

Close(Fout);

End.