基本情報技術者 2015年 春期 午前（科目A） 問54

クリティカルパス法による最短工期【午前解説】

正解の理由

解法ステップ

1. 開始時刻を0とする。Aを経てノード1の最早時刻は $0+3=3$。
2. ノード1からの到達でノード2はB経由で $3+6=9$、E経由（E→下側小円→ダミー→ノード2）は $3+5=8$。ノード2はmax(9,8)=9。
3. ノード3への到達時間を各経路で求め，最大値を取る：C経由 $9+8=17$, F経由 $3+14=17$, G経由 $9+11=20$ → ノード3は20。
4. ノード4への到達はD経由 $20+6=26$，H経由 $9+15=24$ → ノード4はmax(26,24)=26。
5. 終了はIを経て $26+5=31$。以上より最短所要日数は31日。

選択肢別の誤答解説

• ア：27日 — 代表的な誤りはE経由でC→Dを使う短い経路のみを見て，合流条件（Gの遅れ）を無視することです。
• イ：28日 — FまたはB→Cの単一路を最大と見立てると28日になりますが，Gの影響を考慮していない誤りです。
• ウ：29日 — A→B→H→Iの経路は29日でほぼ長いですが，ノード3側（G→D）がさらに遅延するため最終は31日になります。
• エ：エ（31日） — 正解。ノード到着の最大値原則とG(11) の影響を正しく反映した結果です。

よくある誤解

• 作業Gを0日のダミーと見なす誤り：Gは実線の作業（11日）で、その後ろの破線（上側の小円→ノード3）がダミー（0日）です。Gを0日にするとノード3への到達が17日となり、答えを誤ります。
• 合流ノードを「いずれか一方の完了で進行可」と誤認する：AOA形式では合流ノードは全ての先行作業が完了して初めて次工程に進めるため，最大値で評価する必要があります。
• ノード2の時刻をBのみで決めてEの影響を無視するミス：複数の入線がある場合は最大値を取る点を忘れないこと。

補足コラム

• この問題は「AOA（Activity on Arrow）」形式のネットワーク図を用いた典型的なクリティカルパス問題です。ノード＝イベント（結合点）と考え，ノードが有効になるのはそのノードに入るすべての作業（矢印）が完了した時点である、という考え方が基本です。
• 破線のダミーは所要日数0で、作業の順序関係だけを表します。本問では「E→下側の小円→ダミー→ノード2」と「G→上側の小円→ダミー→ノード3」の2本があり、それぞれEの完了をノード2の条件に、Gの完了をノード3の条件に加えています。

FAQ