Алгоритм для нахождения минимального количества прямоугольников, покрывающих определенные элементы в массиве 2d

Упрощенный, мне нужно решить следующую проблему:

У вас есть двумерный массив, заполненный 0s и 1s. Найдите минимальное количество прямоугольников, чтобы они покрывали все 1s. Прямоугольники не должны перекрываться.

Подпись функции может выглядеть так: List<Rectangle> FindCoveringRectangles(bool[,] array)

У меня уже есть решение, которое "достаточно хорошо", но не всегда находит минимальное количество прямоугольников. Я хотел бы знать, есть ли какой-нибудь известный и эффективный алгоритм, который может быть применен для решения этой проблемы?

Пример:

Входной массив:

..........
.1.....11.
.......11.
...111....
...111....
...111....
....1111..
....1111..
......11..
..........

(0s заменены точками для удобочитаемости)

Возможно, вы получите следующие прямоугольники:

(2,2,2,2),
(2,8,3,9),
(4,4,6,6),
(7,5,8,8),
(9,7,9,8)

(верхний, левый, нижний, правый), 1-основанный

Может быть несколько решений, но одного достаточно.

Ответ 1

Это подходящая проблема, которая могла бы легко показать NP-hard. Однако кажется, что на самом деле существует очень быстрое решение!

Используя заливку bfs, вы можете найти каждый подключенный компонент, O(n). Следовательно, wlog можно предположить, что нам просто нужно заполнить одну связанную область.

Если в этой области нет дыр, вы можете использовать алгоритм, описанный в этот документ (или здесь, в google Ученой.)

Предлагается алгоритм O (n log log n) для минимально прямоугольного разбиения простого прямолинейного многоугольника. Для любого простого прямолинейного многоугольника P видимая пара вершинного края представляет собой вершину и ребро, которое может быть связано горизонтальным или вертикальным отрезком линии, целиком лежащим внутри P. Показано, что если обнаружены видимые пары вершинного края, максимальное совпадение и максимальный независимый набор двудольного графа, полученного из хордов простого прямолинейного многоугольника, можно найти в линейном времени без построения двудольного графа. Используя этот алгоритм, задача минимального разбиения выпуклых прямолинейных многоугольников и вертикально (горизонтально) выпуклых прямолинейных многоугольников может быть решена в O (n) времени

Некоторые из упомянутых работ также охватывают случай с областью с отверстиями. Тем не менее, они выполняются в O (n ^ (3/2) logn), но они все еще довольно хороши.

В качестве альтернативы, одна вещь, которую вы можете сделать, это решить проблему без отверстий, решить проблему для каждого отверстия, а затем вычесть. Однако это может не дать оптимального решения, но будет поддерживать время выполнения.

Вы также можете попробовать и разбить фигуру в разных топологических частях, но это, вероятно, будет экспоненциально работать в количестве отверстий.

В-третьих, вы можете попытаться адаптировать предложенный алгоритм для более общего случая, но это может быть сложно.