Переборные задачи
На практике неоднократно встречаются задачи, где требуется обработать (перебрать) все элементы некоторого конечного множества. В простейших случаях элемент множества можно представить числом. Пример такой задачи — поиск заданного числа в одномерном массиве. Здесь для указания элемента массива достаточно задать его индекс.
Более сложные случаи, когда элементы интересующего нас множества сами имеют некоторую структуру. (Именно такие задачи обычно относят к переборным.) Во многих случаях элементы множества естественно записывать в виде последовательности чисел фиксированного или переменного размера. Очень многие переборные задачи можно свести к перебору последовательностей.
В некоторых задачах (см. например, задачу о коммивояжере в главе 1) требуется генерировать последовательности путем всевозможных перестановок компонент некоторой заданной последовательности фиксированной длины. Правила генерации последовательностей могут меняться в зависимости от задачи:
· случайным образом,
· в лексикографическом порядке,
· путем различных сочетаний компонент
· и т. п.
Примером такой задачи (в действительности она эквивалентна задаче перебора последовательностей) является задача прохождения (обхода) деревьев. Дерево — это граф без циклов, в котором выделена одна вершина, называемая корнем. Для каждой вершины дерева существует единственный путь в нее из корня. Задача состоит в том, чтобы «обойти» все вершины дерева. Если перенумеровать все ребра, выходящие из каждой вершины, то путь из корня, однозначно сопоставляемый каждой вершине, можно будет в свою очередь задать с помощью последовательности номеров проходимых ребер. Лексикографический порядок перебора последовательностей отвечает способу прохождения дерева, известному как перебор в глубину. Находясь в какой-либо вершине, мы сначала пытаемся пойти «в глубину», т. е. удалиться от корня; если это невозможно, то мы возвращаемся назад и пытаемся пойти в глубину по следующему ребру.
Многие практические задачи сводятся к отысканию минимума (максимума) некоторой функции на множестве. Искомым элементом множества часто является функция от времени (например, ищется закон управления самолетом, обеспечивающий наибыстрейшее достижение заданной высоты и скорости). Эту функцию аппроксимируют последовательностью ее значений в дискретные моменты времени, получая задачу поиска минимума в множестве последовательностей. Можно осуществить поиск минимума путем полного перебора всех допустимых последовательностей. Метод динамического программирования позволяет в ряде случаев сократить перебор. Рассмотрим несколько типичных примеров генерации последовательностей и работы с ними при решении переборных задач.
Полный перебор.
Во многих прикладных задачах требуется найти оптимальное решение среди очень большого (но конечного!) числа вариантов. Иногда удается построить это решение сразу, но в большинстве случаев единственный способ его отыскать состоит в переборе всех возможных вариантов и сравнении их между собой.
Для решения переборных задач обычно используются разновидности следующей схемы программы:
Схема 1
Var x:элемент множества;
x:= первый элемент;
обработать x;
While x<> последний элемент Do Begin
x: =следующий за x;
обработать x;
End;
Иногда удается добавить к множеству еще один, фиктивный элемент, не подлежащий обработке, который располагается перед первым обрабатываемым элементом, либо вслед за последним В этом случае обработку первого элемента можно выполнить наряду со всеми в цикле:
Схема 2 Схема 3
x:=фиктивный элемент; x:=первый элемент;
Repeat Repeat
x:=следующий за x; обработать x;
обработать x; x:=следующий за x;
Until x = последний элемент; Until x = фиктивный элемент;
Для конкретизации этих схем необходимо ответить на два вопроса.
1. Как будут записываться в программе элементы множества
(тип элемент множества)?
2. В каком порядке мы будем перебирать их (инструкция x:=следующий за x;)?
Рассмотрим пример. Подсчитать число счастливых билетов, т. е. таких наборов из шести цифр А,B,C,D,E,F, что A+B+C=D+E+F. Будем решать задачу путем перебора всех комбинаций из шести цифр (это решение далеко не самое эффективное). Таким образом, элемент множества задается последовательно из шести цифр, каждая из которых принимает значения от 0 до 9. Для хранения этой последовательности используем шесть отдельных переменных. В данном случае можно, не следуя буквально введенным выше схемам, организовать перебор с помощью шести вложенных циклов FOR:
Program Happy_Ticket;
Var A,B,C,D,E,F,k:Integer; { k – число найденных счастливых билетов}
Begin
k:=0;
For A:=0 To 9 Do
For B:=0 To 9 Do
For C:=0 To 9 Do
For D:=0 To 9 Do
For E:=0 To 9 Do
For F:=0 To 9 Do
If A+B+C = D+E+F Then k:=k+1;
Writeln(‘ЧИСЛО СЧАСТЛИВЫХ БИЛЕТОВ=’,k);
End.
Кстати сказать, счастливых билетов 55252 (если считать и 000000), что составляет примерно 1/18 общего числа билетов.
Последовательности.
Важно научиться строить алгоритмы перебора различных комбинаторных объектов - последовательностей, перестановок, подмножеств и т.д.
Схема перебора всегда будет одинакова:
· во-первых, надо установить порядок на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);
· во-вторых, научиться переходить от произвольного элемента к непосредственно следующему за ним (т.е. для заданного элемента x1 строить такой элемент x2, что x1<x2 и между x1 и x2 нет других элементов).
Hаиболее естественным способом упорядочения составных объектов является лексикографический порядок, принятый в любом словаре (сначала сравниваются первые буквы слов, потом вторые и т.д.) - именно его мы и будем чаще всего использовать. А вот процедуру получения следующего элемента придется каждый раз изобретать заново. Пока запишем схему перебора в таком виде:
x:=First;
While x<>Last Do Next(x);
где First - первый элемент; Last - последний элемент; Next - процедура получения следующего элемента.
Hапечатать все последовательности длины N из чисел 1,2,...,M.
First = (1,1,...,1), Last = (M,M,...,M).
Всего таких последовательностей будет MN. Чтобы понять. как должна действовать процедура 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 Posled;
Const N=4; M=3;
Var x:Array[1..N] Of Byte; i:Byte;
Procedure PrintX;
Var i:Byte;
Begin
For i:=1 To N Do Write(X[i]);
Writeln;
End;
Function Next:Boolean;
Var i:Byte;
Begin
i:=N;
While (i>0) And (x[ i ] = M) Do Begin
x[ i ]:=1;
Dec(i)
End;
If i>0 Then Begin Inc(x[ i ]); Next:=True; End
Else Next:=False;
End;
Begin
For i:=1 To N Do X[ i ]:=1;
PrintX;
While Next Do PrintX;
End.
Опишем рекурсивную процедуру GPosl(k), генерирующую все последовательности длины N из чисел 1,...,M, у которых фиксировано начало X[1],X[2],...,X[k]. Понятно, что при k=N мы имеем тривиальное решение: есть только одна такая последовательность - это она сама. При k<N будем сводить задачу к k+1:
Procedure GPosl (k:Byte);
Var i, j:Byte;
Begin
If k=N Then PrintX(N)
Else For i:=1 To M Do Begin
X[k+1]:=i;
GPosl(k+1);
End;
End;
Вызов: …. GPosl(0); ….
Перестановки
Hапечатать все перестановки чисел 1..N (то есть последовательности длины N, в которые каждое из чисел 1..N входит ровно по одному разу).
First = (1,2,...,N); Last = (N,N-1,...,1).
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 3 4
{ для примера} 1 2 5 4 3 -> 1 3 5 4 2 -> 1 3 2 4 5
1 3 2 4 5
1 3 2 5 4
Всего таких перестановок будет N!. Для составления алгоритма 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;
Теперь можно написать программу:
Procedure Next (Var p:boolean);
Var i, j:Byte;
Begin
i:=N-1;
While (i>0) And (X[ i ] > X[i+1]) Do Dec(i); {найти i}
If i>0
Then Begin
j:=i+1;
While (j<N) And (X[ j+1] > X[ i ]) Do Inc(j); {найти j}
Swap(X[ i ],X[ j ]); {обменять X[i] и X[j]};
For j:=i+1 To (N+i) Div 2 Do Swap(X[ j ], X[ N – j + i + 1]); {перевернуть};
p:=True;
E nd
Else p:=False;
End;
Begin
For i:=1 to N do X[ i ]:=i;
Repeat
PrintX; Next(p);
Until Not p;
End;
Перестановки (рекурсивный алгоритм)
Генератор перестановок. Перестановкой порядка п называется расположение п различных объектов в ряд. Для трех объектов а, b, с имеется шесть перестановок:
abc, acb, bac, bca, cab, cba. (1)
Задача та же, что в пункте 7.2. Опишем рекурсивную процедуру GPrst(k), предъявляющую все перестановки чисел 1,...,N, у которых фиксировано начало X[1],X[2],...,X[k]. После выхода из процедуры массив X будут иметь то же значение, что перед входом (это существенно!). Понятно, что при k=N мы снова имеем только тривиальное решение - саму перестановку. При k<N будем сводить задачу к k+1:
Procedure GPrst (k:byte);
Var i:byte;
Begin
If k=N Then PrintX
Else For i:=k+1 to N do Begin
Swap(x[k+1], x[i]);
GPrst(k+1);
Swap(x[k+1], x[i]);
End;
End;
Begin
For i:=1 to N do X[ i ]:=i;
GPrst(0);
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). Программа будет выглядеть так:
1 1 1 1 1
2 1 1 1 {для примера}
2 2 1
3 1 1
3 2
4 1
Function Min(a,b:Integer):Integer; {только для рекурсивной реализации}
Begin If a<b Then Min:=a Else Min:=b; End;
Procedure PrintX(L:Byte);
Var i:Integer;
Begin For i:=1 To L D o write(X[i]); writeln; End;
Procedure Next(Var L:byte);
Var i, j, s:Integer;
Begin
i:=L-1; s:=x[L];
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
For i:=1 to N do X[i]:=1;
PrintX(N);
L:=N;
Repeat
Next(L);
PrintX(L);
Until L=1;
End.
Рекурсивный вариант генератора разбиений:
Procedure GRzb(s,L:Integer);
Var i: Byte;
Begin
If s = n Then PrintX(L)
Else For i:=1 To Min(x[L], n-s) Do Begin
x[L+1]:=i;
GRzb(s+i,L+1);
End;
End;
Вызов: …. x[0]:=n; GRzb(0,0); ….