минимальная прямоугольная поверхность в квадратной матрице - алгоритм

Question

Может ли кто-нибудь указать мне правильный подход к следующей задаче: у меня квадратная матрица (N * N), заполненная значениями 0 и 1. Мне нужно найти два прямоугольника в матрице, чтобы они проверяли следующие условия:

1. Каждый элемент 1 из матрицы должен быть включен как минимум в один прямоугольник;

2. Сумма поверхностей двухпрямоугольники должны быть минимальными (допускается, чтобы один из прямоугольников имел поверхность 0).

Чтобы быть более точным, что такое прямоугольник: прямоугольник определяется двумя интервалами [a1, b1], [a2, b2] и содержит все ячейки матрицы (i, j), так что a1≤i≤b1, a2≤j≤b2.Чтобы было более понятно, что означает поверхность: (b1-a1 + 1) · (b2-a2 + 1).

Не могли бы вы помочь мне с некоторыми идеями.Большое спасибо.

РЕДАКТИРОВАТЬ1: два прямоугольника могут перекрываться.

РЕДАКТИРОВАТЬ2: Один из прямоугольников может иметь поверхность 0

Answer 1

Мой оригинальный подход.Это не работает в случае, когда оптимальное решение требует перекрывающихся прямоугольников (например, «+» 1 с на фоне 0 с).

1. Найти минимальный ограничивающий прямоугольник, содержащий все1с.
2. Ваш первый прямоугольник простирается от верхнего левого угла этого ограничительного прямоугольника, а ваш второй ограничивающий прямоугольник простирается от нижнего правого угла этого ограничительного прямоугольника.
3. Для каждой строки R между верхними в нижней части ограничительного прямоугольника, создайте прямоугольники-кандидаты, простирающиеся от верха до R и от нижнего до R, и ширину ограничивающего прямоугольника.
4. Сократите оба этих кандидата так, чтобы они были минимальными ограничивающими прямоугольниками1 в них.Все эти пары прямоугольников удовлетворяют точке 1. Сохраняйте минимальную единицу по всем R.
5. Повторите процедуру, начиная с шага 2, чтобы покрыть каждую пару углов в общем ограничивающем прямоугольнике и сохранить наилучшее решение в целом.

После нескольких неудачных попыток эффективного решения, каждая из которых в определенных случаях не удалась, я думаю, что единственный подход, который найдет наилучшее решение, заключается в следующем:

Вам нужно только рассмотретьограничивающий прямоугольник 1 с.Два ограничивающих прямоугольника не будут лежать вне этой области.Предположим, что ограничивающий прямоугольник идет от строки (R1, C1) к (R2, C2).

    For S1 in R1 to R2
        For S2 in S1 to R2
            For D1 in C1 to C2
                For D2 in D1 to C2
                    Reduce the rectangle (S1, C1)-(S2, C2) to be the minimum bounding rectangle of the 1s it contains
                    Reduce the rectangle (R1, D1)-(R2, D2) to be the minimum bounding rectangle of the 1s it contains that aren't already in the other rectangle. This is a candidate solution.

                    Reduce the rectangle (R1, D1)-(R2, D2) to be the minimum bounding rectangle of the 1s it contains.
                    Reduce the rectangle (S1, C1)-(S2, C2) to be the minimum bounding rectangle of the 1s it contains that aren't already in the other rectangle. This is another candidate solution.

Выберите лучшее решение, которое вы найдете.

---

Примечания:

• Лучшее решение не будет иметь перекрывающихся прямоугольников, потому что такое решение всегда можно улучшить, уменьшив один из прямоугольников, чтобы он больше не перекрывался.Следовательно, нам нужно выбрать только один R на шаге 3 (вместо независимых максимальных строк для каждого прямоугольника).
• Неважно, делите ли вы на строку (R) или на столбец (C), но нет необходимости делать оба.Для скорости вы можете выбрать строки, когда ограничивающий прямоугольник короткий и толстый, и столбцы, если он высокий и тонкий.
• Если вы найдете подходящее решение, в котором ни один прямоугольник не содержит нулей, то это должно быть наилучшее решение.и вы можете остановиться.