1 2
Понятие комбинаторной задачи
   Сначала мы приведём довольно общие рассуждения, которые имеют отношение к решению произвольных нетривиальных (или как их называют в узком смысле - "олимпиадных") задач, а потом переходим к непосредственному разбору конкретных комбинаторных задач, используя введённые понятия.
Процесс решения задачи
  Существенным отличием задач, рассматриваемых при изучении информатики и математики, является то, что они "полностью определены", т.е. четко описаны на подходящем языке. Чаще всего это язык математики. Задачи, с которыми мы сталкиваемся в реальной жизни, не являются полностью определёнными. Чаще всего они описаны на естественном языке, который с точки зрения формального описания обладает четырьмя недостатками: он неполон, избыточен, неоднозначен и неточен.
   Поставить задачу означает прежде всего понять условие задачи (т.е. удалить неполноту, избыточность и неоднозначность) или, другими словами, найти соответствующее представление. На самом деле задача понята только тогда, когда найдено такое представление, в котором все элементы задачи представлены без избыточности и многозначности. Условие задачи при этом записываются в формализованном виде. Задача становится одновременно и более абстрактной и более строгой. В этом случае говорят о задаче в замкнутой форме или о замкнутой формулировке задачи.
   С математической точки зрения можно предложить такой общий шаблон для задачи в замкнутой форме: Найти в заданном множестве X элементы х, удовлетворяющие заданным ограничениям К(х). Примером такой задачи может служить задача решения уравнения:1 из множества натуральных чисел jc выбрать такие числа, которые удовлетворяют уравнению                 .
   Для одной и той же задачи всегда можно привести несколько разных замкнутых формулировок. Не всегда при этом есть одна наиболее "естественная" формулировка. (Слово "естественная" в данном случае надо понимать не как "напрашивающаяся", а скорее как "наиболее простая".) Если даже такая формулировка одна, не всегда просто её" найти. Иногда нахождение такой формулировки - основное в решении задачи.
    Подход человека к решению задачи включает следующие основные этапы:
1. Выяснение смысла условий задачи.
2. Первые выводы из условий задачи.
3. Проигрывание ситуации, обдумывание.
4. Выбор наилучшего представления - поиск замкнутой формулировки задачи.
5. Частичное (возврат к пункту 2) или общее решение.
6. Проверка и обобщение решения.
Понятие комбинаторной задачи
   Понятие комбинаторной задачи не имеет строгого определения. Иногда говорят о комбинаторных задачах в достаточно узком смысле слова, имея в виду практические задачи, при решении которых возникают проблемы с большим (и часто неприемлемым) количеством операций (а, значит, и времени). Мы будем иметь дело с учебными задачами и нам ближе следующий подход.
   Задачу имеет смысл называть комбинаторной, если ее решение состоит в переборе элементов х множества X. (При этом наравне с термином "комбинаторная" вполне подходит термин "переборная".) Как видим, такое определение описывает не саму задачу, а скорее её решение. Ведь, подходя формально, любую задачу можно пытаться решать таким методом. Надо заметить, что никакого парадокса здесь нет. Действительно, очень большое количество реальных задач - задачи переборные и только для некоторых найдены способы избегать перебора.
Пространство перебора
    Итак, предположим, мы решаем задачу с помощью перебора. При этом решение будет состоять в переборе элементов множества X и проверке условий К(х) для каждого такого элемента. Множество Х в данном случае называется пространством перебора. Для полного решения задачи необходимо выполнить по крайней мере |X|·|K| шагов (не считая шагов, необходимых для порождения элементов множества X), где |Х| - количество элементов множества Х, а |К|- количество шагов, необходимых для проверки одного элемента. Понятно, что размер множества X очень важен для эффективного решения задачи. Часто множество X является декартовым произведением множеств Х1,...,Хn (т.е. состоит из наборов элементов (х1,...,хn), где xi принадлежит Xi). При этом сократив множество перебора для каждого Xi в два раза, мы сократим общий объём перебора в    раз.
  Таким образом, очень важно получить замкнутую формулировку с небольшим пространством перебора. И совершенно неприемлемы формулировки с бесконечным пространством перебора. Иногда, переходя от формулировки к формулировке и сокращая перебор, удаётся полностью его избежать и решить задачу "прямым" методом.
Как избежать перебора
    При решении нестандартных задач невозможно дать конкретный рецепт для того, как сократить перебор или вообще его избежать. Единственное, что можно определенно сказать - это то, что сократить перебор - значит, по-существу, получить новую замкнутую формулировку задачи.
     Рассмотрим лучше конкретный пример. На нём мы проследим этапы решения задачи.
   Задача 1. Пусть имеется шахматная доска, каждая сторона которой содержит 100 клеток. Все 10000 полей доски заняты чёрными шашками. Разрешёнными ходами являются операции замены в каком-то ряду (строке или столбце) всех шашек чёрного цвета на белые и белых на чёрные. Спрашивается, можно ли за конечное число ходов получить 1990 белых шашек?
  Первой, непосредственной замкнутой формулировкой может быть поиск последовательности ходов. Каждый ход задаётся указанием того, со строкой или столбцом производится замена цвета и номером строки или столбца. Но такая формулировка совершенно непригодна для проведения перебора, так как пространство перебора бесконечно.
1 2
Закрыть