Отсечение по времени

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

В Турбо Паскале для реализации отсечения по времени используется переменная типа Longint по абсолютному адресу $0:$46c; ее значение увеличивается на единицу каждые 55 миллисекунд:

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

program TheTime_TP;

const

CriticalTime = 4.8; если время на один тест 5 секунд

var

Ct : Longint absolute 0:$46c;

Ot : Longint;

begin

Ot := Ct + Trunc(CriticalTime*1000/55);

while ... do

begin

if Ct>Ot then

Break;

end;

Классической задачей, которая решается методом перебора с отходом назад считается задача о восьми ферзях: требуется перечислить все способы расстановки 8-ми ферзей на шахматной доске 8 на 8, при которых они не бьют друг друга. Эту задачу решил больше 200 лет тому назад великий математик Леонард Эйлер. Заметьте, что у него не было компьютера, но тем не менее он абсолютно верно нашел все 92 таких расстановки!

Очевидно, на каждой из 8 вертикалей должно стоять по ферзю. Каждую такую расстановку можно закодировать одномерным массивом X[1],...,X[8], где X[i] - номер горизонтали для i-го ферзя. Поскольку никакие два ферзя не могут стоять на одной горизонтали (тогда они бьют друг друга), то все X[i] различны, т.е. образуют перестановку из чисел 1..8. Можно, конечно, перебрать все 8! таких перестановок и выбрать среди них те 92, которые нас интересуют.

В общем случае такой алгоритм состоит в последовательном переборе сначала положения для первого ферзя, после каждого выбора такого положения – в переборе положения для второго ферзя и т.д. Алгоритм записывается с помощью n вложенных циклов:

for i1 := 1 to n do begin

ферзь[1] := i1;

for i2 := 1 to n do begin

ферзь[2] := i2;

for i3 := 1 to n do begin

ферзь[3] := i3;

...

... <проверка построенной позиции>

end;

end;

end;

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

Hо как уже говорилось выше, число 8!=40320 довольно большое даже для очень хорошего компьютера - можете в этом убедиться сами. Понятно, что очень важно отсечь ненужные варианты на наиболее ранних этапах перебора. При этом мы, по-существу, отсекаем сразу группу ``лишних'' вариантов. Поэтому мы воспользуемся алгоритмом перебора с возвратом, который позволит значительно сократить перебор и даст ответ намного быстрее:

Использование N вложенных циклов достаточно просто, однако такое решение можно применять для небольших N. Действительно, вложенные друг в друга циклы – очень жесткая структура и если нам надо решать задачу для 100 ферзей, то нам придется писать 100 вложенных друг в друга циклов. Более того, для каждого N нам придётся писать свой вариант алгоритма, отличающийся количеством вложенных циклов. Поэтому вариант с вложенными циклами обычно бывает неприемлемым для реализации перебора с возвратом.

Рассмотрим алгоритм перебора с возвратом, построенный на использовании рекурсии.

Для того, чтобы расставить N ферзей, надо сначала расставить N-1 ферзя и так далее. Явно рекурсивный алгоритм.

procedure перебор_с_возвратом(m : integer);

var i : integer;

begin

if m > n then

<найдено решение>

else

for i := 1 to n do begin

ферзь[m] := i;

if <ферзь[m] не бьёт предыдущих> then

перебор_с_возвратом(m+1);

end;

end;

Таким образом, перебор с возвратом исключает из перебора большое количество вариантов.

Вот текст программы.

program Queens;

const N=8;

type Index=1..N;

Rasstanovka=array [Index] of 0..N;

var X:Rasstanovka;

Count:word;

function P(var X:Rasstanovka;k,y:Index):boolean;

var i:Index;

begin

i:=1;

while (i<k)and(y<>X[i])and(abs(k-i)<>abs(y-X[i])) do inc(i);

P:=i=k

end;

procedure Backtracking(k:Index);

var i,y:Index;

begin

for y:=1 to N do

if P(X,k,y) then

begin

X[k]:=y;

if k=N then

begin

for i:=1 to N do write(X[i]);

writeln;

inc(Count)

end;

Backtracking(k+1)

end

end;

begin

Count:=0;

writeln('Расстановки ',N,' ферзей:');

Backtracking(1);

writeln('Всего ',Count,' расстановок')

end.