Алгоритм для поиска уникального набора элементов, по одному элементу из набора наборов

Question

Предположим, у вас есть набор людей J, и вам нужно сделать снимок каждого человека. Их только один фотограф, и у фотографа есть конечный набор раз T (|T|>|J|) можно взять каждую фотографию. В любой момент времени t от T, фотограф может взять только одну фотографию. Каждый человек в J доступен только для того, чтобы их фотография была сделана для некоторого подмножества времени в T, хотя каждому человеку было предложено выбрать хотя бы один раз, когда они доступны. По существу, исходя из доступности каждого человека, фотограф хочет попытаться назначить одного человека каждому доступному временному интервалу в T, чтобы каждый мог получить их фотографию. Существует ли алгоритм полиномиального времени для решения этой проблемы? Если нет, то какая неполиномиальная временная задача сводится к этой задаче в полиномиальное время, то есть как можно показать, что эта проблема не находится в P?

Пример:

фотограф доступен в разы [1, 12, 15, 33, 45, 77].
Лицо A доступно порой [12, 33].
Лицо B доступно порой [1, 12].
Лицо C доступно порой [1, 12].

Мы можем сфотографировать всех с выбором:
Person A: 33
Person B: 1
Person C: 12

Если мы должны были начать с выбора A: 12, B: 1, мы не смог бы найти место для C, то есть нам пришлось бы отступить и переназначить А до 33.

По существу, я ищу алгоритм полиномиального времени, чтобы найти соответствующее назначение времен, если оно существует, и в противном случае можно сообщить, что соответствующего назначения не существует.

Answer 1

Модель может быть смоделирована как Assignment Problem (или Bipartite Graph matching problem).

Источниками являются люди, а места назначения должны быть доступны фотографу. Матрица затрат может быть построена за счет того, что стоимость недоступности человека равна 1, а доступность равна 0.

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

Если итоговая стоимость оптимального решения отлична от нуля, это означает, что присвоение невозможно.

Его можно решить, используя Hungarian Algorithm в полиномиальное время.

Answer 2

Ответ Abhishek будет работать для этой проблемы, но я хотел добавить альтернативу, которую я нашел быстрее. Абхишек уже упоминал (попутно) двухстороннее соответствие, к которому относится Hopcroft-Karp algorithm. Алгоритм Hopcroft-Karp используется для определения соответствия максимальной мощности и работает в $O(sqrt(V)*E)$ времени против O(n^3) для венгерского алгоритма.«Максимальное соответствие мощности» в основном означает, что он находит максимальное количество назначений, которые могут быть сделаны, поэтому в моем предыдущем примере максимальное количество людей, которые могут быть запланированы для фотографии, основаны на доступности каждого и доступных временных интервалах фотографа. Поэтому, если возвращаемая максимальная мощность равна числу людей, вы знаете, что назначение возможно для всех.

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

На практике я начал использовать венгерский алгоритм, и потребовалось ~ 30 секунд для выполнения на моем конкретном наборе данных. После его переключения для алгоритма Hopcroft-Karp я мог бы получить тот же результат в < 1 секунду.