競技プログラミング総合スレ 66 (478ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
190: (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/10(月)16:12 ID:GqegRxcS0(1/4) AAS
確かに、その解法ではトポロジカルソートを明示的に実行していないように見えますが、
実際にはトポロジカルソートの考え方が含まれています。DAGの最長パスを求める際、
トポロジカルソートの概念が重要なのは、頂点の順序付けによって依存関係を解決することができるからです。
その解法で、indegree（入次数）が0の頂点からDPを用いて最長パスを求めています。これは、各頂点について、
その頂点に入ってくる辺がなくなる（依存関係が解決される）順序で処理を行っていることを意味します。
この順序付けがトポロジカルソートの結果と同じです。
indegreeが0になる頂点から処理を行い、その後、処理された頂点から出る辺を削除することで、
省3
192: (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/10(月)16:19 ID:GqegRxcS0(2/4) AAS
はい、おっしゃる通りです。DAGであれば、最長パスが存在し、動的計画法（DP）を用いて求めることができます。
繰り返しになりますが、トポロジカルソートの概念を用いることで、DAG内の頂点の順序付けが可能であり、
この順序付けに従ってDPを適用することで、最長パスを求めることができます。
194: (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/10(月)16:26 ID:GqegRxcS0(3/4) AAS
トポロジカルソートを明示的に実行しなくても、DAGの最長パス問題をDPで解くことは可能です。
ただし、その際に頂点の処理順序や依存関係の解決が重要となるため、トポロジカルソートの考え方が役立ちます。
トポロジカルソートを適用したDPでは、頂点の依存関係が効率的に解決されるため、計算量はO(V+E)です。
ここで、Vは頂点数、Eは辺数です。トポロジカルソートによって得られた頂点の順序に従ってDPを行うことで、
各頂点と辺に対して一度だけ計算が行われます。
一方、トポロジカルソートを適用しないDPでは、無駄な計算が発生する可能性があります。
例えば、メモ化再帰を用いたDPの場合、計算量は最悪O(2^V)になることがあります。
省1
200(1): (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/10(月)22:32 ID:GqegRxcS0(4/4) AAS
この問題の場合はメモ化再帰でトポロジカルソートを使わなくても計算量はO(N+M)です。
頂点間に循環がないため、再帰の深さが頂点数Nを超えることがなく、
各頂点に対して rec 関数が最大1回しか呼び出されないからです。
トポロジカルソートを使ってそのコードを書き換えるとこうなります。
外部ﾘﾝｸ:ideone.com
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.019s