Алгоритм: удаление как можно меньшего числа элементов из набора, чтобы обеспечить отсутствие подмножеств

Question

У меня проблема, которую я не знаю, как решить:

У меня есть набор наборов 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).

Существует ли алгоритм определения (минимального количества) удаляемых элементов?

Answer 1

Звучит так, как будто вы хотите удалить минимальный набор ударов из A из B (это тесно связано с проблемой покрытия вершин).

Ударный набор для некоторых наборов наборов A сам по себе является набором, который содержит по крайней мере один элемент из каждого набора в A (он «поражает» каждый набор). Минимальный ударный набор - самый маленький такой ударный набор. Итак, если у вас есть MHS для вашего набора наборов A, у вас есть элемент из каждого набора в A. Удаление этого из B означает, что ни один из наборов в A не может быть подмножеством B.

Все, что вам нужно сделать, это вычислить MHS для (A ₁ , A ₂ , ... A _n ), а затем удалить его из B. К сожалению, поиск MHS является NP-полной проблемой. Зная это, у вас есть несколько вариантов:

1. Если ваш набор данных невелик, используйте очевидное грубое решение
2. Используйте вероятностный алгоритм, чтобы получить быстрый приблизительный ответ (см. в этом PDF )
3. Беги далеко-далеко в противоположном направлении

Answer 2

Если вам просто нужно какое-то приближение, начните с наименьшего набора в A и удалите один элемент из B. (Вы можете просто взять один случайный элемент или проверить, какой элемент находится в большинстве наборов в A, в зависимости насколько точно, как быстро вам нужно)

Теперь самый маленький набор в A не является подмножеством B. Перейдите оттуда, но сначала проверьте, являются ли исследуемые наборы подмножествами в этой точке или нет.

Это напоминает мне о проблеме покрытия вершин, и я помню некоторый алгоритм аппроксимации для этого, который похож на этот.

Answer 3

Я думаю, вы должны найти минимальную длину из этих наборов и затем удалить эти элементы, которые есть в этом наборе.