Введение

В целях наглядности и легкости освоения примеры программ приведены в среде Турбо Паскаля. Это делает их доступными для студентов-первокурсников и школьников и вместе с тем не должно вызывать принципиальных трудностей для перевода в среду Си или С++. При больших размерностях программы без изменений реализуются как консольные приложения в среде Delphi.

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

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

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

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

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

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

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

В общем случае решение задачи состоит из вектора (a₁, a₂, …) конечной, но не определенной длины, удовлетворяющего некоторым ограничениям. Каждое a_i является элементом конечного линейно упорядоченного множества 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₂

………………….

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

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

Распространенным примером применения поиска в глубину является задача о восьми ферзях [1]. Требуется расставить на шахматной доске 8 ферзей так, чтобы они не атаковали один другого. Иными словами, они должны стоять на разных горизонталях, вертикалях и диагоналях.

В каждой строке должен находиться ровно один ферзь, поэтому решение можно представить вектором (a₁, a₂, …, a₈), в котором a_i – номер столбца ферзя из строки с номером i. Более того, в каждом столбце должен быть ровно один ферзь, поэтому a_i ≠ a_j при i ≠ j. Наконец, поскольку ферзи не должны атаковать друг друга по диагонали, то ‌необходимо выполнение условия |a_i - a_j| ‌≠ ‌|i-j| ‌, если i ≠ j.

Указанные ограничения существенно снижают размерность задачи. Существуют 8⁸ вариантов расположения ферзей по одному в каждой строке, 8!=40320 вариантов с учетом того, что ферзи должны быть в разных столбцах, и всего 2096 вариантов, учитывая дополнительно их расположение на разных диагоналях.

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

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

Program Ferzi;

{ Расстановка N ферзей на доске NN, не бьющих друг друга.

Выдача в файл out.txt. Количество вариантов по размеру доски:

для 1 – 1, для 2 – 0, для 3 – 0, для 4 – 2, для 5 - 10

для 6 – 4, для 7 – 40, для 8 – 92, для 9 – 352, для 10 - 724

для 11 – 2680, для 12 - 14200 }

Uses Crt;

Var

Ch: array[1..20] of char;

{символьное обозначение вертикалей доски}

Sc: array[1..20] of integer;{счетчики для строк (положения ферзей)}

N,i,j,k,m: integer;

F: text; {для найденных позиций}

Poz: array [1..20] of integer;

{индекс-номер строки, значение-номер позиции (столбца), где ферзь}

Flag: boolean;

Procedure OutPoz; {выдача позиции}

Begin

For i:=1 to N do

Write(F,Ch[i],Poz[i],' ');

j:=j+1; {количество позиций}

WriteLn(F)

End;

Begin {начало основной программы}

ClrScr;

Write('Введите размер доски (до 12) ');

ReadLn(N);

if (N<1) or (N>12) then

begin

WriteLn(' Недопустимый размер, до новых встреч!');

ReadLn;

Halt

end;

j:=ord('a');

For i:=1 to N do {присвоение обозначений столбцам доски}

begin

Ch[i]:=Chr(j);

j:=j+1

end;

j:=0; {счетчик общего количества позиций}

Assign(F,'out.txt');

Rewrite(F);

WriteLn(F,' Позиции для ',N,' ферзей:');

For i:=1 to N do Sc[i]:=0; {счетчики позиций(столбцов) по строкам}

k:=1; {номер строки}

While k>0 do {для перебора - стек по строкам}

begin

Sc[k]:=Sc[k]+1; {номер столбца}

While Sc[k]<=N do

begin

m:=Sc[k];

{далее: можно ли ставить очередного ферзя на клетку (k,m)?}

Flag:=false;

For i:=1 to k-1 do

if (m=Poz[i]) or (Abs(k-i)=Abs(m-Poz[i])) then

{клетка (k,m) в одном столбце или

на одной диагонали с i-м ферзем}

begin

Flag:=true;

Break

end;

if Flag then {клетка (k,m) под боем предыдущих ферзей}

begin

Sc[k]:=Sc[k]+1; {следующая позиция в строке}

if Sc[k]<=N then Continue {на анализ следующей позиции}

else Break

{ферзь в строке k разместить не удалось,

отступаем на предыдущую строку}

end

else {клетка (k,m) пригодна для следующего ферзя}

begin

Poz[k]:=m;

if k=N then OutPoz

{размещен последний ферзь, вывод расположения ферзей}

else k:=k+2;

{ после следующего оператора Break будет k:=k-1}

Break

end;

end; {конец цикла While по столбцам строки k}

Sc[k]:=0; {может выполняться при k=N+1}

k:=k-1;

end; {конец цикла While по строкам}

WriteLn(F,' Общее количество позиций ', j);

Close(F);

WriteLn

End.

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

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

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

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

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

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

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

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

Пример

Ввод

5 10

##......#.

.#..#...#.

.###....#.

..##....#.

........#.

Вывод

3

В терминах компьютерной графики мы имеем дело с 4-связными областями, каждую из которых можно обойти ходом шахматной ладьи. Следует в любом порядке пройти по всем клеткам поля. Если клетка содержит символ ‘#’ (начало новой грядки), нужно заполнить всю 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;

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

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.