两个向量之间的唯一元素配对最大化总和

Question

我有一个数据框，其中包含两个向量元素之间的所有可能组合，并且对于每个组合，我都有一个相应的分数。我试图找到一种有效的方法来找到具有唯一元素的唯一对的子集（即，来自一个向量的元素在所有对中只能找到一次），从而最大化对应于每个组合的分数总和。作为示例数据，考虑这个 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。你有什么建议吗？提前致谢！

Answer 1

好吧，我最终找到了基于 clue R 包的 solve_LSAP 函数中实现的 Hungarian algorithm 的解决方案。要使其正常工作，请将您的 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！

两个向量之间的唯一元素配对最大化总和

Unique element pairing between two vectors maximizing the overall sum

r

unique-constraint

maximization

pairing