データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
70: 2022/08/31(水)20:45 ID:CIcCYvEQ(1/4) AAS
『アルゴリズム実技検定公式テキスト』という本に以下の最長パスの問題の出題と解答が書いてあります．
外部ﾘﾝｸ:atcoder.jp
解説を読むと，この問題を解くのに，トポロジカルソートが重要だと書いてあります．
71: 2022/08/31(水)20:52 ID:CIcCYvEQ(2/4) AAS
解答は以下のような感じです：
length(v)を点vからの最長パスの長さとします．
v → w_1
v → w_2
…
v → w_n
という辺があるとき，length(v) = max{length(w_1), …, length(w_n)}
とメモ化再帰により計算する．（深さ優先探索を使う．）
この解答のどこでトポロジカルソートの考えが使われているのかが分かりません．
72: 2022/08/31(水)20:55 ID:CIcCYvEQ(3/4) AAS
入次数が0の点達からメモ化再帰（深さ優先探索）を行っています．
73: 2022/08/31(水)20:58 ID:CIcCYvEQ(4/4) AAS
外部ﾘﾝｸ:ideone.com
例えば，上のプログラムのような感じです．
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.012s