4

Могли бы вы посоветовать алгоритм, решающий следующую задачу?

Задана прямоугольная матрица размером nxm и число k. Нужно найти подматрицу (исходная матрица также считается подматрицей) наибольшей площади (число столбцов умноженное на число строк), у которой сумма элементов меньше или равна k. Вернуть площадь этой матрицы. Все элементы матрицы и число k - положительные целые числа. Алгоритм должен иметь сложность ниже О(n^6). Можно использовать дополнительные структуры на основе матрицы.

На данный момент понял, что могут помочь матрицы сумм столбцов и строк: матрица сумм столцов для матрицы с элементами вида

equation

матрица сумм строк:

equation

матрица сумм столбцов:

equation

То есть для матрицы вида

equation

матрица сумм строк:

equation

матрица сумм столбцов:

equation

eще прочитал, что можно использовать матрицу сумм подматриц вида

equation

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

equation

эту матрицу можно использовать для нахождения суммы подматрицы, например, чтобы найти значение элемента

equation

матрицы

equation

как equation

6
  • Что уже получилось? Добавте в вопрос.
    – 0xdb
    2 дек 2017 в 15:53
  • Сложность O(n^6), а n это что? Если M x N, то прямой перебор получается за O(n^3), если n это N, то прямой перебор как раз и получается за ваше O(n^6), только вот логичнее задавать n как M x N, потому непонятно немного...
    – user239133
    2 дек 2017 в 19:36
  • под n подразумеваю один из размеров матрицы, наивный алгоритм имеет сложность O(n^6) 2 дек 2017 в 19:42
  • @МаркСоболев, если это все же именно один из размеров, то второй остается только зафиксировать. Тогда сложность опять O(n^3). Оптимизация мне в голову приходит только слишком сложная, чтобы я мог сходу написать какой-то код. Если перебор всех подмножеств можно реализовать с сохранением сложности O(n^2) так, чтобы последовательно перебирались подмножества одинакового размера P x Q, то сумму можно считать быстрым методом двумерного скользящего среднего. У него сложность все еще O(n), но, по крайней мере, одномерный вариант поддается некоторой оптимизации.
    – user239133
    2 дек 2017 в 20:15
  • Считая, что количество элементов в матрице O(n**2). Самый наивный подход перебирает все возможные дочерние матрицы (i, j, nrows, ncolumns) -- O(n**4) и вычисляет наивно сумму с самого начала n*m -- O(n**2) -> O(n**6) алгоритм. Если использовать S[i,j] матрицу, то можно за O(1) сумму вычислять: Sum(i,j,nrows,ncolumns) = S[i+nrows,j+ncolumns] - S[i+nrows,j] - S[i,j+ncolumns] +S[i,j] то есть используя S[i,j] наивный алгоритм становится O(n**4) по времени и O(n**2) в памяти. Это достаточно для вашего вопроса?
    – jfs
    2 дек 2017 в 21:14

1 ответ 1

1

Весь код будет приведен на C++, а не на чистом C, так как переписать его, если понадобится, не так сложно, но читабельность у плюсов намного выше.


Для начала определим "наивный" алгоритм со сложностью O(n^6):

int main()
{
    /*
    input: int n, int m, int k, vector<vector<int>> a;
    */

    int ans = 0;
    int ans_left_x = -1, ans_left_y = -1, ans_right_x = -1, ans_right_y = -1;

    for (int x1 = 0; x1 < m; ++x1)
    {
        for (int y1 = 0; y1 < n; ++y1)
        {
            for (int x2 = x1; x2 < m; ++x2)
            {
                for (int y2 = y1; y2 < n; ++y2)
                {
                    // (x1, y1) - верхний левый угол матрицы
                    // (x2, y2) - нижний правый угол матрицы

                    int sum = 0;
                    for (int x = x1; x <= x2; ++x)
                    {
                        for (int y = y1; y <= y2; ++y)
                            sum += a[y][x];
                    }
                    
                    int area = (x2 - x1 + 1) * (y2 - y1 + 1);
                    if (sum <= k && area > ans)
                    {
                        ans = area;
                        ans_left_x = x1;
                        ans_left_y = y1;
                        ans_right_x = x2;
                        ans_right_y = y2;
                    }

                }
            }
        }
    }

    /*
    output: ans, ans_x1y1x2y2
    */
}

Данный алгоритм совершает примерно 1 операций.


Теперь стоит заметить одну его интересную оптимизацию:

...
for (int y2 = y1; y2 < n; ++y2)
{
    // (x1, y1) - верхний левый угол матрицы
    // (x2, y2) - нижний правый угол матрицы

    int area = (x2 - x1 + 1) * (y2 - y1 + 1);
    if (area < ans)
        continue;

    ...
    
    if (sum <= k)
    {
        ...
    }
}
...

Если не считать сумму бесперспективных по площади подматриц, то улучшений площади может произойти не более m*n (и что-то мне подсказывает, что на самом деле этих улучшений может быть не более m*log(n)), а следовательно сложность алгоритма резко уменьшается до O(n^2*m^2) + O(n*m) * O(n*m) = O(n^2*m^2), что уже синонимично O(n^4) в данной задаче.

Но все-таки стоит учесть, что это моя недоказанная эвристика, и конкретную оценку сложности можно получить только с помощью обоснованного математического доказательства.


Теперь поговорим о вашей догадке про префиксные суммы (а именно так называется то, о чем вы писали во второй части вопроса). На многомерные пространства префиксные суммы распространяются неохотно, но для двумерного случая формула следующая:

sum(x1, y1, x2, y2) = 
    pref(x2, y2) - 
    pref(x1 - 1, y2) -
    pref(x2, y1 - 1) + 
    pref(x1 - 1, y2 - 1)

где pref(x, y) = sum(0, 0, x, y)

Массив префиксных сумм можно вычислить за O(n*m), что можно принять чуть ли не статистической погрешностью. Вычислив массив префиксных сумм, можно доработать прошлое решение следующим образом:

vector<vector<int>> pref(n + 1, vector<int>(m + 1, 0));
for (int i = 0; i < n; i++)
{
    int s = 0;
    for (int j = 0; j < m; j++)
    {
        s += a[i][j];
        pref[i + 1][j + 1] = pref[i][j + 1] + s;
    }
}
...
for (int y2 = y1; y2 < n; ++y2)
{
    // (x1, y1) - верхний левый угол матрицы
    // (x2, y2) - нижний правый угол матрицы

    int area = (x2 - x1 + 1) * (y2 - y1 + 1);
    if (area < ans)
        continue;
    
    //ко всем индексам была прибавлена единица
    //так как pref[i][0] и pref[0][j] содержат нули для удобства вычислений
    //и суммы префиксных подматриц (0, 0, x, y) содержатся в pref[y+1][x+1]
    int sum = 
        pref[y2+1][x2+1] - 
        pref[y2+1][x1] -
        pref[y1][x2+1] + 
        pref[y2][x1];
    
    if (sum <= k)
    {
        ...
    }
}
...

Асимптотическая сложность данного решения гарантированно не превосходит O(n^2*m^2) или O(n^4), причем с меньшей константой, чем в решении 2.


Далее стоит подумать об упрощенной задаче: если дана не матрица, а линейный массив. В таком случае самый длинный отрезок с суммой, не превосходящей K, может быть найден за линейное время с помощью алгоритма "двух указателей". Общую теорию об алгоритме вы можете найти в гугле, если не знакомы.

Идея такова:

Для любых границ отрезков a и b выполняется sum(a, b + 1) > sum(a, b) и sum(a - 1, b) > sum(a, b), так как все элементы больше нуля. Поэтому если отрезок [a, b] имеет "правильную" сумму, то отрезок [a, b + 1] либо будет тоже иметь сумму не больше K, либо он включает наибольший подотрезок [x, b + 1], сумма которого не больше K, где x > a. Таким образом для любого конца b мы найдем в процессе работы алгоритма наибольший подотрезок с "правильной" суммой, кончающийся в b.

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

Пример:
3 1 4 1      
5 9 2 6 ---> 13 13 11 16
5 3 5 9

Тогда переберем возможные y1 и y2 для подматриц и решим задачу за O(n^2*m).

//Новые префиксные суммы - линейные префиксные по столбцам
vector<vector<int>> pref(m, vector<int>(n + 1, 0));
for (int i = 0; i < m; i++)
{
    for (int j = 0; j < n; j++)
        pref[i][j + 1] = pref[i][j] + a[i][j];
}

for (int y1 = 0; y1 < n; ++y1)
{
    for (int y2 = y1; y2 < n; ++y2)
    {
        //Неявно сожмем подматрицу (0, y1) (m - 1, y2) до одномерной, сложив значения по столбцам
        //Тогда решим задачу для линейного массива с помощью "двух указателей"
        int x1 = 0;
        int s = 0;
        for (int x2 = 0; x2 < m; ++x2)
        {
            s += pref[x2][y2 + 1] - pref[x2][y1];
            while (s > k)
            {
                s -= pref[x1][y2 + 1] - pref[x1][y1];
                x1++;
            }

            int area = (y2 - y1 + 1) * (x2 - x1 + 1);
            if (area > ans)
            {
                //...
            }
        }
    }
}

Стоит отметить, что тут n и m входят в разных степенях в оценку сложности, поэтому стоит перебирать y1 и y2 или x1 и x2 в зависимости от того, какая сторона меньше.


Я не буду утверждать точно, но с большой долей вероятности положительность элементов дает возможность использовать тернарный и бинарный поиск следующим образом:

  1. for x in 0 .. m - 1 - перебор правой границы
  2. for y in 0 .. n - 1 - перебор нижней границы
  3. ternar(0, y) - поиск оптимальной верхней границы
  4. binar(0, x) - поиск минимальной левой границы, для которой сумма правильна
  5. sum(x1, y1, x2, y2) - через префиксные суммы

(цифрами обозначена степень вложенности)


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


И если вы ироничный студент, и у вас ироничный преподаватель, то рекомендую вам использовать алгоритм со сложностью O(n^5), использующий линейные префиксные суммы.


Если вы сумеете написать адекватный (то есть не высосанный из пальца) алгоритм O(n^5 log(n)) или алгоритм O(n*m), то напишите его, пожалуйста, отдельным ответом и вызовите меня через @ в комментариях к моему ответу. Также я был бы рад, если бы кто-то провел бенчмарк приведенных решений и проверил их на корректность.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.