Присвоить элементы минимальному числу групп

Question

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

У меня есть комплект из 4 предметов: [A, B, C, D].

У меня есть 3 группы: 1, 2, 3.

Группа 1 может принимать или B.

Группа 2 могут принимать В или С.

Группа 3 могут принимать C или D .

Назначьте элементы таким образом, чтобы минимизировать количество используемых групп. I.e. решение будет: Группа 1: [A, B]

Группа 2: []

Группа 3: [C, D]

Как бы решить эту проблему программно? Я знаю, что видел это раньше, поэтому любые ключевые слова или ссылки, чтобы указать мне в правильном направлении, были бы очень оценены.

Answer 1

Это проблема с набором покрытий. Это NP трудно, поэтому найти истинный минимальный набор сложно в общем и требует экспоненциального времени. Жадный алгоритм, который берет множество, покрывающее самые оставшиеся элементы, может дать хорошие аппроксимации. Для накрывающих множеств с ограниченным размером его можно также решить в разумные сроки. Для получения дополнительной информации см. http://en.m.wikipedia.org/wiki/Set_cover_problem

Answer 2

Если мы визуализируем эту проблему как проблему Графа, в которой все группы и элементы являются узлами на графике, а между группой и элементами связаны грани, мы можем видеть, что эта проблема представляет собой небольшой случай Vertex Cover

Однако, если количество элементов невелико (менее 16), мы можем использовать динамическое программирование, чтобы легко его решить.