将矩阵拆分为4个子矩阵,其总和之间的差异最小

Question

我必须找到4个子矩阵的总和之间的差异,这是在以任何方式分割矩阵A之后得到的,以便获得子矩阵之和之间的最小差异.

例如,对于矩阵A,

 3   0   2  -8  -8
 5   3   2   2   3
 2   5   2   1   4
 3   4  -1   4   2
-3   6   2   4   3

我可以像这样分开它:

 3 | 0   2  -8  -8
 5 | 3   2   2   3
 2 | 5   2   1   4
 -------------------
 3   4  -1 |  4  2
-3   6   2 |  4  3

每个子矩阵内所有元素的总和给出以下结果:

10 | 8
-------
11 | 13

然后,我计算总和之间所有可能的绝对差异,即

abs(10 - 8)  = 2
abs(10 - 11) = 1
abs(10 - 13) = 3
abs(8 - 11)  = 3
abs(8 - 13)  = 5
abs(11 -13)  = 2

最后,我选择了最大距离,即5.

但是,如果我以任何其他方式分割矩阵A,它将给出不同的最大距离,这是我不想要的.我必须找到5,但如果我要做这种蛮力,我只是花太多时间寻找所有可能性.这个问题有名字,或者你可以给我一个提示吗？

添加

允许的分割是水平分割,然后是上方的垂直分割,水平分割下方可能有不同的垂直分割.在该示例中,矩阵的4×4×4 = 64个允许分区.

通过考虑该分区的4个子矩阵的所有对(将有6个这样的对)形成特定分区的子矩阵之间的最大差异,并且取该对子矩阵之一的子元素的总和之间的最大差异.以及该对的另一个子矩阵的元素之和.我们希望找到所有最大差异的最小值.

实际矩阵可能高达4000 x 4000.

Answer 1

与蛮力相比，有一些加速。首先，通过沿行累加总和，然后向下累加列，您可以构建一个表格，为每个点提供所有点（包括该点）的总和，不比它更靠前，也不比它更靠右。然后，您可以通过减去最多四个小计来计算任何矩形中的总和：粗略地说，是右上角的总和加上左下角的总和减去其他两个角的总和。

对于OP绘制的分割模式，用一条水平线分割整个矩阵，然后用不同的垂直线分割每一半，垂直分割必须是其一半中最均匀的垂直分割。如果总和之间最极端的差异是在垂直分割内，则晚上垂直分割只能改善它。如果总和之间最极端的差异是在（例如）左上角的高总和和右下角的低总和之间，则平分任一垂直分割都会使高总和下降或将低总和向上，平分最极端的差异。这意味着您只需要考虑上半部分的最佳分割和下半部分的最佳分割 - 您不需要考虑所有的分割对。

对于水平分割的同一侧有两个垂直分割的情况，您不必尝试垂直分割的所有位置对：您可以从最左边的最左边的分割开始，然后调整最右边的分割将剩余的尽可能均匀地切成两半。然后将最左边的分割慢慢向右移动，同时，可以反复调整最右边的分割向右移动，以保持尽可能均匀地分割剩余部分。

使用这些想法，在我看来，对于每个可能的分割模式，您可以在给定该模式中最长线的位置的情况下及时找到该模式的最小成本分割，对于方阵来说是 O(N) N 边，因此最长的线有 N 个位置，即 O(N^2)，这与构建每个点下方和左侧的点总和表所需的时间大致相同，这需要时间与矩阵中的单元总数呈线性关系，或者对于 N 边的方阵而言为 O(N^2)。 - 但令人烦恼的是，似乎有六种不同的分割模式。