1. Общая схема рекурсивного перебора
Есть такие комбинаторные задачи, для решения которых приходится организовывать полный перебор возможных вариантов. Перебор с возвратом (backtrack) - это общий метод упорядоченного перебора. Перебор с возвратом особенно удобен для решения задач, требующих проверки потенциально большого, но конечного числа решений. В настоящем разделе описывается общая схема рекурсивного перебора с возвратом.
В самом общем случае мы полагаем, что решение задачи состоит из вектора конечной длины, удовлетворяющего заданным условиям и ограничениям, или из множества таких векторов. Для каждого элемента задано упорядоченное множество его возможных значений . В одних задачах размерность решения (число ) может быть известна заранее, а в других – заранее не определена.
Метод перебора с возвратом основан на том, что при поиске решения многократно делается попытка расширить текущее частичное решение, то есть его продолжить. Если расширение невозможно, то происходит возврат к предыдущему более короткому частичному решению, и делается попытка его расширить другим возможным способом.
В качестве исходного частичного решения мы выбираем пустой вектор, который будем обозначать ( ). На основе заданных ограничений выясняем, какие элементы из являются кандидатами в ; обозначим это подмножество через . В качестве выбираем первый элемент из и получаем частичное решение . В общем случае по частичному решению на основе ограничений задачи строится , из которого выбираются кандидаты для расширения частичного решения до . Если , то есть частичное решение не может быть расширено, мы возвращаемся и выбираем новый элемент . Если новый элемент выбрать нельзя, мы возвращаемся еще дальше и выбираем новый элемент и т.д.
Проиллюстрируем идею перебора с возвратом с помощью задачи прохода через лабиринт. Пример лабиринта приведен на рис. 1.
|
Наш лабиринт представляет собой связную конечную область на плоскости, состоящую из клеток. Наша цель – попасть из некоторой заданной клетки в другую заданную клетку, последовательно перемещаясь по клеткам. В каждый момент времени можно переместиться в одну из соседних клеток по горизонтали или вертикали. Трудность задачи состоит в существовании преград, запрещающих некоторые перемещения.
Мы можем искать путь в лабиринте, руководствуясь двумя правилами:
- В каждой клетке выбирать еще не исследованный путь.
- Если из исследуемой в данный момент клетки не ведут неисследованные пути, то нужно вернуться на одну клетку назад по последнему пройденному пути, по которому мы пришли в клетку.
Первое правило говорит о том, как расширить исследуемый путь, если это возможно, второе правило – как выходить из тупика. В этом и состоит сущность перебора с возвратом: продолжать расширение исследуемого решения до тех пор, пока это возможно, и когда решение нельзя расширить, возвращаться по нему и пытаться сделать другой выбор на самом близком шаге, где имеется такая возможность.
Рассмотрим подробнее, как можно решить задачу прохода через лабиринт, изображенный на рис. 1, применяя перебор с возвратом.
Обозначим через множество направлений возможных перемещений в клетке: - север, - юг, - запад, - восток.
Под решением будем понимать вектор , представляющий собой последовательность элементов из множества . Каждая координата вектора определяет направление перемещения для соответствующей текущей клетки; очевидно, первая координата определяет направление движения в начальной клетке лабиринта, а последняя – направление движения на заключительном шаге, приводящем в конечную клетку. Заметим, что размерность вектора не определена заранее, т.к. мы не знаем, сколько шагов надо сделать, чтобы пройти лабиринт.
На i-м шаге будем определять множество возможных перемещений для текущей клетки следующим образом: включим элемент в в том и только том случае, если соседняя клетка на юге не отделена стенкой и не была использована ранее при предыдущих посещениях клетки. Например, , так как клетка, расположенная на востоке от начальной клетки, не отделена стенкой, и мы ее не посещали ранее. Других возможных перемещений для начальной клетки нет. Договоримся, что если множество содержит более одного элемента, сохраним в нем тот же порядок элементов, что и в множестве .
Для удобства введем систему координат, как показано на рис. 2.
|
| 3 |
| 4
|
| 5
|
| 2 |
| 2 |
| 1 |
| 1 |
| X |
| Y |
| 3 |
| 4
|
| 5
|
Начнем описывать обход лабиринта по шагам. Текущий частичный вектор будем обозначать через .
Шаг 1. Полагаем .
Шаг 2. Вычисляем . Выбираем для продолжения частичного решения. Получаем , и это означает переход в клетку (2,1).
Шаг 3. Так как из клетки (2,1) мы можем перейти только в новую клетку (2,2), т.е. на север, . Выбираем для продолжения частичного решения. Получаем и, следовательно, переходим в клетку (2,2).
Шаг 4. , , переходим в клетку (2,3).
Шаг 5. В клетке (2,3) два варианта продолжений: на запад и на восток, поэтому . Выбираем первый вариант продолжения . Получаем и переходим в клетку (1,3).
Шаг 6. В клетке (1,3) два варианта продолжений: на север и на юг, поэтому . Выбираем первый вариант продолжения . Получаем и переходим в клетку (1,4).
Шаг 7. , , переходим в клетку (1,5).
Шаг 8. , поэтому возвращаемся в предыдущую клетку (1,4), и .
Шаг 9. На шаге 7 мы имели . Так как вариант мы использовали для продолжения, исключаем его, получаем . Поэтому , переходим в клетку (2,4),
Продолжаем процесс до тех пор, пока не попадем в клетку (4,5). В результате мы получим решение .
Процесс получения решения для нашей задачи можно изобразить графически, построив дерево поиска с возвратом. Построение дерева начинается с начальной вершины (корня дерева), которой соответствует пустое частичное решение. Ребра дерева помечаются элементами множества и соответствуют выбору расширения частичного решения. В дереве поиска отмечена вершина, соответствующая решению. Само решение складывается из последовательности символов, приписанных ребрам пути при движении от корня к отмеченной вершине.
SHAPE \* MERGEFORMAT
| Решение |
| Начало |
| E |
| S |
| E |
| W |
| W |
| E |
| N |
| S |
| E |
| E |
| N |
| N |
| N |
| E |
| N |
| W |
| N |
| Рис. 3. Дерево поиска с возвратом для задачи о лабиринте
|
Мы привели пример задачи, в которой требуется найти любое решение, если оно есть. В этом случае алгоритм останавливается, как только найдет первое решение. Если бы надо было перечислить все решения, мы продолжили бы поиск и перебрали бы все возможные пути в лабиринте. В этом случае перебор закончился бы в начальной вершине дерева поиска, при этом все варианты продолжения для корня дерева (все элементы из ) были использованы для поиска. Может оказаться, что решения в задаче нет, т.е. нельзя попасть из начальной клетки в конечную. Для этого случая также пришлось бы исследовать все возможные варианты путей в лабиринте.
На рис. 4 приведен общий вид дерева при использовании метода перебора с возвратом.
Процесс решения задачи перебором с возвратом подразделяется на отдельные подзадачи, которые удобно описывать с использованием рекурсии.
При использовании рекурсии отпадает необходимость непосредственно организовывать возвраты и отслеживать правильность их выполнения. Они становятся встроенной частью механизма выполнения рекурсивных вызовов.
Рис. 4. Дерево поиска для перебора с возвратом
Рекурсивный алгоритм начинает работу с пустого вектора, который будем обозначать . Ниже приведена рекурсивная реализация перебора с возвратом на псевдокоде. Символ || означает конкатенацию (склеивание) векторов: || = , ||
BACKTRACK( ( ), )
procedure BACKTRACK( vector, )
begin
if vector является решением then записать его
вычислить
for do BACKTRACK ( vector || ( ), )
end
Реализация перебора с возвратом обычно приводит к экспоненциальным алгоритмам, что связано с экспоненциальным числом исследуемых вершин в дереве поиска с возвратом.
2. Перечисление комбинаторных объектов. Перестановки. Сочетания
В настоящем разделе рассматриваются примеры использования метода перебора с возвратом в задачах перечисления элементарных комбинаторных объектов.
2.1. Задача перечисления всех перестановок
Пусть - конечное множество различных элементов. Под перестановкой элементов множества понимается произвольная последовательность длины , в которой каждый элемент из встречается ровно один раз. Для примера рассмотрим все перестановки на множестве : 123, 132, 213, 231, 312, 321. Число всех перестановок на -элементном множестве равно . Без ограничения общности будем считать, что элементы являются целыми числами от 1 до n.
| 1 |
| 2 |
| 1 |
| 3 |
| 3 |
| 3 |
| 3 |
| 2 |
| 2 |
| 2 |
| 2 |
| 1 |
| 1 |
| 1 |
Явное применение метода перебора с возвратом к перечислению всех перестановок порождает их в лексикографическом порядке. В лексикографическом порядке, к примеру, перечисляются обычно фамилии учеников в классном журнале. Для случая перестановок, если и - перестановки, то мы говорим, что лексикографически меньше , если и только если для некоторого мы имеем для всех и . Говоря своими словами, найдется такая позиция , что в -ой позиции перестановки стоит меньшее число, чем в перестановке , а во всех предшествующих позициях числа в перестановках совпадают. К примеру, перестановка из трех элементов 213 лексикографически меньше перестановки 231, так как в первой позиции числа совпадают, а во второй позиции в перестановке 213 стоит меньшее число, чем в перестановке 231 (1 меньше 3).
|
Дерево поиска для перечисления всех перестановок из трех элементов перебором с возвратом приведено на рис. 5.
Рассмотрим процесс перехода от произвольной перестановки к следующей. Начнем с примера. Пусть , и - текущая перестановка. Так как числа в перестановке не повторяются, последнее число в перестановке определяется единственным образом. Поскольку других возможностей для последнего числа нет, множество вариантов продолжений ; возвращаемся на один шаг назад, получая частичную перестановку . На 4-й позиции в перестановке стоит максимально возможное значение 5, это означает, что все предыдущие значения исчерпаны, поэтому ; делаем еще один шаг назад, в третью позицию, и получаем частичную перестановку . Определяем, что , так как числа 2 и 3 уже есть в текущей перестановке в первых двух позициях. Выбираем первый вариант из и получаем частичную перестановку . Находим, что и, выбирая 1, получаем частичную перестановку . Делая последний шаг, находим, что следующая после перестановка в лексикографическом порядке равна .
Перестановки можно порождать одну за другой следующим образом. Начиная с перестановки , мы переходим от к ее последующей путем просмотра справа налево в поисках самой правой позиции, в которой . Так как последовательность убывает, это означает, что для каждой из позиций, начиная с позиции i+1, исчерпаны все варианты продолжения при возврате. Поэтому в соответствии с методом перебора с возвратом мы должны начать обновление с позиции i.
Теперь мы ищем - наименьший элемент, расположенный справа от и больший его. Например, для и мы имеем и .
Таким образом, для произвольной перестановки последовательность разбивается на две части. Последовательность образуют числа, большие , поэтому все эти числа и только они входят в множество вариантов продолжения для позиции i. Первый вариант для изменения - это , поэтому меняем местами элементы и , выбирая таким образом первый элемент из для обновления значения . В результате перестановки местами и старое значение освобождается и, во-первых, оно меньше , и во вторых, оно является наибольшим из чисел , поэтому новая последовательность осталась упорядоченной по убыванию.
При фиксированных значениях в первых i позициях лексикографически минимальная перестановка содержит начиная с (i+1)-й позиции возрастающую последовательность из чисел, не встречающихся в первых i позициях. Поэтому после обмена местами элементов и следует перевернуть последовательность .
Для нашего примера перестановка сначала преобразуется в перестановку в результате обмена местами элементов и , т.е. чисел 5 и 7, а затем последовательность переворачивается и принимает вид . Таким образом, мы получаем перестановку , следующую за в лексикографическом порядке.
Приведем алгоритм на псевдокоде, реализующий перечисление всех перестановок на основе метода перебора с возвратом и использующий описанную выше процедуру перехода к следующей перестановке.
{задание начальной перестановки }
for to do
while do
begin
вывести
{найти самое правое место, где }
while do
{найти , наименьший элемент справа от и больший его}
while do
{поменять местами и и затем перевернуть }
while do
begin
end
end
2.2. Сочетания
Пусть - конечное множество различных элементов. Сочетанием мощности k называется k-элементное подмножество множества .
В этом разделе мы рассмотрим задачу порождения всех сочетаний в лексикографическом порядке. Мы делаем упрощающее предположение, что основным множеством является множество натуральных чисел ; таким образом, мы хотим порождать все сочетания мощности k из целых чисел . Будем перечислять сочетания в лексикографическом порядке, с компонентами в каждом сочетании, расположенными в порядке возрастания слева направо. Так, например, сочетания из шести элементов по три (т.е. трехэлементные подмножества множества ) записываются в лексикографическом порядке следующим образом: 123, 124, 125, 126, 134, 135, 136, 145, 146, 156, 234, 235, 236, 145, 246, 256, 345, 346, 356, 456.
Сочетания будем порождать методом перебора с возвратом. Очевидно, начальное сочетание – это множество . Для любого числа при множество вариантов продолжения состоит из чисел .Поэтому каждое следующее сочетание находится просмотром текущего сочетания справа налево с тем, чтобы определить место самого правого элемента, который еще не достиг своего максимального значения. Этот элемент увеличивается на единицу, и всем элементам справа от него присваиваются новые наименьшие возможные значения.
Проиллюстрируем процесс построения нового очередного сочетания на следующем примере. Пусть и рассматривается сочетание . Просматриваем элементы сочетания справа налево и устанавливаем, что два последних элемента имеют наибольшие возможные значения, поэтому их изменить нельзя. Первый справа элемент, который не достиг своего максимального значения, имеет значение 4. Увеличиваем его на единицу, т.е. заменяем на 5, и далее за ним записываем лексикографически минимальную возможную последовательность . Получаем следующее сочетание .
Приведем описание на псевдокоде алгоритма перечисления сочетаний в лексикографическом порядке.
for to do
while do
begin
вывести
while do
for to do
end
3. Оптимизация перебора. Метод ветвей и границ
Применение метода перебора с возвратом к решению задач обычно приводит к алгоритмам с экспоненциальной временной трудоемкостью. Для ускорения перебора с возвратом вычисления стараются организовать так, чтобы была возможность исключать как можно раньше заведомо неподходящие варианты, т.е. сокращать дерево поиска.
Хорошо известным вариантом перебора с возвратом является метод ветвей и границ. Метод основан на упорядоченном переборе решений и рассмотрении только тех из них, которые являются по определенным признакам перспективными, и отбрасывании сразу целых множеств решений, которые бесперспективны.
Для применения метода ветвей и границ должна быть определена стоимость частичных решений; кроме того, для всех частичных решений и для всех расширений должно выполняться условие
.
Здесь через обозначена стоимость частичного решения .
Условия задачи часто позволяют устанавливать границы (верхние и/или нижние) для стоимости решения. Мы можем отбросить частичное решение , если его стоимость превышает верхнюю границу. Мы можем также отбросить частичное решение, если по его стоимости можем определить, что ни при каком расширении этого частичного решения не будет достигнута нижняя граница.
Рассмотрим применение метода ветвей и границ к решению следующей задачи.
Задача. Задано множество целых положительных чисел и число . Требуется узнать, может ли число быть представлено как сумма некоторых из чисел множества , если каждое число можно использовать не более чем по одному разу.
Подмножеству множества поставим в соответствие характеристический вектор по следующему правилу:
положим равным 1, если элемент входит в , и равным 0 в противном случае.
К примеру, для и получаем . Так как числа 2, 3 и 5 входят в множество , вторая, третья и пятая координаты вектора равны единице; числа 1,4 и 6 не входят в , поэтому первая, четвертая и шестая координаты равны нулю.
Нашу задачу можно решать методом перебора с возвратом, перечисляя все возможные характеристические векторы длины , и для каждого такого вектора считать сумму чисел из , которым соответствует значение 1 в .
Всего характеристических векторов , и при больших задача их перечисления будет достаточно трудоемкой. Попробуем сократить перебор, используя метод ветвей и границ.
Пусть - частичный характеристический вектор, . Определим стоимость как сумму чисел из множества , которым соответствует значение 1 в .
Отметим два момента:
а) Стоимость любого частичного вектора , расширение которого может привести к решению задачи, не может быть больше , т.е. , и мы определили верхнюю границу для стоимости частичных решений. В процессе перебора частичных решений будем проверять полученное неравенство и не строить расширения для в случае, когда .
б) Для любого частичного вектора сумма отброшенных элементов из (т.е. элементов, для которых стоит 0 в ) не может быть больше, чем разность суммы всех элементов и (нельзя отбросить слишком много, иначе нам не хватит оставшихся элементов для получения ).
Сформулируем это условие на математическом языке. Для частичного характеристического вектора длины сумма отброшенных элементов равна сумме первых элементов из минус стоимость вектора , т.е. равна . Разность суммы всех элементов и записывается как . Поэтому представляем условие б) в виде неравенства , откуда выводим, что . Мы получили нижнюю границу для стоимости частичного решения.
Таким образом, частичное решение, перспективное для расширения, должно удовлетворять условию
. (*)
Общая рекурсивная схема решения нашей задачи методом ветвей и границ, в предположении, что множество чисел хранится в виде массива, будет иметь следующий вид:
BACKTRACK( ( ), 1, 0, ) {вызов процедуры в основной программе}
procedure BACKTRACK(vector, i, cost, h) {описание процедуры}
begin
if ( и ) then
begin
записать решение
return {выход из программы}
end
for to do
begin
vector:= vector || ( ) {строим расширение вектора}
if then cost:= cost+B[i] {пересчет стоимости решения}
пересчитать нижнюю границу h
if условие (*) для cost выполнено then
BACKTRACK ( vector, i+1)
end
end
Проследим работу алгоритма для конкретных исходных данных. Пусть и . Вычислим начальную нижнюю границу: . Верхняя граница равна 21.
Представим результаты работы алгоритма в виде таблицы (табл.1).
Таблица 1. Результаты работы алгоритма, основанного на методе ветвей и границ
| Шаг | vector | k | cost | h | s | (*) | Примечания |
| 0 | ( ) | 0 | 0 | -7 | 21 | + | Начало |
| 1 | (0) | 1 | 0 | -5 | 21 | + |
|
| 2 | (00) | 2 | 0 | -2 | 21 | + |
|
| 3 | (000) | 3 | 0 | 2 | 21 | - | возврат |
| 4 | (001) | 3 | 4 | 2 | 21 | + |
|
| 5 | (0010) | 4 | 4 | 7 | 21 | - | возврат |
| 6 | (0011) | 4 | 9 | 7 | 21 | + |
|
| 7 | (00110) | 5 | 9 | 13 | 21 | - | возврат |
| 8 | (00111) | 5 | 17 | 13 | 21 | + |
|
| 9 | (001110) | 6 | 17 | 21 | 21 | - | возврат |
| 10 | (001111) | 6 | 25 | 21 | 21 | - | 4 возврата |
| 11 | (01) | 2 | 3 | -2 | 21 | + |
|
| 12 | (010) | 3 | 3 | 2 | 21 | + |
|
| 13 | (0100) | 4 | 3 | 7 | 21 | - | возврат |
| 14 | (0101) | 4 | 8 | 7 | 21 | + |
|
| 15 | (01010) | 5 | 8 | 13 | 21 | - | возврат |
| 16 | (01011) | 5 | 14 | 13 | 21 | + |
|
| 17 | (010110) | 6 | 14 | 21 | 21 | - | возврат |
| 18 | (010111) | 6 | 22 | 21 | 21 | - | 3 возврата |
| 19 | (011) | 3 | 7 | 2 | 21 | + |
|
| 20 | (0110) | 4 | 7 | 7 | 21 | + |
|
| 22 | (01100) | 5 | 7 | 13 | 21 | - | возврат |
| 23 | (01101) | 5 | 13 | 13 | 21 | + |
|
| 24 | (011010) | 6 | 13 | 21 | 21 | - | Возврат |
| 25 | (011011) | 6 | 21 | 21 | 21 | + | Решение |
Найденному решению соответствует характеристический вектор . По нему определяем, что сумма чисел . Действительно, 3+4+6+8=21.
Если бы задача не имела решения, алгоритм закончил бы работу в корне дерева поиска, перебрав все допустимые (т.е. удовлетворяющие верхней и нижней границам) частичные векторы.
На рис.6 приведено дерево поиска для полученного решения.
|
| Начало |
Рис. 6. Дерево поиска с возвратом. Левые ребра соответствуют выбору 0, правые – выбору 1
Таким образом, нам понадобилось исследовать 25 вершин дерева поиска. Проверка соответствия стоимости частичного решения верхней и нижней границам позволила нам отсечь бесперспективные поддеревья, уменьшив тем самым трудоемкость поиска решения. Процессу решения задачи без использования границ соответствовало бы дерево поиска, в котором… Продолжение »