在NxNxN二进制数组中查找仅包含1的最大长方体 [英] Find largest cuboid containing only 1's in an NxNxN binary array

问题描述

给定一个NxNxN二进制数组(仅包含0或1)，如何用非平凡的解(即O(N ^ 3))获得最大的长方体?

Given an NxNxN binary array (containing only 0's or 1's), how can we obtain the largest cuboid with a non-trivial solution i.e. in O(N^3) ?

-

与查找相同的问题N×N二进制矩阵中最大的矩形，仅包含零，但尺寸较大. 另外，以我为例，最大的矩形可以越过数组的边缘"，即该空间就像2D矩阵的圆环.

It is the same problem that Find largest rectangle containing only zeros in an N×N binary matrix but in an upper dimension. Also, in my case, the largest rectangle can "cross the edge" of the array i.e. the space is like a torus for a 2D matrix.

对于2D数组，如果输入为:

For a 2D array, if the entry is :

00111
00111
11000
00000
00111

用'X'表示的解决方案是

the solution depicted by 'X' is

00XXX
00XXX
11000
00000
00XXX

我已经完成了一个NxN二进制数组的计算，并遵循

I've done the computation for a NxN binary array and find a solution for the largest rectangle problem in O(N^2) by following the idea in http://tech-queries.blogspot.de/2011/03/maximum-area-rectangle-in-histogram.html. But I don't know how to apply it for a 3D array.

-

3x3x3数组的示例，其中解决方案穿过边缘":

Example for a 3x3x3 array where the solution "cross the edge":

111
100
011

111
001
111

011
110
011

解决方案应该是:

1XX
100
0XX

1XX
001
1XX

0XX
110
0XX

推荐答案

此解决方案具有O(N ³ log ² N)复杂度(可以优化为O( N ³ 记录N)).需要额外的大小为2 * 8 * N ³ 的整数数组.

This solution has O(N³ log² N) complexity (may be optimized to O(N³ log N)). Additional integer array of size 2*8*N³ will be needed.

1. 计算r(i，j，k):对于N ² 行中的每行，计算所有非零元素的累积和，在找到零元素时将其重置.
2. 使用黄金分割搜索(或斐波那契搜索)以找到最大结果.
3. 计算c(i，j，k):对于N ² 列中的每列，计算r(i，j，k)> = K的所有元素的累加总和，并在出现以下情况时将其重置r(i，j，k)<的元素找到K.为了对步骤1和步骤2进行良好的可视化，请参见此答案.
4. 使用黄金分割搜索找到最大结果，对M的各个值执行最后一步.
5. 计算总和:对于第三个坐标的N ² 个值中的每一个，计算c(i，j，k)> = M的所有元素的累积总和，当具有c (i，j，k)<找到M.计算sum K M，并在必要时更新迄今为止最好的结果.

1. Compute r(i,j,k): for each of the N² rows, compute cumulative sum of all non-zero elements, resetting it when a zero element is found.
2. Perform the following steps for various values of K, using Golden section search (or Fibonacci search) to find the maximum result.
3. Compute c(i,j,k): for each of the N² columns, compute cumulative sum of all elements with r(i,j,k) >= K, resetting it when an element with r(i,j,k) < K is found. For good visualization of steps 1 and 2, see this answer.
4. Perform the last step for various values of M, using Golden section search to find the maximum result.
5. Compute sum: for each of the N² values of 3rd coordinate, compute cumulative sum of all elements with c(i,j,k) >= M, resetting it when an element with c(i,j,k) < M is found. Calculate sumKM and update the best so far result if necessary.

数组的"cross the edge"属性的处理方式很明显:将每个索引重复两次，并使所有累积和不大于N.

"cross the edge" property of the array is handled in obvious way: iterate every index twice and keep all cumulative sums not larger than N.

对于多维情况，此算法具有O(N ^D log ^D-1 N)时间复杂度和O(D * N ^D )的空间复杂度.

For multidimensional case, this algorithm has O(N^D log^D-1 N) time complexity and O(D*N^D) space complexity.

算法的第4步设置M的全局值.如果在本地确定M的值，则可以排除此步骤(并且复杂度降低 log N ).

Step 4 of the algorithm sets a global value for M. This step may be excluded (and complexity decreased by log N) if value for M is determined locally.

为此，应该改进步骤5.它应该维护一个双端队列(其头部包含M的本地值)和一个堆栈(保持从队列中逐出的所有M值的起始位置).

To do this, step 5 should be improved. It should maintain a double-ended queue (head of which contains local value of M) and a stack (keeping starting positions for all values of M, evicted from the queue).

当c(i，j，k)增加时，它会附加到队列的尾部.

While c(i,j,k) increases, it is appended to the tail of the queue.

如果c(i，j，k)减小，则从队列尾部删除所有较大的值.如果它进一步减少(队列为空)，则使用堆栈来还原"sum"值并将相应的"M"值放入队列.

If c(i,j,k) decreases, all larger values are removed from the queue's tail. If it decreases further (queue is empty), stack is used to restore 'sum' value and put corresponding 'M' value to the queue.

然后，如果这可以增加本地解决方案的价值，则可以从队列的开头删除几个元素(并将其推入堆栈).

Then several elements may be removed from the head of the queue (and pushed to the stack) if this allows to increase local solution's value.

对于多维情况，此优化使O(N ^D log ^D-2 N)复杂性.

For multidimensional case, this optimization gives O(N^D log^D-2 N) complexity.

这篇关于在NxNxN二进制数组中查找仅包含1的最大长方体的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！