Перебор с распостранением ограничений

Описываемая в данном разделе техника перебора лежит за пределами того, что используется в олимпиадных задачах. Она используется при решении серьёзных промышленных задач, в которых объём перебора очень велик и важно максимально ускорить решение задачи. Последние сорок лет на исследование перебора с распостранением ограничений были потрачены усилия многих учёных.

Итак, техника перебора с распостранением ограничений слишком сложна для олимпиад. Однако мы подошли к ней слишком близко, чтобы избежать соблазна и не рассмотреть её. Тем более, что описание перебора с распостранением ограничений на русском языке найти очень трудно (единственный источник, изданный массовым тиражом – [1]).

Распостранение ограничений

Вернёмся к задаче о ферзях при n= 3. После расстановке первого ферзя на первом поле пространство перебора можно сократить не только до показаного на рисунке 3, а до одного элемента: x 2=3, x 3=2. Действительно, если x 1 = 1, то x 2 ¹ 1, x 2 ¹ 2, x 3 ¹ 1, x 3 ¹ 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 ферзях. Пусть перебор ещё не закончен и пространство перебора сузилось до множества из декартова произведения множеств Y_m+ 1 ,...,Y_n. Понятно, что порядок перебора элементов в этом множестве мы можем выбирать произвольно. Иначе говоря, мы можем делить это пространство на слои по любой из координат. Это означает, что не обязательно перебирать сначала очередного ферзя, а потом остальных – порядок ферзей может быть произвольным.

Рассмотрим первые шаги перебора для n= 8. Первый ферзь будет поставлен на первое поле, второй – на третье, третий – на пятое (см. рисунок 7).

 

Если мы будем перебирать положения для четвёртого ферзя, то нам придётся перебрать по крайней мере три варианта. Однако мы видим, что для шестого ферзя осталось только одно положение. Если вместо расстановки четвёртого ферзя поставить шестого, пространство перебора ещё более сузится (см. рисунок 5). Теперь всего один вариант для восьмого ферзя, потом – для четвёртого и для пятого. Для седьмого ферзя не остаётся ни одного варианта. (см. рисунок 8). Таким образом, мы можем отвергнуть все варианты расстановок (те, которые могут получиться после расстановки первых трёх ферзей как на рисунке 1) практически без перебора. Это благодаря тому, что мы поменяли порядок расстановки ферзей.

 

Можно сформулировать общий принцип оптимального выбора порядка перебора. Из пространства перебора X_k ´...´ X_l как правило лучше выбирать координату i, такую, что X_i имеет самый малый размер (количество элементов). Понятно, почему это так в случае, если этот размер равен 0 – это означает, что уже не осталось вариантов – перебор зашёл в тупик – естественно, нам лучше это заметить как можно раньше. Понятно, почему это так, если размер X_i равен 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

Задачи

Задача 8. В длинную деревянную рейку вбили несколько гвоздей. Некоторые пары гвоздей связываются верёвочками так, чтобы выполнялись следующие условия:

1. к каждому гвоздю была привязана хотя бы одна верёвочка;
2. суммарная длина верёвочек была бы минимальной.

Написать программу, которая связывает пары гвоздей верёвочками как описано выше.

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

Замечание. Задача решается без перебора.

Задача 9. Квадрат размером 5´ 5 вдоль линий сетки разбили на несколько фигурок. Написать программу, которая определяет, можно ли переложить часть фигурок так, чтобы снова образовался квадрат размером 5´ 5. При перекладывании не разрешается поворачивать и переворачивать фигурки.

Технические требования: Входные данные – символьная матрица размером 5´ 5. Каждая буква в матрице означает идентификатор фигурки, содержащей соответствующую клетку. Идентификаторами являются большие буквы латинского алфавита. Программа должна выдать другой способ составления квадрата размером 5´ 5, либо сообщение, что это невозможно.

Замечание. Это стандартная переборная задача. Решается с помощью перебора с возвратом (можно использовать распостранение ограничений).

Задача 10. В океане расположен архипелаг из N островов, каждый из которых имеет форму многоугольника. Острова не соприкасаются и не пересекаются. Эти острова необходимо соединить между собой мостами так, чтобы от любого острова архипелага можно было добраться до любого другого. Каждый мост должен соединять пару островов, при этом суммарная длина мостов должна быть минимальной.

Технические требования: Входными данными являются число островов в архипелаге (N) и N описаний островов. Каждый остров задаётся числом вершин и их координатами в порядке обхода по часовой стрелке. Программа должна вывести два числа – количество мостов и их суммарную длину.

Замечание. Задача решается без перебора.

Задача 11 Разбиение. Массив натуральных чисел A (A 1 ,...,A_n) разбить на два непересекающиеся массива B и C (то есть каждый элемент массива A должен попасть точно в один из двух массивов: B или C), так, чтобы сумма чисел в B равнялась сумме чисел в C.

Технические требования: Входными данными являются количество чисел (n) и последовательность из n чисел. Программа должна вывести два массива чисел B и C.

Замечание. Задача схожа с задачей о рюкзаке и решается перебором с возвратом. Можно использовать распостранение ограничений. Перед перебором имеет смысл упорядочить массив A по невозрастанию.

Тексты программ на Паскале

{ Программа решения задачи об n ферзях перебором с возвратом }  program BacktrackQueens;  var      n: integer; { размер доски } 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.