Создайте минимальное количество наборов, чтобы охватить все данные

Question

У меня проблема с созданием минимального количества наборов, чтобы охватить весь набор данных.

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

Цель состоит в том, чтобы найти минимальное количество наборов.Количество наборов не обязательно должно быть максимально сбалансированным (но было бы неплохо иметь его).

Пример 1:

Domain = {1, 2, 3, 4, 5, 6}
Exclusivity = 1!=2, 3!=4, 4!=5, 5!=6,

Answer is two sets: {1, 3, 5}, {2, 4, 6}

Пример 2:

Domain = {1, 2, 3, 4, 5, 6}
Exclusivity = 1!=2, 2!=3, 3!=4, 4!=5

anwser is two sets: {1, 3, 5, 6}, {2, 4}

Пример 3:

Domain = {1, 2, 3, 4, 5}
Exclusivity = 1!=2, 2!=3, 3!=4, 4!=5, 5!=1

answer is three sets : {1, 3}, {2, 4}, {5}

Пример 4:

Domain = {1, 2, 3, 4, 5}
Exclusivity = 1!=2!=3!=4, 4!=5,

answer is four sets : {1, 5}, {2}, {3}, {4}

Здесь! = Является транзитивным.

Кто-нибудь знает такой алгоритм для решения этой проблемы?проблема эффективно.Я не мог вспомнить ни одного алгоритма, который я использовал в школе, который решает эту проблему, но это было более 10 лет назад.

Помощь приветствуется.

JT

Answer 1

Игнорирование баланса, это раскраска графика .

домен <=> вершин графа

установить <=> все вершины определенного цвета

ограничения эксклюзивности <=> границ графика.

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

Answer 2

Во-первых, описание этой проблемы как проблемы покрытия немного вводит в заблуждение. На самом деле это проблема разделения множеств с ограничениями на разделы.

Раствор 1

Сформулируйте и решите ее как целочисленную линейную программу (ILP). Google показал Java ILP . Если вам интересно, я могу опубликовать больше информации о том, как сформулировать вашу проблему как ILP.

Раствор 2

Пусть каждый элемент в вашем наборе данных (набор Domain) представляет узел в неориентированном графе. Начните с полного графа (т. Е. Все узлы соединены друг с другом) и добавьте ребра, основываясь на ваших ограничениях эксклюзивности (т. Е. Если вы используете матрицу смежности A для представления графа, 1!=2 подразумевает A(1,2) = 0 и A(2,1) = 0).

Затем найдите минимальное разбиение клика , которое эквивалентно минимальная раскраска графа .

Однако вы можете перечислить все максимальные клики и работать оттуда.

Answer 3

С моей точки зрения, я думаю, вы могли бы создать взвешенный график. Для узлов, которые исключают друг друга, установите вес вершин на Int.MAX, для других на 0.

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

НТН