@bibliophile

Как сделать алгоритм нахождения наименьшего количества групп элементов?

Друзья, привет, есть такая задача. Существует набор элементов, для каждого элемента известны элементы с которыми он не может состоять в одной группе, таких запрещенных элементов может быть несколько, а может и не быть совсем. Вопрос, как должен работать алгоритм который вычислит самое маленькое количество групп(и их состав), в которые войдут все элементы. Вот пример.
А : [B, C, D]
B : [A, C]
C : [A, B]
D : [A]
В одну группу их точно не получиться упаковать.
Проверим можно ли упаковать в 2 группы. Элемент А нельзя положить ни с кем в одну группу, значит если остальные 3 элемента нельзя положить в одну группу, то их невозможно упаковать в 2 группы, а так как В и С не могут быть в одной группе, то мы не сможем упаковать в 2 группы.
Элементы можно упаковать в 3 группы.
Группа 1: D + В
Группа 2: C
Группа 3: А
или же
Группа 1: D + C
Группа 2: B
Группа 3: A
Приложу еще один пример, но без ответов. Этот пример тоже достаточно простой.
а : [b, c, k]
b : [a, c, k]
c : [a, b, e]
k : [a, b, d]
e : [d, c]
d : [k, e]
  • Вопрос задан
  • 168 просмотров
Решения вопроса 1
@Taus
Ваша задача сводится к задаче вычисления хроматического числа графа и поиску его раскраски.
Ваши списки для каждого элемента эквивалентны спискам смежности вершин в графе.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы