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

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

2 Последняя строка C позволяет отличить столбцы, принадлежащие матрице A, от принадлежащих B.

6 Удалить первую строку матрицы C;

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

Теорема 2 [7]. Если матрица A обладает сильным свойством C1P, является редуцированной, а ее строки отсортированы в лексикографическом порядке, то время работы алгоритма составляет O(M3n), где M – максимальное число единиц в строке и в столбце.

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

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