我有一个数值矩阵,需要提取最大可能总和的元素集,但限制为不能选择同一行或列中的任意两个元素。是否有适用于此问题的高效算法,并且是否有R语言实现该算法的方法?
例如,如果矩阵是(使用R的矩阵表示法):
若矩阵求解的结果唯一,则为
然后有三个同等好的解决方案:1,8,9;3,6,9;和5,6,7。它们总和为18。
额外注意事项:
- 如果有多个同样好的解决方案,我需要找到所有的解决方案。(能够找到几乎同样好的额外解决方案也很有用,但不是必要的。) - 矩阵元素都是非负数,其中许多将为零。每行和每列至少包含一个非零元素。 - 矩阵可以包含重复元素。 - 矩阵不一定是方阵。它可能有更多的行而不是列,或反之,但约束始终相同:不能重复使用任何行或列。 - 这个问题也可以重新制定为在不重复使用任何节点的情况下,在二分图的两个部分之间找到一组最大得分的边集合。 - 如果有帮助的话,您可以假设存在某个小的固定k,使得没有行或列包含超过k个非零值。
如果有人感兴趣,矩阵的行表示要标记的项目,列表示标签,每个矩阵元素表示为将标签分配给项目的“一致性得分”。我想以最大化总一致性的方式将每个标签分配给恰好一个项目。
例如,如果矩阵是(使用R的矩阵表示法):
[,1] [,2] [,3]
[1,] 7 1 9
[2,] 8 4 2
[3,] 3 6 5
若矩阵求解的结果唯一,则为
[1,3], [2,1], [3,2]
,其中包含数字9,8和6,总和为23。但是,如果矩阵为: [,1] [,2] [,3]
[1,] 6 2 1
[2,] 4 9 5
[3,] 8 7 3
然后有三个同等好的解决方案:1,8,9;3,6,9;和5,6,7。它们总和为18。
额外注意事项:
- 如果有多个同样好的解决方案,我需要找到所有的解决方案。(能够找到几乎同样好的额外解决方案也很有用,但不是必要的。) - 矩阵元素都是非负数,其中许多将为零。每行和每列至少包含一个非零元素。 - 矩阵可以包含重复元素。 - 矩阵不一定是方阵。它可能有更多的行而不是列,或反之,但约束始终相同:不能重复使用任何行或列。 - 这个问题也可以重新制定为在不重复使用任何节点的情况下,在二分图的两个部分之间找到一组最大得分的边集合。 - 如果有帮助的话,您可以假设存在某个小的固定k,使得没有行或列包含超过k个非零值。
如果有人感兴趣,矩阵的行表示要标记的项目,列表示标签,每个矩阵元素表示为将标签分配给项目的“一致性得分”。我想以最大化总一致性的方式将每个标签分配给恰好一个项目。
m <= n
而不失一般性,因为如果您转置矩阵,则问题仍然相同。 - Ryan C. Thompsonn!
种方式会产生相同的结果。由于在平局情况下您想要全部结果,因此最好的方法是指数级的蛮力计算。 - user58697k!
种方式。如果这是可以接受的,那么再次尝试暴力破解它,也许会有所帮助。 - user58697