Существует ли субкубический алгоритм для следующей задачи?

11

Учитывая симметричную вещественную матрицу , существует ли алгоритм, который вычисляет сумму по всем 1 \ leq i <j <k \ leq n со сложностью по времени лучше, чем O (n ^ 3) ?n×nA=(aij)

i,j,kmax(aij,aik,ajk)
1i<j<knO(n3)
user89217
источник
3
Обратите внимание, что это по крайней мере так же сложно, как подсчитать количество треугольников в данном графике. Если ваша входная матрица кодирует график так, что «0» обозначает ребро, а «1» обозначает отсутствующее ребро, то max(aij,aik,ajk)=0 тогда и только тогда, когда есть треугольник, образованный узлами i , j и k , в противном случае он равен 1 .
Юкка Суомела
1
Я думаю, что единственные известные значительно субкубические алгоритмы для подсчета треугольников основаны на быстром умножении матриц? Это может быть сложно применить эти методы здесь, в этой проблеме. Кроме того, если вы ищете что-то практичное, то все, что основано на быстром умножении матриц, не поможет.
Юкка Суомела

Ответы:

3

Существует довольно практичный подход, который работает за время , где - количество бит в слове процессора. Основная идея заключается в том, что вы последовательно перебираете элементы матрицы в порядке возрастания (произвольно разрываете связи) и «включаете их». Рассмотрим момент, когда включается самый большой элемент некоторой тройки . Для простоты предположим, что указанный элемент является . Естественно добавить значение тройки к ответу сейчас, когда последний элемент включен. Таким образом, мы должны посчитать количество возможных таких, что иO(n3/w)waij,aik,ajkaijkaikajkуже включены (это будет количество троек, здесь - самый большой элемент, поэтому они были полностью включены только сейчас). Здесь мы можем ускорить простую реализацию , используя битовую оптимизацию.aijO(n)

За подробностями вы можете обратиться к следующей реализации в C ++ 11, которая должна работать для , (он не очень оптимизирован; однако он по-прежнему превосходит наивное суммирование для с большим отрывом, по крайней мере, на моей машине).n5000|aij|109n=5000

// code is not very elegant, 
// but should be understandable
// here the matrix a has dimensions n x n
// a has to be symmetric!
int64_t solve (int n, const vector<vector<int32_t>> &a)
{
        std::vector<boost::dynamic_bitset<int64_t>> mat
        (n, boost::dynamic_bitset<int64_t>(n));

        vector<pair<int, int>> order;
        for (int j = 1; j < n; j++)
        for (int i = 0; i < j; i++)
            order.emplace_back(i, j);
        sort(order.begin(), order.end(),
            [&] (const pair<int, int> &l, const pair<int, int> &r) 
            {return a[l.first][l.second] < a[r.first][r.second];});

        int64_t ans = 0;
        for (const auto &position : order)
        {
            int i, j;
            tie (i, j) = position;
            mat[i][j] = mat[j][i] = 1;
            // here it is important that conditions 
            // mat[i][i] = 0 and mat[j][j] = 0 always hold
            ans += (mat[i] & mat[j]).count() * int64_t(a[i][j]);
        }

        return ans;
}

Если вы подумаете об обмане с оптимизацией битов, вы можете использовать метод с четырьмя русскими для получения того же результата, что дает алгоритм , который должен быть менее практичным (потому что довольно велико на большинстве современного оборудования) но теоретически лучше. Действительно, давайте выберем и сохраним каждую строку матрицы как массив целых чисел от до , где число в массив соответствует битам строки в диапазоне от включительно до исключительно вO(n3/logn)wblog2nnb02b1iibmin(n,(i+1)b)0-indexation. Мы можем предварительно рассчитать скалярные произведения каждых двух таких блоков за времени. Обновление позиции в матрице происходит быстро, потому что мы меняем только одно целое число. Чтобы найти скалярное произведение строк и просто выполните итерацию по массивам, соответствующим этим строкам, найдите скалярные произведения соответствующих блоков в таблице и суммируйте полученные произведения.O(22bb)ij

В приведенном выше абзаце предполагается, что операции с целыми числами занимают времени. Это довольно распространенное предположение , потому что оно обычно фактически не меняет сравнительную скорость алгоритмов (например, если мы не используем это предположение, метод грубой силы фактически работает за времени (здесь мы измеряем время в битовых операциях), если принимает целочисленные значения с абсолютными значениями по крайней мере до для некоторой константы (и в противном случае мы можем решить проблему с помощью умножение матриц в любом случае), однако предложенный выше метод четырех русских используетnO(1)O(n3logn)aijnεε>0O(nε)O(n3/logn) операции с числами размера в этом случае; поэтому он выполняет битовых операций, что все же лучше, чем грубая сила, несмотря на изменение модели).O(logn)O(n3)

Вопрос о существовании подхода все еще интересен.O(n3ε)

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

Кабан-5
источник
Во-первых, ваше предложение действительно кажется полезным с практической точки зрения, я мог бы просто попробовать его в моем случае использования. Спасибо! Во-вторых, вычислительная сложность ваших алгоритмов по-прежнему составляет для любого числового типа с фиксированной шириной. Не могли бы вы рассказать о подходе ? Я не понимаю, как мы можем найти скалярное произведение и быстрее, чем (что потребуется, если мы получим доступ ко всем их элементам). O(n3)O(n3/logn)mat[i]mat[j]O(n)
user89217
Кроме того, ваш код не определяет, matчто кажется важным. Я понимаю, как это можно определить, но мне интересно, (mat[i] & mat[j]).count()будет ли работать как угодно с любым контейнером STL.
user89217
1
Что касается mat- я думаю, мы должны использовать std::vector<boost::dynamic_bitset<int64_t>>.
user89217
Что касается mat: да, я имел в виду стандартный битсет на самом деле, но boost::dynamic_bitsetв данном случае это даже лучше, потому что его размер не должен быть постоянным во время компиляции. Отредактирую ответ, чтобы добавить эту деталь и уточнить подход четырех россиян.
Кабан-5
1
Отлично, это выглядит солидно для меня. Незначительный момент: поскольку в трандихотомической модели предполагается, что мы можем выполнять операции над машинными словами в , нет необходимости предварительно вычислять любые скалярные произведения. Фактически, модель предполагает, что , поэтому по крайней мере так же хорош, как . И, как вы говорите, предварительный расчет скалярных произведений не имеет практического смысла (поиск в массиве будет медленнее, чем в бинарной операции). O(1)wlog2nO(n3/w)O(n3/logn)
user89217