Блог

Главная - Вопросы по программированию - Уникальное сопряжение элементов между двумя векторами, максимизирующее общую сумму

Уникальное сопряжение элементов между двумя векторами, максимизирующее общую сумму

#r #unique-constraint #pairing #maximization

#r #уникальное ограничение #сопряжение #максимизация

Вопрос:

У меня есть фрейм данных, который содержит все возможные комбинации между элементами двух векторов, и для каждой комбинации у меня есть соответствующая оценка. Я пытался найти эффективный способ найти подмножество уникальных пар с уникальными элементами (т. Е. элемент из одного вектора может быть найден только один раз во всех парах), который максимизирует сумму баллов, соответствующую каждой комбинации. В качестве примера данных рассмотрим это df :

 df = data.frame(Var1 = c("A", "B", "C"), Var2 = c("A", "C", "D"))
df = expand.grid(df$Var1, df$Var2)
df$score = c(1, 0.5, 2, 1, 0.5, 0.5, 1, 2, 1)
> df
  Var1 Var2 score
1    A    A   1.0
2    B    A   0.5
3    C    A   2.0
4    A    C   1.0
5    B    C   0.5
6    C    C   0.5
7    A    D   1.0
8    B    D   2.0
9    C    D   1.0
>

Ожидаемый результат будет: 

 A  C  1
B  D  2
C  A  2

Обратите внимание, что элементы двух векторов могут перекрываться, но, опять же, каждый элемент из каждого вектора должен появляться только один раз. Кроме того, пара A A 1 разрешена и была бы возможна, но это сделало бы невозможным создание пары, C A 2 которая увеличила бы общую сумму score .
В качестве попытки я использовал этот один вкладыш с функциональностью из dplyr 

 df <- df %>% group_by(Var1) %>% slice(which.max(score)) %>% as.data.frame()

которое производит: 

 > df
  Var1 Var2 score
1    A    A     1
2    B    D     2
3    C    A     2

что достаточно близко.. но A из второго вектора повторяется. У вас есть какие-либо предложения? Заранее благодарю вас!

Комментарии:

1. У вас есть связь, и она выбрала первую запись, вот почему она выбрала A A

2. Да, это я понял. Это which.max поведение, но мне нужно преодолеть это, и я пытался избежать написания какой-либо рекурсивной функции для выполнения этой работы. Пытался также преобразовать его в матрицу, в которой столбцы являются уникальными элементами из одного вектора, а строки — из других, но затем я застрял, извлекая пары строка-столбец, максимизирующие сумму

Ответ №1:

Что ж, в конечном итоге я нашел решение, основанное на венгерском алгоритме, реализованном в solve_LSAP функции clue пакета R. Чтобы это работало, преобразуйте свой df в матрицу следующим образом:

 df = matrix(sapply(df$score, function(x) x), nrow=length(unique(df$Var1)), ncol=length(unique(df$Var2)), dimnames = list(unique(df$Var1), unique(df$Var2)))

и примените функцию

 df.res = solve_LSAP(df, maximum = T)
> df.res
Optimal assignment:
1 => 2, 2 => 3, 3 => 1

а затем верните фактические узлы или имена

 df.res = cbind(rownames(df), colnames(df)[df.res])
> df.res
     [,1] [,2]
[1,] "A"  "C" 
[2,] "B"  "D" 
[3,] "C"  "A" 
>

Tadaaaaam!