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

Ключевые слова и синонимы

Множество представителей

Постановка задачи

Задача покрытия множества SET COVER получает на вход множество R, состоящее из m элементов, множество C из n подмножеств R и весовую функцию [math]\displaystyle{ w: C \to \mathbb{Q} }[/math]. Задача заключается в выборе подмножеств [math]\displaystyle{ C' \subseteq C }[/math] с минимальным весом, объединение которых содержит все элементы R.

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

Дано: бинарная матрица A размера m x n и весовая функция w над столбцами A.

Требуется: выбрать некоторые столбцы A с минимальным весом так, чтобы подматрица A' матрицы A, порождаемая этими столбцами, имела по крайней мере одно значение 1 в каждой строке.

В общем случае задача SET COVER является NP-сложной [4], однако она может быть решена за полиномиальное время для экземпляров, столбцы которых можно переставить таким образом, чтобы единицы в каждой строке появлялись последовательно – иначе говоря, для экземпляров, удовлетворяющих свойству последовательных единиц (C1P). //Свойство C1P может быть симметричным образом определено для столбцов, однако в данной статье рассматриваются строки. Задачу SET COVER над экземплярами со свойством C1P можно решить за полиномиальное время – например, при помощи подхода линейного программирования – поскольку соответствующие матрицы коэффициентов являются полностью унимодулярными (см. [9])//

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

Нотация

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

Бинарная матрица обладает сильным свойством C1P, если (без какой-либо перестановки столбцов) единицы появляются последовательно в каждой строке. Блок последовательных единиц является максимальной последовательностью единиц в строке. Возможно за линейное время определить, обладает ли матрица свойством C1P, и если да, то вычислить перестановку столбцов, в результате которой получается сильное свойство C1P [2, 3, 6]. Однако заметим, что перестановка столбцов бинарной матрицы таким образом, чтобы количество блоков последовательных единиц в полученной матрице было минимальным, является NP-сложной [1, 4, 5].

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

Основные результаты

Правила редукции данных

Для задачи SET COVER существуют хорошо известные правила редукции данных:

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

Правило доминирования для столбцов: если имеются два столбца [math]\displaystyle{ c_{j_1}, c_{j_2} \in C, w(c_{j_1}) \ge w(c_{j_2}) }[/math], и [math]\displaystyle{ \forall r \in R: r \in c_{j_1} }[/math] влечет [math]\displaystyle{ r \in c_{j_2} }[/math], то [math]\displaystyle{ c_{j_2} }[/math] доминирует [math]\displaystyle{ c_{j_1} }[/math]. Удалить столбец [math]\displaystyle{ c_{j_1} }[/math] из матрицы A.

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

Для каждой строки [math]\displaystyle{ r \in R }[/math] обозначим за [math]\displaystyle{ c_{min}(r) }[/math] столбец в C, который покрывает r и имеет минимальный вес при соблюдении этого свойства. Для двух столбцов [math]\displaystyle{ c_{j_1}, c_{j_2} \in C }[/math] определим [math]\displaystyle{ X(c_{j_1}, c_{j_2}) := \{ c_{min}(r) | r \in c_{j_1} \and r \notin c_{j_2} \} }[/math]. Новое правило редукции данных будет выглядеть следующим образом.

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

Теорема 1 [7]. Редукция (приведение) матрицы A может быть выполнена за время O(Nn) в соответствии с правилом доминирования для столбцов, за время O(Nm) в соответствии с правилом доминирования для строк и за время O(Nmn) в соответствии со всеми тремя описанными выше правилами доминирования, где N – количество единиц в матрице A.

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

Алгоритмы

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

Пусть дана строка [math]\displaystyle{ r_i }[/math] матрицы A. Частичное решение для строк [math]\displaystyle{ r_1, ..., r_i }[/math] представляет собой подмножество [math]\displaystyle{ C' \subseteq C }[/math] столбцов A, такое, что для каждой строки [math]\displaystyle{ r_j, j \in \{1, ..., i\} }[/math] существует столбец в C', покрывающий строку [math]\displaystyle{ r_j }[/math].

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

  1	Повторить m раз: {
  2	for каждого частичного решения C' в S, не покрывающего первую строку матрицы A: {
  3	for каждого столбца c матрицы A, покрывающего первую строку A:{
  4	Добавить [math]\displaystyle{  \{ c \} \cup C' }[/math] к S; }
  5	Удалить С' из S;}
  6	Удалить первую строку A;}

Этот простой алгоритм перечисления способен создать множество S экспоненциального размера. Поэтому при помощи приведенных выше правил редукции данных после каждого шага итерации выполняется удаление ненужных более частичных решений. С этой целью матрица B ассоциируется с множеством S, где каждая строка соответствует строке матрицы A, а каждый столбец – частичному решению в S: значение ячейки [math]\displaystyle{ b_{i, j} }[/math] матрицы B равно 1 в том и только том случае, если j-ое частичное решение B содержит столбец A, покрывающий строку [math]\displaystyle{ r_i }[/math]. Алгоритм использует матрицу [math]\displaystyle{ C := \begin{pmatrix} A & B \\ 0...0 & 1...1 \end{pmatrix} }[/math], которая обновляется вместе с S на каждом шаге итерации. //Последняя строка C позволяет отличить столбцы, принадлежащие матрице A, от принадлежащих B//

Строка 6 вышеприведенного алгоритма заменяется двумя следующими строками:

  6	Удалить первую строку матрицы C;
  7	Выполнить редукцию матрицы C и соответствующим образом изменить S;}

По окончании работы алгоритма множество S содержит ровно одно решение, и это решение является оптимальным. Более того, если экземпляр SET COVER хорошо структурирован, то алгоритм имеет полиномиальное время работы:

Теорема 2 [7]. Если матрица A обладает сильным свойством C1P, является редуцированной, а ее строки отсортированы в лексикографическом порядке, то время работы алгоритма составляет [math]\displaystyle{ O(M^{3n}) }[/math], где M – максимальное число единиц в строке и в столбце.

Теорема 3 [7]. Если расстояние между первой и последней единицами в каждом столбце не превышает k, то в любой момент времени в любой точке алгоритма количество столбцов в матрице B равно [math]\displaystyle{ O(2^{kn}) }[/math], а время работы – [math]\displaystyle{ O(2^{2k}kmn^2) }[/math].

Руф и Шёбель [8] представляют алгоритм на основе метода ветвей и границ для экземпляров задачи SET COVER, среднее количество блоков последовательных единиц в строке у которых невелико.

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

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

Применение

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

Если бы сеть железных дорог состояла только из одной прямой рельсовой колеи, то соответствующий экземпляр SET COVER обладал бы свойством C1P; экземпляры, возникающие на базе реальных данных, близки к C1P [7, 8].

Экспериментальные результаты

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

В реальных экземплярах правила редукции данных уменьшают количество единиц до 1-25% от исходного количества единиц без применения расширенного правила редукции столбцов и до 0,2-2,5% – с применением расширенного правила редукции. В случае сгенерированных экземпляров, обладающих свойством C1P, количество единиц уменьшается примерно до 2% без применения и до 0,5% с применением расширенного правила редукции по столбцам. Для экземпляров с 20% возмущением количество единиц снижается до 67% без применения правила и до 20% с применением расширенного правила редукции по столбцам.

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

Руф и Шёбель [7] рассматривают три типа экземпляров: экземпляры из реального мира, экземпляры, возникающие из троек Штейнера, и экземпляры, сгенерированные случайным образом. Последние имеют размер 100 x 100 и содержат либо 1-5 блоков последовательных единиц в каждой строке, каждый из которых включает от одной до девяти единиц, либо вероятность наличия единицы в любой ячейке составляет 3% или 5%.

Правила редукции данных, используемые Руфом и Шёбель, оказываются достаточно мощными для реальных экземпляров (размер матрицы сокращается в среднем примерно с 1100 x 3100 до 100 x 800), в то же время для остальных типов экземпляров значительного уменьшения размеров не наблюдается.

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

См. также

Жадные алгоритмы покрытия множества

Литература

1. Atkins, J.E., Middendorf, M.: On physical mapping and the consecutive ones property for sparse matrices. Discret. Appl. Math. 71(1-3),23-40(1996)

2. Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 335-379 (1976)

3. Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pac. J. Math. 15(3), 835-855 (1965)

4. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)

5. Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Biol. 2(1), 139-152(1995)

6. Hsu, W.L., McConnell, R.M.: PC trees and circular-ones arrangements. Theor. Comput. Sci. 296(1), 99-116 (2003)

7. Mecke, S., Wagner, D.: Solving geometric covering problems by data reduction. In: Proceedings of the 12th Annual European Symposium on Algorithms (ESA '04). LNCS, vol. 3221, pp. 760-771. Springer, Berlin (2004)

8. Ruf, N., Schobel, A.: Set covering with almost consecutive ones property. Discret. Optim. 1(2), 215-228 (2004)

9. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester(1986)