Алгоритм найти наименьшее количество тегов, которые охватывают все элементы?

Question

Я думаю, что это может быть NP-полная, но я все равно спрошу.Жадные алгоритмы, похоже, не работают в моей голове.

Учитывая набор элементов, каждый из которых содержит 1 или более тегов, я хочу найти наименьший набор тегов, который охватывает все элементы.

Редактировать: Смотрите мое "решение" здесь .

Answer 1

Это проблема Set Cover , которая является NP-полной.Каждый тег определяет подмножество вашего списка элементов, и вы хотите найти минимальное количество подмножеств (тегов), объединение которых равно полному списку элементов.