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

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

39 голосов
/ 13 ноября 2009

Мне нужно найти самый большой квадрат 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

Ответ: 

1 1 1 1
1 1 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]);
}

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

Ответы [ 7 ]

77 голосов
/ 13 ноября 2009

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

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

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

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

  1. Если ячейка имеет 0, присвойте count=0
  2. Если ячейка имеет 1 и является краевой ячейкой (только нижний или правый край), присвойте count=1
  3. Для всех остальных ячеек проверьте количество ячеек справа, справа внизу и ниже. Возьмите минимум из них и прибавьте 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)
8 голосов
/ 13 ноября 2009

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) размера.

3 голосов
/ 13 ноября 2009

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

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

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

2 голосов
/ 13 ноября 2009

Пусть входная матрица равна 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) не менее s.
  • Противоположное тоже верно. Если размер хотя бы одного квадрата с нижними правыми углами в точках (i-1, j), (i, j-1), (i-1, j-1) меньше s, то размер квадрата с правым нижним углом при (i, j) не может быть больше s + 1.
1 голос
/ 22 января 2016

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

Алгоритм следующий:

Сохраните двумерный массив целых чисел, называемый 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.

остальное:

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

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

1 голос
/ 13 ноября 2009

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

  1. выберите первый пункт. проверьте, если 1, если это так, у вас есть квадрат 1x1.

  2. отметьте один снизу и один справа, если 1, затем проверьте строку 2, столбец 2, если 1, квадрат 2х2.

  3. проверьте строку 3, столбец 1, столбец 2 и столбец 3, плюс строку 1, столбец 3, ряд 2, столбец 3, если 1, 3x3.

  4. Итак, в основном вы продолжаете расширять ряд и столбец вместе и проверяете все ячейки внутри их границ. Как только вы нажмете 0, он сломается, поэтому вы двигаетесь вдоль 1 пункта подряд и начинаете снова.

  5. В конце ряда перейти к следующему ряду.

  6. до конца.

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

Удачи!

0 голосов
/ 08 июля 2013

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

...