Отдельные группы людей на основе членов

Question

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

Пример:

GroupA - John, Bob, Nick 
GroupB - Jack, Nick 
GroupC - Brian, Alex, Steve 

Как вы можете видеть GroupA и GroupB перекрытия (они оба содержат Ник) Мне нужен алгоритм, чтобы установить группы, GroupA-> GroupC-> GroupB

Спасибо

Answer 1

Это зависит от того, как вы точно определяете проблему - с перекрытиями и затратами и вещами.

Это может сводится к Travelling salesman problem - вы можете установить край вес как 0, если группа i и j не имеют ничего общего, и некоторую функцию f(i,j), которая зависит от количества общих элементов между ними. Затем вам нужен список, который идет от одной группы к последней группе, один раз посещая каждую группу, сводя к минимуму некоторую функцию перекрытия.

Возможно, вы можете уменьшить TSP до версии этого (в зависимости от того, насколько конкретно вы имеете в виду «насколько возможно максимально», в отношении конкурирующих перекрытий) аналогично.

К сожалению, это NP-complete, что означает, что вы должны начать поиск чего-то, что «достаточно хорошо».

Answer 2

Эта проблема не имеет уникального или даже содержательного решения, если у вас есть произвольные группы. См. Например:

GroupA = {Alice, Bob} 
GroupB = {Bob, David} 
GroupC = {David, Alice}