Методы программирования: переборные алгоритмы

Булычев В.А.
Данная статья открывает цикл работ, посвященных не особенностям какого-то отдельного языка программирования (например Паскаля), а общим ИДЕЯМ и МЕТОДАМ разработки алгоритмов. Тем не менее, опираться мы все равно будем на теория, числа, оптимальные алгоритмы, вычислительная, определение, который вы уже знаете. Первоначальный вариант любого алгоритма мы будем записывать на псевдокоде - языке, который занимает промежуточное положение между нашим обычным языком и языками программирования. Он не имеет каких-то жестких правил и требований, т.к. предназначен прежде всего для человека, а не компьютера. Это позволит нам избавиться от излишней детализации алгоритма на раннем этапе разработки и сразу выразить его основную идею. Превратить этот псевдокод в программу на Паскале задача совсем несложная - как это делать вы быстро поймете.
Основные идеи первого задания - ПЕРЕБОР, РЕКУРСИЯ, ПЕРЕБОР С ОТХОДОМ НАЗАД. Этими понятиями должен хорошо владеть каждый программист. Кроме того, переборные задачи составляют значительную долю всех школьных олимпиад по информатике.
== Порождение и перебор комбинаторных объектов ==
Во многих прикладных задачах требуется найти оптимальное решение среди очень большого (но конечного!) числа вариантов. Иногда удается построить это решение сразу, но в большинстве случаев единственный способ его отыскать состоит в переборе ВСЕХ возможных вариантов и сравнении их между собой. Поэтому так важно для нас научиться строить алгоритмы ПЕРЕБОРА различных комбинаторных объектов - последовательностей, перестановок, подмножеств и т.д.
Схема перебора всегда будет одинакова:
* во-первых, надо установить ПОРЯДОК на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);
* во-вторых, научиться переходить от произвольного элемента к НЕПОСРЕДСТВЕHHО СЛЕДУЮЩЕМУ за ним (т.е. для заданного элемента x1 строить такой элемент x2, что x1 < x2 и между x1 и x2 нет других элементов).
Наиболее естественным способом упорядочения составных объектов является ЛЕКСИКОГРАФИЧЕСКИЙ порядок, принятый в любом словаре (сначала сравниваются первые буквы слов, потом вторые и т.д.) - именно его мы и будем чаще всего использовать. А вот процедуру получения следующего элемента придется каждый раз изобретать за- ново. Пока запишем схему перебора в таком виде:
 X := First;
 while X <> Last do Next(X);
где First - первый элемент; Last - последний элемент; Next - процедура получения следующего элемента.
=== Последовательности ===
Напечатать все последовательности длины N из чисел 1, 2, ..., M.
 First = (1, 1, ..., 1)
 Last = (M, M, ..., M)
Всего таких последовательностей будет M^N (докажите!). Чтобы понять. как должна действовать процедура Next, начнем с примеров. Пусть N=4,M=3. Тогда:
 Next(1,1,1,1) -> (1,1,1,2)
 Next(1,1,1,3) -> (1,1,2,1)
 Next(3,1,3,3) -> (3,2,1,1)
Теперь можно написать общую процедуру Next:
procedure Next;
begin
 { найти i: X[i] < M, X[i+1] = M, ..., X[N] = M }
 X[i] := X[i]+1;
 X[i+1] := ... := X[N] := 1
end;
Если такого i найти не удается, то следующей последовательности нет - мы добрались до последней (M, M,..., M). Заметим также, что если бы членами последовательности были числа не от 1 до M, а от 0 до M-1, то переход к следующей означал бы прибавление 1 в M-ичной системе счисления. Полная программа на Паскале выглядит так:
program Sequences;
type
 Sequence = array [byte] of byte;
var
 M, N, i: Byte;
 X: Sequence;
 Yes: Boolean;
procedure Next(var X: Sequence; var Yes: Boolean);
var
 i: Byte;
begin
 i := N;
 { поиск i }
 while (i > 0) and (X[i] = M) do
 begin
 X[i] := 1;
 Dec(i)
 end;
 if i > 0 then
 begin
 Inc(X[i]);
 Yes := True
 end
 else
 Yes := False;
end;
begin
 Write('M, N=');
 ReadLn(M, N);
 for i := 1 to N do
 X[i] := 1;
 repeat
 for i := 1 to N do
 Write(X[i]);
 WriteLn;
 Next(X, Yes);
 until not Yes
end.
=== Перестановки ===
Напечатать все перестановки чисел 1..N (то есть последовательности длины N, в которые каждое из чисел 1..N входит ровно по одному разу).
 First = (1, 2, ..., N)
 Last = (N, N-1, ..., 1)
Всего таких перестановок будет N! = N*(N-1) * ... * 2 * 1 (докажите!). Для составления алгоритма Next зададимся вопросом: в каком случае i-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше i).
Мы должны найти наибольшее i, при котором это так, т.е. такое i, что X[i] < X[i+1] > ... > X[N] (если такого i нет, то перестановка последняя). После этого X[i] нужно увеличить минимально возможным способом, т.е. найти среди X[i+1], ..., X[N] наименьшее число, большее его. Поменяв X[i] с ним, остается расположить числа с номерами i+1, ..., N так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке:
procedure Next;
begin
 { найти i: X[i] < X[i+1] > X[i+2] > ... > X[N] };
 { найти j: X[j] > X[i] > X[j+1] > ... > X[N] };
 { обменять X[i] и X[j] };
 { X[i+1] > X[i+2] > ... > X[N] };
 { перевернуть X[i+1], X[i+2], ..., X[N] };
end;
Теперь можно написать программу:
program Perestanovki;
type
 Pere = array [Byte] of Byte;
var
 N, i, j: Byte;
 X: Pere;
 Yes: boolean;
procedure Next(var X: Pere; var Yes: Boolean);
var
 i: Byte;
 procedure Swap(var a, b: Byte); { обмен переменных }
 var
 c: Byte;
 begin
 c := a;
 a := b;
 b := c;
 end;
begin
 i := N-1;
 { поиск i }
 while (i > 0) and (X[i] > X[i+1]) do
 Dec(i);
 if i > 0 then
 begin
 j := i+1;
 { поиск j }
 while (j < N) and (X[j+1] > X[i]) do
 Inc(j);
 Swap(X[i], X[j]);
 for j := i+1 to (N+i) div 2 do
 Swap(X[j], X[N-j+i+1]);
 Yes := True
 end
 else
 Yes := False
end;
begin
 Write('N=');
 ReadLn(N);
 for i := 1 to N do
 X[i] := i;
 repeat
 for i := 1 to N do
 Write(X[i]);
 WriteLn;
 Next(X, Yes);
 until not Yes;
end.
=== Разбиения ===
Перечислить все разбиения целого положительного числа N на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно).
Пример: N=4, разбиения: 1+1+1+1, 2+1+1, 2+2, 3+1, 4.
 First = (1,1,...,1) - N единиц Last = (N)
Чтобы разбиения не повторялись, договоримся перечислять слагаемые в невозрастающем порядке. Сказать, сколько их будет всего, не так-то просто (см.следующий пункт). Для составления алгоритма Next зададимся тем же вопросом: в каком случае i-ый член разбиения можно увеличить, не меняя предыдущих?
Во-первых, должно быть X[i-1] > X[i] или i=1. Во-вторых, i должно быть не последним эле ментом (увеличение i надо компенсировать уменьшением следующих). Если такого i нет, то данное разбиение последнее. Увеличив i, все следующие элементы надо взять минимально возможными, т.е. равными единице:
procedure Next;
begin
 { найти i: (i < L) and ( (X[i-1] > X[i]) or (i=1) ) }
 X[i] := X[i]+1;
 { L := i + X[i+1] + ... + X[L] - 1 }
 X[i+1] := ... := X[L] := 1
end;
Через L мы обозначили количество слагаемых в текущем разбиении (понятно, что 1 <= L <= N). Программа будет выглядеть так:
program Razbieniya;
type
 Razb = array [Byte] of Byte;
var
 N, i, L: Byte;
 X: Razb;
procedure Next(var X: Razb; var L: Byte);
var
 i, j: Byte;
 s: Word;
begin
 i := L-1;
 s := X[L];
 { поиск i }
 while (i > 1) and (X[i-1] <= X[i]) do
 begin
 s := s+X[i];
 Dec(i);
 end;
 Inc(X[i]);
 L := i+s-1;
 for j := i+1 to L do
 X[j] := 1;
end;
begin
 Write('N=');
 ReadLn(N);
 L := N;
 for i := 1 to L do
 X[i] := 1;
 for i := 1 to L do
 Write(X[i]);
 WriteLn;
 repeat
 Next(X, L);
 for i := 1 to L do
 Write(X[i]);
 WriteLn;
 until L = 1;
end.
=== Подсчет количеств ===
Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: C(n,k) - число всех k-элементных подмножеств n-элементного множества - можно найти, заполняя таблицу значений функции С по формулам:
 C(n, 0) = C(n, n) = 1 (n >= 1)
 C(n, k) = C(n-1, k-1) + C(n-1, k) (n > 1, 0 < k < n);
или по формуле n! / (k! * (n-k)!) (первый способ эффективнее, если надо вычислить много значений С(n,k)).
Попробуем посчитать таким способом количество разбиений из пункта 1.3. Обозначим через R(N, k) (при N >= 0, k >= 0) число разбиений N на целые положительные слагаемые, не превосходящие k (при этом R(0, k) считаем равным 1 для всех k >= 0). Очевидно, что число R(N, N) и будет искомым. Все разбиения N на слагаемые, не превосходящие k, разобьем на группы в зависимости от максимального слагаемого (обозначим его i).
Число R(N,k) равно сумме (по всем i от 1 до k) количеств разбиений со слагаемыми не больше k и максимальным слагаемым, равным i. А разбиения N на слагаемые не более k с первым слагаемым, равным i, по существу представляют собой разбиения n-i на слагаемые, не превосходящие i (при i<=k). Так что
 R(N,k) = R(N-1, 1) + R(N-2, 2) + ... + R(N-k, k).
Остальное вы сделаете сами в домашнем задании.
== Рекурсия ==
Вы уже знаете, что рекурсивными называются процедуры и функции, которые вызывают сами себя. Рекурсия позволяет очень просто (без использования циклов) программировать вычисление функций, заданных рекуррентно, например факториала f(n) = n!:
 f(0) = 1
 f(n) = n * f(n-1).
Оказывается, рекурсивные процедуры являются удобным способом порождения многих комбинаторных объектов. Мы заново решим здесь несколько задач предыдущей главы и вы убедитесь, что запись многих алгоритмов значительно упростится благодаря использованию рекурсии.
;Примечание сайта: рекурсия, безусловно, весьма удобна, однако часто требует громадное количество ресурсов. В частности, программа для факториала на 7-мом десятке завесит самый быстрый Pentium - III+. Из-за времени выполнения. О том, как этого избежать, можно прочитать в статье Динамическое программирование.
=== Факториал ===
Еще раз напомним рекурсивный алгоритм вычисления факториала:
program Factorial;
var
 N: Word;
function F(n: Word): LongInt;
begin
 if n = 0 then
 F := 1
 else
 F := n*F(n-1)
end;
begin
 Write('N=');
 ReadLn(N);
 WriteLn('N!=', F(N));
end.
=== Ханойская башня ===
Игра "Ханойская башня" состоит в следующем. Есть три стержня. Hа первый из них надета пирамидка из N колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на другой стержень. Разрешается перекладывать кольца со стержня на стержень, но класть большее кольцо поверх меньшего нельзя. Составить программу, указывающую требуемые действия.
Напишем рекурсивную процедуру перемещения M верхних колец с A-го стержня на B-ый в предположении, что остальные кольца больше по размеру и лежат на стержнях без движения:
procedure Move(M, A, B: Integer);
var
 C: Integer;
begin
 if M = 1 then
 begin
 WriteLn('сделать ход ', A, '->', B);
 end
 else
 begin
 C := 6-A-B; { C - третий стержень: сумма номеров равна 6 }
 Move(M-1, A, C);
 Move(1, A, B);
 Move(M-1, C, B);
 end;
end;
Сначала переносится пирамидка из M-1 колец на третий стержень C. После этого M-ое кольцо освобождается, и его можно перенести на B. Остается перенести пирамиду из N-1 кольца с C на B. Чем это проще первоначальной задачи? Тем, что количество колец стало на единицу меньше. Теперь основную программу можно записать в несколько строк:
program Hanoi;
var
 N: Integer;
procedure Move(M, A, B: Integer);
begin
 Write('N=');
 ReadLn(N);
 Move(N, 1, 2);
end.
Если вы владеете основами компьютерной графики, можете попробовать "нарисовать" каждый ход на экране.
Таким образом, ОСНОВНАЯ ИДЕЯ любого рекурсивного решения - свести задачу к точно такой же, но с меньшим значением параметра. При этом какое-то минимальное значение параметра (например, 1 или 0) должно давать решение без рекурсивного вызова - иначе программа "зациклится" (последовательность рекурсивных вызовов будет бесконечной). Это напоминает метод математической индукции в математике. В некоторых задачах удобно наоборот, увеличивать значение параметра при рекурсивном вызове. Тогда, естественно, "безрекурсивное" решение должно предусматриваться для некоторого максимального значения параметра. Попробуем использовать эту идею для перебора комбинаторных объектов.
=== Последовательности (рекурсивный алгоритм) ===
Задача та же, что в пункте 1.1. Опишем рекурсивную процедуру Generate(k), предъявляющую все последовательности длины N из чисел 1, ..., M, у которых фиксировано начало X[1], X[2], ..., X[k]. Понятно, что при k=N мы имеем тривиальное решение: есть только одна такая последовательность - это она сама. При k < N будем сводить задачу к k+1:
procedure Generate(k: Byte);
var
 i, j: Byte;
begin
 if k = N then
 begin
 for i := 1 to N do
 Write(X[i]);
 WriteLn;
 end
 else
 for j := 1 to M do
 begin
 X[k+1] := j;
 Generate(k+1);
 end;
end;
Основная программа теперь выглядит очень просто:
program SequencesRecursion;
type
 Sequence = array [Byte] of Byte;
var
 M, N: Byte;
 X: Sequence;
procedure Generate(k: Byte);
begin
 Write('M, N=');
 Readln(M, N);
 Generate(0);
end.
=== Перестановки (рекурсивный алгоритм) ===
Задача та же, что в пункте 1.2. Опишем рекурсивную процедуру Generate(k), предъявляющую все перестановки чисел 1, ..., N, у которых фиксировано начало X[1], X[2], ..., X[k]. После выхода из процедуры массив X будут иметь то же значение, что перед входом (это существенно!). Понятно, что при k = N мы снова имеем только тривиальное решение - саму перестановку. При k < N будем сводить задачу к k+1:
procedure Generate(k: Byte);
var
 i, j: Byte;
 procedure Swap(var a, b: Byte);
 var
 c: Byte;
 begin
 c := a;
 a := b;
 b := c;
 end;
begin
 if k = N then
 begin
 for i := 1 to N do
 Write(X[i]);
 WriteLn;
 end
 else
 for j := k+1 to N do
 begin
 Swap(X[k+1], X[j]);
 Generate(k+1);
 Swap(X[k+1], X[j]);
 end;
end;
Основная программа:
program PerestanovkiRecursion;
type
 Pere = array [Byte] of Byte;
var
 N, i, j: Byte;
 X: Pere;
procedure Generate(k: Byte);
begin
 Write('N=');
 ReadLn(N);
 for i := 1 to N do
 X[i] := i;
 Generate(0);
end.
Чтобы до конца разобраться в этой непростой программе, советуем выполнить ее на бумаге при N=3. Обратите внимание, что порядок вывода перестановок не будет лексикографическим!
== Перебор с отходом назад ==
Как вы уже поняли, перебор комбинаторных объектов - задача весьма трудоемкая даже для компьютера. Например, перестановок из восьми чисел будет 8! = 40320 - число немаленькое. Поэтому в любой переборной задаче главная цель состоит в СОКРАЩЕНИИ ПЕРЕБОРА, т.е. в исключении тех объектов, которые заведомо не могут стать решением задачи. Предположим, что нам требуется рассмотреть только те перестановки, для которых сумма |X[i]-i| равна 8. Понятно, что их будет гораздо меньше: например, все перестановки, начинающиеся на 8,7,... рассматривать не нужно! Как можно модифицировать наш переборный алгоритм в этом случае? Если на каком-то этапе сумма
 |X[1]-1| + |X[2]-2| + ... + |X[k]-k|
уже больше 8, то рассматривать все перестановки, начинающиеся на X[1], ..., X[k] уже не нужно - следует вернуться к X[k] и изменить его значение ("отойти назад" - отсюда название метода).
Для такой ситуации мы рассмотрим один общий метод, который почти всегда позволяет значительно сократить перебор. Пусть искомое решение находится среди последовательностей вида
 X[1], ..., X[N],
где каждое X[i] выбирается из некоторого множества вариантов A[i]. Предположим мы уже построили начало этой последовательности X[1], ..., X[k] (k < N) и хотим продолжить его до решения.
Предположим также, что у нас есть некоторый простой метод P(X[1], ..., X[k]), который позволяет получить ответ на вопрос: можно продолжить X[1], ..., X[k] до решения (True) или нет (False). Заметим, что значение True еще НЕ ГАРАНТИРУЕТ существование такого продолжения, но зато значение False ГАРАНТИРУЕТ непродолжаемость ("не стоит дальше и пробовать"). Получаем простую рекурсивную процедуру ПЕРЕБОРА С ОТХОДОМ НАЗАД:
procedure Backtracking(k);
begin
 for (y in A[k]) do
 begin
 if P(X[1], ..., X[k-1], y) then
 begin
 X[k] := y;
 if k = N then
 { X[1], ..., X[N] - решение }
 Backtracking(k+1)
 end;
 end;
end;
Author: Булычев В.А.
Source: http://algolist.manual.ru
ID: 04195
Category:Алгоритмы