Поиск с возвратом

Алгоритмы перебора вариантов

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

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

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

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₂

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

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

Другим распространенным примером для алгоритма поиска с возвратом является задача о восьми ферзях. Требуется раставить на шахматной доске 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 вариантов, учитывая дополнительно их расположение на разных диагоналях.

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-01-11