十二分的追求 发表于 2014-9-6 10:59

13*20矩阵最小和

      每行选一个，每列只能选一个（即不同行不同列，选13个数值的和最小），怎么做？最好MATLAB的解决方案。（菜鸟）
谢谢！！！

847717213 发表于 2014-9-7 00:54

我大概是这么想的，穷举的话应该需要20！/7！，量级挺大。现成的算法也没想到能套用上的。
可以尝试如下算法：
1找出每行最小值
2将每行元素都减去每行最小值，得出损失矩阵（即，若不用最小值会损失多少）
3对损失矩阵中次小元素（即除了0以外的最小元素）进行排序，得出最大的元素所在行，将最小元素定下来，作为结果集合中的元素
4然后将3中最小元素所在行和列都填成一个极大值，比如远远超过矩阵中最大值的一个值。
5对A进行1-4步骤直至A矩阵只剩一个元素
应该可以求出一个较优解，是不是最优很难说，需要证明
(matlab算法及编程咨询，画图，解方程组，最优化：http://shop108557885.taobao.com)

847717213 发表于 2014-9-7 00:55

我大概是这么想的，穷举的话应该需要20！/7！，量级挺大。现成的算法也没想到能套用上的。
可以尝试如下算法：
1找出每行最小值
2将每行元素都减去每行最小值，得出损失矩阵（即，若不用最小值会损失多少）
3对损失矩阵中次小元素（即除了0以外的最小元素）进行排序，得出最大的元素所在行，将最小元素定下来，作为结果集合中的元素
4然后将3中最小元素所在行和列都填成一个极大值，比如远远超过矩阵中最大值的一个值。
5对A进行1-4步骤直至A矩阵只剩一个元素
应该可以求出一个较优解，是不是最优很难说，需要证明
(matlab算法及编程咨询，画图，解方程组，最优化：shop108557885.taobao.com)

啊nong 发表于 2014-9-7 08:49

可以参考0——1规划问题   

梦@di?~ 发表于 2014-9-8 13:33

A=; %换成相应要求的矩阵
=size(A);
s=0;
for i=1:n
    b(i,1)=0;
    b(i,2)=max(A(i,:));
    for j=1:m
        while (A(i,j)<b(i,2) && b(i,2)~=j)  %满足最小且不同列
            b(i,2)=A(i,j);
            b(i,1)=j;
        end
    end
    s=s+b(i,2);
end
s

mingtingqing 发表于 2014-10-6 15:29

可以参考下2楼的想法
页: [1]
查看完整版本: 13*20矩阵最小和