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

クリティカルパスと最短完了日数【午前解説】

正解の理由

• 開始 → A（3日）→ A の終点：3日
• A の終点 → B（6日）→ B の終点：9日。E（5日）の終点（8日）からのダミーも B の終点に入るので、max(9, 8) = 9日
• B の終点 → G（11日）→ G の終点：20日
• C の終点（D の始点）に入るのは、B → C（8日）の17日、A → F（14日）の17日、G の終点からのダミーの20日で、max(17, 17, 20) = 20日
• C の終点 → D（6日）→ D の終点：26日。B → H（15日）の24日も D の終点に入るが、26日の方が大きい
• D の終点 → I（5日）→ 終了：31日

解法ステップ

1. 開始を0日とし、A の終点の最早時刻を求める（0 + 3 = 3）。
2. A の終点から出る B・E・F の到着時刻を求める（B の終点 3 + 6 = 9、E の終点 3 + 5 = 8、F は C の終点へ 3 + 14 = 17）。
3. E の終点からのダミーで B の終点は max(9, 8) = 9。
4. B の終点から出る C・G・H の到着時刻を求める（C の終点へ 9 + 8 = 17、G の終点 9 + 11 = 20、H は D の終点へ 9 + 15 = 24）。
5. C の終点には B → C の17、F の17、G の終点からのダミーの20が入るので、最早時刻は20。
6. D の終点は max(20 + 6, 24) = 26、終了は 26 + 5 = 31。

選択肢別の誤答解説

• ア: 27
  D・I の日数を一部足し忘れたり、ダミーを逆向きに扱ったりすると短く見積もってしまいます。
• イ: 28
  A → B → C → D → I の合計（3 + 6 + 8 + 6 + 5）は28日ですが、G の終点からのダミーが C の終点を20日まで遅らせるので、28日では終わりません。
• ウ: 29
  A → B → H → I の合計（3 + 6 + 15 + 5）は29日ですが、最長の経路ではありません。
• エ: 31（正解）
  A → B → G →（ダミー）→ D → I の 3 + 6 + 11 + 6 + 5 = 31日が最長です。

よくある誤解

• 破線（ダミー）を無視すると、C の終点の最早時刻を17日と見積もってしまい、28日などの誤答になります。
• F（14日）は日数が最も大きい作業ですが、A の直後から C の終点までの経路は 3 + 14 = 17日で、B → G → ダミーの経路（20日）より短くなります。日数の大きい作業がクリティカルパスに入るとは限りません。

補足コラム

• AOA（アクティビティ・オン・アロー）表記では，破線のダミーは長さ0だが依存関係を表す重要な要素です。ダミーを無視するとクリティカルパス解析で誤った最早時刻が出ます。
• クリティカルパス法（CPM）は最早開始（ES）・最遅開始（LS）を求め，余裕（フロート）が0の経路がクリティカルパスです。本問は最早時刻だけで最長経路を見つければ答えが出ます。
• PERTとCPMの違い：PERTは確率論的に所要時間を扱うのに対し，CPMは固定時間での最長経路解析が中心です。本問は固定時間のCPMに相当します。

FAQ