solved-从受最大化约束的矩阵中查找逐列的最大元素

Question

我有一个由随机正数组成的N x N平方矩阵A。我有一个函数需要最大化(为了简单起见，考虑它对所有输入求和(，它的输入是矩阵每列中的一个元素。约束条件是每个输入的位置应该不同。例如，N=5

A =
0.43207      0.53996      0.68063      0.70952       0.6297
0.9656      0.72609      0.88174      0.50072      0.41381
0.47571      0.99827     0.061184      0.93099      0.88015
0.98318      0.42879      0.56813       0.3835    0.0039668
0.30498      0.30033      0.76003      0.80426      0.84147
best =
4     3     2     1     5
bestA =
0.98318      0.99827      0.88174      0.70952      0.84147

现在我正在检查所有可能的组合。但随着矩阵大小的增加，例如N=10，搜索空间变为10！这对我的要求来说太贵了。我试图对矩阵进行排序并寻找模式，但我遇到了重复的情况，在排序后可以看到这种情况。

>> [Asorted,I] = sort(A,1,'descend')
Asorted =
0.98318      0.99827      0.88174      0.93099      0.88015
0.9656      0.72609      0.76003      0.80426      0.84147
0.47571      0.53996      0.68063      0.70952       0.6297
0.43207      0.42879      0.56813      0.50072      0.41381
0.30498      0.30033     0.061184       0.3835    0.0039668
I =
4     3     2     3     3
2     2     5     5     5
3     1     1     1     1
1     4     4     2     2
5     5     3     4     4

我能遵循什么算法或直觉吗？

我用的是MATLAB，但你可以用任何流行的编程语言来解释。

编辑：矩阵已经给定，它是随机生成的。主要目标是最大化我上面提到的给定函数的输出，并找出输出最大的输入是什么。

编辑2：上面示例的MATLAB代码示例

N=5;
A = rand(N,N)
combs = perms(1:N);
Sbest = -1;
for i=1:size(combs,1)
x = combs(i,:);
S = 0;
for i=1:N
S=S + A(x(i),i); 
end
if S>Sbest
Sbest=S; best = x;
end
end
best
[Asorted,I] = sort(A,1,'descend')

解决方案：正如@在评论中指出的，这可以使用匈牙利算法来解决。这里有一些资源，matlab代码

Answer 1

关于算法，我怀疑可能有必要通过所有组合来找到最好的，即暴力。我不确定是否有任何图论算法直接适用于这个问题，但也许一些修改后的算法可以工作。

从加速的角度来看，也许你可以通过用sum代替内部的for环路来加速，即

for i=1:size(combs,1)
x = combs(i,:);
S = sum(A(((1:N)-1)*N + x));
if S > Sbest
Sbest=S; 
best = x;
end
end