最大化矩阵中"非重叠"数字的总和

Question

只是寻找一些方向,我意识到给出的例子可以使用强力迭代来解决,但我正在寻找一个更优雅(即数学？)解决方案,它可以解决更大的例子(比如20x20或30x30) ).完全有可能无法做到这一点,而且我在提出一种不依赖蛮力的方法方面收效甚微......

我有一个矩阵(称之为A),它是nxn.我希望从矩阵A中选择一个子集(称之为B).子集将由n个元素组成,其中从每一行和A的每一列中取出一个且只有一个元素.输出应提供解决方案( B)使得构成B的元素的总和是给定这些约束的最大可能值(例如,在下面的示例中为25).如果找到B的多个实例(即,给出相同最大总和的不同解),则应选择具有最大最小元素的B的解.

B也可以是n×n的选择矩阵,但是只有n个期望的元素是非零的.

例如:如果A =

|5 4 3 2 1|
|4 3 2 1 5|
|3 2 1 5 4|
|2 1 5 4 3|
|1 5 4 3 2|

=> B会的

|5 5 5 5 5|

但是,如果A =

|5 4 3|
|4 3 2|
|3 2 1|

B =

|3 3 3|

因为B的最小元素是3,它大于

|5 3 1|

要么

|4 4 1|

这也是9的总和

Answer 1

您的问题几乎与分配问题相同,例如可以通过匈牙利算法在多项式时间内解决.

请注意,赋值问题通常是最小化问题,但是将矩阵乘以-1并添加一些常量应该使该方法适用.此外,对于多个最优解的情况,没有正式的制动条件.但是,该方法可以为您提供具有最佳总和的解决方案.设m是最小加数.通过将所有小于或等于m的条目设置为零来修改矩阵,然后再次求解.你要么得到一个比上一个更好的总和的解决方案.如果没有,先前的解决方案已经是最佳的.