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

Question

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

Пример:

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

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

Спасибо

Answer 1

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

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

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

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

Answer 2

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

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