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

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

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

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

  2 '''for''' каждого частичного решения C' в S, не покрывающего первую строку матрицы A: {

  3 '''for''' каждого столбца c матрицы A, покрывающего первую строку A:{

  5 Удалить С' из S;}

  6 Удалить первую строку A;}

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