基本情報技術者 2024年 科目A 問13

クリティカルパスの合計日数【午前解説】

正解の理由

解法ステップ

1. ノードごとに「最早発生時刻（Earliest Event Time）」を前方に計算する。
   • 開始ノードを0とする。
2. 各矢印（作業）について、尾ノードの最早時刻＋作業日数を頭ノードの候補時刻とし、頭ノードの最早時刻は候補の最大値を取る（複数入力がある場合）。
3. 最終ノードの最早時刻がプロジェクト最短所要日数である（ダミーは0日として扱う）。

• 開始 = 0
• Aの完了（中央左ノード） = 0 + 30 = 30
• Bの完了（上ノード） = 30 + 5 = 35
• Cの完了（中央ノード） = 30 + 30 = 60
  • ここへダミー（上ノード→中央ノード）があるが、ダミーは0日なので候補は35。最大を取ると60のまま。
• Dの完了（下ノード） = 30 + 20 = 50
  • ただし、ダミー（中央ノード→下ノード）により中央ノードの完了60も入力されるため下ノードの最早時刻は max(50, 60) = 60
• 収束ノード（上経路E / 中央経路F / 下経路G のうち最大）
  • E経路：上ノード(35) + 40 = 75
  • F経路：中央ノード(60) + 25 = 85
  • G経路：下ノード(60) + 30 = 90 ← 最大
  • したがって収束ノード = 90
• 終了ノード = 収束ノード(90) + H(30) = 120

選択肢別の誤答解説

• ア: 105
  • これは A→B→E→H の単純和 $30+5+40+30=105$ を最大と見なした誤り。収束ノードで他経路の遅延（ダミーの影響）により更に長い経路が存在するため不足する。
• イ: 115
  • これは A→C→F→H の単純和 $30+30+25+30=115$ を用いた誤り。中央経路は長いが、下経路の遅延（ダミーによって下ノードが60に引き上げられる）により上回られる。
• ウ: 120
  • 正しい。前方計算で収束ノードが90になり、Hの30を加えて120になる。
• エ: 125
  • どこかで余分に待ち時間や作業日数を誤って二重計上した値。与えられた作業日数・ダミーを正しく前方集計すれば発生しない。

よくある誤解

• ダミー矢印を無視する
  • ダミーは日数0でも「先行関係」を変えるため、ノードの最早時刻に影響を与えることがある。特に収束点での最大値判定を忘れると短く出る。
• 単に枝ごとの合計だけを比較する
  • 分岐と収束があるネットワークでは、ノード時刻を前方に伝播させて最大値を取るのが正しい。複数経路が交差する場合、ある経路が他を遅らせることがある。
• AOA（矢印図）とAON（ボックス図）の扱いを混同する
  • AOAでは「矢印が作業」「ノードがイベント」で、ダミーが必要。AONと同じ直観で見ないこと。

補足コラム

• 実務上は「最早時刻（ES/ET）」と「最遅時刻（LS/LT）」を前方・後方計算で求め、各作業のフロート（余裕）を算出します。フロート0の作業がクリティカルパス上の作業です。本問題ではダミーが作用して、クリティカル（余裕0）となるのは下流の G と H となることが多い点が興味深いです（詳細な最遅時刻計算で確認できます）。

FAQ