最短経路問題に対する
高校代数による解法

1 はじめに

最短経路（SP）問題は、2 つの頂点間のパスのうち、そのパスに沿ったエッジの重みの総和がグラフ内のすべてのパスの中で最小となるものを求める問題である。最短経路問題の応用には、デジタル地図サービス、サプライチェーン管理、ロボットの経路計画、電気通信のネットワークルーティング、電力網の想定事故解析、回路設計、ソーシャルネットワークにおけるコミュニティ検出、金融市場における裁定取引などがある。

既存の解法、特に Dijkstra 法 [4] と Bellman-Ford 法 [2,3,8] は、反復的なグラフ探索と、距離の推定値を維持するための大量の記録管理に依存している。これらの手法は基礎的なものであるが、特定の条件下では非効率になるか、あるいは失敗する。

本論文では、高校代数の新しい使い方を考案してグラフ問題を解くという、根本的に異なる視点を示す。[1, 7] で詳述されている高校代数は、強力で美しく、複雑な数学的定義や証明に巻き込まれることなく取り組めるものである。この代数は、本質的には難しい問題を扱いやすくするための概念を考案することにある。本論文では、グラフ問題を単純な代数方程式によって捉え、それらの方程式を解くことで答えを見つける新しい代数的枠組みを紹介する。これは学校で文章題を解くことに似ている。この手法は、SP 問題のようなさまざまな難しいグラフ問題に適用できる。「全パス」問題の根本的な難しさは、グラフが天文学的な数のパスを持ち得ること、そして答えを見つけるためにすべてのパスを解析することが問題によって求められることにある。代数は、有向グラフ内のすべてのパスを体系的に整理し解析するための強力な方法を提供する。

我々の代数的枠組みでは、有向グラフ内のすべてのパスは、変数がグラフのエッジに対応する代数式として表される。特定の全パス問題は、代数演算の問題固有の解釈と、代数式の構文解析と簡約によって解かれる。SP 問題では、加算は最小値として解釈され（p₁ + p₂: 2 つのノード間のパスの区間の加算は、パスの区間 p₁ と p₂ のうち重みが最小のものである）、乗算は連結として解釈される（p₁p₂: 乗算は、ノード a から b へのパスの区間 p₁ と、ノード b から c へのパスの区間 p₂ の連結であり、p₁p₂ の重みは p₁ と p₂ の重みの和である）。このモデルの効率は代数的な簡約に由来する。例えば、代数的な因数分解によって、有向グラフ内のすべてのパスに対するコンパクトな式が得られる。

最大流問題やソフトウェア検証問題のような「全パス」問題に対する代数的アプローチの、より広い意味と利点について論じる。ソフトウェア検証の根本的な難しさは、すべての実行パスを解析することが求められる点にある。ソフトウェア検証に関する Dijkstra の構想 [5] と構造化プログラミングに関する Knuth の構想 [6] を受けて、異なる分野の難しい問題に対する統一的な解法アプローチのための新しい代数的なつながりと、効率的で洗練された解法を見つけるために代数の強力な能力を活用できる可能性について論じる。

第 2 節では、有向グラフの問題を解くための代数の使用を動機付け例示する例を示す。第 3 節では、パス代数の形式的な説明と、それを用いたパスの代数モデルの構築を示す。第 4 節では、負の重みと閉路を持つ有向グラフに対する効率的な代数的 SP 解法を説明する。第 5 節では、代数的解法を従来の解法と比較する。第 6 節では、代数的手法のより広い探究について論じる。第 7 節は結論である。

2 動機付けの例

次の新しいアイデアを動機付けるための例を示す。

1. 有向グラフは代数方程式として表すことができる。
2. その代数的表現から、グラフ内のパスのコンパクトな代数モデルが得られる。
3. コンパクトな代数モデルは、全パス問題を解くために使える。最短経路問題を通じてこれを説明する。

2.1 代数方程式として表されたグラフ

図 1 は、有向グラフとそれを表す代数方程式を示している。頂点ごとに 1 つの代数方程式がある。各頂点 v_i には変数 x_i が割り当てられる。x_i は v₀ から v_i へのすべてのパスを表す。変数 x_i は、我々が答えを得たい未知数である。

各 x_i について方程式を立てる。x_i の方程式は、v_i へのパスが、その先行頂点 v_j へのパスから得られることを表している。v_i へのパスを得るには、先行頂点 v_j へのパスをとり、それに v_j から v_i へのエッジを右から掛ける（連結する）。v₁ が v₂ の唯一の先行頂点であり、e₂ が v₁ から v₂ へのエッジであるとすると、方程式は x₂ = x₁e₂ である。v₂ と v₃ が v₄ の先行頂点であり、e₄、e₅ がそれぞれ先行頂点からのエッジであるとすると、v₄ の方程式は x₄ = x₂e₄ + x₃e₅ である。加算はパスの和集合を表す。言い換えれば、x₄ = x₂e₄ + x₃e₅ は、v₀ から v₄ へのパスの集合が 2 つの集合の和集合であることを意味する。1 つは v₀ から v₂ へのパスの集合に e₄ を連結したものであり、もう 1 つは v₀ から v₃ へのパスの集合に e₅ を連結したものである。図 1 では、v₀ から v₄ へのパスの集合が {e₁e₂e₄} ∪ {e₁e₃e₅} であることが分かる。先行頂点を持たない頂点であるソースについては x₀ = 1 であることに注意されたい。代数モデルにおいて、「1」は数の 1 ではなく空のパスを表す。

2.2 パスの代数モデル

図 2 は、ソースからシンクへのパスのコンパクトな代数モデルとしての代数式の導出を示している。上で立てた頂点の方程式（図 1）を解く。得られる答えは、変数がエッジの記号 e_i である代数式である。この代数式がパスの代数モデルである。代数モデルの部分式を右から掛け合わせて得られる各項が、エッジの列によってラベル付けされたちょうど 1 つのパスを与えることが分かるであろう。すべてのパスは、パスの代数モデルによって一意に捉えられる。

この例では、v₀ がソース、v₇ がシンクである。図 2 に示すように、代数式はソースから始まる後退代入によって導出される。後退代入を 1 回行うごとに 1 つの v_i の代数モデルが得られ、最終的に v₇ の代数モデルが得られる。x_i の解として得られる代数式は、v₀ から v_i へのパスのモデルである。

解 x₇ = e₁(e₂e₄ + e₃e₅)(e₆e₈ + e₇e₉) は、v₀ から v₇ へのすべてのパスを表す。パスは、ちょうど部分式を掛け合わせて得られる項である。ここでの項は e₁e₂e₄e₆e₈、e₁e₂e₄e₇e₉、e₁e₃e₅e₆e₈、e₁e₃e₅e₇e₉ である。図 1 では、これらの項がちょうど v₀ から v₇ への 4 つのパスであることが分かる。各項は、エッジの列によってラベル付けされた 1 つのパスである。

すべてのパスを表す代数式がコンパクトなのは、代数的な因数分解によるものである。パスの数はエッジの数に比べて極めて大きくなり得るが、パスの代数モデルのサイズはエッジの数に比例し、コンパクトなままである。

2.3 代数モデルからの最短経路

エッジの重みの集合が与えられると、それに対応する最短経路がある。代数モデルから最短経路を得る方法を例示する。重みについて 2 つのシナリオで行う。第 1 のシナリオではすべての重みが正であり、第 2 のシナリオでは一部の重みが負である。代数的手法を Dijkstra と Bellman-Ford の SP アルゴリズムに関連付けるために、この 2 つのシナリオを選んだ。

Dijkstra の SP アルゴリズムは負の重みでは機能しない。Bellman-Ford の SP アルゴリズムは負の重みでも機能するが、Dijkstra のアルゴリズムよりもかなり多くの計算を必要とする。代数的手法は、Bellman-Ford のアルゴリズムが必要とする追加の計算なしに、負の重みでも機能する。

Dijkstra と Bellman-Ford のアルゴリズムでは、重みが変わると計算全体を繰り返す必要がある。対照的に、代数的手法では、重みが変わっても計算の大部分（方程式を立てて解くこと）を繰り返さない。代数モデルから最短経路を得るためにエッジの重みを代入する作業だけを繰り返す。これは、重みが変わり続ける多くの応用において、代数的手法の重要な利点である。例えば、SP 問題が最速ルートを計算することであるデジタル地図の応用では、各エッジは道路の区間に対応し、エッジを通過する時間がそのエッジの重みであり、重みは交通状況の変化に応じて変わり続ける。

2 つの重みのシナリオを見ていく前に、簡単な観察をしておく。代数モデルはすべてのパスを表す。前述のとおり、各パスを代数的な項として得ることができる。パス内のエッジの重みを加算することで、各パスの重みを得られる。そして、重みが最小のパスを選べばよい。ここで、x₇ = e₁(e₂e₄ + e₃e₅)(e₆e₈ + e₇e₉) は、v₀ から v₇ への 4 つのパス p₁: e₁e₂e₄e₆e₈、p₂: e₁e₂e₄e₇e₉、p₃: e₁e₃e₅e₆e₈、p₄: e₁e₃e₅e₇e₉ を表す。各パス内のエッジの重みを加算すると、パス p₁, p₂, p₃, p₄ の重みはそれぞれ 16、14、26、24 である。最短経路は、すべてのパスの中で最小の重み 14 を持つ p₂ である。この手順で最短経路は見つかるが、ひどく非効率である。以下のシナリオでは、最短経路を見つけるためのかなり効率的な方法を示唆する。要点の 1 つは、各パスの重みを個別に計算するのを避けることである。図 3 と図 4 の 2 つのシナリオで最短経路を計算するうえで代数的な簡約が果たす決定的な役割について、考えてみてほしい。最も効率的な代数的手法は後で形式的に説明する。

2.3.1 シナリオ 1: 正の重みでの最短経路

図 3 は、正の重みで最短経路を求める方法を示している。重みは e₁: 3, e₂: 2, e₃: 8, e₄: 3, e₅: 7, e₆: 6, e₇: 5, e₈: 2, e₉: 1 である。重みをエッジに代入する。SP 問題は、加算を重みが最小の項の選択として、乗算を連結と重みの加算として解釈することで解かれる。

いくつかの代数的な簡約を用いて解いてみよう。まず、重み 2 と 3 を加算して e₂e₄ の重み 5 を得る。同様に、e₃e₅ の重み 15 を得る。次に、(e₂e₄ + e₃e₅) を重みが最小の項 e₂e₄ で置き換える。同様に、e₆e₈ の重みは 8、e₇e₉ の重みは 6 であるため、(e₆e₈ + e₇e₉) を重みが最小の項 e₇e₉ で置き換える。すると、x₇ = e₁(e₂e₄ + e₃e₅)(e₆e₈ + e₇e₉) について e₁e₂e₄e₇e₉ が得られる。これが重み 3 + 5 + 6 = 14 の最短経路である。先の答えと同じであるが、今回はより少ない作業で済んだことに注意されたい。

2.3.2 シナリオ 2: 負の重みでの最短経路

図 4 は、負の重みで最短経路を求める方法を示している。重みは e₁: 3, e₂: 2, e₃: 8, e₄: 3, e₅: −7, e₆: 6, e₇: 5, e₈: −2, e₉: 1 である。

代数的手法では違いはない。負の重みは正の重みと同じように扱われる。(e₂e₄ + e₃e₅) を、重み 1 を持つ重みが最小の項 e₃e₅ で置き換える。(e₆e₈ + e₇e₉) を、重み 4 を持つ重みが最小の項 e₆e₈ で置き換える。すると、x₇ = e₁(e₂e₄ + e₃e₅)(e₆e₈ + e₇e₉) について e₁e₃e₅e₆e₈ が得られる。これが重み 3 + 1 + 4 = 8 の最短経路である。

代数モデルを用いれば、正の重みでも負の重みでも同じ手順が機能することに注意されたい。

3 パス代数とすべてのパスの代数モデル

動機付けの例は、パスの代数モデル、その使い方、そしてその構築についての直観を伝えるものであった。ここでは、パス代数を導入することで形式的な説明を与える。

3.1 パス代数

パス代数は、有向グラフのパスの区間の上で定義される。

パス代数において、代数式 E はパスの区間の集合を表す。2 つの代数式の加算 E₁ + E₂ は、パスの区間の集合の和集合である。2 つの代数式の乗算 E₁E₂ は、p_α が E₁ のパスの区間であり、q_β が E₂ のパスの区間であるようなパスの区間 p_αq_β の集合である。パスの区間の乗算は区間の連結である。乗算は可換ではない。乗算では正しい順序を保つよう注意しなければならない。したがって、方程式 x₂ = x₁e₂（例 1 のように）を x₂ = e₂x₁ に変えることはできない。解 x₂ = e₁e₂ を x₂ = e₂e₁ に変えることもできない。

代数モデルにおける加算と乗算では、パスの区間にいくつかの制約がある。これは行列の加算と乗算におけるサイズの制約に似ている。加算 p₁ + p₂ では、p₁ と p₂ は同じ始点と同じ終点を持たなければならない。乗算 p₁p₂ では、p₁ の終点が p₂ の始点でなければならない。例えば、代数モデル E₁(E₂ + E₃)E₄ を考える。E₁ のすべてのパスの区間は、E₂ と E₃ のパスの区間が始まる頂点 A で終わる。E₂ と E₃ のすべてのパスの区間は、E₄ のすべてのパスの区間が始まる同じ頂点 B で終わる。各頂点について方程式を立てて解くことで代数モデルを構築すれば、パスの区間の加算と乗算に対するこれらの制約が満たされることが保証される点に注意されたい。

正規表現の Kleene 代数 [9]（そして一般に環と呼ばれる代数構造）と同様に、パス代数の加算と乗算は結合的である。パス代数は、その要素（パスの区間）が加法逆元を持たないため半環である。パス代数は環の重要な性質を持つ。すなわち、乗算は加算に対して分配的である。この性質によって因数分解が可能になり、これはすべてのパスのコンパクトな代数モデルを形成するうえで決定的に重要である。例えば、深さ n の完全に埋まった二分木は、根から葉まで 2ⁿ 本のパスを持つ。我々は、2ⁿ 本のパスすべてを、わずか 2n 項の式、本質的には n∏i=1(e_i,1 + e_i,2) で表すことができる。

3.2 パスの代数モデル

パスの代数モデルは、根付き有向グラフのためのものである。このモデルは、根（ソースと呼ぶ）からグラフの各ノードへのすべてのパスのコンパクトな表現として重要である。すべてのパスの解析を必要とする問題（例えば、SP 問題や最大流問題）は、モデルがコンパクトな表現と問題を解くための代数的な簡約を提供するため、効率的に解くことができる。

定義: 頂点 v₀（ソース）、v₁, v₂, … , v_t を持つ有向グラフ G について、G の代数モデルとは、パス代数の式の集合 E₁, E₂, … , E_t であり、E_i は v₀ から v_i へのパスの集合を表す。

パスの代数モデルの構築

1. グラフの線形方程式を立てる。
2. 後退代入を行って方程式を解く。

線形方程式を立てる

各ノード v_i に変数 x_i を割り当てる。x_i は v₀ から v_i へのすべてのパスを表す。k(i) を v_i の先行ノードの数とする。各 x_i の方程式を次のように立てる。v_{i 1}, v_{i 2}, … , v_{i k(i)} を v_i の先行ノードとし、e_{i j} を v_{i j} から v_i へのエッジとする。x_i の方程式は x_i = k(i)∑j=1 x_{i j}e_{i j} である。

x_i の方程式は、v_i へのパスが、その各先行ノード v_{i j} へのパスに、先行ノード v_{i j} から v_i へのエッジ e_{i j} を右から掛けた（連結した）ものであることを表している。

v₀ の方程式は x₀ = 1 である。

後退代入によって方程式を解く

x_i について解くには、v_i の各先行ノード v_{i j} の解として得られたパスの式を後退代入する。E_{i j} を v_{i j} の解として得られたパスの式とする。後退代入により、x_i の解は x_i = k(i)∑j=1 E_{i j}e_{i j} となる。

後退代入は x₀ = 1 から始まる。各後退代入では、x_i について解くために k(i) 回の演算が必要である。ここで k(i) は x_i の方程式の項の数である。

3.3 後退代入中の閉路の検出

閉路とは、ノードが繰り返し現れるパスのことである。例として、パス ABCABCD は、閉路 ABC を持つノード A から D へのパスである。このパスは、C から 2 本のエッジがなければならないことを意味する。閉路を作るために A へ向かう e₁ と、閉路 ABC の外にある D へ向かう e₂ である。

閉路は、後退代入を行いながら次のように検出できる。閉路が生じるのは、v_i の先行ノード v_{i j} が v_i を祖先として持つためである。このとき、後退代入によって、同じ変数が方程式の両辺に現れる方程式、すなわち x_i = Exp1 + x_iExp2 が得られる。後退代入によって変数が方程式の両辺に現れる方程式に至ったとき、閉路が検出される。

図 5 は、閉路とその検出方法を例示している。後退代入により x₁ = e₁ + x₁e₂e₃e₄ が得られ、x₁ が両辺にあることが閉路を示している。

4 効率的な代数的 SP 解法

代数モデルは、特定の問題に対してより効率的になるようカスタマイズできる。ここでは SP 問題のためのカスタマイズについて論じる。

SP のためのカスタマイズは次のとおりである。代数式 x_i = E_i は、ソースから v_i へのすべてのパスを表すことに注意されたい。E_i を後退代入する前に、E_i から SP のための部分式 S(E_i) を導出し、E_i の代わりに S(E_i) を後退代入することができる。

SP の導出において、パスの乗算はパスの連結と重みの加算であり、パスの加算は重みが最小のパスである。例えば、E_i = ∑_j E_{i j} であり、部分式 E_{i 1} が SP を与えるならば、E_{i 1} を後退代入する。このカスタマイズを図 6 に示す。

V を頂点の数、E をエッジの数とする。この効率的な代数的解法の時間計算量は E に比例する。代数的解法は 2 つのステップからなり、以下で論じるように、各ステップの時間計算量は E に比例する。

方程式を立てる時間計算量: 各頂点 v_i について、方程式は x_i = k(i)∑j=1 x_{i j}e_{i j} である。ここで x_{i j} は v_i の先行ノード v_{i 1}, v_{i 2}, …, v_{i k(i)} の変数であり、e_{i j} は v_{i j} から v_i へのエッジである。各エッジ e はちょうど 1 つの方程式の中に e = e_{i j} としてちょうど 1 回現れるため、エッジの全体は、すべての方程式にわたる x_{i j}e_{i j} 項の全体にちょうど対応する。すなわち V∑i=1 k(i) = E である。直観的には、頂点ごとに 1 つ、V 個の方程式がある。各方程式は、その頂点に入るエッジ 1 本につき 1 つの項を持つ。頂点あたりのそのようなエッジの平均数が E/V であれば、アルゴリズムは V ∗ E/V、つまり単に E に比例する作業を行わなければならない。したがって、方程式を立てる時間計算量は E に比例する。

後退代入の時間計算量: カスタマイズした代数的 SP 解法（図 6 を参照）で論じたように、後退代入は、頂点 v_i の各先行ノード v_{i j} について SP p_{i j} を求め、方程式 x_i = k(i)∑j=1 x_{i j}e_{i j} の x_{i j} に p_{i j} を代入することで順次進む。この代入は p_{i j} を e_{i j} で延長し、延長したパスの重みを計算するために 1 回の加算を伴う。v_i の SP は、k 本の延長したパスの間の k − 1 回の比較によって決まる。したがって、x_i の SP を計算する後退代入のステップ x_i = k(i)∑j=1 x_{i j}e_{i j} には、k(i) 回の加算と k(i) − 1 回の比較が必要である。V∑i=1 k(i) = E であるから、加算の総数は E、比較の総数は V∑i=1(k(i) − 1) = E − V である。

したがって、効率的な代数的 SP 解法の全体の計算量は E に比例する。密なグラフでは、E は V² に比例する。実際の応用では、グラフは疎である。すなわち、E は V に比例する。

5 代数と従来のグラフ探索による解法の比較

代数的解法が Dijkstra 法 [4] や Bellman-Ford 法 [2,3,7] による解法より優れている理由を論じる。正または負の重みを持つ有向グラフについて解法を比較する。Dijkstra 法は無向グラフを扱えるが、負の重みには機能しない。Bellman-Ford 法は負の重みを扱えるが、負の重みを持つ無向グラフには機能しない。負の重みを持つ無向エッジは負の閉路であることに注意されたい。Bellman-Ford 法は、負の閉路がある場合には最短単純パスを見つけられない。我々の知る限り、負の重みを持つ無向グラフに対する最短単純パス（SSP）問題は未解決のままである。

5.1 ソースからシンクへの SP 問題のための最小の作業量

まず、負の重みを持つ有向グラフにおけるソースからシンクへの SP 問題では、最小の作業量が E に比例することを指摘するために、いくつかの観察を示す。

観察 1: SP を見つけるために各エッジを少なくとも 1 回調べる必要がある、正のエッジの重みを持つ有向グラフが存在する。

例 1: 観察 1 の簡単な実例を示す。G を、ソースからシンクへの 2 本の異なるパス e_{1 1}e_{1 2} … e_{1 k} と e_{2 1}e_{2 2} … e_{2 k} を持つ有向グラフとする。すべてのエッジの重みは 1 である。G で SP を見つけるには、各エッジを少なくとも 1 回調べる必要がある。

観察 2: すべてのエッジを調べることなく SP を見つけられる、正のエッジの重みを持つ有向グラフが存在する。

例 2: 観察 2 の簡単な実例を示す。G を、ソースからシンクへの 2 本の異なるパス e_{1 1}e_{1 2} … e_{1 k} と e_{2 1}e_{2 2} … e_{2 k} を持つグラフとする。e_{2 1} が重み k を持つことを除き、すべてのエッジの重みは 1 である。ここでは、エッジ e_{2 2} から e_{2 k} を調べることなく、SP e_{1 1}e_{1 2} … e_{1 k} を見つけることができる。

観察 3: 負のエッジの重みを持つ有向グラフでは、SP を見つけるために各エッジを少なくとも 1 回調べることが常に必要である。

Dijkstra 法は、重みによってはすべてのエッジを調べない可能性があるため、負の重みを持つグラフでは失敗し得る。

例 3: G を例 2 と同じとし、e_{2 k} が重み −k を持つことを除いて重みも同じとする。Dijkstra 法は e_{1 1}e_{1 2} … e_{1 k} を SP として見つけ、エッジ e_{2 2} から e_{2 k} を調べない。Dijkstra 法は誤った SP を得る。正しい SP は e_{2 1}e_{2 2} … e_{2 k} である。

5.2 代数と Dijkstra 法

Dijkstra 法の時間計算量は E + V に比例する [8]。第 3 節で論じたように、代数的解法の時間計算量は E に比例し、Dijkstra 法より効率的である。

Dijkstra 法は負の重みで失敗し得る。代数的解法は負の重みを扱える。代数的解法は最適であり、E 回の連結と E 回の加算を必要とする。これは負の重みを扱うのに必要な最小の作業量である。Dijkstra 法は正の重みを持つ無向グラフに機能する。代数的手法は無向グラフには適用できない。

動機付けの例で述べたように、重みが変わるために最短経路を繰り返し再計算しなければならない応用では、代数的手法は Dijkstra 法に対して重要な利点を持つ。代数的手法では、作業の大部分である方程式を立てて解く作業は、異なる重みに対して繰り返されない。対照的に、Dijkstra 法では、重みが変わると作業全体を繰り返さなければならない。

5.3 代数と Bellman-Ford 法

Bellman-Ford 法は負の重みを扱えるが、そのためには Dijkstra 法よりかなり多くの計算を必要とする。代数的手法は、計算を増やすことなく負の重みを扱う。Bellman-Ford 法の時間計算量は EV に比例する [8]。代数的解法の時間計算量は E に比例し、Bellman-Ford 法よりかなり効率的である。

動機付けの例で述べたように、重みが変わるために最短経路を繰り返し再計算しなければならない応用では、代数的手法は Bellman-Ford 法に対して重要な利点を持つ。代数的手法では、作業の大部分である方程式を立てて解く作業は、異なる重みに対して繰り返されない。対照的に、Bellman-Ford 法では、重みが変わると作業全体を繰り返さなければならない。

6 代数のより広い探究

我々は、代数的手法の適用可能性と利点が SP 問題をはるかに超えて広がると期待している。SP 問題はそれほど複雑でないため、代数的手法のいくつかの重要な能力は SP 問題では必要とされない。進行中の探究において、最大流問題が次の段階の複雑さを示し、その先にはソフトウェアにおける制御フローとデータフローを解析する、より複雑な問題があることが分かっている。我々は、これらの複雑な問題に対する新しい効率的な代数的解法を見つけられると期待している。本節では、他の研究者が代数的手法の探究と発展に関心を持ってくれることを願って、代数的手法の利点と拡張性についての我々の理解を共有する。

6.1 代数的な因数分解による構造を考慮した計算

代数的な因数分解はグラフの構造を捉え、すべてのパスのコンパクトなモデルを構築することを可能にする。代数は、構造的な異常を分離するフィルタとしても働く。

代数的な因数分解がどのように構造を捉えるかを例で示そう。図 7 (a) は、2 つの部分グラフ G₁ と G₂ から構成されるグラフ G を示している。これは G = G₁G₂ のようなものであり、すなわち G は G₁ の後に G₂ が続くものとして因数分解できる。G はソース v_s とシンク v_t を持つ。G₁ はソース v_s とシンク v_x を持つ。G₂ はソース v_x とシンク v_t を持つ。G について問題（例えば、SP 問題、最大流問題など）を解くことは、G₁ についての問題と G₂ についての問題という、2 つのより小さな問題を解くことになる。G₁ と G₂ の解を組み合わせることで G の解が得られる。例えば、G の SP は p₁p₂ である。ここで p₁ と p₂ はそれぞれ G₁ と G₂ の最短経路である。

グラフの構造的な分解は、計算上の障壁となり得るパスの数の天文学的な増大を克服できる。G, G₁、G₂ のパスの数をそれぞれ m, m₁、m₂ で表す。G では、ソースから目的地への m = m₁m₂ 本のパスについて計算する。分解を用いると、m₁ + m₂ 本のパスについて計算する。パスの数の天文学的な増大は、部分グラフの乗法的な効果によるものである。天文学的な数のパスという計算上の障壁は、分解を用いることで回避できる。

代数的な因数分解は、まさにグラフの構造的な分解を用いるための数学的な道具である。図 7(a) は、代数的な因数分解が構造的な分解にどのように対応するかを示している。高校で学ぶ代数的な因数分解が、グラフ上の効率的な計算のための強力な手法になるのは興味深い。図 7(a) では、2 つのグラフの部分構造が、代数的な因数分解における 2 つの部分式として反映されていることに注意されたい。

代数的な因数分解には、もう 1 つ微妙だが重要な利点がある。それは、分解を見えにくくする構造的な異常を取り除くことである。これを図 7(b) に示す。ここでは、構造的な分解がエッジ e₁₀ によって見えにくくなっている。因数分解が、エッジ e₁₀ によって生じる異常を、それに隣接するエッジ e₃ と e₉ とともに分離していることに注意されたい。

6.2 構造化プログラム、構造化グラフ、代数的な因数分解

Knuth は、Structured Programming with go to Statements [6] と題した論文で次のように書いている。

「本当の問題は構造化プログラミングであるが、残念ながらこれは、その意味が人によって同じように理解されることがめったにない標語になってしまった。誰もがそれを良いものだと知っているが、McCracken が言ったように、『あえて定義しようとする人はほとんどいない。実際、今のところ単純な定義が存在するかどうかも明らかではない。』本当に明らかなことは 1 つだけである。構造化プログラミングとは、プログラムを書いてからその go to 文を取り除く過程ではない。」

Knuth はさらに続ける。

「実際、構造化プログラミングという名前の由来となった Dijkstra の元の論文は、go to 文にまったく触れていない。彼は、『プログラムが大きくなっても、過度な労力なしに正しさの証明を与えられるのは、どのようなプログラム構造に対してか』という決定的な問いに注意を向けたのである。正しさの証明とは公理からの形式的な導出を意味するのではなく、『十分に説得力のある』あらゆる種類の証明（形式的であれ非形式的であれ）を意味すると彼は説明した。そして証明とは、実のところ理解を意味する。」

代数的手法が構造化プログラムとどう関係するのかと思われるかもしれない。非常に興味深いつながりを指摘できる。図 7(a) と 7(b) のグラフを制御フローグラフだと想像してほしい。図 7(a) のグラフのプログラムは、2 つの連続する if 文で書かれた「構造化された」ものになる。図 7(b) のグラフは、エッジ e₁₀ のために go to 文を必要とする。興味深いことに、グラフにおける構造的な異常は、非構造的とみなされるプログラミングの文に対応する。

我々は、「構造化プログラム」の概念に並行する「構造化グラフ」という数学的な概念を推測している。Dijkstra の直観 [5] に従えば、制御フローグラフが構造化されているプログラムでは、ソフトウェア検証がより単純になり得る。ソフトウェア検証にはすべての実行パスの解析が必要である。同様に、すべてのパスの解析を必要とする他のグラフ問題でも、グラフが構造化されていれば解法がより単純になり得る。今後の論文では、グラフが構造化されている場合の最大流問題に対する、より単純で効率的な代数的解法を示す予定である。

進行中の研究において、我々は構造化グラフの興味深い特徴付けを追求している。1 つのソースと 1 つのシンクを持ち、すべてのノードがソースからシンクへのいずれかのパス上にある有向グラフが構造化されているのは、ソースからシンクへのすべてのパスの最適に因数分解された代数モデルにおいて、すべてのエッジがちょうど 1 回現れるとき、かつそのときに限る。その系として、構造化プログラムは、その制御フローグラフが構造化されているプログラムとして特徴付けられることになる。

図 7(a) のグラフでは、代数モデル e₁(e₂e₄ + e₃e₅)(e₆e₈ + e₇e₉) においてすべてのエッジがちょうど 1 回現れることに注意されたい。図 7(b) のグラフでは、代数モデル e₁[(e₂e₄ + e₃e₅)(e₆e₈ + e₇e₉) + e₃e₁₀e₉] において一部のエッジが複数回現れる。図 7(b) のグラフについて他の因数分解を試すこともできるが、どの因数分解でも一部のエッジは必ず繰り返される。繰り返しが最大になるのは因数分解をまったく行わない場合であり、そのときすべてのパスの代数モデルは単にすべてのパスの和 e₁e₂e₄e₆e₈ + e₁e₂e₄e₇e₉ + e₁e₃e₅e₆e₈ + e₁e₃e₅e₇e₉ + e₁e₃e₁₀e₉ となる。読者には、図 7(b) に示したグラフについて代数方程式を立てて解き、代数モデルを求めてみることをお勧めする。それは第 2 節の動機付けの例で示した作業と同様のものになる。読者は、C プログラムを入力とする自動化ツールによってグラフ、方程式、代数モデルが導出される動画 [11] を見ることもできる。

代数を用いれば、SP 問題に対して行ったように、特定の問題に対する効率的な解法を開発できる。しかし、全パスのグラフ問題に対する代数的解法の一般理論を探究する必要がある。代数式を因数分解する方法は複数あることに注意されたい。有望な道筋は、因数分解の一般理論である。そこには、その最適性と、根本的な課題が天文学的な数のパスである難しいグラフ問題に対して効率的な解法を導くためのその利用が含まれる。

7 結論

本論文は、有向グラフに対する新しい SP 解法を示す。この解法は負の重みと負の閉路を扱う。時間計算量は、Dijkstra 法では E + V に比例し、Bellman-Ford 法では EV に比例し、新しい解法では E に比例する。新しい解法は負の閉路を検出する。

我々の知る限り、次の SP 問題は未解決である。

1. 有向グラフ: 負の閉路が存在するときに最短単純パスを見つける。
2. 無向グラフ: 一部のエッジの重みが負であるときに最短単純パスを見つける。

我々は、提案する代数的解法を拡張して 1 つ目の問題を解けると考えている。代数は現在、無向グラフに対しては定義されておらず、したがって 2 つ目の問題に取り組むには自明でない拡張が必要である。ディスカッションフォーラムでの主張（例えば [10]）に反して、Bellman-Ford 法は 2 つ目の問題を解けない。負の重みを持つ無向エッジは負の閉路であるため、Bellman-Ford 法は負の閉路を検出するが、最短単純パスは見つけない。

特定のグラフ問題に対する解法に加えて、我々は従来のアルゴリズムが用いるグラフ探索の手法に代わるものを紹介する。その代替は、グラフ問題を代数によって解くという、まったく異なる視点である。この新しい視点は、Chrystal の古典的な代数の教科書 [1] を用いた高校代数での我々の訓練と、高校代数を用いた代数幾何学における Abhyankar と Hironaka の偉大な進歩から得た貴重な教訓に触発されたものである。この話題については、Abhyankar が [7] で振り返っている。

我々は、代数的手法の適用可能性と利点が SP 問題をはるかに超えて広がると期待している。SP 問題はそれほど複雑でないため、代数的手法のいくつかの重要な能力は SP 問題では必要とされない。進行中の探究において、次の段階の複雑さは最大流問題に見られ、その先にはさらに複雑なソフトウェアの制御フローとデータフローの問題がある。我々は、これらに対して代数を用いた新しい効率的な解法を期待している。代数は、ソフトウェアについて推論する方法を変え、Dijkstra [5] と Knuth [6] が構想したとおりにソフトウェア検証を行う機会を提供する。ソフトウェア検証は、壊滅的な安全性とサイバーセキュリティの障害を回避するための差し迫った必要である。根本的な課題は、天文学的な数の実行パスを解析する必要があることである。数百行のコードでさえ、実行パスの数は宇宙の原子の推定数より大きくなり得る。代数は、因数分解によって、すべてのパスのコンパクトなモデルを構築し操作する能力を提供する。すべてのパスのコンパクトなモデルは、大規模なソフトウェア検証にとって切実な必要である。

我々は、代数的解法の一般理論を探究する必要があると考えている。有望な道筋は、因数分解の一般理論である。そこには、その最適性と、さまざまな応用で生じる難しいグラフ問題に対する新世代の代数的解法を開発するためのその利用が含まれる。