Динамическое программирование - самый большой квадратный блок

Question

Динамическое программирование - самый большой квадратный блок

Мне нужно найти самый большой квадрат 1 в гигантском файле, полном 1 и 0. Я знаю, что должен использовать динамическое программирование. Я храню его в 2D-массиве. Любая помощь с алгоритмом, чтобы найти самый большой квадрат была бы отличной, спасибо!

Пример ввода:

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

ответ:

Мой код до сих пор:

int Square (Sq[int x][int y]) {
   if (Sq[x][y]) == 0) {
       return 0;
   }
   else {
       return 1+MIN( Sq(X-1,Y), Sq(X,Y-1), Sq(X-1,Y-1) );
   }
}

(при условии, что значения уже введены в массив)

int main() {
    int Sq[5][6]; //5,6 = bottom right conner
    int X = Square(Sq[5][6]);
}

Как мне идти дальше?

43

c matrix dynamic-programming

Источник

user210111 13 ноя '09 в 01:46

7 ответов

Другие вопросы по тегам c matrix dynamic-programming

user166973 13 ноя '09 в 02:03 2009-11-13 02:03 · Answer 1 · 2009-11-13 02:03

Вот эскиз решения:

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

Начните итерацию с нижней правой ячейки и перейдите в нижний левый, затем перейдите на один ряд вверх и повторите.

При каждом сканировании сделайте это:

Если ячейка имеет 0 назначить count=0
Если ячейка имеет 1 и является краевой ячейкой (только нижний или правый край), назначьте count=1
Для всех остальных ячеек проверьте количество ячеек справа, справа и снизу. Возьмите минимум из них и добавьте 1 и присвойте это количеству. Держите глобальный max_count переменная для отслеживания максимального количества пока.

В конце обхода матрицы, max_count будет иметь желаемое значение.

Сложность не более, чем стоимость обхода матрицы.

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

1(1) 0(0) 1(1) 0(0) 1(1) 0(0)
1(1) 0(0) 1(4) 1(3) 1(2) 1(1)
0(0) 1(1) 1(3) 1(3) 1(2) 1(1)
0(0) 0(0) 1(2) 1(2) 1(2) 1(1)
1(1) 1(1) 1(1) 1(1) 1(1) 1(1)

Реализация в Python

def max_size(mat, ZERO=0):
    """Find the largest square of ZERO's in the matrix `mat`."""
    nrows, ncols = len(mat), (len(mat[0]) if mat else 0)
    if not (nrows and ncols): return 0 # empty matrix or rows
    counts = [[0]*ncols for _ in xrange(nrows)]
    for i in reversed(xrange(nrows)):     # for each row
        assert len(mat[i]) == ncols # matrix must be rectangular
        for j in reversed(xrange(ncols)): # for each element in the row
            if mat[i][j] != ZERO:
                counts[i][j] = (1 + min(
                    counts[i][j+1],  # east
                    counts[i+1][j],  # south
                    counts[i+1][j+1] # south-east
                    )) if i < (nrows - 1) and j < (ncols - 1) else 1 # edges
    return max(c for rows in counts for c in rows)

user148870 13 ноя '09 в 02:05 2009-11-13 02:05 · Answer 2 · 2009-11-13 02:05

LSBRA(X,Y) означает "Самый большой квадрат с правым нижним углом в X,Y"

псевдокод:

LSBRA(X,Y):
   if (x,y) == 0:
       0
   else:
       1+MIN( LSBRA(X-1,Y), LSBRA(X,Y-1), LSBRA(X-1,Y-1) )

(Для краевых ячеек вы можете пропустить часть MIN и просто вернуть 1, если (x,y) не равно 0.)

Работайте по диагонали через сетку в "волнах", как показано ниже:

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 2 3 4 5 6
2 | 3 4 5 6 7
3 | 4 5 6 7 8

или, альтернативно, работайте слева направо, сверху вниз, пока вы заполняете краевые ячейки.

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 6 7 8 9 .
2 | . . . . .
3 | . . . . .

Таким образом, вы никогда не столкнетесь с вычислениями, в которых вы ранее не вычисляли необходимые данные - так что все LSBRA() "вызовы" на самом деле являются просто поисками таблиц ваших предыдущих результатов вычислений (отсюда и аспект динамического программирования).

Почему это работает

Чтобы иметь квадрат с правым нижним углом в X,Y - он должен содержать перекрывающиеся квадраты одного меньшего измерения, которые касаются каждого из трех других углов. Другими словами, чтобы иметь

XXXX
XXXX
XXXX
XXXX

Вы также должны иметь...

XXX.    .XXX    ....    ....
XXX.    .XXX    XXX.    ....
XXX.    .XXX    XXX.    ....
....    ....    XXX.    ...X

Пока у вас есть эти 3 (каждый из проверок LSBRA) квадратов N-размера плюс текущий квадрат также "занят", у вас будет квадрат (N+1) размера.

user132961 13 ноя '09 в 01:56 2009-11-13 01:56 · Answer 3 · 2009-11-13 01:56

Первый алгоритм, который приходит мне в голову:

'&&' column / row 1 with column / row 2 if, то есть выполнить операцию '&&' между каждой записью и соответствующей ей записью в другой колонке / строке.
Проверьте полученный столбец, если есть какие-либо длины 2 1, что означает, что мы попали в квадрат 2x2.
И следующий столбец с результатом первых двух. Если есть длина 3 1, мы попадаем в квадрат 3х3.
Повторяйте, пока все столбцы не будут использованы.
Повторите 1-4, начиная со столбца 2.

Я не буду показывать вам реализацию, поскольку она довольно проста, и ваша проблема звучит как домашняя работа. Кроме того, вероятно, есть гораздо более эффективные способы сделать это, так как это станет медленным, если ввод был очень большим.

user13441 13 ноя '09 в 02:03 2009-11-13 02:03 · Answer 4 · 2009-11-13 02:03

Пусть входная матрица M: n x m

T[i][j] матрица DP, которая содержит наибольшую квадратную сторону с квадратами внизу справа (i,j),

Общее правило для заполнения таблицы:

if (M[i][j] == 1) {
  int v = min(T[i][j-1], T[i-1][j]);
  v = min(v, T[i-1][j-1]);
  T[i][j] = v + 1;
}
else 
  T[i][j] = 0;

Размер квадрата результата - максимальное значение в T,

начинка T[i][0] а также T[0][j] тривиально.

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

Следующие примечания могут помочь понять общую идею:

все квадраты с правыми нижними углами (i-1, j), (i, j-1), (i-1, j-1) с размером s находятся внутри квадрата с правым нижним углом (i, j) с размером s+1.
если есть квадрат размера s + 1 с правым нижним углом в (i, j), то размер максимального квадрата с правыми нижними углами (i-1, j), (i, j-1), (i-1, J-1) по крайней мере с.
Противоположное тоже верно. Если размер хотя бы одного квадрата с нижними правыми углами в точках (i-1, j), (i, j-1), (i-1, j-1) меньше s, то размер квадрата с правым нижним углом at (i, j) не может быть больше s + 1.

user175051 13 ноя '09 в 02:02 2009-11-13 02:02 · Answer 5 · 2009-11-13 02:02

ОК, самый неэффективный, но простой способ:

выберите первый пункт. проверьте, если 1, если так, у вас есть квадрат 1x1.
отметьте один ниже и один справа, если 1, то проверьте строку 2 столбец 2, если 1, 2x2 квадрат.
проверьте строку 3, столбец 1, столбец 2 и столбец 3, плюс строку 1, столбец 3, строку 2, столбец 3, если 1, 3x3.
Таким образом, вы продолжаете расширять ряд и столбец вместе и проверяете все ячейки внутри их границ. Как только вы нажмете 0, он сломается, поэтому вы двигаетесь вдоль 1 пункта подряд и начинаете снова.
В конце строки перейдите к следующему ряду.
до конца.

Вы можете, вероятно, увидеть, как они вписываются в циклы while и т. Д. И как &&s можно использовать для проверки нуля, и, посмотрев на него, вы, возможно, также заметите, как его можно ускорить. Но, как уже упоминалось в другом ответе, это немного похоже на домашнее задание, поэтому мы оставим фактический код на ваше усмотрение.

Удачи!

user5815635 22 янв '16 в 13:49 2016-01-22 13:49 · Answer 6 · 2016-01-22 13:49

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

Алгоритм выглядит следующим образом:

Сохраните двумерный массив целых чисел, называемый max-square, где элемент с индексом i, j представляет размер квадрата, в котором i, j - нижний правый угол. (если max[i,j] = 2, это означает, что индекс i, j - это нижний правый угол квадрата размером 2^2 = 4)

Для каждого индекса i,j:

если в i, j элемент равен 0, тогда установите max-square i, j в 0.

еще:

Найдите минимум max-square[i - 1, j] и max-square[i, j - 1] и max-square[i - 1][j -1]. установите max-square[i, j] на 1 + минимум 3. Индуктивно, вы в конечном итоге заполните массив max-square. Найти / или отслеживать максимальное значение в процессе, вернуть это значение ^2.

Посмотрите на эти решения, которые предложили люди: https://leetcode.com/discuss/questions/oj/maximal-square?sort=votes

user1850829 07 июл '13 в 21:38 2013-07-07 21:38 · Answer 7 · 2013-07-07 21:38

Пусть N будет количеством ячеек в двумерном массиве. Существует очень эффективный алгоритм для перечисления всех максимально пустых прямоугольников. Самый большой пустой квадрат находится внутри одного из этих пустых прямоугольников, и его создание становится тривиальным после вычисления списка максимально пустых прямоугольников. Документ с алгоритмом O(N) для создания такого списка можно найти по адресу http://www.ulg.ac.be/telecom/rectangles, а также с исходным кодом (не оптимизирован). Обратите внимание, что существует доказательство (см. Статью), что число самых больших пустых прямоугольников ограничено N. Следовательно, выбор наибольшего пустого квадрата может быть выполнен в O(N), и общий метод также равен O(N). На практике этот метод очень быстрый. Реализация очень проста, поскольку весь код не должен превышать 40 строк C (алгоритм для перечисления всех максимально пустых прямоугольников занимает около 30 строк C).