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

本文介绍了最大化“非重叠"的总和矩阵中的数字的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

只是寻找一些方向，我意识到给出的示例可以使用蛮力迭代来解决，但我正在寻找一个更优雅的(即数学?)解决方案，它可能会解决更大的示例(比如20x20 或 30x30).这完全有可能无法做到，而且我在想出一种不依赖蛮力的方法方面几乎没有成功......

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

B 也可以是一个 nxn 的选择矩阵，但其中只有 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 将是

|5 5 5 5 5|

然而，如果 A =

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

B =

|3 3 3|

因为 B 的最小元素是 3 比 for 大

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

|5 3 1|

或

|4 4 1|

两者的总和为 9

推荐答案

您的问题几乎与 Assignment 相同问题，例如由匈牙利算法在多项式时间内求解.

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 的条目设置为零来修改矩阵并再次求解.要么你得到一个总和比上一个更好的解决方案.如果不是，则之前的解决方案已经是最优的.

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.