問題プレビューID: 3bd036d4基本情報技術者試験 午前免除試験 2012年6月24日

問 53
基本情報技術者試験 午前免除試験 2012年6月24日

図は,あるプロジェクトの作業(A〜I)とその作業日数を表している。このプロジェクトが終了するまでに必要な最短日数は何日か。

凡例

解説

正解は「エ」です。

各結合点の最早結合点時刻(その点に到達できる最も早い時刻)を順に求めます。

  1. 開始点:0
  2. N1:0+A(3)=30 + A(3) = 3
  3. N3:3+E(5)=83 + E(5) = 8
  4. N2:max⁡(N1+B(6),N3+0)=max⁡(3+6,8+0)=max⁡(9,8)=9\max(N1 + B(6), N3 + 0) = \max(3 + 6, 8 + 0) = \max(9, 8) = 9(ダミー作業の日数は 0)
  5. N4:max⁡(N1+F(14),N2+G(11))=max⁡(3+14,9+11)=max⁡(17,20)=20\max(N1 + F(14), N2 + G(11)) = \max(3 + 14, 9 + 11) = \max(17, 20) = 20
  6. N5:max⁡(N2+C(8),N4+0)=max⁡(9+8,20+0)=max⁡(17,20)=20\max(N2 + C(8), N4 + 0) = \max(9 + 8, 20 + 0) = \max(17, 20) = 20(ダミー作業の日数は 0)
  7. N6:max⁡(N2+H(15),N5+D(6))=max⁡(9+15,20+6)=max⁡(24,26)=26\max(N2 + H(15), N5 + D(6)) = \max(9 + 15, 20 + 6) = \max(24, 26) = 26
  8. 終了点:26+I(5)=3126 + I(5) = 31

したがって,このプロジェクトが終了するまでに必要な最短日数は 31 日となります。最長経路(クリティカルパス)は「開始 → A → B → G → (ダミー) → D → I」で,3+6+11+0+6+5=313 + 6 + 11 + 0 + 6 + 5 = 31 日です。

関連問題

本文が同じ・似ている問題を表示しています