おかしな行列積

有向グラフの最短路の計算と正方行列のべき乗の計算の間には密接な関係があります。この関係は Alfonso によって最初に発見され、後に Bellman も独立に発見しました。\(n \times n\) の行列の二乗を求めるアルゴリズムを次に示します。これを \(\textsc{FischerMeyerAPSP}\) の内側のループと比べてみてください (似ていることが分かりやすいように二つ目のアルゴリズムの記法を少し変えています)。

procedure \(\texttt{MatrixSquare}\)(\(A\))

for \(i \leftarrow 1\) to \(n\) do

for \(j \leftarrow 1\) to \(n\) do

\(A^{\prime}[i, j] \leftarrow 0\)

for \(k \leftarrow 1\) to \(n\) do

\(A^{\prime}[i, j] \leftarrow A^{\prime}[i, j] + A[i, k] \cdot A[k, j]\)

procedure \(\texttt{FischerMeyerInnerLoop}\)(\(D\))

for 頂点 \(u\) do

for 頂点 \(v\) do

\(D^{\prime}[u, v] \leftarrow \infty\)

for 頂点 \(x\) do

\(D^{\prime}[u, v] \leftarrow \min \lbrace D^{\prime}[u, v],\ D[u, x] + D[x, v] \rbrace\)

二つのアルゴリズムの唯一の違いは、一つ目のアルゴリズムの乗算の部分で二つ目のアルゴリズムは加算を使っていて、一つ目のアルゴリズムの加算の部分で二つ目のアルゴリズムは最小化を使っている点です。このことから、最短路アルゴリズムの内側のループは「min-plus 行列積」や「距離行列積」あるいは「おかしな行列積 (funny matrix multiplication)」と呼ばれることがあります。

低速な方のアルゴリズム \(\textsc{ShimbelAPSP}\) は重み行列 \(w\) の \(V-1\) "min-plus 乗" を計算するための標準的な反復アルゴリズムです。最初のループで対角線上に \(0\) が、それ以外の場所に \(\infty\) が並んだ min-plus 単位行列が作られ、二つ目のループが次の "min-plus" 乗を計算します。そして \(\textsc{FischerMeyerAPSP}\) ではこの反復法を二乗の繰り返しに置き換えています。これはちょうど一章で紹介した乗算アルゴリズムと同じであり、エジプト人 \(\acute{\alpha} \rho \pi \varepsilon \delta o \nu \acute{\alpha} \pi \tau \alpha \iota\) の影響をここにも見ることができます！

整数乗算に対する Karatsuba の分割統治アルゴリズムと同じように、(通常の) 行列乗算に対するさらに高速な分割統治アルゴリズムが存在します。そのようなアルゴリズムの中で最初に示されたのは 1969 年の Volker Strassen (フォルカー・シュトラッセン) によるアルゴリズムであり、\(n \times n\) の行列乗算を七つの \(n/2 \times n/2\) の行列乗算で計算するものです。Strassen のアルゴリズムの実行時間は \(O(n^{\lg 7}) = O(n^{2.807355})\) です。Strassen のアルゴリズムは過去五十年間の間に何度も改善され、2018 年時点で最速の行列乗算アルゴリズムの実行時間は \(O(n^{2.372864})\) です。

二乗の繰り返しよりも高速なこれらのアルゴリズムは全て減算を使っているのですが、残念ながら "おかしな" 減算なるものは存在しません (\(\min\) の逆の演算とは何でしょうか？)。そのため少なくとも一般的なグラフに対しては、動的計画法を使ったアルゴリズムの内側のループを高速化する明らかな方法は存在しません。

しかし "明らかな方法がない" は "不可能である" を意味しません！実は、全組最短路問題の特殊ケースに対する格段に高速なアルゴリズムがいくつか存在します。そのようなアルゴリズムの中で最も素晴らしいものの一つは、1991 年に Zvi Galil と Oded Margalit によって発見され、1992 年に Raimund Seidel によって簡略化された単純な乱択アルゴリズムであり、このアルゴリズムを使うと重み無し無向グラフの全組最短路を平均 \(O(M(V) \log V)\) 時間で計算できます。ここで \(M(n) = O(n^{2.372864})\) は \(n \times n\) の整数行列の (通常の意味の) 乗算にかかる時間です¹。Galil, Margalit, Seidel のアプローチはそれからさらに拡張され、今では小さい重みを持つ有向グラフの実際の最短路を、三乗を大きく下回る時間で決定的に計算できるようになっています。

重みが小さい整数の場合には大きな進展がみられているものの、辺に一般的な重みの付いたグラフに対する全組最短路問題が \(O(V^{2.999999})\) 時間で解けるのかどうかは、9 の数に関わらず誰も知りません。さらにそのようなアルゴリズムが不可能であることを示唆する証拠もいくつか存在します！そのためおそらくは、"明らかな方法がない" は "不可能である" を本当に意味するのでしょう。

Raimund Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of Computer and System Sciences, 51(3):400-403, 1995. この論文 (の少なくとも 1992 年の会議で使われたバージョン) はアルゴリズムの完全な説明と解析が論文の概要に収まっているという稀な論文の一つです。 Noga Alon, Zvi Galil, Oded Margalit*. On the exponent of the all pairs shortest path problem. Journal of Computer and System Sciences 54(2):255–262, 1997. も参照してください。^[return]