Олимпиадные задачи
по информатике
|
Переборные алгоритмы
Задачи на эту тему.
Перебор с распостранением ограничений
Описываемая в данном разделе техника перебора лежит за пределами того, что используется в олимпиадных задачах. Она используется при решении серьёзных промышленных задач, в которых объём перебора очень велик и важно максимально ускорить решение задачи. Последние сорок лет на исследование перебора с распространением ограничений были потрачены усилия многих учёных.
Итак, техника перебора с распространением ограничений слишком сложна для олимпиад. Однако мы подошли к ней слишком близко, чтобы избежать соблазна и не рассмотреть её. Тем более, что описание перебора с распространением ограничений на русском языке найти очень трудно (единственный источник, изданный массовым тиражом – [1]).
4.1 Распространение ограничений
Вернёмся к задаче о ферзях при n=3. После расстановке первого ферзя на первом поле пространство перебора можно сократить не только до показанного на рисунке 3, а до одного элемента: x2=3, x3=2. Действительно, если x1=1, то x2№1, x2№2, x3№1, x3№3.
Как реализовать полностью такое сокращение пространства перебора при выборе очередного ферзя? Для этого надо представлять пространство перебора в памяти. Таким представлением могут быть массивы различных положений для каждого ферзя (как показано на рис. 4, 5, 6). Вместе такие массивы как бы "образуют доску''. Если ферзя можно поставить на данное поле, то в соответствующем элементе массива должен быть записан 0.
При каждом выборе ферзя можно "удалять'' с "доски'' те ``поля'', на которые нельзя поставить ферзей, т.е. записывать в соответствующий элемент не 0.
При этом надо помнить, что при возврате мы все изменения элементов должны восстановить. Как это сделать? Как узнать какие именно изменения были сделаны после того уровня перебора, к которому мы возвращаемся? Возможное решение – исправлять 0 на номер шага! Тогда, если мы возвращаемся к шагу с номером m, то должны восстановить (превратить в 0) все те "поля'', значения которых больше или равны m.
procedure распостранение_ограничений(m:integer);
var i:integer;
if m>n then
<найдено решение>
else
for i:= 1 to n do
if пространство[m,i] = 0 then begin
ферзь[m]:=i;
сократить_пространство_перебора(m,i);
распостранение_ограничений(m+1);
восстановить_пространство_перебора(m,i);
end;
end;
Такое изменение алгоритма оказывается не столь существенным, как можно было ожидать. Действительно, порядок перебора (а, значит, и его объем) остаётся по существу тем же самым. Удешевляется (точнее, делается на более раннем этапе) лишь проверка возможности очередного выбора.
Однако такое изменение позволяет реализовать ещё одно улучшение алгоритма, которое мы описываем в следующем подразделе.
4.2 Изменение порядка перебора
Рассмотрим снова пространство перебора для задачи об n ферзях. Пусть перебор ещё не закончен и пространство перебора сузилось до множества из декартова произведения множеств Ym+1,...,Yn. Понятно, что порядок перебора элементов в этом множестве мы можем выбирать произвольно. Иначе говоря, мы можем делить это пространство на слои по любой из координат. Это означает, что не обязательно перебирать сначала очередного ферзя, а потом остальных – порядок ферзей может быть произвольным.
Рассмотрим первые шаги перебора для n=8. Первый ферзь будет поставлен на первое поле, второй – на третье, третий – на пятое (см. рисунок 7).
Если мы будем перебирать положения для четвёртого ферзя, то нам придётся перебрать по крайней мере три варианта. Однако мы видим, что для шестого ферзя осталось только одно положение. Если вместо расстановки четвёртого ферзя поставить шестого, пространство перебора ещё более сузится (см. рисунок 5). Теперь всего один вариант для восьмого ферзя, потом – для четвёртого и для пятого. Для седьмого ферзя не остаётся ни одного варианта. (см. рисунок 8). Таким образом, мы можем отвергнуть все варианты расстановок (те, которые могут получиться после расстановки первых трёх ферзей как на рисунке 1) практически без перебора. Это благодаря тому, что мы поменяли порядок расстановки ферзей.
Можно сформулировать общий принцип оптимального выбора порядка перебора. Из пространства перебора Xk...Xl как правило лучше выбирать координату i, такую, что Xi имеет самый малый размер (количество элементов). Понятно, почему это так в случае, если этот размер равен 0 – это означает, что уже не осталось вариантов – перебор зашёл в тупик – естественно, нам лучше это заметить как можно раньше. Понятно, почему это так, если размер Xi равен 1. Объясним, почему этот принцип остаётся справедливым и при большем размере.
Чем меньше вариантов выбора очередного ферзя мы рассматриваем, тем большие группы вариантов попадают в каждый такой вариант. А значит, сокращение пространства перебора будет происходить для большей группы за один раз. Это означает в конечном счёте меньший объём перебора.
Запишем алгоритм, реализующий этот принцип. Для хранения номеров ещё не расставленных ферзей и для записи того, какой ферзь перебирается на очередном шаге используется массив на_шаге. Переменная m содержит номер шага, переменная qm – номер перебираемого ферзя. Процедуры сократить_пространство_перебора и восстано вить_пространство_перебора должны быть изменены. Кроме изменения пространства перебора они должны еще пересчитывать количество возможных положений для каждого ферзя, которое хранится в массиве кол_вариантов.
procedure просмотр_вперёд(m:integer);
var i, qm:integer;
if m>n then
<найдено решение>
else begin
{ выбирается ферзь с наименьшим количеством вариантов }
minq:=n+1;
for i:=m to n do
if кол_вариантов[на_шаге[i]] < minq then begin
l:=i; qm:=на_шаге[l];
minq:=кол_вариантов[qm];
end;
на_шаге[l]:=на_шаге[m]; на_шаге[m]:=qm;
for i:=1 to n do
if пространство[qm,i] =0 then begin
ферзь[qm]:= i;
сократить_пространство_перебора(qm,i,m);
просмотр_вперёд(m+1);
восстановить_пространство_перебора(qm,i,m);
end;
end;
Технология такого варианта перебора называется ``просмотром вперёд'' (forward checking).
В заключение небольшая таблица, показывающая время решения (в сотых долях секунды) задачи об n ферзях для алгоритма перебора с возвратом и перебора с распространением ограничений и просмотром вперёд.
| N |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
| перебор с возвратом |
6 |
33 |
154 |
851 |
5174 |
33010 |
420397 |
| распространение ограничений |
3 |
16 |
60 |
280 |
1368 |
7272 |
41507 |
Тексты программ на языке Pascal
{ Программа решения задачи об n ферзях перебором с возвратом }
queen : array[1..100] of integer; { массив положений ферзей }
{ Процедура печати решения }
procedure WriteSolution;
var
i : integer;
begin
for i := 1 to n do
Write(queen[i],' ');
WriteLn
end;
{ Функция проверки совместимости m-го ферзя с предыдущими }
function Check(m : integer) : boolean;
var
i : integer;
begin
for i := 1 to m-1 do
if (queen[i] = queen[m]) { совпадают горизонтали }
Or (i+queen[i] = m+queen[m]) { нисходящие диагонали }
Or (i-queen[i] = m-queen[m]) { восходящие диагонали }
then begin
Check := False; Exit;
end;
Check := True;
end;
{ Процедура, осуществляющая перебор }
procedure Backtrack(m : integer);
var
i : integer;
begin
if m > n then { найдено решение }
WriteSolution
else
for i := 1 to n do begin
queen[m] := i;
if Check(m) { m-ый ферзь не бьёт предыдущих } then
Backtrack(m+1);
end;
end;
begin
Write('Размер доски? '); Read(n);
Backtrack(1)
end.
{ Программа решения задачи об n ферзях перебором с распространением ограничений и просмотром вперёд }
program PropagateQueens;
var
n : integer; { размер доски }
queen : array[1..160] of integer; { массив положений ферзей }
space : array[1..160,1..160] of integer;{пространство перебора}
step : array[1..160] of integer; { порядок выбора ферзей }
cases : array[1..160] of integer; { количество вариантов }
{ Процедура печати решения }
procedure WriteSolution;
var
i : integer;
begin
for i := 1 to n do
Write(queen[i],' ');
WriteLn
end;
{ Процедура сокращения пространства перебора }
procedure Prune(qm,queen,m : integer);
var i, nq : integer;
procedure ExcludeField(queen : integer);
begin
if (queen >= 1) and (queen <= n) then
if space[nq,queen] := 0 then begin
Dec(cases[nq]); space[nq,queen] := m;
end;
end;
begin
for i := m+1 to n do begin
nq := step[i];
ExcludeField(queen); { на той же горизонтали }
ExcludeField(queen+nq-qm); { на той же диагонали }
ExcludeField(queen-nq+qm);
end;
end;
{ Процедура восстановления пространства перебора }
procedure Restore(qm,queen,m : integer);
var i, nq : integer;
procedure IncludeField(queen : integer);
begin
if (queen >= 1) and (queen <= n) then
if space[nq,queen] = m then begin
Inc(cases[nq]); space[nq,queen] = 0;
end;
end;
begin
for i := m+1 to n do begin
nq := step[i];
IncludeField(queen); { на той же горизонтали }
IncludeField(queen+nq-qm); { на той же диагонали }
IncludeField(queen-nq+qm);
end;
end;
var minq, l : integer;
procedure Propagate(m : integer);
var i, qm : integer;
begin
if m > n then
WriteSolution
else begin
{ Выбирается ферзь с наименьшим количеством вариантов }
minq := n+1;
for i := m to n do
if cases[step[i]] <= minq then begin
l := i; qm := step[l]; minq := cases[qm];
end;
step[l] := step[m]; step[m] := qm;
for i := 1 to n do
if space[qm,i] = 0 then begin
queen[qm] := i;
Prune(qm,i,m);
Propagate(m+1);
Restore(qm,i,m);
end;
end;
end;
var i, j : integer;
begin
Write('Размер доски? '); Read(n);
for i := 1 to n do begin
for j := 1 to n do
space[i,j] := 0;
step[i] := i; cases[i] := n;
end;
Propagate(1)
end.
Сайт управляется системой
uCoz