DAGのtopological processing

概要

依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。

考え方

入次数0の頂点から取り除くと、すべての先行頂点が済んだ順を得る。DPや制約伝播では、その時点で必要な入力値が確定していることを不変量にする。

入次数degを全辺から数え、deg=0の全頂点をqueueへ入れる。取り出したuをorderへ追加し、各辺u→vでdeg[v]を1減らして0ならqueueへ入れる。残りのgraph内の入次数だけをdegが表すので、取り出したuには未処理の依存元がない。全V頂点を出せればorderがトポロジカル順、出せなければ残りは必ず有向閉路を含む(入辺を辿り続けると頂点が繰り返す)。DPは始点だけを初期化し、このorderで確定したdp[u]を出辺へ渡す。未到達の番兵からは遷移しない。

成立条件と計算量

O(V+E)時間。全頂点を処理できなければcycleがある。異なるtopological orderでも答えが同じになる合成を確認する。掲載順や単なる頂点番号順が、この依存順であるとは限らない。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。入次数による処理順を作り、有向非循環グラフ上の伝播やDPを実装する。

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

概念上の親: SCCで閉路・DAG順・2-SATを処理する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dag-topological-processing

DAGのtopological processing

習得する技能

  • 依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

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

直接の前提単元: 状態グラフのモデリングと探索。

このUnitを直接前提とする単元: SCC・縮約DAG・トポロジカル順序。

状態グラフのモデリングと探索で得た考え方と実装を再利用し、DAGのtopological processingの発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • DAGのtopological processingの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠