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

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

Это задача оптимизации с фиксированной размерностью. Элемент плана xiможно понимать как номер города, в который нужно ехать на 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) = Sc_ix_i при ограничениях G(X) = Sb_ix_i £ B и x_i ³ 0, где i = 1…n.

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

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

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

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

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

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

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

1.3.7. Задача о тождественной истинности ДНФ. Дана дизъюнктивная нормальная форма от булевых переменных x₁, x₂, …, x_n. Непривычное для булевых величин обозначение x^s следует понимать как x¹ = x, x^-1 =`x, x⁰ = 1. Таким образом, массив параметров s_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 ходов», по которому в некоторых ситуациях затянувшаяся партия объявляется ничьей.

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