Наивный способ найти самый большой блок в прямоугольнике из 1 и 0

Я пытаюсь найти грубое (наивное) решение, чтобы найти самый большой блок 1 или 0 в прямоугольнике 1 и 0. Я знаю оптимальные способы, которые могут сделать это в O(n) время, где п - общий размер прямоугольника.

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

В приведенном выше прямоугольнике это прямоугольник, начинающийся с (строка 2, столбец 2) размера 6. Я думал об этом..

Пройдите через каждый элемент и затем найдите его размер, повторяя его во всех направлениях.

Это грубая сила? Какой будет сложность? Я прохожу все элементы, которые есть n, но затем я повторяюсь во всех направлениях, сколько это будет?

Я знаю, что этот вопрос задавался 100 раз, но они говорят об оптимальных решениях. То, что я ищу, - это грубое решение и его сложность?

Источник

3 ответа

Описанный вами алгоритм выглядит примерно так:

//for each entry
for(int x = 0; x < width; ++x)
    for(int y = 0; y < height; ++y)
    {
        char lookFor = entries[x][y];
        int area = 0;
        for(int row = y; row < height; ++row)
        {
            if(entries[x, row] != lookFor)
                break;
            for(int col = x; col < width; ++col)
            {
                if(entries[col, row] != lookFor)
                    break;
                int currentArea = (col - x + 1) * (row - y + 1);
                if(currentArea > area)
                {
                    //save the current rect
                }
            }
        }
    }

Есть четыре вложенных цикла. Внешние циклы будут повторяться точно n раз (с n быть количество записей). Внутренние циклы будут повторяться width * f1 а также height * f2 раз в среднем (с f1 а также f2 будучи некоторой постоянной долей). Остальная часть алгоритма занимает постоянное время и не зависит от размера задачи.

Следовательно, сложность O(n * f1 * width * f2 * height) = O(n^2), что по существу означает "перейти к каждой записи и оттуда, посетить каждую запись снова", независимо от того, действительно ли нужно проверять все записи или только постоянную долю, которая увеличивается с увеличением размера проблемы.

редактировать

Приведенные выше объяснения предполагают, что записи не распределены случайным образом и что для больших полей более вероятно найти более крупные однородные субрегионы. Если это не так, и среднее количество итераций для внутренних циклов вообще не зависит от размера поля (например, для случайно распределенных записей), то результирующая временная сложность O(n)

Источник

Грубая сила обычно делится на две (иногда последовательные) части. Первая часть генерирует все возможные кандидаты для решения проблемы. Вторая часть тестирует их, чтобы увидеть, действительно ли они являются решениями.

Грубая сила: Предположим, ваш прямоугольник m x n. Создайте все под прямоугольники размера a x b, где a находится в {1..m}, а b в {1..n}. Установить maximum переменная к 0. Проверьте все под прямоугольники, чтобы видеть, все ли это 0 и 1. Если это так, пусть maximum = max(maximum, size(sub-rectangle), В качестве альтернативы просто начните с тестирования больших суб-прямоугольников и переходите к тестированию меньших суб-прямоугольников. Как только вы найдете под прямоугольник со всеми 0 или 1, остановитесь. Временная сложность будет одинаковой, потому что в худшем случае для обоих методов вам все равно придется перебирать все под прямоугольники.

Сложность времени:

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

Есть m*n под прямоугольников размером 1 x 1.

Есть (m-1)*n под прямоугольников размера 2 x 1.

Есть m*(n-1) под прямоугольников размером 1 x 2.

Есть (m-1)*(n-1) под прямоугольников размером 2 x 2.

... <и так далее>

Есть (m-(m-1))*(n-(n-1)) под прямоугольников размера m x n.

Таким образом, формула для подсчета количества прямоугольников размера a x b из большего прямоугольника размера mxn просто:

number_of_subrectangles_of_size_a_b = (m-a) * (m-b)

Если мы представим эти числа, изложенные в арифметической серии, мы получим

1*1 + 1*2 + ... + 1*n + 2*1 + ... + m*n

Это может быть учтено с целью:

(1 + 2 + ... + m) * (1 + 2 + ... + n),

Эти два арифметических ряда сходятся к порядку O (m2) и O (n2) соответственно. Таким образом, генерация всех под прямоугольников прямоугольника m*n является O (m2 n2). Теперь посмотрим на этап тестирования.

После генерации всех вложенных прямоугольников проверяется, равен ли каждый вложенный прямоугольник размера a x b всем 0 или всем 1 является O (a * b). В отличие от предыдущего шага генерации под прямоугольников размера a x b, который масштабируется вверх при уменьшении a x b, этот шаг увеличивается пропорционально размеру оси b.

Например: есть 1 под прямоугольник размером m x n. Но проверка, чтобы видеть, является ли тот прямоугольник всеми 0 или всеми 1, занимает O (m*n) время. И наоборот, есть m*n под прямоугольников размера 1. Но проверка на то, что все эти прямоугольники равны 0 или всем 1, занимает всего O (1) времени на прямоугольник.

То, что вы, в конечном итоге, в итоге усложняете по времени, - это серия вроде этой:

O( (m-(m-1))(n-(n-1))*(mn) + (m-(m-1))(n-(n-2))*m(n-1)... + mn*(m-(m-1))(n-(n-1)) )

Обратите внимание на 2 вещи здесь.

  1. Самый большой член в ряду будет где-то близко к (m / 2)(n / 2)(m / 2) (n / 2), который равен O (m2 n2)

  2. Всего в серии m*n терминов.

Таким образом, фаза тестирования решения для перебора будет O (mn * m2 n2) = O (m3 n3).

Общая сложность времени составляет:

O(generating) + O(testing) = O(m2n2 + m3n3) = O(m3n3)

Если площадь данного прямоугольника равна N, мы будем иметь O (N3) временную сложность.

Источник

Посмотрите на алгоритмы "связанных компонентов" для дополнительных идей. То, что вы представили в виде двумерного массива двоичных значений, выглядит как двоичное черно-белое изображение. Важным исключением является то, что при обработке изображений мы обычно разрешаем подключенному компоненту (объекту 0 или 1) иметь непрямоугольные формы. Некоторые настройки существующих многопроходных и однопроходных алгоритмов должны быть легко осуществимы.

http://en.wikipedia.org/wiki/Connected-component_labeling

Хотя это более общее решение, чем вам нужно, вы также можете запустить алгоритм подключенных компонентов, чтобы найти все подключенные области (0 или 1, фон или передний план), а затем отфильтровать результирующие компоненты (или большие двоичные объекты). Я также упомяну, что для компонентов переднего плана предпочтительнее выбрать "4-связность", а не "8-связность", где первая означает, что подключение разрешено только в пикселях выше, ниже, слева и справа от центрального пикселя, и последнее означает, что соединение разрешено для любого из восьми пикселей, окружающих центральный пиксель.

Чуть дальше, для очень больших двумерных массивов это может (просто может) помочь сначала уменьшить пространство поиска, создав то, что мы бы назвали "пирамидой изображений", то есть стек массивов постепенно уменьшающегося размера: по 1/2 каждого размер (заполняется по мере необходимости) 1/4, 1/8 и т. д. Прямоугольник, обнаруживаемый в изображении с уменьшенным разрешением, является хорошим кандидатом на роль самого большого прямоугольника в очень большом изображении (или двумерном массиве битов). Хотя это может быть не лучшим решением для любых рассматриваемых вами случаев, оно масштабируемое. Естественно, потребуются некоторые усилия для определения стоимости масштабирования массива / изображения в сравнении с затратами на поддержание относительно больших списков кандидатов-прямоугольников в исходном большом изображении.

Кодирование длин серий также может вам помочь, тем более что вы имеете дело с прямоугольниками, а не со связанными компонентами произвольной формы. При кодировании длины серии каждая строка выражается в виде растяжений или "длин серий", равных 0 или 1. Этот метод был использован для ускорения алгоритмов подключения компонентов десять или два года назад, и это все еще разумный подход.

Во всяком случае, это не самый прямой ответ на ваш вопрос, но я надеюсь, что это поможет.

Источник
Другие вопросы по тегам