Что такое лучший алгоритм, чем грубая сила для разделения элементов в перекрывающихся категориях?

У меня есть произвольный набор элементов (точки ниже), а некоторое количество категорий перекрывается произвольным образом (ниже - A-C). Тест состоит в том, чтобы определить, возможно ли, чтобы каждый элемент был присвоен одной категории, среди тех, к которым он уже принадлежит, так что каждая категория заканчивается по крайней мере некоторым количеством элементов.

Так, например, мы можем потребовать, чтобы A, B и C могли претендовать на один элемент. Если нам даны все 4 точки ниже, показывая, что это возможно, просто: просто вставьте все элементы в список, пройдите по категориям и у каждой категории удалите элемент, к которому у него есть доступ, и до тех пор, пока каждый категория может удалить один элемент, мы сдаем тест.

Теперь предположим, что мы удалим синюю точку и повторим тест. Ясно, что мы можем назначить желтый для A, красный для B и зеленый для C, и снова мы пройдем. Но трудно кодифицировать это решение: если мы следуем предыдущему методу (опять же нет синей точки), тогда предположим, что А начинается с удаления зеленой точки. Теперь, если B удаляет желтую точку, мы пропустим тест (так как C не может удалить красную точку), тогда как если B удаляет красную точку, C все еще может принимать желтый цвет и пропускать.

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

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

Ответ 1

Вы были правы, указав, что это проблема назначения, и как таковая она может быть решена с использованием классических алгоритмов Graph Theory.

Вы можете перевести вашу проблему следующим образом:

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

Fold-Fulkerson можно использовать для поиска максимального соответствия в двудольном графе в O (ES), где E - количество ребер и S - максимальный поток в сети.

Ответ 2

Пусть D обозначает множество ваших точек, а C обозначает набор категорий.

Вы можете построить двудольный граф G (D ∪ C, E), где D ∪ C - множество вершин, а E - множество ребер между D и C.

(d, c) находится в E тогда и только тогда, когда точка D принадлежит к категории C.

Затем вам интересен поиск максимального двухстороннего соответствия на этом графике.

Поскольку граф двудольный, его можно решить с помощью известного алгоритма Hopcroft-Karp

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