Метод чотирьох росіян

В інформатиці, метод чотирьох росіян— це техніка пришвидшення алгоритму, що використовує булеві матриці або, загальніше, алгоритмів, що використовують матриці в яких кожна комірка може набувати обмеженої кількості можливих значень.

Розроблений комбінаторний алгоритм дозволяв множити булеві матриці за $O\left(\frac{n^3}{\log n}\right)$. З маленькою зміною алгоритм може працювати за $O\left(\frac{n^3}{{\log }^{2}n}\right)$. Станом на 2015 було вже отримано алгоритм, що працює за $O\left(\frac{n^3}{{\log }^{4}n}\right)$.

Алгоритм

Нехай $A$ і $B$ будуть $n\times n$ булевими матрицями. Обираючи довільне $ϵ$ можна розбити $A$ на блоки розміру $ϵ\log n\times ϵ\log n$. Позначимо кожен такий блок через $A_{ij}$, тоді $1\le i,j\le \frac{n}{ϵ\log n}$.

Для кожної двійки $i,j$ створюємо таблицю пошуку $T_{ij}$ згідно з такою специфікацією:

для кожного бітового вектора $v$ завдовжки $ϵ\log n$: $T_{ij}[v]=A_{ij}\cdot v$.

Маємо, що $|T_{ij}|=n^{ϵ}ϵ\log n$.

Час необхідний для обчислення всіх таблиць асимптотично становить:

${\left(\frac{n}{\log n}\right)}^2{n}^{ϵ}{\log }^{2}n=n^{2+ϵ}$,

бо всього ${\left(\frac{n}{\log n}\right)}^2$ двійок $i,j$, $n^{ϵ}$ векторів $v$ і обчислення $A_{ij}v$ потребує $O({\log }^{2}n)$ для сталої $ϵ$.

Щодо матриці $B$, то кожен її стовпчик можна розбити на $\frac{n}{ϵ\log n}$ частин. Нехай $B_j^k$ буде $j-$й шматок $k-$го стовпчика. Кожен добуток $A_{ij}{B}_j^k$ можна обчислити за сталий час, бо ми вже маємо обчислені таблиці.

Щоб обчислити $Q=AB$, можна зробити наступне.

Для $j\in [1..\frac{n}{ϵ\log n}]$ : $Q_{ij}=Q_{ik}\vee (A_{ij}\cdot B_j^k)$ (за означенням булевого добутку матриць). Таким чином, час потрібний для виконання алгоритму становить

$O(n\cdot {\frac{n}{\log n}}^2\cdot \log n)=O\left(\frac{n^3}{\log n}\right)$.

Передобчисливши всі можливі побітові $\vee$ у таблицю $S$ так, що $S(u,v)=u\vee v$, де $u,v\in \{0,1{\}}^{ϵ\log n}$, можна зменшити час виконання до $O\left(\frac{n^3}{{\log }^{2}n}\right)$.

Історія

Алгоритм запропонували Арлазаров, Дініц, Кронрод і Фараджев в 1970.Шаблон:Sfn Походження назви невідоме; Шаблон:Harvtxt пояснюють:

Другий метод, часто згадуваний як алгоритм «чотирьох росіян», через кількість і громадянство його винахідників, що «практичніше» ніж алгоритм в теоремі 6.9.Шаблон:Sfn

Всі чотири автори працювали тоді в Москві.

Примітки

• Шаблон:Citation. Оригінальна назва: "Об экономном построении транзитивного замыкания ориентированного графа".
• Шаблон:Citation