ポテンシャル法入門 (1) 〜 ポテンシャルとダイクストラ法

みなさまこんにちは、ながたかなです。ツイッターアカウントは @ngtkana です。さあさあ始まりました、みなさまお待ちかね新連載¹「ポテンシャル法入門」、記念すべき第一回はポテンシャルとダイクストラ法についてです。ぜひです。

このシリーズでは議論の簡略化と第 2 回でご紹介するハンガリー法への応用を考えて、重み付きグラフの表現としてもっぱら隣接行列表現を使っていきますが、少し変えると隣接リスト表現でもできるかとです。

連載

ポテンシャル法入門 (1) 〜 ポテンシャルとダイクストラ法 ← いまここです。
ポテンシャル法入門 (2) 〜 ハンガリー法とポテンシャル使い回し、効率的な実装について ← 来週です。

実行可能ポテンシャルの定義と性質

$
\newcommand {\nonnegativeRealNumberInfty} { \mathbb R _ { \ge 0 } \cup \lbrace \infty \rbrace }
\newcommand {\nonnegativeRealNumber} { \mathbb R _ { \ge 0 } }
\newcommand {\realNumberInfty} { \mathbb R \cup \lbrace \infty \rbrace }
\newcommand {\realNumber} { \mathbb R }
\DeclareMathOperator \Map { \mathrm { Map } }
\DeclareMathOperator \argmin { \mathrm { argmin } }
\DeclareMathOperator * \bigArgmin { \mathrm { argmin } }
\DeclareMathOperator \const { \mathrm { const } }
\DeclareMathOperator \Nil { \mathtt { Nil } }
$点集合 $V$ とコスト行列 $c: V \times V \rightarrow \realNumber$ が与えられているとします。任意の $x, y \in V$ に対して、$x$ から $y$ への最短路長を $\delta ( x, y )$ と書きましょう。

実行可能ポテンシャルの定義と基本的な性質

頂点重み $\varphi: V \rightarrow \realNumber$ であって$$
\varphi ( y ) - \varphi ( x ) \le c ( x, y )
$$（ただし $x, y \in V$）を満たすものを、実行可能ポテンシャルと呼ぶことにします。またとても雑なノーテーションで大変恐縮なのですが、誤解のなさそうな文脈では $\varphi ( x, y ) = \varphi ( y ) - \varphi ( x )$ （ただし $x, y \in V$) と書くことにしましょう。

任意の $x, y \in V$ に対して、$c ^ \varphi ( x, y ) = c ( x, y ) - \varphi ( x, y )$ と定義し、これを辺 $(x, y)$ の被約コストと呼びましょう。実行可能ポテンシャルの定義より全ての辺に対して被約コストは非負です。コスト行列 $c ^ \varphi$ によって重み付けられたグラフを被約グラフと呼びます。任意の $x, y \in V$ に対して被約グラフ上の最短路長を $\delta ^ \varphi ( x, y )$（$x, y \in V$）と書き、被約最短路長と呼びましょう。

さらに全てのパスに対して、その元のコストと被約コストの差は端点のポテンシャルの差であり、これは端点のみに依存しますから、あるパスが元のグラフの最短路であることと被約グラフの最短路であることは同値であり、任意の $x, y \in V$ に対して、$\delta ( x, y ) = \delta ^ \varphi ( x, y ) + \varphi ( x, y )$ も成り立ちます。さらにすでにお話したように全ての辺の被約コストが非負ですから、被約最短路長は非負であることがわかります。これはすなわちポテンシャルの差は真の最短路長の下界を与えていることを意味します。

これらの記法は $\varphi$ が実行可能ポテンシャルであることが証明できていなくても使いますが、以下すべてのこのような記述では $\varphi$ が実行可能ポテンシャルであることが結果的にわかります。ポテンシャル $\varphi$ が実行可能であることと、すべての辺の被約コストが非負であることは同値です。

実行可能ポテンシャルの存在

負閉路を持たないことと、実行可能ポテンシャルが存在することは同値です。

(証明)
負閉路を持たないとします。このときもとのグラフに超頂点 $\hat s$ を付け加えて、そこから $V$ の各点には重み $0$ の辺がはられているようにしたグラフを $\hat G$ と置き、$\hat G$ における最短経路長関数を $\hat \delta$ と置きましょう。このとき $G$ の頂点重み $\varphi$ を、$\varphi ( x ) = \hat \delta ( \hat s, x )$によって定めます。すると三角不等式などにより$$
\varphi ( x, y ) = \varphi ( y ) - \varphi ( x ) = \delta ( \hat s, y ) - \delta ( \hat s, x ) \le \delta ( x, y ) \le c ( x, y )
$$が従い、$\varphi$ 実行可能ポテンシャルであることがわかります。

逆に $\varphi$ が実行可能ポテンシャルであるとします。すると任意のサイクル $x _ 0, x _ 1, \dots, x _ k = x _ 0$ に対し、$$
\sum _ { i = 0 } ^ { k - 1 } c \left ( x _ i, x _ { i + 1 } \right )
\ge \sum _ { i = 0 } ^ { k - 1 } \varphi \left ( x _ i, x _ { i + 1 } \right )
= 0.
$$が成り立ちますから、従って任意のサイクルの重みは非負です。∎

ゼロポテンシャルの実行可能性

すべての辺の重みが非負ならば、$\varphi ( x ) = 0$（ただし $x \in V$）によって定義されるポテンシャル $\varphi: V \rightarrow \realNumber$ は実行可能です。

ダイクストラのアルゴリズム

ダイクストラのアルゴリズムといえば辺の重みが全て非負なときに使えるアルゴリズムですが、重みが負な辺があったとしても、予め何らかの実行可能ポテンシャルさえ与えられていれば、被約グラフに関してダイクストラを適用することで最短路問題を解くことができます。特に辺の重みが全て非負のときにはこの実行可能ポテンシャルとしてゼロポテンシャルを考えると、いわゆる普通のダイクストラと結局同じことをしていることになります。

ダイクストラのアルゴリズムの普通の実装は、確定頂点集合 $T$ を管理してそこに属しない中で始点から最も近い頂点を探すのを繰り返すのですが、今回は少し工夫をしましょう。アルゴリズムの進行に従ってポテンシャルを変化させていき、$T$ に属する頂点は全て始点からの被約最短路長が常に $0$ であるようにします。$T$ に新しい頂点を追加するときには、$T$ と $V \setminus T$ の間のポテンシャル差を変化させて辻褄を合わせるとできます。

この方針で行くと、$T$ に挿入すべき頂点を探すときに、始点からの距離の変わりに $T$ からの距離を使うことができるのが楽です。またこれはネットワークフローなどでグラフの辺を逆辺に取り変える操作を挟みながら最短路を複数回計算するときに、ポテンシャルの使い回しによってベルマン−フォードを最初以外全てダイクストラで済ますことができるなど、漸近的計算量的にも嬉しいケースがあったりなどです。ハンガリー法への応用は次回の記事をご覧いただけるとです。

アルゴリズムの定義

入力

• $c: V \times V \rightarrow \realNumber$: コスト行列
• $\varphi: V \rightarrow \realNumber$: 初期ポテンシャル
• $s \in V$: 始点

入力の制約

• $\varphi$ は実行可能ポテンシャル

出力

• $\pi: V \rightarrow V$: 先行点部分グラフ
• $\varphi: V \rightarrow \realNumber$: 最終ポテンシャル

出力の要件

• $\varphi$ は実行可能ポテンシャル
• $\pi$ は $s$ を根とする木であり、すべての木辺の被約コストは $0$

なおこのとき $\pi$ は $c ^ \varphi$ の、従って $c$ の最短路木です。また任意の点 $x \in V$ に対して、$s$ から $x$ への被約最短路長は $0$ であり、もとの最短路長は$$
\delta ( s, x ) = \delta ^ \varphi ( s, x ) + \varphi ( s, x ) = \varphi ( s, x )
$$のようにして求めることができます。

疑似コード

$\mathrm { dijkstra } ( c, \varphi, s)$
 1.   $T = \lbrace s \rbrace$
 2.   $\pi: V \rightarrow V$: 全点に $s$ を代入です。
 3.   $x _ 0 = s$
 4.   while $T \neq V$
 5.        $y _ 0 = \argmin _ { y \in T ^ c } c ^ \varphi ( \pi [ y ], y )$
 6.        $\Delta = c ^ \varphi ( \pi [ y _ 0 ], y _ 0 )$
 7.        for $x \in T$
 8.             $\varphi [ x ] = \varphi [ x ] - \Delta$
 9.        $x _ 0 = y _ 0$
10.        $T = T \cup \lbrace x _ 0 \rbrace$
11.        for $y \in T ^ c$
12.             if $c ^ \varphi ( x _ 0, y ) \le c ^ \varphi ( \pi [ y ], y )$
13.                  $\pi [ y ] = x _ 0$
14.   return $(\pi, \varphi)$

ちなみに第 7, 8 行を
  for $y \in T ^ c$
       $\varphi [ y ] = \varphi [ y ] + \Delta$
に書き換えても良くて、これをすると $\varphi [ s ] = 0$ になって嬉しいという説です。

正当性・停止性の証明

まず地味パートですが、$\argmin$ とありますが、これは空ではありませんから、大丈夫です。それでは派手パートの方に移っていきましょう。

ループ不変式の主張と証明

第 4 行から始まるループの各繰り返し開始時点で

1. $\varphi$ は $c$ の実行可能ポテンシャル
2. $\pi [ y ] = \argmin _ { x \in T } c ^ \varphi ( x, y ) \ \left ( y \in T ^ c \right )$
3. $\pi \vert _ T$ は $s$ を根とする木であり、すべての木辺の被約コストは $0$

が成り立ちます。

(証明)
繰り返し回数に関する帰納法で示しましょう。まずは初回ループです。1 は入力から $\varphi$ を一度も変えていいませんから OK です。2 は $T = \lbrace s \rbrace$ であり $\pi$ は全点に $s$ が代入されていますから、OK です。3 は $\pi [ s ] = s$ より OK です。

さてあるイテレーションで主張が正しいとして次のイテレーションでも正しいことを示しましょう。帰納法の仮定 2 より、第 5. 6 行の代入直後時点で、$$
\left ( \pi [ y _ 0 ], y _ 0 \right ) = \bigArgmin _ { ( x, y ) \in T \times T ^ c } c ^ \varphi ( x, y ) \\
\Delta = \min _ { ( x, y ) \in T \times T ^ c } c ^ \varphi ( x, y )
$$が成り立ちます。まず 2 つめの式より第 7, 8 行のループ脱出時点でも $\varphi$ は $c$ の実行可能ポテンシャルであり、これは次のイテレーションでも主張 1 が成り立つことを意味します。また 1 つめの式より $c ^ \varphi ( \pi [ y _ 0 ], y _ 0 ) = \Delta$ ですから、第 7. 8 行のループ脱出時点では $c ^ \varphi ( \pi [ y _ 0 ], y _ 0 ) = 0$ が成り立っていることを意味します。これは次のイテレーションでも主張 3 が成り立つことを意味します。その後第 10 行で $T$ に $x _ 0$ が挿入されるのですが、それによって主張 1 が成り立たなくなるのを第 11, 12, 13 行のループで回復しています。∎

正当性の証明

ループ不変式に加えて $T = V$ まで成り立つのですよ。これは私たちの完全勝利です。

停止性の証明

$T$ はどんどん増えていきます。天国へのカウントダウンですね。

Special Thanks

ハンガリー法について調べているときに、みさわさんが教えてくださいました。ありがとうございます。こちらが当時のツイッターのスレッドです。

お手数なのですが、可能ならばどの変数がなんの意味かについて教えていただけないのでしょうか。もしわかりやすいループ不変式があればそれも知りたいです。私は読解に挫折仕掛けており…… （Spagetti source さんのものはもっと辛かったのでこちらに流れてきたのですが。）

— ながたかな (@ngtkana) January 24, 2021

まとめ

• 実行可能ポテンシャルは、差がコストの下限を与えるようなものです。
• もとのグラフの最短路問題は、被約グラフの最短路問題に帰着します。
• 被約グラフは辺のコストが全て非負です。
• 負辺がなくても負閉路さえなければ実行可能ポテンシャルは存在します。
• 何かしら実行可能ポテンシャルが与えられていれば、単一始点最短路問題はダイクストラ法で解けます。

中身を読んでくださった皆様ならばひょっとすると共感くださるかもしれないのですが、きれいですね。

次回はハンガリー法におけるポテンシャル使い回しと効率的な実装についてです。ご期待のほうよろしくお願い致します。

1. 全 2 回の予定です。（あの？） ↩