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

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

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

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


algorithm subset
person phimuemue    schedule 19.05.2010    source источник

Ответы (3)


arrow_upward
8
arrow_downward

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

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

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

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

arrow_upward
0
arrow_downward

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

Теперь наименьшее множество в A не является подмножеством B. Двигайтесь дальше, но сначала проверьте, являются ли изучаемые вами множества подмножествами на данный момент или нет.

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

person Daniel Harms    schedule 19.05.2010

arrow_upward
0
arrow_downward

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

person dato datuashvili    schedule 19.05.2010
comment
@ davit-datuashvili: Ответ Криса точен, я предлагаю вам прочитать его. - person ; 19.05.2010