Поиск максимальной размерной подматрицы всех 1 в матрице с 1 и 0
Предположим, вам задан битмап mXn, представленный массивом M [1..m, 1.. n], чьи записи все 0 или 1. Все-один блок является подмассивом формы M [i.. i0, j.. j0], в котором каждый бит равен 1. Опишите и проанализируйте эффективный алгоритм, чтобы найти все-один блок в M с максимальной площадью
Я пытаюсь сделать динамическое программирование. Но мой рекурсивный алгоритм работает в O (n ^ n) времени, и даже после memoization я не могу думать о том, чтобы свести его ниже O (n ^ 4). Может ли кто-нибудь помочь мне найти более эффективное решение?
Ответы
Ответ 1
Решение O (N) (количество элементов):
A
1 1 0 0 1 0
0 1 1 1 1 1
1 1 1 1 1 0
0 0 1 1 0 0
Создайте массив C, где каждый элемент представляет число 1s выше и включает его, вплоть до первого 0.
C
1 1 0 0 1 0
0 2 1 1 2 1
1 3 2 2 3 0
0 0 3 3 0 0
Мы хотим найти строку R и левый, правый индексы l, R, который максимизирует (r-l+1)*min(C[R][l..r]). Вот алгоритм для проверки каждой строки в времени O (cols):
Поддерживать стек пар (h, i), где C[R][i-1] < h ≤ C[R][i]. В любой позиции cur мы должны иметь h=min(C[R][i..cur]) для всех пар (h, i) в стеке.
Для каждого элемента:
- Если
h_cur>h_top
-
- Else:
-
-
-
- Поместите верхнюю часть стека.
-
-
- Проверьте, будет ли он работать лучше, т.е.
(i_cur-i_pop)*h_pop > best.
-
-
-
- Нажмите
(h, i_lastpopped).
Пример этого в выполнении для третьей строки в нашем примере:
i =0 1 2 3 4 5
C[i]=1 3 2 2 3 0
(3, 4)
S= (3, 1) (2, 1) (2, 1) (2, 1)
(1, 0) (1, 0) (1, 0) (1, 0) (1, 0)
(0,-1) (0,-1) (0,-1) (0,-1) (0,-1) (0,-1)
i=0, C[i]=1) Нажмите (1, 0).
i=1, C[i]=3) Нажмите (3, 1).
i=2, C[i]=2) Pop (3, 1). Проверьте, является ли (2-1)*3=3 новым лучшим.
Последним i popped было 1, поэтому нажмите (2, 1).
i=3, C[i]=2) h_cur=h_top, не делайте ничего.
i=4, C[i]=3) Нажмите (3, 4).
i=5, C[i]=0) Pop (3, 4). Проверьте, является ли (5-4)*3=3 новым.
Поп (2, 1). Проверьте, является ли (5-1)*2=8 новым.
Поп (1, 0). Проверьте, является ли (5-0)*1=5 новым.
Конец. (Хорошо, мы должны, вероятно, добавить дополнительный термин C [cols] = 0 на конец для хорошей меры).
Ответ 2
Вот алгоритм O(numCols*numLines^2). Пусть S[i][j] = sum of the first i elements of column j.
Я буду работать с алгоритмом в этом примере:
M
1 1 0 0 1 0
0 1 1 1 0 1
1 1 1 1 0 0
0 0 1 1 0 0
Имеем:
S
1 1 0 0 1 0
1 2 1 1 1 1
2 3 2 2 1 1
2 3 3 3 1 1
Теперь рассмотрим проблему нахождения максимального подмашины всех единиц в одномерном массиве. Это можно решить с помощью этого простого алгоритма:
append 0 to the end of your array
max = 0, temp = 0
for i = 1 to array.size do
if array[i] = 1 then
++temp
else
if temp > max then
max = temp
temp = 0
Например, если у вас есть этот 1d-массив:
1 2 3 4 5 6
1 1 0 1 1 1
вы сделаете следующее:
Сначала добавьте 0:
1 2 3 4 5 6 7
1 1 0 1 1 1 0
Теперь обратите внимание, что всякий раз, когда вы нажимаете 0, вы знаете, где заканчивается последовательность смежных. Поэтому, если вы сохраняете текущую итоговую сумму (temp) текущего количества единиц, вы можете сравнить это значение с максимальным значением до сих пор (max variable), когда вы нажмете нуль, а затем reset работает Всего. Это даст вам максимальную длину смежной последовательности единиц в переменной max.
Теперь вы можете использовать этот субалгоритм, чтобы найти решение своей проблемы. Прежде всего добавьте столбец 0 в свою матрицу. Затем вычислим S.
Тогда:
max = 0
for i = 1 to M.numLines do
for j = i to M.numLines do
temp = 0
for k = 1 to M.numCols do
if S[j][k] - S[i-1][k] = j - i + 1 then
temp += j - i + 1
else
if temp > max then
max = temp
temp = 0
В принципе, для каждой возможной высоты подмассива (существуют допустимые высоты O(numLines^2)), вы найдете ту, которая имеет максимальную площадь с этой высотой, применяя алгоритм для одномерного массива (в O(numCols)).
Рассмотрим следующее "изображение":
M
1 1 0 0 1 0 0
i 0 1 1 1 0 1 0
j 1 1 1 1 0 0 0
0 0 1 1 0 0 0
Это означает, что мы зафиксировали высоту j - i + 1. Теперь возьмем все элементы матрицы, которые находятся между i и j включительно:
0 1 1 1 0 1 0
1 1 1 1 0 0 0
Обратите внимание, что это напоминает одномерную проблему. Пусть суммируют столбцы и видят, что получим:
1 2 2 2 0 1 0
Теперь проблема сводится к одномерному случаю, за исключением того, что мы должны найти подпоследовательность непрерывного j - i + 1 (что в данном случае 2). Это означает, что каждый столбец в нашем j - i + 1 "окне" должен быть полным. Мы можем проверить это эффективно, используя матрицу S.
Чтобы понять, как работает S, рассмотрим одномерный случай: пусть s[i] = sum of the first i elements of the vector a. Тогда какова сумма подпоследовательности a[i..j]? Это сумма всех элементов вплоть до a[j], за вычетом суммы всех тех, что до и включая a[i-1], что означает s[j] - s[i-1]. Случай 2d работает одинаково, за исключением того, что для каждого столбца имеется S.
Надеюсь, это понятно, если у вас возникнут вопросы, пожалуйста, спросите.
Я не знаю, соответствует ли это вашим потребностям, но я думаю, что существует и алгоритм O(numLines*numCols), основанный на динамическом программировании. Я еще не могу понять, кроме случая, когда подмассива, который вы используете, квадратная. Однако у кого-то может быть лучшая проницательность, поэтому подождите немного больше.
Ответ 3
Определите новую матрицу A, которая сохранит в [i, j] два значения: ширину и высоту самой большой подматрицы с левым верхним углом в i, j, заполните эту матрицу, начиная с нижнего правого угла, по строкам сверху вниз. Вы найдете четыре случая:
Выполните эти случаи, когда заданная матрица в [i, j] = 1
case 1: ни один из элементов правого или нижнего соседа в исходной матрице не равен текущему, т.е. M [i, j]!= M [i + 1, j] и M [i, j]!= M [i, j + 1], являющееся M исходной матрицей, в этом случае значение A [i, j] равно 1x1
случай 2: соседний элемент справа равен текущему, а нижний - другому, значение A [i, j].width равно A [i + 1, j].width + 1 и A [I, J].height = 1
случай 3: соседний элемент снизу равен, но правый - другой, A [i, j].width = 1, A [i, j].height = A [i, j + 1]. высота + 1
случай 4: оба соседства равны: Рассматриваются три прямоугольника:
-
А [I, J].width = А [I, J + 1].width + 1; A [I, J].height = 1;
-
А [I, J].height = А [I + 1, J].height + 1; а [I, J].width = 1;
-
A [i, j].width = min (A [i + 1, j].width + 1, A [i, j + 1].width) и A [i, j].height = min (A [i, j + 1] + 1, A [i + 1, j])
Тот, который имеет максимальную площадь в трех вышеуказанных случаях, будет считаться представляющим прямоугольник в этом положении.
Размер самой большой матрицы, которая имеет верхний левый угол в i, j, равна A [i, j].width * A [i, j].height, поэтому вы можете обновить максимальное значение, найденное при вычислении A [ I, J]
нижняя строка и самые правые элементы столбца обрабатываются так, как если бы их соседи снизу и справа соответственно были разными.
Ответ 4
Вот реализация O (N) в С#.
Идея состоит в том, чтобы использовать динамическое программирование для создания накопленной матрицы, размер которой является самой большой подматрицей, включая текущую ячейку.
public static int LargestSquareMatrixOfOne(int[,] original_mat)
{
int[,] AccumulatedMatrix = new int[original_mat.GetLength(0), original_mat.GetLength(1)];
AccumulatedMatrix[0, 0] = original_mat[0, 0];
int biggestSize = 1;
for (int i = 0; i < original_mat.GetLength(0); i++)
{
for (int j = 0; j < original_mat.GetLength(1); j++)
{
if (i > 0 && j > 0)
{
if (original_mat[i, j] == 1)
{
AccumulatedMatrix[i, j] = Math.Min(AccumulatedMatrix[i - 1, j - 1], (Math.Min(AccumulatedMatrix[i - 1, j], AccumulatedMatrix[i, j - 1]))) + 1;
if (AccumulatedMatrix[i, j] > biggestSize)
{
biggestSize = AccumulatedMatrix[i, j];
}
}
else
{
AccumulatedMatrix[i, j] = 0;
}
}
else if ( (i > 0 && j == 0) || (j > 0 && i == 0))
{
if (original_mat[i, j] == 1) { AccumulatedMatrix[i, j] = 1; }
else { AccumulatedMatrix[i, j] = 0; }
}
}
}
return biggestSize;
}
