Выберите прямоугольники для максимизации области

Question

У меня есть двумерная матрица произвольного размера. Я хочу найти набор прямоугольников в этой матрице, показывая максимальную площадь. Ограничения:

• Прямоугольники могут покрывать только поля «0» в матрице и «поля 1».
• Каждый прямоугольник должен иметь заданное расстояние от следующего прямоугольника.

Итак, позвольте мне проиллюстрировать это немного дальше от этой матрицы:

1 0 0 1 
0 0 0 0 
0 0 1 0 
0 0 0 0 
0 1 0 0 

Пусть минимальное расстояние между двумя прямоугольниками равен 1. Следовательно, оптимальным решением было бы, выбирая прямоугольники с углами (1 , 0) - (3,1) и (1,3) - (4,3). Эти прямоугольники минимальны. 1 друг от друга, и они не лежат на «1» -полях. Кроме того, это решение получило максимальную площадь (6 + 4 = 10).

Если минимальное расстояние будет равным 2, оптимальным будет (1,0) - (4,0) и (1,3) - (4,3) с площадью 4 + 4 = 8.

До сих пор я достиг, чтобы узнать, прямоугольники, аналогичные этому сообщению: Find largest rectangle containing only zeros in an N×N binary matrix

я сохранил все эти прямоугольники в списке:

list<rectangle> rectangles; 

с

struct rectangle { 
    int i,j; // bottom left corner of rectangle 
    int width,length; // width=size in neg. i direction, length=size in pos. j direction 
}; 

До сих пор , Я только думал о методах грубой силы, но, конечно, я не доволен этим.

Надеюсь, вы можете дать мне несколько советов о том, как найти соответствующие прямоугольники в моем list, и я надеюсь, что моя проблема будет понятна вам.

Answer 1

Следующие контрпример показывает, что даже проверка перебора всех комбинаций максимальной-области прямоугольников могут не найти оптимальный:

110 
000 
110 

В приведенном выше примере, есть 2 максимальная зоны прямоугольники, каждая из областей 3, одна вертикальная и одна горизонтальная. Вы не можете выбрать оба варианта, поэтому, если вы ограничены выбором подмножества этих прямоугольников, лучше всего выбрать один из них для общей области 3. Но если вместо этого вы выбрали прямоугольник с вертикальной площадью-3 , а затем также взял немаксимальный прямоугольник 1x2, состоящий из самых левых двух 0, вы можете получить лучшую общую площадь 5 (это минимальное расстояние разделения 0, если минимальное расстояние разделения равно 1, как в вашем Например, вы можете выбрать только самый левый 0 как прямоугольник 1x1 для общей площади 4, что все же лучше, чем 3.)

Для особого случая, когда расстояние разделения равно 0, существует тривиальный алгоритм : вы можете просто поместить прямоугольник 1x1 на каждый 0 в матрице. Когда расстояние разделения строго больше 0, я пока не вижу быстрый алгоритм, хотя я не уверен, что проблема сейчас NP-hard, чем я был несколько минут назад ...