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

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 

хранить сравнение каждого пользователя от й для каждого пользователя от у, как так

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 для пользователей и в моих тестовых случаях, а не для заполнения каждого раунда. Я буду иметь около 90% в то время как столкновения, подобные описанным выше, вызывают проблемы.

Answer 1

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

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

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

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

Answer 2

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

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

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

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