Покрытие множества почти последовательными подмножествами: различия между версиями

Множества R и C могут быть представлены в виде бинарной матрицы A размера m x n, включающей строку для каждого элемента из R и столбец для каждого подмножества R из C, где значение ячейки <math>a_{i, j}</math> равно 1 в том и только том случае, если i-й элемент R является частью j-го подмножества C. Таким образом, задачу SET COVER можно сформулировать следующим образом.

Вдохновленные задачами, возникающими в связи с оптимизацией железнодорожного транспорта, Мекке и Вагнер [7] рассматривают случай с экземплярами SET COVER, обладающими свойством «почти C1P». Обладающие свойством «почти С1Р» матрицы похожи на матрицы, сгенерированные следующим образом: начиная с матрицы, обладающей свойством С1Р, случайным образом заменяем определенный процент единиц на нули [7]. Напротив, с точки зрения Руфа и Шёбель [8], наличие свойства «почти С1Р» означает, что среднее количество блоков последовательных единиц в строке значительно меньше количества столбцов матрицы. В данной статье будут приведены некоторые полученные ими результаты.

Пусть дан экземпляр (A, w) задачи SET COVER. Обозначим за R множество строк матрицы A, а за C – множество ее столбцов. Столбец <math>c_j</math> ''охватывает'' (или ''покрывает'') строку <math>r_i</math>, что обозначается <math>r_i \in c_j</math>, если <math>a_{i, j} = 1</math>.

''Правило редукции данных'' за полиномиальное время преобразует заданный экземпляр ''I'' задачи оптимизации в экземпляр ''I' ''той же задачи таким образом, что ''|I'| < |I|'', и оптимальное решение для ''I' ''имеет то же значение (например, вес), что и оптимальное решение для ''I''. При наличии набора правил редукции данных процесс ''редуцирования'' экземпляра задачи заключается в многократном применении правил до тех пор, пока не останется других возможностей применения правил; полученный в результате экземпляр называется ''редуцированным''.

'''Правило доминирования для строк:''' если имеются две строки <math>r_{i_1}, r_{i_2} \in R</math>, а <math>\forall c \in C: r_{i_1} \in c</math> влечет <math>r_{i_2} \in c</math>, то <math>r_{i_1}</math> ''доминирует'' <math>r_{i_2}</math> (или, что то же самое, <math>r_{i_2}</math> доминируется <math>r_{i_1}</math>). Удалить строку <math>r_{i_2}</math> из матрицы A.

В дополнение к этим двум правилам, столбец <math>c_{j_1} \in C</math> может также доминироваться подмножеством <math>C' \subseteq C</math> столбцов вместо одного столбца: если имеется подмножество <math>C' \subseteq C</math> и <math>w(c_{j_1}) \ge \sum_{c \in C'} w(c)</math>, а <math>\forall r \in R: r \in c_{j_1}</math> влечет <math>(\exist c \in C': r \in c)</math>, удалить <math>c_{j_1}</math> из A. К сожалению, поиск доминирующего подмножества C' для заданного множества <math>c_{j_1}</math> является NP-сложной задачей. Мекке и Вагнер [7] представили ограниченный вариант данного обобщенного правила доминирования столбцов.

'''Расширенное правило доминирования для столбцов:''' пусть имеются два столбца <math>c_{j_1}, c_{j_2} \in C</math> и строка, которую покрывают оба столбца <math>c_{j_1}</math> и <math>c_{j_2}</math>, и если <math>w(c_{j_1}) \ge w(c_{j_2}) + \sum_{c \in X (c_{j_1}, c_{j_2})} w(c)</math>, то <math>c_{j_1}</math> ''доминируется'' <math>\{ c_{j_2} \} \cup X(c_{j_1}, c_{j_2})</math>. Удалить столбец <math>c_{j_1}</math> из матрицы A.

В базах данных, которые использовали Руф и Шёбель [8], матрицы представлены столбцовыми индексами первой и последней единиц в ее блоках последовательных единиц. Для таких матричных представлений было предложено правило быстрой редукции данных [8], которое устраняет «лишние» столбцы и в конкретных реализациях заменяет правило доминирования для столбцов. Новое правило работает быстрее, чем правило доминирования для столбцов (редукция матрицы по новому правилу может быть выполнена за время O(mn)), однако оно является менее мощным: в результате редукции матрицы A с использованием нового правила может получиться матрица с большим числом столбцов, чем в результате ее редукции по правилу доминирования для столбцов.

Мекке и Вагнер [7] представили алгоритм, который решает задачу SET COVER с помощью перечисления всех допустимых решений.

Алгоритм на каждом шаге рассматривает строку <math>r_i</math> текущей матрицы (которая ранее была редуцирована с помощью правил редукции данных) и производит ее ветвление на <math>bl_i</math> случаев, где <math>bl_i</math> – это количество блоков последовательных единиц в <math>r_i</math>. В каждом случае выбирается по одному блоку последовательных единиц в <math>r_i</math>, а единицы во всех остальных блоках в этой строке заменяются нулями. После этого вычисляются нижняя и верхняя границы веса решения для каждого полученного экземпляра. Если нижняя граница более чем на <math>1 + \epsilon</math> (для заданной константы <math>\epsilon</math>) отличается от достигнутой на данный момент наилучшей верхней границы, соответствующий экземпляр подвергается дальнейшему ветвлению. Наконец, возвращается найденная лучшая верхняя граница.

На каждом шаге ветвления вновь созданные экземпляры <math>bl_i</math> «ближе» к (сильному) C1P, чем экземпляр, потомками которого они являются. Если экземпляр обладает свойством C1P, то нижнюю и верхнюю границу можно легко вычислить, решив задачу точно. В противном случае используются стандартные эвристики.

Экземпляры SET COVER встречаются, например, при оптимизации железнодорожной сети, где задача заключается в том, чтобы определить места построения новых железнодорожных станций. Каждая строка в этом случае соответствует существующему населенному пункту, а каждый столбец – точке на существующем пути, где можно было бы построить станцию. Столбец c покрывает строку r, если населенный пункт, соответствующий r, лежит в пределах заданного радиуса вокруг места, соответствующего c.

Мекке и Вагнер [7] проводят эксперименты на экземплярах из реального мира, как описано в разделе «Применение», а также на экземплярах, которые были сгенерированы, начиная с матрицы, обладающей свойством C1P, и заменяя случайным образом определенный процент единиц на нули. Реальные данные представляют собой граф железных дорог с 8200 вершинами и 8700 ребрами плюс 30 000 населенных пунктов. Сгенерированные экземпляры состоят из 50-50 000 строк с 10-200 единиц на строку. До 20% единиц заменены нулями.

Перечисляющий алгоритм демонстрирует почти линейное время работы для реальных и большинства сгенерированных экземпляров. Только у сгенерированных экземпляров с 20% возмущением время выполнения является квадратичным.