組み合わせ最適化

7章 最短パス

グラフに負の重みのコストの辺がなければ、移動すればするほどコストがかかるので、比較的貪欲なアプローチで二点間の最短パスが求められる、というのがダイクストラ。ある点集合のコストがそれより改善されないことが分かっているなら、それらの点を経由して行ったときに一番コストが小さくなる点が存在して、そいつを追加してやる。既にコストの決まっている点以外から、その点への移動コストをより小さくするパスがあるのだとすると、その点よりも小さいコストで移動できる点が存在するはずなので。

これを効率良くやるには、まず最初の点から開始して、移動できる点すべてと、そのコストを覚えておく。一番コストの小さい点を追加して、そこから移動できる点すべてと、そのコストを覚えておく。次に一番コストの小さい点を追加して...、と繰り返す。同じ点が複数回出てくるが、二回目以降はより遠回りしているはずなので無視する。一番コストの小さい点を取り出すのにPriorityQueueが必要になる。これは有向グラフでも無向グラフでもうまくいく。

コストが負の辺がある場合、無向グラフだとその辺を行ったり来たりするとコストが無限に小さくなるのでうまくいかないし、有向グラフでも遠回りして得することがあるので、おかしなことが起きる。(当然ながら、コストが負のループがあると、そこを回り続けることで無限にコストが小さくなる。)大雑把には、二回目以降でも良いスコアになることが起こり得るので、そこで計算し直せば良いという感じ。ただ、こうすると更新の回数がたくさんになるので、改善する必要がある。負のループはないとき、長さがNより長いパスを考慮する必要がなくなるので、パスの長さとそのときの到達コストでDPすれば、最終的な最短パスが出てくる。(これを続けてコストが改善されることがあるのだとすると、負のループがあると判定できる。)これがいわゆるベルマンフォード。

で、このとき、グラフから負の辺がなくなるような変形が可能で、すべてのノードに実行可能エントロピーとか呼ばれる重みを付けて、辺(v,w)のコストをc(v,w)からc(v,w)+E(v)-E(w)みたいに変形することができる。これをすると負の辺がなくなるので、ダイクストラで最短パスが求まる。(実際には始点と終点のエントロピーの分だけずれるけれど、どのようなパスでも始点と終点の分だけしかずれないように打ち消し合うので、パスによらず距離に相当するものが求められる。)先のベルマンフォードで求まるある点からの距離をエントロピーを求めることができる。

一見するとベルマンフォードの方がダイクストラよりも重たいので、意味がないように感じられるが、実はこのエントロピーは9章で再登場して、最小費用流を計算するときに大活躍するアプローチがあるので、ある意味この章の最重要事項だったりする。この章では全点間の最短パスを求めるときに、N^2回ベルマンフォードするのではなくて、一度エントロピーを計算してから、N回(始点を変えて)ダイクストラをすれば良い、という話で使っている。N^3でできるFloyd-Warshallについても言及している。

最後に最小平均長の閉路を求めるアルゴリズムについて。(実はこれも最小費用流を計算するアプローチの一つであるので、この章はかなり重要だったという事実に2周目にして気付いたりもした...。)最小平均長の閉路というのは結構癖があるけれど、ループの長さがいくつであれ、先のベルマンフォードのNステップ目にはそのループが一周終わった点が存在するので、そいつをうまく捕まえるという方式。Nステップ目のコストとそれより前のKステップ目のコストでループだとして、に最大になるKをすべての点について探して、最小となる点がループになっているところ。(正確にはループの影響をNステップ目でちょうど受けるところ。)