Описываемая в данном разделе техника перебора лежит за пределами того, что используется в олимпиадных задачах. Она используется при решении серьёзных промышленных задач, в которых объём перебора очень велик и важно максимально ускорить решение задачи. Последние сорок лет на исследование перебора с распостранением ограничений были потрачены усилия многих учёных.
Итак, техника перебора с распостранением ограничений слишком сложна для олимпиад. Однако мы подошли к ней слишком близко, чтобы избежать соблазна и не рассмотреть её. Тем более, что описание перебора с распостранением ограничений на русском языке найти очень трудно (единственный источник, изданный массовым тиражом – [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;
Такое изменение алгоритма оказывается не столь существенным, как можно было ожидать. Действительно, порядок перебора (а, значит, и его объем) остаётся по существу тем же самым. Удешевляется (точнее, делается на более раннем этапе) лишь проверка возможности очередного выбора.
Однако такое изменение позволяет реализовать ещё одно улучшение алгоритма, которое мы описываем в следующем подразделе.
Рассмотрим первые шаги перебора для 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 |