Подтвердить что ты не робот

Найти наибольший кубоид, содержащий только 1 в двоичном массиве NxNxN

Учитывая двоичный массив NxNxN (содержащий только 0 или 1), как мы можем получить наибольший кубоид с нетривиальным решением, т.е. в O (N ^ 3)?

-

Это та самая проблема, что Найти большой прямоугольник, содержащий только нули в двоичной матрице N × N, но в верхнем измерении. Кроме того, в моем случае наибольший прямоугольник может "пересекать край" массива, т.е. Пространство подобно тору для двумерной матрицы.

Для двумерного массива, если запись:

00111
00111
11000
00000
00111

решение, изображенное "X", равно

00XXX
00XXX
11000
00000
00XXX

Я выполнил вычисление для двоичного массива NxN и нашел решение для самой большой проблемы прямоугольника в O (N ^ 2), следуя идее в http://tech-queries.blogspot.de/2011/03/maximum-area-rectangle-in-histogram.html. Но я не знаю, как применить его для 3D-массива.

-

Пример для массива 3x3x3, где решение "пересекает край":

111
100
011

111
001
111

011
110
011

решение должно быть:

1XX
100
0XX

1XX
001
1XX

0XX
110
0XX
4b9b3361

ОТВЕТЫ

Ответ 1

Здесь только O (N ^ 4).

Предположим, что вы храните кубиок в bool cuboid [N] [N] [N];

bool array2d[N][N];

for(int x_min = 0; x_min < N; x_min++) {
   //initializing array2d
   for(int y = 0; y < N; y++) {
      for(int z = 0; z < N; z++) {
         array2d[y][z] = true;
      }
   }

   //computation
   for(int x_max = x_min; x_max < N; x_max++) {
      // now we want to find largest cube that
      // X coordinates are equal to x_min and x_max

      // cells at y,z can be used in cube if and only if
      // there are only 1 in cuboid[x][y][z] where x_min <= x <= x_max

      // so lets compute for each cell in array2d,
      // if are only 1 in cuboid[x][y][z] where x_min <= x <= x_max
      for(int y = 0; y < N; y++) {
         for(int z = 0; z < N; z++) {
            array2d[y][z] &= cubiod[x_max][y][z];
         }
      }

      //you already know how to find largest rectangle in 2d in O(N^2)
      local_volume = (x_max - x_min + 1) * find_largest_area(array2d);

      largest_volume = max(largest_volumne, local_volume);
   }
}

Вы можете использовать тот же трюк, чтобы вычислить лучшее решение в X-размерах. Просто уменьшите проблему до размеров X-1. Сложность: O (N ^ (2 * X-2)).

Ответ 2

Это решение имеет сложность O (N 3 log 2 N) (может быть оптимизирована до O (N 3 log N)). Требуется дополнительный целочисленный массив размером 2 * 8 * N 3.

  • Вычислить r (i, j, k): для каждой из строк N 2 вычислить суммарную сумму всех ненулевых элементов, сбросив ее, когда найден нулевой элемент.
  • Выполните следующие шаги для различных значений K, используя Поиск в золотом сечении (или поиск по Фибоначчи), чтобы найти максимальный результат.
  • Вычислить c (i, j, k): для каждой из столбцов N 2 вычислить суммарную сумму всех элементов с r (i, j, k) >= K, сбросив ее, когда элемент с r (i, j, k) K. Для хорошей визуализации шагов 1 и 2 см. этот ответ.
  • Выполните последний шаг для различных значений M, используя поиск в золотом сечении, чтобы найти максимальный результат.
  • Вычислить сумму: для каждого из значений N 2 3-й координаты вычислите суммарную сумму всех элементов с c (i, j, k) >= M, сбросив ее, когда элемент с c (i, j, k) M. Вычислить sumKM и обновить наилучшее до сих пор результат, если это необходимо.

"пересечь границу" свойство массива обрабатывается очевидным образом: повторяйте каждый индекс дважды и сохраняйте все суммарные суммы не более N.

В многомерном случае этот алгоритм имеет O (N D log D-1 N) временную сложность и O (D * N D) сложность пространства.

Оптимизация до O (N 3 log N)

Шаг 4 алгоритма устанавливает глобальное значение для M. Этот шаг может быть исключен (и сложность уменьшена на log N), если значение для M определяется локально.

Чтобы сделать это, шаг 5 должен быть улучшен. Он должен поддерживать двухстороннюю очередь (глава которой содержит локальное значение M) и стек (сохраняя начальные позиции для всех значений M, выведенных из очереди).

В то время как c (i, j, k) увеличивается, он добавляется к хвосту очереди.

Если c (i, j, k) уменьшается, все большие значения удаляются из хвоста очереди. Если он еще больше уменьшается (очередь пуста), стек используется для восстановления значения "sum" и помещает соответствующее значение "M" в очередь.

Затем несколько элементов могут быть удалены из головы очереди (и помещены в стек), если это позволяет увеличить значение локального решения.

Для многомерного случая эта оптимизация дает сложность O (N D log D-2 N).