矩阵的总和之间的差异最小

为了得到子矩阵之和的最小差值，我必须找出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 x 4 x 4 = 64个可允许的分区。

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

实际的矩阵可能高达4000 x 4000。

---

蛮力有一些加速。 首先，通过沿行和列累积和数，你可以建立一个表格，为每个点提供所有点的总和，包括那个点，不会比它更远，也不会比它更远。 然后，您可以通过减去至多四个小计来计算任意矩形中的总和：粗略地说，右上角的总和加上左下角的总和减去其他两个角的总和。

对于OP的分割模式，用水平线分割整个矩阵，然后在每一半分割不同的垂直线，垂直分割必须是它们一半的最均匀的垂直分割。 如果总和之间的最大差异在垂直分割内，那么垂直分割只能改善它。 如果总和之间的最大差值介于（例如）左上角的高位和右下角的低位之间，那么平衡任一垂直分割都会使高位总数减少或低位总数增加最极端的区别。 这意味着你只需要考虑上半部分的最佳分割和下半部分的最佳分割 - 你不需要考虑所有的分割对。

对于在水平分割的同一侧有两个垂直分割的情况，您不必尝试垂直分割的所有位置对：您可以从最左边的最左边的分割开始，并调整最右边的分割尽可能均匀地将余数切成两半。 然后将最左侧的分割线缓慢地移到右侧，并且如此，最右侧的分割线可以重复调整以向右移动，以便尽可能均匀地分割剩余分割线。

使用这些想法，在我看来，对于每个可能的分割模式，给定该模式中最长线的位置（对于方形矩阵而言为O（N）），您可以及时找到该模式的最小成本分割的边N，因此N个位置的最长直线是O（N ^ 2），这大约与在每个点的左下方建立一个点总和表所需的时间相同时间线性矩阵中的单元格总数，或O（N ^ 2）的方阵N的一个方阵。 - 但它是令人讨厌的，似乎有六个不同的分割模式。

链接地址: http://www.djcxy.com/p/19151.html

上一篇: matrices with lowest difference between their sum

下一篇: How to calculate struct padding in c++11 during compile time?