基本情報技術者 2025年 科目A 問14

クリティカルパス計算【午前解説】

正解の理由

解法ステップ

1. 各作業の所要日数を確認：A3、B6、C8、D6、E5、F14、G11、H15、I5。ダミーは日数0。
2. ノードごとに「そのノードに到達するまでの最長経過日数」を順に計算（前向き計算）。
   • 開始ノード = 0
   • Aの終点（分岐ノード） = $0+3=3$
   • 分岐ノードからの各枝：
     • B経由で中央ノード = $3+6=9$
     • E経由で下端ノード = $3+5=8$
     • F経由（上段） = $3+14=17$（上段右ノードへはさらにダミーで接続）
   • 中央ノード（B経由で到達）はすでに9。ここから：
     • C先のノード = $9+8=17$
     • Gで上段右ノード = $9+11=20$
     • HでD先のノード = $9+15=24$
   • 上段右ノードには Fから17 と Gから20 が入る → 受ける側は最大値 $20$（ダミーでC先へ接続し、C先のノードは既存の17と比較して最大値を採る）
   • C先のノードへは C経路で17、上段右ノードからのダミー経路で20 → 最大は $20$
   • C先のノードからDを経てD先のノード = $20+6=26$
   • D先のノードはH経路で24 と D経路で26 が入る → 最大は $26$
   • 最後に I を経て終了 = $26+5=31$
3. 上の計算で最長経路（クリティカルパス）長が $31$ 日であることを確認する。

選択肢別の誤答解説

• ア: 27
  • これは A→E→（ダミー）→C→D→I の合計 $3+5+8+6+5=27$ を見てしまった結果。E→中央はダミーで依存関係は表現できるが、中央に到達する他経路（B経由）がある場合は中央ノードの到達時間はその最大値を採るため、27にはならない。
• イ: 28
  • 28 は主に A→B→C→D→I の合計 $3+6+8+6+5=28$ や、A→F→（ダミー）→D→I の $3+14+6+5=28$ を参照した誤り。いずれも中央の他の経路（特に G 経路）がより長いため最大値にはならない。
• ウ: 29
  • 29 は A→B→H→I の $3+6+15+5=29$ を見落としやすい候補。Hは長いが、G経由の累計（31）には及ばないため誤り。
• エ: 31
  • 正解。A→B→G→（ダミー）→D→I の合計 $3+6+11+6+5=31$ が最大となる。

よくある誤解

• ダミー矢印を作業時間があるものと勘違いする：ダミーは依存関係を示すのみで日数は 0 です。合計に含めないこと。
• ノード到達時間を「合計（sum）」で処理してしまう：複数の先行作業がある場合は「最大（max）」を取ること（クリティカルパスは最長経路を採る）。
• 分岐の扱いを誤る：枝ごとの経路を全部比較せずに一つの経路だけ追ってしまうミス。必ずすべての主要経路を確認する。

補足コラム

• クリティカルパス法(CPM)の基本手順は「前向き計算（最早開始/終了）→ 後向き計算（最遅開始/終了）→ スラック（余裕）算出」です。本問は「前向き計算だけで最短所要日数（＝全体の工期）を求める」典型問題です。
• 実務ではネットワーク図が大きくなるため、ノードごとに「最早終了時間（ES/EF）」を表にして順に更新すると確実です。計算式（前向き）は次の通り： $$\text{最早開始}(j)=\underset{i\in pred(j)}{\max }(\text{最早終了}(i))$$ $$\text{最早終了}(j)=\text{最早開始}(j)+\text{作業時間}(j)$$

FAQ