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

Ответ 1

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

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

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

При каждом сканировании выполните следующее:

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

Ответ 2

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

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

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

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

Ответ 4

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

Ответ 5

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

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

• проверьте один ниже и один справа, если 1, затем проверьте строку 2 col 2, если 1, 2x2.

• проверьте строку 3 col 1, col 2 и col 3, а также строку 1 col 3, строку 2 col 3, если 1, 3x3.

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

• В конце строки перейдите к следующей строке.

• до конца.

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

Удачи!

Ответ 6

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

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

Сохраните 2D-массив из ints, называемый 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.

else:

Найдите минимум 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

Ответ 7

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