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

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

正解の理由

解法ステップ

1. ノード（イベント）に最早発生時刻を割り当てる（開始ノードを0とする）。
2. 矢印（作業）ごとに「始点時刻＋所要日数」で終点候補時刻を算出する。
3. 終点ノードには複数の入射がある場合、最大値（すべての入射完了を待つ）を最早発生時刻とする。ダミーは所要0だが入射として扱う。
4. 全ノードを左から右へ順に計算し、収束ノードの時刻を求め、最後にHの30日を加算する。

• 開始ノード = $0$
• Node（分岐ノード）＝A の終了 = $0+30=30$
• 上ノード（Bの終了）＝ $30+5=35$
• 中ノード（Cの終了）＝ $30+30=60$；ただし中ノードは上ノードからのダミー入射(35)も待つが $60\ge 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
    よって収束ノード = $\max (75,85,90)=90$
• 終了ノード = 収束ノード(90) + H(30) = $120$

選択肢別の誤答解説

• ア: 105
  • 何を想定したか：A(30) + 最短枝(45) + H(30) = 105 の誤計算。ダミーや各枝の競合を無視し短い枝を選んでしまった結果です。
• イ: 115
  • 何を想定したか：A(30) + 最大単純枝(55) + H(30) = 115 の単純和。ダミーによる「開始・終了の同期」を無視したため、実際より短く見積もっています。
• ウ: 120（正解）
  • 正しい理由：ダミーの制約で中・下ノードの時刻が変わり、収束ノードが90日となって終了は120日になります。
• エ: 125
  • 何を想定したか：ダミーを誤って所要日数として加算した、あるいは枝の和を過剰に二重計上した誤りです。

よくある誤解

• ダミーは無視してよい：ダミーは所要日数0でも「前後関係」を作るため、ノード発生時刻に影響します。
• 各枝の作業時間の単純な最大値を取ればよい：枝の終了ノードが他の枝に依存すると、各枝の終わりが相互に制約され合います。
• ダミーがあると時間が加算されると誤解する：時間は増えないが「遅れ」が発生し、結果的に最長経路が変わります。

補足コラム

• AOA（アローダイアグラム）では作業は矢印、イベントはノードで表し、ダミー矢印は論理関係を表現するために使います。ダミーは時間ゼロですが、イベントの発生条件（入射の完了）に含まれるため、最早・最遅時刻に影響を与えます。
• 実務ではこの違いがクリティカルパスの判定や余裕度の計算に直結します。ダミーの有無や位置の見落としが最も落とし穴になりやすいポイントです。
• 計算は「順方向（最早時刻）」→「逆方向（余裕の有無）」の流れで行うのが基本。午前問題では順方向だけで完答できる場合が多いです。

FAQ