Установить проблему с обложкой
Проблема покрытия множества — классический вопрос комбинаторики , информатики , исследования операций и теории сложности . Это одна из 21 NP-полной задачи Карпа, которая в 1972 году оказалась NP-полной .
Учитывая набор элементов {1, 2, …, n } (называемый универсумом ) и набор S из m множеств, объединение которых равно универсуму, задача покрытия множества состоит в том, чтобы идентифицировать наименьший поднабор S , чье объединение равно вселенная. Например, рассмотрим универсум U = {1, 2, 3, 4, 5} и набор множеств S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }. Ясно, что объединение S есть U . Однако мы можем покрыть все элементы следующим меньшим количеством наборов: { {1, 2, 3}, {4, 5} }.
Более формально, учитывая универсум и семейство подмножеств , покрытие - это подсемейство множеств, объединение которых равно . В задаче решения множества, покрывающей вход, есть пара и целое число ; вопрос в том, есть ли комплект покрытия размером или меньше. В задаче оптимизации покрытия множества входными данными является пара , и задача состоит в том, чтобы найти покрытие множества, которое использует наименьшее количество множеств.
Версия решения покрытия множества является NP-полной , а версия покрытия множества оптимизации/поиска является NP-трудной . [1] Это проблема, «исследование которой привело к развитию фундаментальных методов для всей области» алгоритмов аппроксимации . [2] Если каждому набору присваивается стоимость , это становится проблемой взвешенного покрытия набора.
Эта ILP принадлежит к более общему классу ILP для решения проблем . Зазор целочисленности этого ILP не превышает , поэтому его релаксация дает алгоритм факторной аппроксимации для задачи минимального покрытия множества (где - размер вселенной). [4]
