問題プレビューID: 30190255基本情報技術者試験 2017年(平成29年度)春期 午前

問 51
基本情報技術者試験 2017年(平成29年度)春期 午前

図のアローダイアグラムで表されるプロジェクトは,完了までに最短で何日を要するか。

※ アローダイアグラムの構造から各ノードの最短開始時刻を算出します。

解説

アローダイアグラムにおけるクリティカルパス(最長経路)を求める問題です。「最短で何日」というのは、すべての作業が終わるために最低限必要な日数、つまり開始から終了までの最長の道筋を探します。

  1. 最初: ノード (1) を 0 日目とする。
  2. ノード (2) [Aの終了後]: 0+30=300 + 30 = 30 日目。
  3. ノード (3) [Bの終了後]: 30+5=3530 + 5 = 35 日目。
  4. ノード (4) [Cの終了後]: max⁡(30+30,35+0[ダミー])=60\max(30+30, 35+0 \text{[ダミー]}) = 60 日目。
  5. ノード (5) [Dの終了後]: max⁡(30+20,60+0[ダミー])=60\max(30+20, 60+0 \text{[ダミー]}) = 60 日目。
  6. ノード (6) [E, F, Gの前段階]:
    • 経路 E: 35+40=7535 + 40 = 75 日
    • 経路 F: 60+25=8560 + 25 = 85 日
    • 経路 G: 60+30=9060 + 30 = 90 日 最短開始時刻はこれの最大値なので 90 日目 です。
  7. 最後 [Hの終了後]: 90+30=12090 + 30 = 120 日。

したがって、最長経路は A →\rightarrow C →\rightarrow (ダミー) →\rightarrow G →\rightarrow H などを通る 120 日 となります。

したがって、正解は ウ です。

関連問題

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