Алгоритм: Удаление как можно меньше элементов от набора для осуществления подмножеств
Я получил проблему, которую я не знаю, как решить:
У меня есть ряд наборов 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).
Существует ли алгоритм для определения (минимальное количество) элементы, которые будут удалены?
3 ответа
Похоже, вы хотите удалить минимальный набор попаданий из A из B (это тесно связано с проблемой покрытия вершин).
Набор совпадений для некоторого набора наборов A сам по себе является набором, таким, что он содержит по крайней мере один элемент из каждого набора в A (он «попадает» в каждый набор ). Минимальный набор ударов - это наименьший такой набор ударов. Итак, если у вас есть MHS для набора наборов A , у вас есть элемент из каждого набора в A . Удаление этого параметра из B означает отсутствие набора в A может быть подмножеством B .
Все, что вам нужно сделать, это вычислить MHS для (A 1 , A 2 , ... A n ), а затем удалить его из B . К сожалению, найти MHS - это NP-полная проблема. Однако, зная это, у вас есть несколько вариантов:
- Если ваш набор данных невелик, воспользуйтесь очевидным методом перебора.
- Используйте вероятностный алгоритм, чтобы получить быстрый приблизительный ответ (см. этот PDF-файл ])
- Бежать далеко-далеко в противоположном направлении
Если вам просто нужно некоторое приближение, начните с наименьшего набора в A и удалите один элемент из B. (Вы можете просто взять один случайным образом или проверить, какой элемент находится в наибольшем количестве наборов в A, в зависимости от того, насколько точно и как быстро вам нужно)
Теперь наименьший набор в A не равен ' t подмножество B. Двигайтесь дальше, но сначала проверьте, являются ли исследуемые множества подмножествами на данном этапе или нет.
Это напоминает мне проблему покрытия вершин, и я помню некоторый приближенный алгоритм для этого, похожий на этот.
Я думаю, вы должны найти минимальную длину из этих наборов, а затем удалить эти элементы, которые есть в этом наборе.