Czy istnieje podububowy algorytm dla następującego problemu?

Biorąc pod uwagę symetryczną rzeczywistą macierz , czy istnieje algorytm, który oblicza sumę ponad wszystkimi ze złożonością czasową lepszą niż ? $n \times n$ $A=(a_{ij})$

\sum_{i, j, k} max (a_{i j}, a_{i k}, a_{j k})

$\sum_{i,j,k}\max(a_{ij},a_{ik},a_{jk})$

1 \leq i < j < k \leq n

$1\leq i<j<k\leq n$

O (n^{3})

$O(n^3)$

algorithms time-complexity

— użytkownik89217
źródło

Zauważ, że jest to co najmniej tak trudne, jak zliczanie liczby trójkątów na danym wykresie. Jeśli macierz wejściowa koduje wykres w taki sposób, że „0” oznacza krawędź, a „1” oznacza brakującą krawędź, to

max (a_{i j}, a_{i k}, a_{j k}) = 0

$\max(a_{ij}, a_{ik}, a_{jk}) = 0$ jeśli i tylko jeśli istnieje jest trójkątem utworzonym przez węzły

i

$i$ ,

j

$j$ oraz

k

$k$ , a w przeciwnym razie jest to

1

$1$ .

— Jukka Suomela

Wydaje mi się, że jedyne znane znacznie subububne algorytmy liczenia trójkątów oparte są na szybkim mnożeniu macierzy? Zastosowanie tych technik w tym problemie może być trudne. Ponadto, jeśli szukasz czegoś praktycznego, cokolwiek oparte na szybkim mnożeniu macierzy nie będzie pomocne.

— Jukka Suomela

Istnieje dość praktyczne podejście, które działa w czasie , gdzie jest liczbą bitów w słowie procesora. Główną ideą jest to, że iterujesz kolejno elementy macierzy w kolejności rosnącej (arbitralnie zrywaj wiązania) i „włączaj je”. Rozważ moment, w którym włączony jest największy element potrójnego . Dla uproszczenia załóżmy, że wspomniany element to . Naturalne jest dodanie wartości potrójnej do odpowiedzi teraz, gdy ostatni element jest włączony. Musimy więc policzyć liczbę możliwych , takich jak i $O(n^3 / w)$ $w$ $a_{ij}, a_{ik}, a_{jk}$ $a_{ij}$ $k$ $a_{ik}$ $a_{jk}$ są już włączone (byłaby to liczba potrójnych, tutaj jest największym elementem, więc zostały całkowicie włączone). Tutaj możemy przyspieszyć naiwną implementację za pomocą optymalizacji bitów. $a_{ij}$ $O(n)$

Szczegółowe informacje można znaleźć w następującej implementacji w C ++ 11, która powinna działać dla , (nie jest zbytnio zoptymalizowany, jednak nadal bije naiwne sumowanie dla o dużym marginesie przynajmniej na mojej maszynie). $n \leqslant 5000$ $|a_{ij}| \leqslant 10^9$ $n = 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;
}

Jeśli zastanawiasz się nad wykorzystaniem oszukiwania bitów, możesz użyć metody czterech Rosjan do tego samego wyniku, uzyskując algorytm , który powinien być mniej praktyczny (ponieważ jest dość duży na większości nowoczesnych urządzeń) ale teoretycznie jest lepszy. Rzeczywiście, wybierzmy i zachowajmy każdy wiersz macierzy jako tablicę liczb całkowitych od do , gdzie -ta liczba w tablica odpowiada bitom rzędu od włącznie do wyłączne w $O(n^3 / \log n)$ $w$ $b \approx \log_2 n$ $\lceil \frac{n}{b} \rceil$ $0$ $2^b - 1$ $i$ $ib$ $\min(n, (i + 1)b)$ $0$ -indeksacja. Możemy wstępnie obliczyć iloczyn skalarny co dwa takie bloki w czasie . Aktualizacja pozycji w macierzy jest szybka, ponieważ zmieniamy tylko jedną liczbę całkowitą. Aby znaleźć iloczyn skalarny wierszy i po prostu iteruj po tablicach odpowiadających tym wierszom, wyszukaj produkty skalarne odpowiednich bloków w tabeli i podsumuj uzyskane produkty. $O(2^{2b} b)$ $i$ $j$

Powyższy akapit zakłada, że operacje na liczbach całkowitych zajmują czas . Jest to dość powszechne założenie , ponieważ zwykle nie zmienia w rzeczywistości szybkości porównawczej algorytmów (na przykład, jeśli nie użyjemy tego założenia, metoda brutalnej siły faktycznie działa w czasie (tutaj mierzymy czas w operacjach bitowych) jeśli weźmy wartości całkowite o wartościach bezwzględnych co najmniej do dla niektórych stałych (a w przeciwnym razie możemy rozwiązać problem z tak mnożenia macierzy), jednak sugerowana powyżej metoda czterech Rosjan używa $\leqslant n$ $O(1)$ $O(n^3 \log n)$ $a_{ij}$ $n^{\varepsilon}$ $\varepsilon > 0$ $O(n^{\varepsilon})$ $O(n^3 / \log n)$ Operacje z numerami o rozmiarze w takim przypadku; więc wykonuje operacje bitowe , co jest nadal lepsze niż brutalna siła pomimo zmiany modelu). $O(\log n)$ $O(n^3)$

Pytanie o istnienie podejścia jest jednak nadal interesujące. $O(n^{3 - \varepsilon})$

Techniki (optymalizacja bitów i metoda czterech Rosjan) przedstawione w tej odpowiedzi nie są bynajmniej oryginalne i zostały tutaj przedstawione w celu uzupełnienia ekspozycji. Jednak znalezienie sposobu ich zastosowania nie było trywialne.

— Kaban-5
źródło

Po pierwsze, twoja sugestia rzeczywiście wydaje się pomocna z praktycznego punktu widzenia, mógłbym po prostu wypróbować ją w moim przypadku użycia. Dzięki! Po drugie, złożoność obliczeniowa algorytmów wciąż wynosi dla dowolnego typu liczbowego o stałej szerokości. Czy mógłbyś wyjaśnić podejście ? Nie rozumiem, jak moglibyśmy znaleźć iloczyn skalarny i szybszy niż (co byłoby wymagane, jeśli uzyskamy dostęp do wszystkich ich elementów).

O (n^{3})

$O(n^3)$

O (n^{3} / \log n)

$O(n^3 / \log n)$ mat[i]mat[j]

O (n)

$O(n)$

— user89217,

Ponadto twój kod nie określa, matktóre wydają się ważne. Rozumiem, jak można to zdefiniować, ale zastanawiam się, czy (mat[i] & mat[j]).count()będzie działać zgodnie z oczekiwaniami z dowolnym kontenerem STL.

— user89217,

Odnośnie mat- myślę, że musimy użyć std::vector<boost::dynamic_bitset<int64_t>>.

— user89217,

Odnośnie mat: tak, miałem na myśli standardowy zestaw bitów, ale boost::dynamic_bitsetw tym przypadku jest jeszcze lepszy, ponieważ jego rozmiar nie musi być stały w czasie kompilacji. Przeredaguje odpowiedź, aby dodać ten szczegół i wyjaśnić podejście czterech Rosjan.

— Kaban-5

Świetnie, dla mnie wygląda to solidnie. Drobna uwaga: ponieważ model transdikotomiczny zakłada, że możemy wykonywać operacje na słowach maszynowych w , nie ma potrzeby wstępnego obliczania produktów skalarnych. W rzeczywistości model zakłada, że , więc jest co najmniej tak dobre jak . I, jak mówisz, wstępne obliczanie produktów skalarnych nie ma praktycznego sensu (wyszukiwanie tablicy będzie wolniejsze niż operacji binarnych).

O (1)

$O(1)$

w \geq \log_{2} n

$w\ge\log_2 n$

O (n^{3} / w)

$O(n^3/w)$

O (n^{3} / \log n)

$O(n^3/\log n)$

— user89217,