Алгоритм заполнения матрицы элемента, пары элементов

Question

Эй, ребята, у меня есть приложение типа скоростного знакомства ( не используется для знакомства, просто похожая концепция ), которое сравнивает пользователей и сопоставляет их в раундовом событии.

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

For example with a setup like so (assuming 6 users, 3 from each group)

Round (User1, User2)
----------------------------
1  (x1,y1)  (x2,y2)  (x3,y3)
2  (x1,y2)  (x2,y3)  (x3,y1)
3  (x1,y3)  (x2,y1)  (x3,y2)

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

My current algorithm

Я сохраняю сравнение каждого пользователя от x с каждым пользователем от y, вот так

Round, user1, user2, similarity

И чтобы построить расписание событий, я просто сортирую сравнения по сходству, а затем перебираю результаты, находя открытый раунд для обоих пользователей, например:

event.user_maps.all(:order => 'similarity desc').each do |map|
  (1..event.rounds).each do |round|
    if user_free_in_round?(map.user1) and user_free_in_round?(map.user2)
      #creates the pairing and breaks from the loop
    end
  end
end

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

EDIT

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

Вот так:

Round (User1, User2)
----------------------------
1  (x1,y1)  (x2,y2)  (x3,y3)
2  (x1,y3)  (x2,nil)  (x3,y1)
3  (x1,y2)  (x2,y1)  (x3,y2)

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

В реальных сценариях гораздо больше совпадений, чем доступных раундов и неравное количество x пользователей для y пользователей, и в моих тестовых примерах вместо заполнения каждого раунда у меня будет заполнено только около 90% или около того, пока столкновения, подобные приведенным выше, вызывают проблемы.

Answer 1

Я думаю, что вопрос все еще нуждается в разъяснении даже после редактирования, но я мог что-то упустить.

Насколько я могу судить, вы хотите, чтобы каждый новый раунд начинался с наилучшего возможного соответствия (определяется как сумма косинусных сходств всех совпадающих пар).После того, как любая пара (x_i, y_j) была подобрана в раунде, они не могут участвовать в следующем раунде.

Вы можете сделать это, построив двудольный граф, где ваши X - это узлы в одной стороне, а Y -узлы в другую сторону, а вес ребра имеет косинусное сходство.Затем вы найдете максимальное взвешенное соответствие на этом графике.В следующих раундах вы удаляете ребра, которые уже использовались в предыдущем раунде, и снова запускаете алгоритм сопоставления.Подробнее о том, как кодировать сопоставление максимального веса в двудольном графе, см. здесь .

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

Answer 2

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

Тем не менее, мне нужно больше информации о компромиссах, которые вы хотели бы сделать (и, возможно, я просто что-то упустил в вашем вопросе). Каковы явные цели алгоритма?

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

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