7.2. Отсечения

Как правило, переборное решение, написанное тупо, делает кучу лишней работы. А именно:

  • если нам надо найти объект, который удовлетворяет определённым требованиям, то перебор находит ещё кучу объектов, которые этому требованию не удовлетворяют (например, в задаче о разложении \(N\) на \(k\) степеней двойки находятся куча наборов из \(k\) степеней двойки, которые в сумме не дают \(N\))
  • если надо найти объект с минимальной стоимостью и т.п., то находятся куча объектов, у которых сумма явно не минимальная.
  • если надо посчитать некоторые объекты, то тоже возможно, что много веток рекурсии не будут приводить к решению.

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

7.2.1. Разложение числа \(N\) в сумму \(k\) степеней двойки

У нас была такая процедура:

procedure find(i:integer);
var j:integer;
begin
if i>k then begin
   check;
   exit;
end;
for j:=0 to 30 do begin
    a[i]:=1 shl j;
    find(i+1);
end;
end;

Попробуем какие-нибудь ветки дерева решений поотсекать. Т.е. фактически надо, чтобы \(find\) не рассматривало некоторые варианты \(a[i]\), которые нам точно не интересны.

Во-первых, очевидно, что не стоит рассматривать \(a[i]\), если оно больше \(n\). Более того, если ввести глобальную переменную \(s\), в которой хранить текущую сумму, то можно рассматривать только \(a[i]\), которые не превосходят \(n-s\):

var s:...
procedure find(i:integer);
var j:integer;
begin
if ....
end;
for j:=0 to 30 do if 1 shl j<=n-s then begin
    a[i]:=1 shl j;
    s:=s+a[i];
    find(i+1);
    s:=s-a[i]; {Откатываем назад!!!}
end;
end;

Очевидно, что это тоже будет работать корректно (кстати, это ещё и исправляет баг с переполнением в процедуре \(check\), который обсуждался в предыдущем разделе).

Заметьте, что можно это написать и по-другому:

var s:...
procedure find(i:integer);
var j:integer;
begin
if i>k...
end;
if s>=n then
   exit;
for j:=0 to 30 do  begin
    a[i]:=1 shl j;
    s:=s+a[i];
    find(i+1);
    s:=s-a[i]; {Откатываем назад!!!}
end;
end;

т.е. вынести проверку в начало процедуры \(find\). Теперь, если в некоторый момент мы взяли \(a[i]>n-s\), то мы попробуем такой вариант, войдём в \(find(i+1)\), но тут же выйдем назад, т.к. \(s\geq n\). Обратите внимание, что проверка стала нестрогой (\(\geq\), а не \(>\)), т.к. я её переместил после проверки if i>k.

(Этот вариант, в отличии от предыдущего, видимо, не будет решать бага с переполнением, но баг с переполнением — это особая фича именно этой задачи; в других задачах таких приколов может не быть).

Задача 7.13:

Переделайте эту программу, чтобы не хранить глобальную переменную \(s\), а передавать \(s\) (или \(n-s\), т.е. оставшееся число) через параметр процедуры.

Заметьте также, что на самом деле \(s\) можно не хранить и не передавать, а вычислять заново на каждом шаге. Но ясно, что это дольше и сложнее. Вообще мне кажется более естественным проводить отсечения в начале процедуры \(find\) (как правило, после проверки на выход из рекурсии), как в последнем примере. Типа процедура \(find\) сначала оценит, стоит ли вообще возится с дальнейшим перебором: если не стоит (в данном случае если \(s\geq n\)), то \(exit\), иначе перебираем все подряд,

Попробуем поотсекать дальше. Например, очевидно, что в начале \(find(i)\) у нас ещё \(k-i+1\) мест не заполнены. На них встанут как минимум единицы (т.е. \(2^0\)), поэтому, если \(s+k-i+1>n\), то тоже можно отсекать. Вообще, обычно отсечения можно проводить почти что до бесконечности :) придумывая все более и более точные критерии того, что решения не найдётся, и, если на олимпиаде делать нечего, то можно над этим и думать. Главное, нигде не наглючить, т.к. сложность программы с увеличением количества отсечений возрастает, и соответственно возрастает вероятность ошибки, а вот скорость работы программы может и не сильно увеличиваться.

7.2.2. Виды отсечений

Какие обычно бывают отсечения:

  • Если задача программы — найти оптимальный объект (объект с минимальной стоимостью и т.п.), то обычно можно оценить, какая минимальная стоимость будет у объекта, когда мы его достроим, исходя из текущего начала объекта (например, часто она больше текущей стоимости). Если эта «оценка снизу» на стоимость достроенного объекта уже больше лучшей из полученных на данный момент стоимостей, то дальше искать бессмысленно (см. пример дальше).
  • Если задача программы — получить объект с определёнными свойствами, то если очевидно, что это свойство точно уже не выполнить при данном начале, то дальше искать бессмысленно (как в примере выше: если \(s>n\), то искать дальше точно бессмысленно).
  • Если же задача программы — посчитать количество таких объектов, то здесь все сложнее. Смысл отсечения тут разве что в том, чтобы каждая ветка рекурсии заканчивалась нахождением решения. Пример будет ниже.
  • Сразу замечу про ещё одно важное отсечение: отсечение по времени. Про него тоже скажу ниже.

Пример по второму пункту мы разобрали; разберём примеры по двум оставшимся пунктам.

7.2.3. Пример на отсечения при подсчёте количества объектов

Пусть цель программы — посчитать объекты. Рассмотрим в качестве примера странную задачу про нули и единицы (сначала попробуйте сами его порешать!) Конечно, как и предлагалось в подсказке, будем перебирать разбиения нулей на группы. Будем решать задачу: сколькими способами можно разбить \(m\) нулей на \(nn\) групп так, чтобы в последовательных группах количества нулей или совпадали, или увеличивались на единицу.

Во-первых, тут \(i=1\) — особый случай (см. ещё ниже). Когда мы выбираем, сколько нулей у нас будет в первой группе, нет никаких ограничений. А когда выбираем, сколько нулей в дальнейших группах, у нас только два варианта: столько же, как и в прошлой группе, и на единицу больше. Будем передавать в процедуру количество нулей, которые осталось разбить по группам, чтобы было удобнее. Получаем следующий код (дополнительные комментарии см. ниже):

procedure find(i,k:integer);
var j:integer;
    prev:integer;
begin
if i>nn then begin
   check;
   exit;
end;
if k<=0 then
   exit;
if i=1 then begin
   for j:=1 to k do begin
       a[1]:=j;
       find(2,k-j);
   end;
end else begin
    prev:=a[i-1];
    a[i]:=prev;
    find(i+1,k-a[i]);
    a[i]:=prev+1;
    find(i+1,k-a[i]);
end;
end;

Подумаем, как можно отсечь. По сути, наша цель — чтобы каждая ветка заканчивалась нахождением решения. Подумаем, как может получиться так, что решение не найдётся. Могут быть два варианта: либо у нас нулей слишком мало осталось, либо слишком много. Что значит слишком мало — значит, что, даже если расходовать их в группы по минимуму, нулей не хватит. Групп у нас остаётся ещё \(nn-i+1\), в каждую надо как минимум \(prev\) нулей, поэтому, если \(k<prev\cdot(nn-i+1)\), то решений точно не найдётся. Аналогично, что значит, что нулей слишком много? В первую группу мы можем поставить максимум \(prev+1\) нуль, во вторую — \(prev+2\) и т.д. В \(nn-i+1\)-ую — \(prev+nn-i+1\), тогда общее количество нулей (сумма арифметической прогрессии) получится \((prev+1+prev+nn-i+1)\cdot(nn-i+1)/2\). Поэтому, если \(k>(prev+1+prev+nn-i+1)\cdot(nn-i+1)/2\), то решений тоже точно не найдётся. Поэтому получаем отсечение

if (k<prev*(nn-i+1))or (k>(prev+1+prev+nn-i+1)*(nn-i+1) div 2) then
   exit;

и окончательное решение (привожу на этот раз полную программу):

var a:array[1..100] of integer;
    n,m:integer;
    nn:integer;
    ans:longint;
    res:longint;

procedure check;
var i:integer;
    s:integer;
begin
s:=0;
for i:=1 to nn do
    s:=s+a[i];
if s<>m then
   exit;
for i:=2 to nn do
    {на всякий случай проверим, что все правильно.
    На самом деле это никогда не должно сработать}
    if (a[i]<>a[i-1])and(a[i]<>a[i-1]+1) then begin
       writeln('!!2');
       halt;
    end;
inc(ans);
end;

procedure find(i,k:integer);
      {k --- сколько нулей осталось разбить по группам}
var j:integer;
    prev:integer;
begin
if i>nn then begin
   check;
   exit;
end;
if k<=0 then begin
       {если нулей не осталось,
        то бессмысленно что-либо перебирать.
        Обратите внимание, что это
        написано после предыдущего if'а.}
   exit;
end;
if i=1 then begin
      {i=1 здесь особый случай, т.к. у него
      нет предыдущей группы.
      Как это сделать поэлегантнее, я не придумал}
   for j:=1 to k do begin
       a[1]:=j;
       find(2,k-j);
   end;
end else begin
    prev:=a[i-1];
    if (k<prev*(nn-i+1))or
         (k>(prev+1+prev+nn-i+1)*(nn-i+1) div 2) then
       exit;
    a[i]:=prev;
    find(i+1,k-a[i]);  {k-a[i] нулей осталось разбить}
    a[i]:=prev+1;
    find(i+1,k-a[i]);
end;
end;

function count(n,m:integer):longint;
begin
ans:=0;
nn:=n;
if n>0 then
   find(1,m);
count:=ans;
end;

begin
read(n,m);
res:=count(n-1,m)+2*count(n,m)+count(n+1,m);
{если n=1, то в count передастся n-1=0.
Для этого и стоит проверка if n>0 в функции count}
writeln(res);
end.

Можете потестить это решение. На тесте, на котором самый большой ответ при ограничениях \(n,m\leq 100\) (видимо, \(n=27\), \(m=100\)) оно у меня работает секунды три, при том, что динамика там же работает немногим быстрее. Если же отсечение убрать, то тормозит много сильнее.

А теперь самое важное тут:

Важно

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

Следовательно, мы можем оценить, сколько всего веток перебора будет: у дерева решений листьев будет примерно столько же, сколько мы найдём решений, т.е. столько, сколько ответ на задачу. Очевидно, что, поскольку мы тут не умеем считать объекты пачками, т.е. мы каждый объект (разбиение) считаем отдельно, то быстрее работать вряд ли получится: на каждый объект нужен лист дерева решений, т.е. листьев должно быть не меньше, чем ответ на задачу (с другой стороны то же самое: процедура \(check\) делает \(inc(ans)\), следовательно, она должны будет быть вызвана как минимум столько раз, каков ответ на задачу. Могло оказаться, что она вызвана будет намного большее количество раз, но в нашей программе это не так: мы специально сделали, чтобы каждый вызов \(check\) делал \(inc(ans)\); ладно, почти каждый. Ещё меньше вызовов \(check\) сделать в рамках решений, которые делают только \(inc(ans)\), невозможно).

Количество листьев приблизительно характеризует время работы программы: понятно, что, чем их больше, тем дольше работает программа. Поэтому всегда надо стараться уменьшить число листьев. Но тут мы уменьшили их до минимума: меньше, чем ответ на задачу, не получится. Таким образом, быстрее написать перебор, видимо, тут не получится. Мы оптимизировали дерево решений как могли. (Не программу, а дерево решений. Решение, может быть, можно оптимизировать ещё. Например, придумать, как убрать цикл из процедуры check; может быть, избавиться от деления на 2 в отсечении, и т.п. Но дерево решений все равно уже не изменится).

Кроме того, можно время, которое работает наша программа, теперь можно оценить по ответу на тест (ведь процедура \(check\) будет именно столько раз вызываться — ну, почти столько); если ответ небольшой, то можно рассчитывать, что наша программа тормозить не будет. Идея переборного решения этой задачи родилась у меня, когда я узнал, что максимальный ответ в тестах был пятизначным. Стало ясно, что такой перебор тормозить не может.

Задача 7.14:

(Творческое) Попробуйте придумать, как бы написать программу, чтобы не нужно было выделять \(i=1\) в особый случай. Это не очень тривиально, и есть несколько вариантов, как это сделать.

Примечание

Общепрограммистский (т.е. не относящийся именно к перебору) комментарий

Всегда старайтесь все делать как можно проще. Особые случаи — это то, что очень сильно усложняет программу, поэтому всегда старайтесь придумать, как бы обойтись без особых случаев. Кроме того, особые случаи — это первый признак того, что решение у вас неправильное. Т.е. если у вас в программе появляется особый случай, то задайтесь вопросом: чем этот случай действительно особый? Почему его не получается обработать общим случаем? Нет ли ещё аналогичных особых случаев? (собственно, именно наличие уверенного и обоснованного ответа на последний вопрос и обозначает, что вы поняли, почему этот случай особый) Может быть, есть другие особые случаи, причём их много — проще говоря, надо искать другой алгоритм для общего случая, т.е. ваше текущее решение неправильное? (На самом деле имеет смысл задавать вообще ещё более общий вопрос: зачем написана каждая строчка кода, каждый цикл, каждый \(if\)? Почему без них нельзя обойтись?) И даже если вы поняли, чем этот случай действительно особый, попробуйте его все-таки свести к общему случаю (см. пример в следующем абзаце); правда, не переусердствуйте; эта задача —плохой пример, здесь сведение слишком сложное и, может быть, проще оставить все как было. Если в результате сведения все получается только сложнее, то, может быть, и не надо избавляться от особого случая.

В данной задаче вроде ясно, почему случай \(i=1\) особый: в первую группу мы можем поставить сколько угодно нулей, в то время как во вторую и дальнейшие — либо столько же, сколько и в предыдущей, либо на единицу больше. Но это не оправдание до конца. Во многих задачах удаётся и в такой ситуации свести частный случай к общему, например, введением нулевых элементов (сравните с осуществлением требования, чтобы в переборе всех \(C_n^k\) и т.п. все элементы возрастали: случай \(i=1\) там обрабатывается в общем порядке, несмотря на то, что у него нет предыдущего элемента. Ну и что, а мы сделали ему предыдущий элемент, \(a[0]\), который всегда меньше всего, что может быть). Но в этой задаче я не смог придумать, как бы поэлегантнее избежать выделения \(i=1\) в особый случай. Конечно, можно убрать этот особый случай из процедуры \(find\), но придётся наворачивать кучу кода в других местах…В общем, видимо, проще программу сделать у меня не получается. Но вдруг у вас получится? Или хотя бы попробуйте сделать, чтобы действительно понять, в чем тут трудности.

7.2.4. Отсечения в задачах на оптимизацию

Пусть цель программы — найти оптимальный объект. Рассмотрим в качестве примера задание про удаление чисел со штрафом.

(Ещё раз замечу, что на самом деле многие задачи, которые мы тут обсуждаем, решаются более крутыми способами. Например, эта задача решается динамикой. Но тут мы обсуждаем, как их можно было решать перебором.)

Итак, наша программа будет перебирать все возможные последовательности удаления чисел, и для каждой считать штраф. Процедура \(check\) будет проверять, верно ли, что штраф меньше оптимального, и, если да, то запоминать текущее решение. Напишем программу следующим образом:

var a,b,ans:array...
    nn:integer;
    cur,best:longint;

procedure insert(i:integer;v:integer);
var j:integer;
begin
for j:=nn downto i do
    b[j+1]:=b[j];
b[i]:=v;
inc(nn);
end;

function delete(i:integer):integer;
var j:integer;
begin
delete:=b[i];
for j:=i+1 to nn do
    b[i-1]:=b[i];
dec(nn);
end;

procedure check;
begin
if cur<best then begin
   best:=cur;
   ans:=a;
end;
end;

procedure find(i:integer);
var j:integer;
    x:integer;
begin
if nn=2 then begin
   check;
   exit;
end;
for j:=2 to nn-1 do begin
    a[i]:=j;
    cur:=cur+b[j]*(b[j-1]+b[j+1]);
    x:=delete(j);
    find(i+1);
    insert(j,x);
    cur:=cur-b[j]*(b[j-1]+b[j+1]);
end;
end;

Поясню. У нас есть массив \(a\), в котором, как всегда, мы храним текущее решение. В данном случае — последовательность номеров удаляемых чисел. \(Ans\) — наилучшее найденное на данный момент решение. \(Cur\) — текущий штраф (за те удаления, которые мы уже сделали), \(best\) — штраф в наилучшем найденном к данному моменту решении. В массиве \(b\) мы храним текущие числа, \(nn\) — их количество.

Процедура \(delete\) удаляет число из массива \(b\), корректируя \(nn\), и возвращает удалённое число. Процедура \(insert\) отыгрывает удаление числа: вставляет его назад. На самом деле лучше было бы работать со связными списками, где удалить и вставить число можно намного быстрее (т.к. циклы в \(insert\) и \(delete\) сильно тормозят программу), но, чтобы не загромождать основные идеи, в этом примере я буду писать так. Процедура \(check\) просто проверяет, лучшее это решение, или нет.

Процедура \(find\) — основная процедура перебора. Работает она так. Во-первых, если в массиве осталось всего 2 элемента (\(nn=2\); на самом деле, очевидно, это условие равносильно \(i=n-2\)), то делать больше ничего не надо (удалять надо все числа, кроме крайних), поэтому \(check\) и \(exit\).

В противном случае посмотрим, какое число будем удалять. Запомним его номер в массиве \(a\), скорректируем текущий штраф \(cur\) и текущий массив \(b\) (последнее — вызовом \(delete\)), и пойдём перебирать дальше: \(find(i+1)\). После этого не забудем вернуть все назад!

Надеюсь, что вам понятно, как работает эта программа. Пара замечаний:

  • Здесь процесс «отката» изменений весьма нетривиален. Можно было сохранить \(cur\) и \(b\) в стеке:

    procedure find(i:integer);
    var j:integer;
        ocur:... {old cur}
        ob:.. {old b}
    begin
    if nn=2 ...
    end;
    ocur:=cur;
    ob:=b;
    for j:=2 to nn-1 do begin
        a[i]:=j;
        cur:=cur+b[j]*(b[j-1]+b[j+1]);
        delete(j);
        find(i+1);
        b:=ob;
        cur:=ocur;
    end;
    end;
    

    обратите внимание, что теперь переменная \(x\) не нужна. Но в результате может не хватить стека, т.к. каждая копия процедуры \(find\) будет хранить свой массив \(ob\).

  • На самом деле нас теперь массив \(a\) нужен только для того, чтобы выводить ответ. Если сам ответ выводить не надо, то можно не хранить массив \(a\) (и, соответственно, массив \(ans\)) вообще. Тогда нам не нужна будет и переменная \(i\); процедура \(find\) теперь не будет принимать никаких параметров (!), она теперь будет перебирать один шаг удаления и запускаться рекурсивно для дальнейшего перебора (а текущая глубина перебора пока неявно присутствует в переменной \(nn\)).

Задача 7.15:

Напишите программу без массива \(a\) и переменной \(i\). Попробуйте её осознать «с нуля».

Задача 7.16:

Напишите эту программу, работая со связными списками.

Подумаем тут над тем, какие можно придумать отсечения. Во-первых, если все числа положительны, то очевидно, что если \(cur\geq best\), то решения лучше чем текущее, мы точно не найдём. Поэтому первое отсечение — if cur>=best then exit. Это (как я уже говорил), фактически, стандартное отсечение в подобных задачах.

Обратите внимание: условие нестрогое. if cur>=best, а не if cur>best. Действительно, нам несколько раз получать оптимальное решение не надо. Вот если бы надо было вывести все оптимальные решения, тогда пришлось бы писать \(cur>best\).

Можно пытаться придумывать другие отсечения. Например, за каждое удаление мы получаем штраф, как минимум равный удвоенному удаляемому числу (считаем, что у нас числа натуральные, и значит, сумма соседей \(\geq 2\)). Поэтому за удаление всех чисел мы получим штраф как минимум равный удвоенной сумме всех чисел. Поэтому, если знать сумму всех чисел (кроме крайних) \(s\), то можно отсекать по условию \(cur+2\cdot s\geq best\). Сумму можно поддерживать во время работы программы или каждый раз считать заново. (Поддерживать значит хранить в отдельно переменной и быстро пересчитывать при каждом изменении массива. Мы это уже много раз делали).

Задача 7.17:

Напишите оба этих варианта программы: с хранением суммы в отдельной переменной или с вычислением каждый раз заново.

На самом деле, как я уже говорил, отсечения можно придумывать до бесконечности. Можно учесть, какой минимальный элемент у нас остался, и умножать не на 2, а на удвоенный этот элемент и т.д. Главное, не запутаться в этих отсечениях, нигде не ошибиться, не опоздать решить другую задачу :) и не писать отсечения, которые будут все равно неэффективны. Т.е. главное — не переборщить.

Задача 7.18:

Придумайте отсечения к задаче о паросочетании в произвольном графе, в обоих вариантах: а и б). Напишите полную программу.