Подсчет подмножеств в бесконечной / (динамической) вселенной набор буквенно-цифровых элементов - PullRequest
Новая
       0

Подсчет подмножеств в бесконечной / (динамической) вселенной набор буквенно-цифровых элементов

0 голосов
/ 07 апреля 2011

Дано бесконечное множество / Вселенная (U) буквенно-цифровых элементов и семейство (F) подмножеств (U).

Рассчитать / сгруппировать все связанные подмножества в (F), где все элементы покрыты или меньше, см. Пример.

Вселенная на самом деле не бесконечна, но очень велика, примерно 59 миллионов элементов и растет. Семейные (F) подмножества, также не являются постоянными, примерно 13Mil элементов и растут.

Пример:

U = {9b3745e9, ab70de17, 1c410139, 44038bbf, 9c610bb, ..., N}

F1 = {9b3745e9, 07ee0220}

F2 = {9b3745e9, ab70de17, 99b5d738}

F3 = {99b5d738,07ee0220}

F4 = {9b3745e9, ab70de17, 1c410139}

F4 * +1030 * высчитывает () * +1031 * = {F2, (2), F1 (1)} * * одна тысяча тридцать две

Конечно, вы можете сделать это на брутальной итерации, но со временем это не оптимальное решение (NP-полная задача).

Есть идеи, как это можно решить более эффективно? Кодирование подмножеств при использовании элемента / вектора Codebook, который больше, чем Universe, например, 70Mil или 100Mil. Но я не уверен насчет расчета.

1 Ответ

0 голосов
/ 07 апреля 2011

Кажется, основываясь на примере, что «связанные» подмножества являются подмножествами, которые содержат по крайней мере один общий элемент.В этом примере F4 имеет два общих элемента: 0x9b3746e9 (совместно с F1) и 0xab70de17 и 0x9b3746e9, совместно используемых с F2.Цифры в скобках обозначают количество общих элементов (F2 (2) = 2 общих элемента с F2).Предполагая, что это интерпретация:

Это, очевидно, не NP-полная проблема, а простой случай индексации.В хэш-таблице свяжите каждый элемент U (59 * 10 6 ) со списком подмножеств, которые их содержат (например, 0x9b3746e9 -> {F1, F2, F4}).При поиске связанных подмножеств данного подмножества перебирайте элементы U в подмножестве и ищите хеш-таблицу для каждого элемента.Итерируйте по спискам, и вы найдете соответствующие подмножества.Это быстрая операция, и в ней нет ничего NP-полного.

Однако другая интерпретация вопроса заключается в том, что это является примером задачи комбинаторной оптимизации SET COVER.Это действительно NP-полная.

...