応用情報技術者 2010年 春期 午前2 問52

最遅開始日の算出【午前2解説】

正解の理由

解法ステップ

1. ノードに最早時刻（Earliest Event Time）を順方向で計算する（複数の入力があれば最大値を取る）。
   • 開始ノード = $0$
   • ノード1 = $0+3=3$ （A）
   • ノード2 = $3+6=9$ （B）
   • ノード3 は node1→C と node2→D の両方から来るので max$(3+5,9+3)=\max (8,12)=12$
   • ノード4 は node2→E と node3→F の両方から来るので max$(9+4,12+5)=\max (13,17)=17$
   • 終了ノード = $17+3=20$ （G）
   • よってプロジェクト最短完了日 = $20$ 日
2. 終了ノードの最遅終了時刻（Latest Event Time）をプロジェクト最短完了日に置き、逆方向に計算する（複数の出力があれば最小値を取る）。
   • 終了ノードの最遅終了 = $20$
   • ノード4 の最遅終了 = $20-3=17$ （Gの所要3日を差し引く）
   • 作業E の最遅開始 = ノード4の最遅終了 $17$ − Eの所要 $4$ = $13$
   • 他のノード・作業も同様に逆算すればクリティカルパス（浮動時間0の経路）は A→B→D→F→G（合計20日）であることが確認できる
3. 一般式：作業の最遅開始 = 後続ノードの最遅終了 − 当該作業の所要日数

選択肢別の誤答解説

• ア: 9
  9日はノード2の最早（または最遅）時刻に関係する数値であり、作業Eの最遅開始ではありません。具体的にはノード2の最早時刻＝9で、Eの開始候補の一つ（最早開始）は $9$ だが、最遅開始はそれより大きくなり得ます（この問題では13日）。
• イ: 12
  12日はノード3の最早時刻（または作業Fの最遅開始）に該当する数値です。作業Eはノード2→ノード4を通る経路に属するため、ノード3の時刻と直接の関係はなく、Eの最遅開始は12日ではありません。
• エ: 17
  17日はノード4の最遅終了（かつノード4の最早終了）時刻です。作業Eの最遅開始日をノード4の時刻そのままと誤解すると17日とする誤りが起きますが、作業Eは所要4日なので開始は $17-4=13$ 日でなければなりません。

よくある誤解

• 「最遅時刻は単純にノードの値をそのまま使う」こと：ノード（イベント）の最遅終了時刻と作業の最遅開始時刻を混同しやすい。作業の最遅開始は必ず「後続ノードの最遅終了 − 所要日数」で求める。
• 「最早時刻は足し算、最遅時刻は引き算だけ」だが、複数前後関係がある場合の取り扱い（最早：最大、最遅：最小）を忘れると誤答につながる。

補足コラム

FAQ