Как сделать алгоритм нахождения наименьшего количества групп элементов?
Друзья, привет, есть такая задача. Существует набор элементов, для каждого элемента известны элементы с которыми он не может состоять в одной группе, таких запрещенных элементов может быть несколько, а может и не быть совсем. Вопрос, как должен работать алгоритм который вычислит самое маленькое количество групп(и их состав), в которые войдут все элементы. Вот пример.
А : [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]
Иван, наверно тем, что когда у меня будет 100 элементов, каждый их которых на кого то ссылается, то у меня не получиться решить такую задачу. Нужен компьютерный алгоритм
Иван, это не так, в определенных условиях ты можешь собрать группу из элементов, которые перекроют возможность собрать группу с большим количеством элементов, в итоге ты вместо того, чтобы сделать меньшее кол-во групп, сделаешь большее количество.
Иван, я конечно не уверен, но по моему без сочетаний(те которые из комбинаторики) этот алгоритм нельзя сделать. Но я могу ошибаться, поэтому и решил задать вопрос
Roman, вы пробовали применить это к чему то сложнее моего примера? Насколько я понимаю это не сработает.
Попробуйте на такой комбинации:
а : [b, c, k]
b : [a, c, k]
k : [a, b, d]
c : [a, b, e]
e : [d, c]
d : [k, e]
Ваша задача сводится к задаче вычисления хроматического числа графа и поиску его раскраски.
Ваши списки для каждого элемента эквивалентны спискам смежности вершин в графе.
Простой
Простой
