Алгоритм покрытия населения минимальными метками

Question

Мои данные состоят из людей и тегов, имеющих отношение многие ко многим.

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

Есть идеи?

Answer 1

Это NP-сложная проблема.Потребуется МНОГО обработки, чтобы убедиться, что у вас действительно есть абсолютное минимальное количество требуемых тегов.

Довольно быстрое и простое решение, которое я бы использовал, -

while there are users left in the pool:
    find the tag that represents the most users
    add that tag to the list
    remove all the users that that tag represents from the pool

If you want, you can then loop through and make sure there aren't any 
unnecessary tags //but that probably won't help much

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

Answer 2

Отношение «многие ко многим» между людьми и тегами образует двудольный граф, который, к счастью, сильно отличается от общего случая.Следовательно, проблема не является NP-полной, но можно решить за полиномиальное время .Кажется, что это равносильно поиску максимального соответствия, для которого Википедия предоставляет несколько альтернатив .

Answer 3

Это эквивалентно NP-полной задаче покрытия вершин .

Простой набросок доказательства: если мы можем найти минимальное покрытие вершин, мы можем найти наименьший набор тегов,Просто создайте граф с вершинами = тегами, объединяющими людей, и свяжите их соответствующим образом, а также соедините все теги между собой.Наименьшее покрытие вершин соответствует минимальному набору тегов, которое легко увидеть, если мы поймем, что для каждого покрытия вершин в таком графе существует покрытие вершин того же размера, состоящее только из вершин «тегов».

Опозицию (покрытие вершин можно уменьшить до минимальных тегов) можно показать, создав тег и человека для каждой вершины и связав тег для каждой вершины с человеком для той же самой вершины + ее соседей.