最大化的总和＆QUOT;非重叠＆QUOT;从矩阵号码 [英] Maximise sum of "non-overlapping" numbers from matrix

问题描述

只是找了一下方向，我认识到，给出的例子是可能使用蛮力迭代来解决，但我要寻找一个更优雅（即数学？）解决方案，它可能会解决显著大规模的例子（比如20×30×30或）。这是完全可能的，这不能做，和我有非常小的成功，在未来与不靠蛮力的方法...

Just looking for a bit of direction, I realise that the example given is possible to solve using brute force iteration, but I am looking for a more elegant (ie. mathematical?) solution which could potentially solve significantly larger examples (say 20x20 or 30x30). It is entirely possible that this cannot be done, and I have had very little success in coming up with an approach which does not rely on brute force...

我有一个矩阵（称为A），它是n×n的。我想选择的子集点（称之为B）的矩阵A的子集将包括n个元素，其中一个且仅一个元件是取自每个行和从A的各列的输出应提供的溶液（乙），使得构成B中的元素的总和为最大可能值，给定这些约束条件（在下面的例子中，例如25）。如果乙的多个实例被发现（即不同的解决方案，从而使该相同的最大总和）的溶液B，其具有应选择最大的最小元素。

I have a matrix (call it A) which is nxn. I wish to select a subset (call it B) of points from matrix A. The subset will consist of n elements, where one and only one element is taken from each row and from each column of A. The output should provide a solution (B) such that the sum of the elements that make up B is the maximum possible value, given these constraints (eg. 25 in the example below). If multiple instances of B are found (ie. different solutions which give the same maximum sum) the solution for B which has the largest minimum element should be selected.

乙也可以是选择矩阵是n×n个，但其中只有n个所需的元素为非零。

B could also be a selection matrix which is nxn, but where only the n desired elements are non-zero.

例如： 如果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.将

=> B would be

|5 5 5 5 5|

然而，如果A =

However, if A =

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

B =

|3 3 3|

作为B的最小元素是3，其比

As the minimum element of B is 3 which is larger than for

|5 3 1|

或

|4 4 1|

这也是两者之和为9

which also both sum to 9

推荐答案

您的问题是几乎相同的分配问题 ，其可以例如由匈牙利算法在多项式时间内解决。

Your problem is almost identical to the Assignment problem, which can e.g. be solved by the Hungarian algorithm in polynomial time.

请注意，该分配问题通常是一个最小化的问题，而是你的矩阵相乘-1再加入一些常数应使该方法适用。此外，没有正式的领带制动工况，对案件多的最佳解决方案。然而，该方法产生具有你最优总和的溶液。令m的最小加数。通过设置所有条目小于或等于m为零，再次解决修改矩阵。无论你用相同的金额比最后一个更好的解决方案。如果不是，则previous溶液已经最优

Note that the assignment problem is usually a minimization problem, but multiplying your matrix with -1 and adding some constant should make the method applicable. Further, there is no formal tie-braking condition, for case of multiple optimal solutions. However, the method yields you a solution having the optimal sum. Let m be the minimum summand. Modify your matrix by setting all entries less or equal to m to zero and solve again. Either you get a solution with the same sum that is better than the last one. If not, the previous solution was already optimal.

这篇关于最大化的总和＆QUOT;非重叠＆QUOT;从矩阵号码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！