Полиномиальный алгоритм спаривания пользователя времени

Question

У меня проблема. Рассмотрим пользователей с разным весом, которые зависят от текущего канала .i.e. если канал хороших весов высок. Мне приходилось спаривать пользователей таким образом, чтобы общий вес системы был максимальным. Я расскажу об этом. Рассмотрим 4 канала и 8 пользователей, теперь я должен разместить парных пользователей в каждом канале таким образом, чтобы общая сумма весов была максимальной, и все пользователи должны быть сопряжены. Пожалуйста, предложите несколько полиномиальных алгоритмов времени, отличных от оптимальной (грубой силы), которая становится сложной, когда число пользователей велико, что очень помогло бы мне.

Thanks and regards, srinu.

Answer 1

Владимир Колмогоров опубликовал в 2009 году Blossom V: a new implementation of a minimum cost perfect matching algorithm, который предоставляет полиномиальный алгоритм для «задачи вычисления идеального соответствия минимальной стоимости в неориентированном взвешенном графе».

Изменение максимальной стоимости тривиально, изменяя знак ваших весов.

Этот алгоритм имеет наихудшую сложность O (n^3m) (но для типичных примеров часто намного быстрее). n - количество узлов, а m - количество ребер. В вашем случае я считаю, что все n^2 ребра присутствуют, поэтому сложность O (n^5).

Быстрые алгоритмы, если ваш граф двудольный (например, пользователи делятся на две категории, такие как мужчина и женщина, где вы всегда должны соответствовать мужчине с женщиной), но я не верю, что это так?

Программная реализация этого алгоритма here.