Перебор с возвратом

Вариант алгоритма перебора, на котором мы остановились в подразделе 2.1, называется перебором с возвратом. Слово ``возврат'' выражает то, что есл происходит возврат к последнему выбранному элементу и выбирается для него следующее значение.

3.1 Использование рекурсии для записи алгоритма

Приведенная нами в подразделе 2.1 схема алгоритма довольно проста, однако она обычно неприемлема для реализации. Действительно, вложенные друг в друга циклы – очень жесткая структура и если нам надо решать задачу для 100 ферзей, то нам придется писать 100 вложенных друг в друга циклов. Более того, для каждого n нам придётся писать свой вариант алгоритма, отличающийся количеством вложенных циклов. Поэтому вариант с вложенными циклами обычно бывает неприемлемым для реализации перебора с возвратом. В книге [2] приведён алгоритм перебора с возвратом основанный на интерпретации перебора как последовательности переходов вперед-назад. Мы сейчас приведем схему алгоритма перебора с возвратом, построенную на принципах структурного программирования (т.е. без переходов) с использованием рекурсии.

Посмотрим на текст алгоритма. Сам текст алгоритма рекурсивен! Текст для n=k состоит из текста для n=k-1, помещённого в цикл. Таким образом, алгоритм легко переписать в рекурсивном виде. Сначала мы приведём рекурсивный вариант алгоритма полного перебора.


 procedure полный_перебор(m : integer);
 var i : integer;
 begin
     if m > n  then
        <проверка построенной позиции>
     else
        for i := 1  to n  do begin
          ферзь[m] := i;
          полный_перебор(m+1);
        end;
 end;

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


 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;

Чем отличаются данные алгоритмы ? Тем, что в первом проверка позиции происходит на самом позднем (``глубоком'') этапе перебора, а во втором на каждом этапе перебора происходит частичная проверка. (Если же все частичные проверки завершились успешно, получившуюся позицию уже можно не проверять.) Таким образом, перебор с возвратом исключает из перебора большое количество вариантов по сравнению с полным перебором.

3.2 Примеры решения задач при помощи перебора с возвратом

Рассмотрим использование перебора с возвратом при решении других задач. Если пространство перебора представляет собой X1 ґ X2 ґ ... ґ X_n, то общую схему можно записать так:


 procedure перебор_с_возвратом(m : integer);
 var i : integer;
 begin
     if m > n  then
        <найдено решение>
     else
        for i О X_m  do begin
           x[m] := i;
           if <x[m] совместимо с x[1],...,x[m-1]>  then
           перебор_с_возвратом(m+1);
        end;
 end;

Первая задача – очень известная задача о раскраске карты (математики предпочитают обычно говорить о раскраске вершин графа).

Задача 3 Раскраска карты. Имеется географическая карта, на которой расположено n стран. Каждую страну надо раскрасить в один из k цветов так, чтобы соседние страны были раскрашены в разные цвета.

Географическую карту будем задавать в виде матрицы C размером nґ n. Элемент C_i,j равен 1, если страны i и j – соседние и равен 0 иначе.

Пространство перебора состоит из наборов (x1,...,x_n), x_i О {1, ...,k}. Условие совместимости m-го элемента с предыдущими: если C_i,m=1 (1 Ј i < m), то x_i № x_m.

Рекурсивная процедура, осуществляющая перебор с возвратом запишется по рассмотренной схеме:


  procedure перебор_с_возвратом(m : integer);
  var i : integer;
  begin
    if m > n  then
       <найдено решение>
    else
       for i := 1  to k  do begin
          цвет[m] := i;
          if <цвета стран 1,...,m-1 соседних с m-ой не i>  then
           перебор_с_возвратом(m+1);
          end;
  end;

Однако в отличие от задачи о ферзях, в данной задаче перебор можно сократить ещё больше за счёт симметрии решений задачи. Предположим, мы нашли решение задачи. Если мы теперь в этом решении у всех вершин поменяем местами i-ую и j-ую краску, то получившаяся раскраска тоже будет решением. Из таких симметричных решений нам достаточно найти одно. Таким образом, при выборе краски для очередной страны нам достаточно перебрать все уже используемые краски и всего одну (первую) из новых.


  procedure перебор_с_возвратом(m : integer);
  var i : integer;
  begin
     if m > n  then
        <найдено решение>
     else begin
         for i := 1  to кол_красок  do begin
            цвет[m] := i;
            if <цвета стран 1,...,m-1 соседних с m-ой не i>  then
                перебор_с_возвратом(m+1);
         end;
         if кол_красок < k  then begin
            кол_красок := кол_красок+1;
            цвет[m] := кол_красок;
            перебор_с_возвратом(m+1);
            кол_красок := кол_красок-1;
         end;
     end;
  end;

Задача 4 Укладка рюкзака. Из заданных n предметов выбрать такие, чтобы их суммарная стоимость была не менее чем S, а суммарный объём не превосходил V.

Мы немного видоизменили стандартную формулировку этой задачи. Обычно требуется выбрать предметы, чтобы стоимость была максимальной. В нашей формулировке задача несколько упрощена. (это упрощение непринципиально).

Стоимости предметов будут храниться в массиве стоимость, а объёмы – в массиве объём. Пространством перебора в данном случае будут все подмножества множества {1,...,n}. Каждое подмножество можно задавать набором (x1,...,x_n), x_i О {0,1}. Теперь задачу можно переформулировать в следующем виде: Найти набор (x1,...,x_n), x_i О {0,1}, такой что:
S_i=1,...,n x_i· стоимость_i і S, S_i=1,...,n x_i· объём_i Ј V.

Условия, которые можно проверять при выборе:

суммарный объём уже выбранных предметов не превосходит V;
суммарная стоимость выбранных предметов и тех, которые мы можем выбрать не меньше S.

Второе условие удобнее переписать в виде: суммарная стоимость невзятых предметов не превосходит стоимости всех предметов минус S. Cтоимость всех предметов минус S будем хранить в переменной доп_ост. Получаем следующий алгоритм:


  procedure перебор_с_возвратом(m : integer);
  var i : integer;
  begin
     if m > n  then
         <найдено решение>
     else begin
        x[m] := 0;
        ост_стоимость := ост_стоимость+стоимость[m];
        if ост_стоимость <= доп_ост  then
            перебор_с_возвратом(m+1);
        ост_стоимость := ост_стоимость-стоимость[m];
        x[m] := 1;
        сумм_объём := сумм_объём+объём[m];
        if сумм_объём <= V  then
            перебор_с_возвратом(m+1);
        сумм_объём := сумм_объём-объём[m];
     end;
  end;

Задача 5 Расстановка знаков. Дано целое число m. Вставить между некоторыми цифрами 1, 2, 3, 4, 5, 6, 7, 8, 9, записанными именно в таком порядке, знаки ``+'' и ``-'' так, чтобы значением получившегося выражение было число m. Например, если m=122, то подойдёт выражение: 12+34-5-6+78+9. Если расставить знаки требуемым образом невозможно, сообщить об этом.

Решение. Приводимая в [3] программа осуществляет полный перебор вариантов. Причём даже построение выражения осуществляется для каждого варианта отдельно – т.е. самым неэффективным способом. Приведём такой вариант решения (немного улучшенный по сравнению с версией в [3]).


  program signs1;
  var i, ii, kod : integer;
     t : string; op : char;
     s,r,m : longint;
  begin
     readln(m);
     { полный перебор вариантов }
     for ii := 0 to 6560  do begin
         { построение выражения }
         kod := ii; t := '1';
         for i := 2  to 9  do begin
               case (kod mod 3)  of
                1: t := t+'+';
                2: t := t+'-';
               end;
              t := t+chr(48+i);
              kod := kod div 3
         end;
         { вычисление результата }
         t := t+'.'; s := 1; r := 0; op := '+';
         for i := 2  to length(t)  do begin
            if t[i] < '0'  then begin
                 if op = '+'  then r := r+s  else r := r-s;
                s := 0; op := t[i];
             end
             else s := s*10+(ord(t[i])-48)
         end;
         { проверка равенства }
         if r=m  then writeln(t)
     end;
  end.

Если основной цикл представить несколькими вложенными циклами – каждый для отдельной позиции знака в строке, то получится 8 вложенных циклов. Тогда уже можно начинать строить выражение сразу для группы вариантов. На самом нижнем (и наиболее часто исполняемом, а значит и наиболее дорогом) уровне перебора уже нет операций построения строки – они делаются раньше – сразу для групп элементов. Получим следующий текст (строка на первом уровне – t1, на втором – t2 и т.д.):


      for i2 := 1  to 3  do begin
        case (i2 mod 3)  of
           1: t2 := t1+'+'+'2';
           2: t2 := t1+'-'+'2';
            else t2 := t1+'2';
        end;
        for i3 := 1  to 3  do begin
          case (i3 mod 3) of
           1: t3 := t2+'+'+'3';
           2: t3 := t2+'-'+'3';
            else t3 := t2+'2';
          end;
        ...

И так 8 циклов. Довольно длинно, но более эффективно. Причём рекурсивный вариант этого алгоритма устраняет громоздкость текста:


  procedure sign_choice2(n : integer;  var t : string);
  var tnew : string; i : integer;
  begin
    if n <= 9  then
      for i := 1  to 3  do begin
        case i  of
           1: tnew := t+'+'+chr(48+n);
           2: tnew := t+'-'+chr(48+n);
            else tnew := t+chr(48+n);
        end;
        sign_choice2(n+1,tnew);
      end
    else begin
         { вычисление результата }
         t := t+'.'; s := 1; r := 0; op := '+';
         for i := 2  to length(t)  do begin
             if t[i] < '0'  then begin
                 if op = '+'  then r := r+s  else r := r-s;
                s := 0; op := t[i];
             end
             else s := s*10+(ord(t[i])-48)
         end;
         { проверка равенства }
         if r=m  then writeln(t)
    end
  end;

(Вызов данной процедуры заменяет в программе signs1 весь основной цикл.)

Теперь цикл, перебирающий три варианта расстановки знаков, проще расписать напрямую следующим образом:

       tnew := t+'+'+chr(48+n); sign_choice(n+1,tnew);
       tnew := t+'-'+chr(48+n); sign_choice(n+1,tnew);
       tnew := t+chr(48+n);     sign_choice(n+1,tnew);

Теперь осуществим самое важное улучшение алгоритма: не только построение выражения, но и подсчёт результата будем выполнять как можно раньше:


  procedure sign_choice3(s,r : longint; op : char; n : integer;
                t : string);
  var newr : longint;
  begin
    if op = '+'  then newr := r+s  else newr := r-s;
    if n <= 9  then begin
       sign_choice3(n,newr,'+',n+1,t+'+'+chr(48+n));
       sign_choice3(n,newr,'-',n+1,t+'-'+chr(48+n));
       sign_choice3(s*10+n,r,op,n+1,t+chr(48+n));
    end
    else { проверка равенства }
        if newr=m  then writeln(t)
  end;

И, наконец, последнее, уже не столь существенное улучшение. Раз построенное выражение (символьную строчку t) мы не используем для вычисления результата, то можно её вообще не строить (правда, запоминать расставленные знаки всё же придётся, чтобы можно было выдать результат).


  program signs4;
  var t : array[2..9] of string;
  procedure sign_choice4(s,r : longint; op : char; n : integer);
  var newr : longint;
  begin
    if op = '+'  then newr := r+s  else newr := r-s;
    if n <= 9  then begin
       t[n] := '+'; sign_choice4(n,newr,'+',n+1);
       t[n] := '-'; sign_choice4(n,newr,'-',n+1);
       t[n] := ''; sign_choice4(s*10+n,r,op,n+1);
    end
    else { проверка равенства }
        if newr=m  then begin
          for i := 2  to 9  do write(i-1,t[i]);
          writeln('9');
        end;
  end;

  begin
   readln(m);
   sign_choice4(1,0,'+',2);
  end.

Итак, мы пришли всё к той же схеме перебора с возвратом. Правда в этой задаче не удаётся отсечь варианты на ранних этапах перебора (поэтому перед рекурсивным вызовом нет оператора if) и есть еще одно непринципиальное отличие – цикл заменён на три последовательных рекурсивных вызова.

Время выполнения программы, приведенной в [3] – 2.42 сек., программы signs1 – 2.20 сек., программы с процедурой sign_choice2 – 0.96 сек., программы с процедурой sign_choice3 – 0.22 сек., программы signs4 – 0.11 сек. Таким образом, нам удалось значительно сократить перебор. Да и текст программы стал короче.

Задача 6 Минимальный путь. На рисунке изображен треугольник из чисел:

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 Требуется вычислить наименьшую сумму чисел на пути от верхней точки треугольника до основания. При этом:

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

Решение. При решении задачи полным перебором число вариантов равно 2^n-1, где n – число строк в треугольнике. Это, конечно же, неприемлимо. Но как сократить перебор ? Трудно придумать условие, по которому мы могли бы отсекать частично построенные варианты.

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

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

Пусть a_i,j означает j-ое число в i-ой строке, s_i,j – наименьшую сумму чисел от вершины до числа a_i,j. Для s_i,j выполняются следующие соотношения:

s1,1 = a1,1, s_i,1 = a_i,1 + s_i-1,1, s_i,i = a_i,i + s_i-1,i-1,

s_i,j = a_i,j + min {s_i-1,j,s_i-1,j-1}, 1 < j < i Ј n

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

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

Задача 7 Бал. Во время бала в зале, имеющем форму M-угольника A1A2...A_M, этикетом предписано размещаться N придворным дамам вдоль стен и в углах так, чтобы у всех стен стояло равное число дам. Если дама находится в углу, то она считается стоящей у обеих стен этого угла. Вдоль стены может размещаться любое количество дам, а в углу не больше одной. Найти требуемое расположение дам.

Решение. Первый приходящий в голову способ решения для данной задачи – перебор. Однако легко догадаться, что по-существу важно получить какую-либо расстановку дам с суммарным количеством дам, стоящих вдоль стен, кратным количеству стен. Распредилить же потом их поровну не составит труда. А суммарное количество дам, стоящих вдоль стен, (при фиксированных количестве стен и дам) зависит только от того, сколько дам стоит в углах. Оно минимально, если в каждом углу стоит по даме и максимально, если вообще ни в одном углу не стоят дамы. Точнее (обозначим это число через s): N Ј s Ј N+M. Нам требуется так подобрать s, чтобы оно было кратно M. Среди чисел от N до N+M хотя бы одно такое число обязательно найдётся. Это N+M - (N mod M). В углах будет стоять M-(N mod M) дам. Остаётся только выбрать углы и распределить оставшихся дам по сторонам.

3.3 Возврат

В алгоритмах перебора с возвратом надо реализовывать не только собственно перебор, но и возврат назад. Не случайно и сам метод называется ``перебор с возвратом''. Действительно, если вычисления возвращаются к предыдущему уровню перебора и выбирается следующее значение, то должно быть восстановлено то состояние вычислений, которое было в момент предыдущего выбора.

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

Однако, если при ``движении вперёд'' производятся ещё какие-нибудь изменения, их необходимо отменять при возврате.

В задаче о раскраске карты есть такие изменения – это пересчёт количества использованных красок – операторы: кол_красок := кол_красок+1; и восстановление – кол_красок := кол_красок-1;

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

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

Следующая часть, Содержание