Алгоритм: удаление как можно меньше элементов от установленного для обеспечения подмножеств
Вопрос
Я получил проблему, которую я не знаю, как решить:
У меня есть набор наборов A = {A_1, A_2, ..., A_n}
и у меня есть набор B
.
Целью сейчас - удалить как можно меньше элементов от B
(Создание B'
), так что, после удаления элементов для всех 1 <= i <= n
, A_i
является нет подмножество B'
.
Например, если у нас есть A_1 = {1,2}, A_2 = {1,3,4}, A_3={2,5}
, а также B={1,2,3,4,5}
, мы могли бы, например, удалить 1 и 2 из B
(это будет уступить B'={3,4,5}
, что не сумерее одного из A_i
).
Есть ли алгоритм для определения (минимального количества) элементов для удаления?
Решение
Похоже, вы хотите удалить минимальный Удар набора из A
от B
(Это тесно связано с проблемой крышки вершины).
Набор ударов для некоторых наборов A
Сама набор такой, что он содержит хотя бы один элемент из каждого набора в A
(это «хиты» каждый набор). Минимальный набор ударов - самый маленький такой набор ударов. Итак, если у вас есть MHS для вашего набора A
, у вас есть элемент из каждого набора в A
. Отказ Удаление этого из B
означает, что нет набора в A
может быть подмножественным B
.
Все, что вам нужно сделать, это вычислять MHS для (A1, А.2, ... аN.), затем удалите это из B
. Отказ К сожалению, нахождение MHS - это проблема с НП. Знание этого, хотя у вас есть несколько вариантов:
- Если ваш набор данных невелик, сделайте очевидное решение Brute-Force
- Используйте вероятностный алгоритм, чтобы быстро получить приближенный ответ (см. этот PDF.)
- Бежать далеко, далеко в противоположном направлении
Другие советы
Если вам просто нужно некоторое приближение, начните с наименьшего набора в A, и удалите один элемент из B. (Вы можете просто захватить один случайным или проверять, какой элемент в большинстве наборов в зависимости от того, насколько точно Как быстро вам нужно)
Теперь самый маленький набор в не подмножестве B. Перемещается оттуда, но сначала проверьте, являются ли наборы, которые вы изучаете, являются подмножествами на данный момент или нет.
Это напоминает мне о проблеме охватывания вершин, и я помню несколько алгоритма приближения для того, что похоже на это.
Я думаю, что вы должны найти минимальную длину от этих наборов, а затем удалить эти элементы, которые находятся в этом наборе.