Олимпиадные задачи
по информатике
Главная страница
Правила участия и регистрация
О тестировании
Архив задач
Полезные ссылки
Download
Отправить решение
Текущие результаты
Задать вопрос на форуме
О жюри
Переборные алгоритмы
Задачи на эту тему.
Понятие комбинаторной задачи

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

1.1 Процесс решения задачи

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

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

С математической точки зрения можно предложить такой общий шаблон для задачи в замкнутой форме: Найти в заданном множестве X элементы x, удовлетворяющие заданным ограничениям K(x). Примером такой задачи может служить задача решения уравнения: ``из множества натуральных чисел x выбрать такие числа, которые удовлетворяют уравнению x3+84=37x2

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

Подход человека к решению задачи включает следующие основные этапы:

1. Выяснение смысла условий задачи.

2. Первые выводы из условий задачи.

3 .Проигрывание ситуации, обдумывание.

4 .Выбор наилучшего представления – поиск замкнутой формулировки задачи.

5 .Частичное (возврат к пункту 2) или общее решение.

6 .Проверка и обобщение решения.

1.2 Понятие комбинаторной задачи

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

Задачу имеет смысл называть комбинаторной, если ее решение состоит в переборе элементов x множества X. (При этом наравне с термином ``комбинаторная'' вполне подходит термин ``переборная''.) Как видим, такое определение описывает не саму задачу, а скорее её решение. Ведь, подходя формально, любую задачу можно пытаться решать таким методом. Надо заметить, что никакого парадокса здесь нет. Действительно, очень большое количество реальных задач – задачи переборные и только для некоторых найдены способы избегать перебора.

1.3 Пространство перебора

Итак, предположим, мы решаем задачу с помощью перебора. При этом решение будет состоять в переборе элементов множества X и проверке условий K(x) для каждого такого элемента. Множество X в данном случае называется пространством перебора. Для полного решения задачи необходимо выполнить по крайней мере |X|·|K| шагов (не считая шагов, необходимых для порождения элементов множества X), где |X| – количество элементов множества X, а |K| – количество шагов, необходимых для проверки одного элемента. Понятно, что размер множества X очень важен для эффективного решения задачи. Часто множество X является декартовым произведением множеств X1,...,Xn (т.е. состоит из наборов элементов (x1,...,xn), где xiОXi). При этом сократив множество перебора для каждого Xi в два раза, мы сократим общий объём перебора в 2n раз.

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

1.4 Как избежать перебора

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

Рассмотрим лучше конкретный пример. На нём мы проследим этапы решения задачи.

Задача 1

Пусть имеется шахматная доска, каждая сторона которой содержит 100 клеток. Все 10000 полей доски заняты чёрными шашками. Разрешёнными ходами являются операции замены в каком-то ряду (строке или столбце) всех шашек чёрного цвета на белые и белых на чёрные. Спрашивается, можно ли за конечное число ходов получить 1990 белых шашек?

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

Если проиграть ситуацию (возможно мысленно) на модели доски (например, размером 4 ґ 4), появляются следующие заключения:

1. Если дважды подряд заменяют цвет у одного и того же ряда, позиция не меняется.

2. Пусть мы хотим сделать два хода (a и b). От того, какой ход мы сделаем первым, а какой – вторым, результат не зависит. Это определяется тем, что разные строки, как и столбцы, не имеют между собой общих шашек. У пересекающихся строки и столбца – только одна общая шашка, которая при любом порядке ходов в результате вернется к исходному цвету.

3. На основании двух первых заключений можно сделать вывод, что порядок ходов не является существенным и, кроме того, результирующее состояние ряда то же при 2n+k ходах, что и при k ходах. Таким образом, пространство перебора сокращается: надо перебирать всевозможные множества строк и столбцов с которыми будет проведена замена цвета. Таких множеств уже конечное число, хотя всё же ещё очень много - 220000.

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

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

Число строк L в верхних и число столбцов C в левых прямоугольниках соответствуют рядам шашек, модифицированных один раз.

Таким образом, пространство перебора ещё более сокращается: надо перебирать всевозможные пары (L,C). Объем пространства перебора уже вполне приемлемый – 10000.

6. Представленная на доске позиция обладает симметрией относительно строк и столбцов. Если (L,C) – решение задачи, то и (C,L) также будет решением.

7. Рассматриваемая позиция обладает ещё и центральной симметрией. Если (L,C) – решение задачи, то и (100-C,100-L) также будет решением. Теперь пространство перебора можно задать как пары (L,C), в которых L <= C, L <= 100-C и его объём – 2100.

Однако на этом мы не остановимся, а продолжим изучение задачи. Запишем замкнутую формулировку. Число белых шашек составляет: вверху — Lx(100-C) и внизу — Cx(100-L). В результате условие, которой должна удовлетворять искомая пара можно записать в виде: 100(L+C)-2LC=1990 Становится очевидным, что достаточно перебирать только первый элемент пары — L, а C вычислять по формуле C=(1990-100L)/(100-2L) и проверять на приемлемость. Таким образом, пространство перебора сокращается до 50 элементов.

(L+C)-LC=n Сделаем замену переменных L=l+p, C=c+p. Получим уравнение lc=p2-n Целое число, стоящее справа, известно. Это 50x50 - 1990/2=1505. Для существования решения необходимо, чтобы число 1505 было разложимо на множители, сопоставимые с размерами доски. 1505=5x7x43, а так как p=50, то -50 <= l <= 50, -50 <= c <= 50. В данном случае имеется решение, удовлетворяющие этим условиям: l=5x7, c=43, L=85, C=93 (или симметричное ему l=-5x7, c=-43, L=15, C=7). Таким образом, имеется вариант получения на доске 1990 белых шашек.

Если при решении задачи удается полностью избежать перебора – то такую задачу, в точном смысле слова, нельзя назвать комбинаторной. Можно только говорить, что она сформулирована в комбинаторной форме. Собственно же комбинаторные задачи не позволяют полностью устранить перебор. Поэтому на первый план выдвигается проблема сокращения перебора.

Сокращение перебора

Если при решении задачи удается полностью избежать перебора – то такую задачу, в точном смысле слова, нельзя назвать комбинаторной. Можно только говорить, что она сформулирована в комбинаторной форме. Собственно же комбинаторные задачи не позволяют полностью устранить перебор. Поэтому на первый план выдвигается проблема сокращения перебора.

2.1 Отсечение лишних вариантов

Первый принцип при таком подходе предельно прост – не рассматривать те варианты, которые не могут дать решение задачи. Как правило, большую часть таких вариантов можно избежать, организовав перебор соответствующим образом. Часто ``лишние'' варианты не продиктованы смыслом задачи, а возникают из-за способа организации перебора. Действительно, часто используемый способ получения простых формулировок – грубо (``с запасом'') описывает пространство решений задачи. При этом структура алгоритма поиска решения становится наиболее простой – как правило, это вложенные циклы. Но ценой этому – расширение пространства перебора. Пространство перебора может быть излишне расширено и просто из-за неподходящей, неумело подобранной формулировки. Так, переходя в разобранной задаче о шашках от первой формулировки к последующим, мы посуществу убирали из рассмотрения лишние варианты (например, варианты, содержащие два одинаковых хода подряд). Сейчас же остановимся на случае, когда пространство перебора уже не удаётся сократить принципиально – получив новую формулировку, но можно исключать отдельные элементы.

Рассмотрим задачу о расстановке n ферзей.

На шахматной доске размером nxn требуется расставить n ферзей, так, чтобы они не били друг друга.

Построим замкнутую формулировку этой задачи. Позицию будем записывать в виде набора, состоящего из координат x, y всех ферзей. Условие xi<>xj (yi<>yj) означает то, что i-ый и j-ый ферзи стоят на разных вертикалях (горизонталях). Условия xi+yi<>xj+yj и xi-yi<>xj-yj означают что i-ый и j-ый ферзи не стоят на одной диагонали. Получаем следующую замкнутую формулировку: Найти набор (x1, y1, x2, y2,..., xn, yn), xi, yiО{1,...,n}, такой что: xixj, yiyj, xi+yixj+yj, xi-yixj-yj для всех i, jО{1,...,n}. Заметим, что среди координат x ферзей x1,x2,...,xn ровно один раз встречается каждое из чисел 1, 2, ..., n. Таким образом, достаточно перебирать только координаты y. Номера же ферзей можно рассматривать как координаты x. Итак, переформулируем задачу: Найти набор (y1, y2, ..., yn), yiо{1,...,n}, такой что: yiyj, i+yij+yj, i-yij-yj для всех i, jО{1,...,n}.

Нарисуем пространство для n=3 (это слишком небольшое число для данной задачи и в этом случае вообще нет решения, но нам важно понять, что представляет из себя пространство перебора). Пространство перебора – множество {(y1, y2, y3) : y1, y2, y3О{1, 2, 3}}. На рисунке элементы пространства перебора отмечены точками.

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

Таким образом, пространство перебора всегда – параллелепипед. (В общем случае – множество наборов {(y1,...,yn) : y1ОY1, ynОY}, Y1, ..., YnНY.) Такое пространство можно задать, задав множества Y1, ..., Yn. В нашем случае это означает, что мы должны указать, какие значения разрешены для каждого из ферзей. Так мы приходим к компактному представлению пространства перебора, с которым и будем работать в дальнейшем

На рисунках 4, 5, 6 показаны те же пространства перебора, что и на рисунках 1, 2, 3 соответственно. Там, где значение для ферзя запрещено - квадрат изображён чёрным цветом, где разрешено – белым. В дальнейшем мы будем вертикали, соответствующие ферзям изображать вплотную (у нас получится шахматная доска).

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

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

for i1 := 1  to n  do begin
      ферзь[1] := i1;
      for i2 := 1  to n  do begin
          ферзь[2] := i2;
          for i3 := 1  to n  do begin
             ферзь[3] := i3;
             ...
             ...  <проверка построенной позиции>
          end;
      end;
 end;
Проследим, какими будут первые полностью построенные позиции при приведённом алгоритме. Сначала будет рассмотрен вариант, когда все ферзи занимают положение 1, потом последний ферзь займёт положение 2 и т.д. Но постойте! Ведь уже когда первый ферзь занимает положение 1, то все позиции, в которых второй ферзь занимает положение 1 или 2 будут заведомо неприемлемы. Т.о. первые 2 · nn-2 вариантов будут рассмотрены впустую. Но ведь это можно было заметить уже при расстановке второго ферзя.

Иначе говоря, из пространства перебора заведомо можно удалить варианты, когда второй ферзь занимает положение 1 или 2. Для случая n=3 сокращённое пространство перебора показано на рис.3.

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

for i1 := 1  to n  do begin
    ферзь[1] := i1;
    for i2 := 1  to n  do begin
       ферзь[2] := i2;
              { проверка частично построенной позиции }
       if <ферзь[2] не бьёт ферзь[1]>  then
          for i3 := 1  to n  do begin
              ферзь[3] := i3;
                     { проверка частично построенной позиции }
              if <ферзь[3] не бьёт предыдущих>  then
                  for i4 := 1  to n  do begin
                      ...
                      if <ферзь[n] не бьёт предыдущих>  then
                            <решение найдено>
                  end;
          end;
    end;
 end;
Понятно, что очень важно отсечь ненужные варианты на наиболее ранних этапах перебора. При этом мы посуществу отсекаем сразу группу "лишних'' вариантов. При сокращении пространства перебора надо иметь в виду насколько сокращается пространство и соотносить размер этого сокращения с затратами на его реализацию. Если размер сокращения не велик по сравнению с общим объёмом перебора, то обычно не стоит ``городить огород'' и реализовывать такое сокращение, так как затраты на выполнение более сложной схемы перебора могут ``съесть'' весь выигрыш от сокращения. Кроме того, каждое усложнение алгоритма – лишняя возможность сделать ошибку.

2.2 Использование симметрии

Приём использования симметрии дал возможность в задаче о шашках несколько раз переформулировать задачу и предельно сократить пространство перебора. Действительно, сначала мы использовали симметрию различных последовательностей одних и тех же ходов, потом симметрию различных строк (столбцов) доски, потом центральную симметрию и поворот на 90°.

Симметрию часто удаётся использовать и в процессе перебора (а не только при переформулировке задачи). Так например, в задаче о ферзях за счёт симметрии можно считать, что первый ферзь находится на нижней половине доски. Это сократит перебор в два раза. Очень сильно сокращается перебор за счёт симметрии в рассматриваемой в следующем разделе задаче о раскраске карты.

2.3 Группирование элементов

Часто при проверке перебираемых вариантов многие операции повторяются для разных элементов пространства перебора. Напрашивается следующая идея оптимизации: выполнять эти операции сразу для групп элементов. Причём чем больше группы, тем лучше. Посуществу, сокращение пространства перебора в последнем рассмотренном варианте задачи о ферзях осуществляется как раз за счёт отсечения сразу группы элементов. Кроме того, позиция тоже строится не для каждого варианта с самого начала, а насколько это возможно сразу для групп вариантов. Это делают операторы ферзь[1] := i1; ... , которые выдвинуты на максимально верхний уровень.

В результате группирования алгоритм может существенно измениться. Выразительные примеры (5 и 6) приведены в следующем разделе.

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

Дальше
Сайт управляется системой uCoz