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

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

Как мне продолжать?

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

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

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

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

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

    По окончании прохождения матрицы max_count будет иметь требуемое значение.

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

    Вот как выглядит matrix после обхода. Значения в круглых скобках – это подсчеты, т. Е. Наибольший квадрат, который может быть сделан с использованием ячейки как верхний левый.

     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) 

    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() с вычислениями, в которых вы ранее не вычисляли необходимые данные, поэтому все LSBRA() самом деле являются просто просмотрами таблиц ваших предыдущих результатов вычислений (следовательно, аспект динамического программирования).

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

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

     XXXX XXXX XXXX XXXX 

    вы также должны иметь …

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

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

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

    1. ‘&&’ column / row 1 с столбцом / строкой 2, если это означает, что операция «&&» между каждой записью и соответствующей ей записью в другом столбце / строке.
    2. Проверьте полученный столбец, если есть длина 2 1, что означает, что мы нажмем квадрат 2×2.
    3. И следующий столбец с результатом первых двух. Если есть длина 3 1, мы попали в квадрат 3×3.
    4. Повторяйте до тех пор, пока не будут использованы все столбцы.
    5. Повторите 1-4, начиная со столбца 2.

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

    Пусть входная matrix M : nxm

    T[i][j] – это matrix 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.

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

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

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

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

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

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

    6. до конца.

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

    Удачи!

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

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

    Храните 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.

    еще:

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

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

    Interesting Posts

    Лучший способ представить сетку или таблицу в AngularJS с помощью Bootstrap 3?

    Замените «CopyFileFromGuestToHost» и «runProgramInGuest» на xcopy и простое выполнение, что я могу ожидать

    Почему этот код SSE в 6 раз медленнее без VZEROUPPER на Skylake?

    Полный пример

    распределять и инициализировать то, что они на самом деле делают

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

    Как вы объявляете интерфейс на C ++?

    Как остановить Proguard от удаления параметров типа?

    В чем разница между кодировками utf8mb4 и utf8 в mysql?

    Как я могу использовать свой считыватель отпечатков пальцев IBM / Lenovo на не-Lenovo Windows 7 ПК?

    Почему я получаю сообщение об ошибке? Объектный литерал может указывать только известные свойства?

    SyncAdapter без ContentProvider

    Ошибка раздувания classа android.support.design.widget.NavigationView

    Как передать параметры пользовательскому действию?

    ошибка LNK2038: обнаружено несоответствие для ‘_ITERATOR_DEBUG_LEVEL’: значение ‘0’ не соответствует значению ‘2’ в main.obj

    Давайте будем гением компьютера.