Даны N упорядоченных множеств U₁, U₂, ..., U_N (N - известно), и требуется построить вектор A=(a₁, a₂, ..., a_N), где a₁U₁, a₂U₂, ..., a_NU_N, удовлетворяющий заданному множеству условий и ограничений.

В алгоритме перебора вектор А строится покомпонентно слева направо. Предположим, что уже найдены значения первых (k-1) компонент, А=(а₁, а₂, ..., а_(k-1), ?, ..., ?), тогда заданное множество условий ограничивает выбор следующей компоненты а_k некоторым множеством S_kU_k. Если S_k<>[ ] (пустое), мы вправе выбрать в качестве а_k наименьший элемент S_k и перейти к выбору (k+1) компоненты и так далее. Однако если условия таковы, что S_k оказалось пустым, то мы возвращаемся к выбору (k-1) компоненты, отбрасываем а_(k-1) и выбираем в качестве нового а_(k-1) тот элемент S_(k-1), который непосредственно следует за только что отброшенным. Может оказаться, что для нового а_(k-1) условия задачи допускают непустое S_k, и тогда мы пытаемся снова выбрать элемент а_k. Если невозможно выбрать а_(k-1), мы возвращаемся еще на шаг назад и выбираем новый элемент а_(k-2) и так далее.

Графическое изображение - дерево поиска. Корень дерева (0 уровень) есть пустой вектор. Его сыновья суть множество кандидатов для выбора а₁, и, в общем случае, узлы k-го уровня являются кандидатами на выбор а_k при условии, что а₁, а₂, ..., а_(k-1) выбраны так, как указывают предки этих узлов. Вопрос о том, имеет ли задача решение, равносилен вопросу, являются ли какие-нибудь узлы дерева решениями. Разыскивая все решения, мы хотим получить все такие узлы.

Рекурсивная схема реализации алгоритма.

procedure Backtrack(вектор,i);

begin

if <вектор является решением> then <записать его>

else begin <вычислить Si>;

for aSi do Backtrack(векторa,i+1);

{- добавление к вектору компоненты}

end;

end;

Оценка временной сложности алгоритма. Данная схема реализации перебора приводит к экспоненциальным алгоритмам. Действительно, пусть все решения имеют длину N, тогда исследовать требуется порядка S₁*S₂*...*S_N узлов дерева. Если значение S_i ограничено некоторой константой С, то получаем порядка С^N узлов.

1. Задача о расстановке ферзей

На шахматной доске N*N требуется расставить N ферзей таким образом, чтобы ни один ферзь не атаковал другого.

Отметим следующее. Все возможные способы расстановки ферзей - С^N_N^2 (около 4,4*10⁹ для N=8). Каждый столбец содержит самое большее одного ферзя, что дает только N^N расстановок (1,7*10⁷ для N=8). Никакие два ферзя нельзя поставить в одну строку, а поэтому, для того чтобы вектор (а₁, а₂, ..., a_N) был решением, он должен быть перестановкой элементов (1, 2, ..., N), что дает только N! (4,0*10⁴ для N=8) возможностей. Никакие два ферзя не могут находиться на одной диагонали, это сокращает число возможностей еще больше (для N=8 в дереве остается 2056 узлов). Итак, с помощью ряда наблюдений мы исключили из рассмотрения большое число возможных расстановок N ферзей на доске размером N*N. Использование подобного анализа для сокращения процесса перебора называется поиском с ограничениями или отсечением ветвей в связи с тем, что при этом удаляются поддеревья из дерева. Второе. Другим усовершенствованием является слияние, или склеивание, ветвей. Идея состоит в том, чтобы избежать выполнения дважды одной и той же работы: если два или больше поддеревьев данного дерева изоморфны, мы хотим исследовать только одно из них. В задаче о ферзях мы можем использовать склеивание, заметив, что если а₁>N/2, то найденное решение можно отразить и получить решение, для которого а₁N/2. Следовательно, деревья, соответствующие, например, случаям а₁=2 и а₁=N-1, изоморфны.

Следующие рисунки иллюстрируют сказанное и поясняют ввод используемых структур данных.

Структуры данных.

Up:array[2..16] of boolean;{признак занятости диагоналей первого типа}

Down:array[-7..7] of boolean;{признак занятости диагоналей второго типа}

Vr:array[1..8] of boolean;{признак занятости вертикали}

X:array[1..8] of integer;{номер вертикали, на которой стоит ферзь на каждой горизонтали}

Далее идет объяснение “кирпичиков”, из которых “складывается” решение (технология “снизу вверх”).

procedure Hod(i,j:integer); {сделать ход}

begin

X[i]:=j;Vr[j]:=false;Up[i+j]:=false;Down[i-j]:=false;

end;

procedure O_hod(i,j:integer);{отменить ход}

begin

Vr[j]:=true;Up[i+j]:=true;Down[i-j]:=true;

end;

function D_hod(i,j:integer);

{проверка допустимости хода в позицию (i,j)}

begin

D_hod:=Vr[j]andUp[i+j]andDown[i-j];

end;

Основная процедура поиска одного варианта расстановки ферзей имеет вид:

procedure Solve(i:integer;var q:boolean);

var j:integer;

begin

j:=0;

repeat

inc(j);q:=false;{цикл по вертикали}

if D_hod(i,j) then begin Hod(i,j);

if i<8 then begin Solve(i+1,q);

if not q then O_hod(i,j);

end else q:=true;{решение найдено}

end;

until q or (j=8);

end;

Возможные модификации.

Поиск всех решений. Для доски 8*8 ответ 92.

Procedure Solve(i:integer);

var j:integer;

begin

if i<=N then begin

for j:=1 to N do if D_hod(i,j) then begin

Hod(i,j);

Solve(i+1);

O_hod(i,j);

end;

end

else begin

Inc(S);{счетчик числа решений, глобальная переменная}

Print;{вывод решения}

end;

end;

Поиск только не симметричных решений. Для доски 8*8 ответ 12.

Эта модификация требует предварительных разъяснений. Из каждого решения задачи о ферзях можно получить ряд других при помощи вращений доски на 90^о, 180^о и 270^о и зеркальных отражений относительно линий , разделяющих доску пополам (система координат фиксирована). Доказано, что в общем случае для доски N*N (N>1) для любой допустимой расстановки N ферзей возможны три ситуации:

при одном отражении доски возникает новая расстановка ферзей, а при поворотах и других отражениях новых решений не получается;

новое решение при повороте на 90^о и ее отражения дают еще две расстановки;

три поворота и четыре отражения дают новые расстановки.

Для отсечения симметричных решений на всем множестве решений требуется определить некоторое отношение порядка. Представим решение в виде вектора длиной N, координатами которого являются числа от 1 до N. Для ферзя, стоящего в i-й строке, координатой его столбца является i-я координата вектора. Для того, чтобы не учитывать симметричные решения, будем определять минимальный вектор среди всех векторов, получаемых в результате симметрий. Процедуры Sim1, Sim2, Sim3 выполняют зеркальные отображения вектора решения относительно горизонтальной, вертикальной и одной из диагональных осей. Известно (из геометрии), что композиция этих симметрий дает все определенные выше симметрии шахматной доски, причем не принципиально, в какой последовательности выполняются эти процедуры для каждой конкретной композиции. Проверка «на минимальность» решения производится функцией Cmp, которая возвращает значение true в том случае, когда одно из симметричных решений строго меньше текущего.

{не лучший вариант реализации - отсечение на выводе решений}

type Tarray=array[1..N] of integer;

procedure Sim1(var X:Tarray);

var i:integer;

begin

for i:=1 to N do X[i]:=N-X[i]+1;

end;