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

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

Комбинаторную задачу с фиксированной размерностьюопределим следующим образом.

Даны nконечных множествU₁, U₂, ... U_n(множества значений переменных) и множество значений параметров (исходных данных задачи)P(не обязательно конечное). Задана такжефункция ограниченийG(X, p) = G(x₁, x₂, ... x_n, p) ® (0, 1), описывающая область допустимых значений переменныхx₁, x₂, ... x_nпри значении параметраp Î P.

Требуется для заданных исходных данных p Î Pпостроить ... (далее возможна одна из трех постановок задачи):

A)любой набор значенийx₁, x₂, ... x_n, такой, чтоG(X, p) = 1(задача поиска);

B)все наборы значенийx₁, x₂, ... x_n, такие, чтоG(X, p) = 1(задача перечисления);

C)такой набор значенийx₁, x₂, ... x_n, чтоG(X, p) = 1и заданнаяцелевая функцияF(X, p)принимает минимальное значение (задача оптимизации).

Наборы значений переменных X = x₁, x₂, ... x_nпринято называтьпланамиданной задачи¹; те планы, для которыхG(X, p) = 1, называютсядопустимыми планами. Набор значений, в котором определены только некоторые компонентыx_i, называетсячастичным планомзадачи.

В этой терминологии задачи A, B, C можно сформулировать лаконичнее:

A)найти любой допустимый план;

B)перечислить все допустимые планы;

C)найти оптимальный план.

Следует пояснить, что функции G(X, p)иF(X, p)вовсе не обязательно заданы в виде формул. Часто множество допустимых планов задается алгоритмически, т.е. с помощью набора некоторых правил, позволяющих определить, является ли данный план допустимым.

Комбинаторная задача с нефиксированной размерностьюотличается тем, что величинаn(длина плана) заранее неизвестна и может быть различной для разных планов одной и той же задачи. Для таких задач план строится, начиная сx₁, и после выбора значения каждой очереднойx_kпо определенным правилам определяется, получен ли уже полный план задачи или требуется определение следующей переменнойx_k+1. В то же время требуется, чтобы число шагов было заведомо конечно.

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

1.3. Примеры комбинаторных задач

1.3.1. Задача о коммивояжере.Дана матрицаL = {l_ij}размеромnn– матрица расстояний между городами. Требуется построить кратчайший замкнутый маршрут, проходящий ровно по одному разу через каждый город.

Это задача оптимизации с фиксированной размерностью. Элемент плана x_iможно понимать как номер города, в который нужно ехать наi-том шаге, либо как номер города, в который нужно ехать изi-того города. Исходные данныеpзаданы в виде матрицыL. Функция ограничений задана неявно, в виде требований замкнутости маршрута и однократного посещения каждого города. Роль целевой функции играет длина маршрута. Задача решается достаточно трудно, далее будет рассмотрен один из алгоритмов решения.

Подобно многим другим математическим задачам, задача о коммивояжере допускает множество разных содержательных интерпретаций. Например, «расстояние» может также пониматься как стоимость или время, а «города» – как точки на электронной схеме или станции перекачки нефти. Матрица расстояний не обязана быть симметричной (т.е. расстояние от AдоBможет не совпадать с расстоянием отBдоA).

1.3.2. Задача о кратчайшем пути в графе.Дан графG = (V,E)и матрица длин реберL. Заданы также две вершиныAиB. Требуется найти кратчайший путь изAвB.

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

1.3.3. Задача о длиннейшем пути в графе.В условиях предыдущей задачи требуется найти самый длинный путь изAвB, не образующий циклов.

Как ни странно, эта задача, в отличие от предыдущей, весьма сложна для решения.

1.3.4. Задача о рюкзаке.Имеетсяnнаименований товара, причем товар дискретный (его можно отмерять только целыми единицами, как телевизоры или книги, а не вещественным количеством, как сахар или ткань). Заданы объемы единиц каждого товараb_iи их стоимостьc_i. Имеется рюкзак объемаB. Требуется подобрать набор товаров, вмещающийся в рюкзак и имеющий при этом максимальную стоимость. Более формально: требуется максимизировать функциюF(X) = c_ix_iпри ограниченияхG(X) = b_ix_i  Bиx_i  0, гдеi = 1…n.

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

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

1.3.5. Задача о многопроцессорном расписании. Даныmодинаковых процессоров иnнезависимых задач, каждая из которых может решаться на любом процессоре. Время решения каждой задачи равноt_i,i = 1…n. Как распределить задачи по процессорам таким образом, чтобы выполнение всех задач было завершено в кратчайший срок?

В другой интерпретации это задача о куче камней: требуется так разложитьnкамней с весамиt_iнаmкуч, чтобы вес самой тяжелой кучи был минимален.

1.3.6. Задача о раскраске графа.Дан неориентированный графG = (V,E). Требуется каждой вершине графа сопоставить целое число (номер цвета) таким образом, чтобы никакие две смежные вершины не были одного цвета и при этом число использованных цветов было минимально.

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

Широко известен вариант задачи о раскраске, в котором задано, что граф планарный (т.е. может быть нарисован на плоскости без пересечений ребер). По-другому это формулируется как задача раскраски карты (никакие две страны, имеющие общий отрезок границы, не должны быть одного цвета). С конца XIXвека было известно, что для любой карты достаточно использовать 5 цветов, однако только в 80-х годахXXвека удалось доказать, что всегда можно обойтись 4 цветами.

1.3.7. Задача о тождественной истинности ДНФ.Дана дизъюнктивная нормальная формаот булевых переменныхx₁,x₂, …,x_n. Непривычное для булевых величин обозначениеx^следует понимать какx¹ = x,x^-1 =x,x⁰ = 1. Таким образом, массив параметров_jiсодержит информацию о том, входит лиi-тая переменная вj-тую элементарную конъюнкцию, и если входит, тоcинверсией или без.

Требуется дать ответ, существует ли набор значений переменных x₁,x₂, …,x_n, при котором значение ДНФ равно 0, или же данная ДНФ является тождественно истинной, т.е. всегда равна 1.

Это задача поиска, ее решение завершается, если найден хотя бы один план, на котором ДНФ принимает значение 0.

Используя законы Де Моргана, нетрудно сформулировать двойственную задачу: дана конъюнктивная нормальная форма, требуется определить, существует ли набор значений переменных x₁,x₂, …,x_n, при котором значение КНФ равно 1. Эту задачу принято называтьзадачей о выполнимости КНФ. Как будет показано далее, задача о выполнимости играет важную роль в теории вычислительной сложности.

1.3.8. Задача о 8 ферзях.На шахматной доске размером 88 требуется расставить 8 ферзей так, чтобы они не били друг друга (т.е. никакие два ферзя не должны находиться на одной горизонтали, вертикали или диагонали).

Это задача поиска, если требуется найти хотя бы одну расстановку, либо задача перечисления, если нужно найти все возможные расстановки. В отличие от всех предыдущих примеров, задача не имеет никаких параметров. Это не семейство задач, а одна конкретная задача. Разумеется, она давно решена, число различных расстановок равно 92.

При желании можно параметризовать задачу, рассмотрев расстановку kферзей на прямоугольной доскеnm.

1.3.9. Головоломка «15».Предполагается, что все ее видели и, вероятно, решали. Требуется восстановить нарушенный порядок квадратиков, причем желательно за минимальное число ходов. К тому же типу принадлежит более новая и сложная головоломка «кубик Рубика».

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

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

1.3.10. Шахматы.В сущности, шахматную игру (и многие другие игры) можно рассматривать как комбинаторную задачу выбора наилучших ходов. Можно рассматривать ее как задачу оптимизации, если считать, что целевая функция равна 1 при выигрыше белых, 0 – при ничьей и –1 – при выигрыше черных. Конечность каждой партии гарантируется «правилом 50 ходов», по которому в некоторых ситуациях затянувшаяся партия объявляется ничьей.

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