Перебор с возвратом (стр. 1 из 3)

Министерство образования Республики Беларусь

Учреждение образования

«Гомельский государственный университет им. Ф. Скорины»

Математический факультет

Кафедра МПУ

Курсовая работа

Перебор с возвратом

Исполнитель:

Студентка группы М-32

Ловренчук А.Ю.

Научный руководитель:

Канд. физ-мат. наук, доцент

Звягина Т.Е.

Гомель 2007

Введение

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

В алгоритме перебора вектор А строится покомпонентно слева направо. Предположим, что уже найдены значения первых (k-1) компонент, А=(а₁, а₂, ..., а_(k-1), ?, ..., ?), тогда заданное множество условий ограничивает выбор следующей компоненты а_k некоторым множеством S_kÌU_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 aÎSi 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

elsebegin

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;

procedure Sim2(var X:Tarray);

var i,r:integer;

begin

for i:=1 to N do begin

r:=X[i]; X[i]:=X[N-i+1];X[N-i+1]:=r;

end;

end;

procedure Sim3(var X:Tarray);

var Y:Tarray;

i:integer;

begin

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

X:=Y;

end;

function Cmp(X,Y:Tarray):boolean;

var i:integer;

begin

i:=1;

while (i<=N) and (Y[i]=X[i]) do Inc(i);

if i>N then Cmp:=false

else if Y[i]<X[i] then Cmp:=true else Cmp:=false;

end;

Procedure Solve(i:integer);

var j:integer;f:boolean;

Y:Tarray;

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

f:=true;

for j:=0 to 7 do begin

Y:=X;

if j and 1 =0 then Sim1(Y);

if j and 2 =0 then Sim2(Y);

if j and 4 =0 then Sim3(Y);

if Cmp(Y,X) then f:=false;

end;

iffthenbegin

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

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

end;

end;

end;

2. Задача о шахматном коне

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

Разбор задачи начинается с оценки числа 64! - таково общее число способов разметки доски 8*8. Каждую разметку следует оценивать на предмет того, является ли она способом обхода конем доски(решение в “лоб”). Затем оцениваем порядок сокращения перебора исходя из условия - логика выбора очередного хода коня. Будем считать, что поля для хода выбираются по часовой стрелке. Объяснение иллюстрируется следующими рисунками.

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

Const N= ; M= ;

Dx:array[1..8] of integer=(-2,-1,1,2,2,1,-1-2);

Dy:array[1..8] of integer=(1,2,2,1,-1,-2,-2,-1);

Var A:array[-1..N+2,-1..M+2] of integer;

Основной фрагмент реализации - процедура Solve.

procedure Solve(x,y,l:integer);

var z,i,j:integer;

begin

A[x,y]:=l;

if l=N*M then Inc(t)

else for z:=1 to 8 do begin i:=x+Dx[z];j:=y+Dy[z];