状態グラフ探索・到達関係

概要

探索は、今いる頂点から辺をたどり、どこまで到達できるかを調べる方法である。到達の有無を知りたいのか、最短の辺数を知りたいのかで、頂点を調べる順序の意味が変わる。

入力がグラフでなくても、問題の状態を頂点、合法な1回の操作を辺とみなせば探索を使える。長距離に及ぶ効果が通行条件を決める問題では、先に方向別の走査で通行可能な場所を確定し、その後で探索する。

考え方

到達できることと、最短で到達すること

独自の小例として、五つの頂点 s,a,b,c,ts,a,b,c,t と、無向辺 sa,ac,ct,sb,btsa,ac,ct,sb,bt だけを持つグラフを考える。ss から tt へは次の二つの経路がある。

  • s→a→c→ts\to a\to c\to t:3辺。
  • s→b→ts\to b\to t:2辺。

深さ優先探索(DFS)は、未訪問の隣接頂点へ進み、そこから先を調べ終えたら戻る。ss から先に aa を選べば、tt に初めて着く経路は3辺になり得る。到達できることは分かるが、最初に見つけた経路が最短とは限らない。到達判定では、頂点へ入る時点で探索全体の訪問済み記録 visited に印を付け、戻っても消さない。どの経路で来ても、その頂点から進める先は同じなので、一度調べればよい。初めて各頂点へ進んだ辺を残せば探索木も得られる。

幅優先探索(BFS)は、先に追加した頂点から取り出すFIFOのキューを使う。ss の距離を0としてキューへ入れ、頂点 vv を取り出したら、未訪問の隣接頂点 uu に距離 d(u)=d(v)+1d(u)=d(v)+1 を記録し、その場で訪問済みにして末尾へ追加する。小例で a,ba,b の順に調べると、キューは次のようになる。左端が次に取り出す頂点で、括弧内は距離である。

処理直後未処理のキュー
ss を追加s(0)s(0)
ss を展開a(1),b(1)a(1),b(1)
aa を展開b(1),c(2)b(1),c(2)
bb を展開c(2),t(2)c(2),t(2)

cc より先に bb を処理するので、tt の距離は2で確定する。後で cc から tt を調べても、既に訪問済みなので追加しない。

キューの距離層が最短性を保証する理由

同じ最短距離の頂点の集まりを距離層と呼ぶ。先頭の距離が dd のとき、キューには未処理の距離 dd の頂点、その後ろに距離 d+1d+1 の頂点しかない。最初は距離0の始点だけであり、距離 dd の頂点から新しく追加する頂点の距離は d+1d+1 だからである。FIFOでは残りの距離 dd の頂点を追い越さず、次の層を先に展開することもない。距離 dd の層を処理し終えると、同じ性質が次の層へ引き継がれる。

距離 dd の頂点から初めて見つけた頂点に、d+1d+1 辺より短い経路があると仮定する。その経路の直前の頂点には dd 辺未満で着けるため、もっと前の層で処理され、この頂点も既に発見されているはずである。これは初めての発見に反する。従って、キューへの追加時に記録する距離が最短距離となる。同時に訪問を記録すれば、複数の隣接頂点から同じ頂点を重複追加することもない。

辺の向きと、訪問済みの意味を確認する

無向グラフなら、一つの始点から到達できる頂点の集合が、その始点の連結成分になる。有向グラフでは辺の向きにだけ進む。辺 s→as\to a が1本だけなら、ss から aa には着けても逆には着けない。一方向の到達を、無向の連結性や相互に到達できる関係と同一視しない。

ここまでの訪問済み記録は「この頂点は既に発見し、そこから先を調べる対象にした」という意味である。履歴によって次の操作が変わる場合は、同じ位置でも別の状態として扱う必要がある。また、異なる経路を列挙する目的では、到達判定と同じ訪問制限は使えない。この区別を状態グラフのモデリングと探索で具体化する。

成立条件と計算量

頂点数を VV、辺数を EE とする。隣接リストを使い、各頂点を一度だけ展開するDFS・BFSなら、各頂点の処理と隣接辺の走査を合わせて O(V+E)O(V+E) 時間となる。無向辺は両端から1回ずつ調べる。入力の隣接リストが O(V+E)O(V+E)、訪問記録とBFSのキューが O(V)O(V) なので、全体で O(V+E)O(V+E) 空間を使う。再帰DFSでは、最悪で VV 段になる呼出しスタックも必要である。

BFSが追加時に最短距離を確定できるのは、すべての辺の費用が1のときである。同じ正の費用なら最短辺数にその費用を掛けられるが、辺ごとに費用が違うとFIFOの距離層は成り立たない。最短路モデルで重みに合う方法を選ぶ。到達不能な頂点は未訪問のまま残し、始点の距離0と区別する。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 緑色(800–1199)。入力の頂点以外にも状態を作り、探索と到達関係を使う入口。

対象色の読み方は本書の読み方を参照してください。

概念上の親: グラフアルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-graph-search

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • eventをsortしてactive集合を増減するsweep line。
  • 非負重み付き距離の緩和・確定と最短路certificateの復元。

根拠