Алгоритм разбиения множества множеств на куски примерно одинакового размера?

Question

Рассмотрим множество A из n конечных множеств, , члены которого не обязательно не пересекаются . Пусть P = {P [1], P [2], ..., P [m]} - разбиение A, и для каждого i в 1..m пусть U [i] - объединение всех элементы P [i]. Итак, U = {U [1], U [2], ..., U [m]}. Я хотел бы, чтобы алгоритм нашел P, такой, что соответствующий U является разделом, и таким образом, чтобы разница в количестве элементов (то есть размер) между наименьшим и наибольшим элементами U была минимизирована.

Характеристики данных:

• м маленький (от 2 до 5) и n <10000 </li>
• Как правило, в A
• Пересечения между парами множеств в A обычно малы или пусты

Answer 1

Моя аналогия с ожерельем в комментариях к вопросу предлагает следующее решение:

1. Постройте неориентированный граф G, вершинами которого являются элементы A, и где есть ребро от A [i] до A [j] тогда и только тогда, когда A [i] пересекается с A [j].
2. Найдите подключенные компоненты C из G. Это можно сделать с помощью простого алгоритма шириной в первую или в глубину.
3. Длякаждый C [i], возьмите вершины C [i] и объедините их вместе, получая D [i].Теперь вы свели проблему к специальному случаю, потому что множество D является разбиением объединения элементов A.
4. Используйте алгоритм упаковки в двоичную упаковку, чтобы попытаться вписать элементы D точно в mбункеры, каждый из которых имеет размер ceil (t / m), где t - размер объединения всех элементов D. Если это не удастся, увеличивайте размеры бинов несколько раз, пока либо это не удастся, либо станет ясно, что это никогда не удастся,Алгоритмы упаковки бина, как правило, эвристические, поэтому идеальное решение может быть не найдено.Кроме того, это больше, чем простая проблема упаковки бина, поэтому даже идеальный алгоритм упаковки бина может не найти оптимального решения.

Мне было бы интересно узнать, есть ли более эффективныйрешение.В частности, у меня есть предположение, что повторное использование алгоритма упаковки бина на шаге 4 не имеет смысла.

Answer 2

Я бы начал с графа пересечения A, который имеет элементы узлов A и ребра, когда два узла имеют непустое пересечение.Каждый связный компонент этого графа должен содержаться в одном P (i) для некоторого i.

Пусть C (1), ..., C (k) будут связными компонентами графа.Пусть

size(j)=|union(a in C(j))|

Теперь вы можете переписать задачу в терминах значений размера (i) с i = 1 ... k.А именно, даны положительные целочисленные значения s (1), .., s (k).Для подмножества P из [1, .. k] мы определяем s (P) = sum (j в P) s (j).

Мы хотим найти разбиение P '= (P' (1).), ..., P '(m)) of [1, .., k] с условием, что оно минимизирует значение:

max s(P'(j)) - min s(P'(j))

Следовательно, нам действительно нужно знать не вероятные размерыэлементов A, но вероятные размеры связанных компонентов графа, чтобы придумать «лучший» алгоритм.