応用情報技術者 2009年 春期 午前2 問51

プロジェクト所要日数【午前2解説】

正解の理由

解法ステップ

1. ノード（作業終了時点）の「最早開始時刻（ES）／最早終了時刻（EF）」を順に求める。ダミーは所要日数0として、依存関係だけ反映する。
2. 各実線作業の所要日数を足し、ノードごとの到達時刻を計算する。
3. 終点に到達する各経路の合計を比較し、最長（クリティカルパス）を採る。

• 出発点: 時刻 0
• A（出発→中段左）: 0 + 10 = 10 → 中段左到達時刻 = 10
• C（中段左→上段）: 10 + 10 = 20 → 上段到達時刻 = 20
• D（中段左→中段中央）: 10 + 15 = 25 → 中段中央への入力の一つは25
• （上段→中段中央のダミー）: 上段の到達時刻 20 により、もう一方の入力は 20（ダミーは時間0）
• 中段中央は両方の入力完了後に作業開始 → M の開始時刻 = max(25,20) = 25
• F（中段中央→中段右）: 25 + 15 = 40 → 中段右への入力の一つは 40
• E（上段→中段右）: 上段 20 + 20 = 40 → 中段右への入力の一つは 40
• 下段（出発→下段は B=5 だが、同時に中段左からのダミーを受けるため実際の開始は中段左到達後）:
  • B 単独なら 0+5=5 だが、ダミー（中段左→下段）が中段左到達時刻 10 を要求するため、下段開始は max(5,10)=10
  • G（下段→中段右）: 10 + 25 = 35 → 中段右への入力の一つは 35
• 中段右は全入力（E:40、F:40、G:35）がそろうまで待つ → 中段右到達時刻 = max(40,40,35) = 40
• H（中段右→終点）: 40 + 15 = 55 → 終点到達時刻 = 55

選択肢別の誤答解説

• ア: 40
  • 40日は下段経路（B→G→H）を単独で追った場合に出る値（B=5→ただしダミー待ちで実際は開始遅延する）や、一部の作業を並列可能と誤認した場合に得られやすい数字です。しかし上段・中段の連鎖が存在するため最長ではありません。
• イ: 45
  • 45日は下段経路の終了に H(10) を加えた誤計算などから生じることがあります（下段終了35 + H=10 = 45）。ただし中段中央→中段右へ至る経路が 40 を生むため、45 は最長になりません。
• ウ: 50
  • 50日は「上段経路（A→C→E→H）＝10+10+20+10」と「中段経路（A→D→F→H）＝10+15+15+10」を同一視して 10 を H に採った場合に導出されます。先の誤りは H の所要日数を誤認（ここでは H=15）していること、またはダミーによる待ちを考慮しきれていないことが原因です。
• エ: 55
  • 正しくダミー依存と全入力の到着待ちを考慮すると終点到達は 55 日になります（上の「正解の理由」と「解法ステップ」を参照）。

よくある誤解

• ダミーは「所要日数0だから無視して良い」と考える誤り。ダミーはスケジュール上の順序制約を設定するため、ノード開始時刻に影響します（開始を遅らせる要因になり得る）。
• ノードの到達時刻は「どれか一つの入力が終わればよい」と誤解するケース。実際は「そのノードに入る全ての前提作業が完了して初めて次工程開始」です（並列入力は最大値で決まる）。
• クリティカルパスを「単に経路の和が最大のもの」としか見ずに、ダミーや共通起点による同期遅延を考慮しないこと。

補足コラム

• クリティカルパス法（CPM）では、各ノードの最早開始（ES）・最早終了（EF）、最遅開始（LS）・最遅終了（LF）を算出して余裕時間（スラック）を求め、クリティカルな作業（スラック0）を特定します。本問はダミー（依存のみ）を含む典型問題で、スラック計算をすると A、D、F、H がクリティカルであることが確認できます。
• 試験では図の細部（矢印の向き、実線／破線、各作業日数）を丁寧に読み取り、各ノードがどの作業を「待つ」必要があるかを紙に書き出すとミスが減ります。

FAQ