基本情報技術者 2015年 春期 午前（科目A） 問54
問題文
図は、あるプロジェクトの作業（A〜I）とその作業日数を表している．このプロジェクトが終了するまでに必要な最短日数は何日か．
選択肢
ア：27
イ：28
ウ：29
エ：31（正解）
🔒 解説は解答すると表示されます
クリティカルパス法による最短工期【午前解説】
正解の理由
ノードごとに最早到達時刻（Earliest Event Time）を順に求めると，ノード3には C（ノード2→ノード3：8日），F（ノード1→ノード3：14日），G（ノード2→ノード3：11日）の到着があり，ノード3の到達はこれらの最大値に依存します。具体的に計算するとノード2の最早時刻は 9 日（開始→A(3)→B(6)、E 経由は 8 日で B が遅いので 9 日）、よって G 経由は 9＋11＝20 日で最も遅く，ノード3 は 20 日で有効になります。そこから D(6) を経てノード4 は 26 日，H 経由は 24 日であるためノード4 の最早時刻は 26 日、最後に I(5) を加えて合計 31 日となります。したがって正解は エ です。
解法ステップ
- 開始時刻を 0 とする。A を経てノード1 の最早時刻は 。
- ノード1 からの到達でノード2 は B 経由で 、E 経由（E→下側小円→ダミー→ノード2）は 。ノード2 は max(9,8)=9。
- ノード3 への到達時間を各経路で求め，最大値を取る：C 経由 , F 経由 , G 経由 → ノード3 は 20。
- ノード4 への到達は D 経由 ，H 経由 → ノード4 は max(26,24)=26。
- 終了は I を経て 。以上より最短所要日数は 31 日。
選択肢別の誤答解説
- ア：27 日 — 代表的な誤りは E 経由で C→D を使う短い経路のみを見て，合流条件（G の遅れ）を無視することです。
- イ：28 日 — F または B→C の単一路を最大と見立てると 28 日になりますが，G の影響を考慮していない誤りです。
- ウ：29 日 — A→B→H→I の経路は 29 日でほぼ長いですが，ノード3 側（G→D）がさらに遅延するため最終は 31 日になります。
- エ：エ（31 日） — 正解。ノード到着の最大値原則と G(11) の影響を正しく反映した結果です。
よくある誤解
- 破線（ダミー）＝必ず 0 日と見なす誤り：図中に示された破線のうち，ノード間の実体作業（ここでは G と表記され 11 日）は実作業として考慮する必要がある場合がある点に注意。
- 合流ノードを「いずれか一方の完了で進行可」と誤認する：AOA 形式では合流ノードは全ての先行作業が完了して初めて次工程に進めるため，最大値で評価する必要があります。
- ノード2 の時刻を B のみで決めて E の影響を無視するミス：複数の入線がある場合は最大値を取る点を忘れないこと。
補足コラム
- この問題は「AOA（Activity on Arrow）」形式のネットワーク図を用いた典型的なクリティカルパス問題です。ノード＝イベント（結合点）と考え，ノードが有効になるのはそのノードに入るすべての作業（矢印）が完了した時点である、という考え方が基本です。
- 図中で「破線」が凡例でダミーと示されていても，図に作業名と日数が明示されている場合はその値を無視せず，問題文の意図（どの矢印が実作業か）を読み取ることが重要です。
FAQ
Q1. 破線の矢印は常に無視してよいですか？
A1. いいえ。破線は通常ダミー（所要時間0）を表しますが，問題文や図示で作業名と日数が付されている場合は実作業とみなす必要があることがあります。図と凡例を照合して判断して下さい。
A1. いいえ。破線は通常ダミー（所要時間0）を表しますが，問題文や図示で作業名と日数が付されている場合は実作業とみなす必要があることがあります。図と凡例を照合して判断して下さい。
Q2. 合流ノードで到着時刻をどう計算しますか？
A2. 合流ノードの最早到達時刻は「すべての先行作業の完了時刻のうち最大値」です。最遅開始の評価でも同様に扱います。
A2. 合流ノードの最早到達時刻は「すべての先行作業の完了時刻のうち最大値」です。最遅開始の評価でも同様に扱います。
Q3. どの経路がクリティカルパスになりますか？
A3. 本問ではノード2→G(11)→ノード3→D(6)→ノード4→I(5) が遅延要因となり，開始から見ると A(3)→B(6)→G(11)→D(6)→I(5) が実質的にクリティカルパスを構成します（合計 31 日）。
A3. 本問ではノード2→G(11)→ノード3→D(6)→ノード4→I(5) が遅延要因となり，開始から見ると A(3)→B(6)→G(11)→D(6)→I(5) が実質的にクリティカルパスを構成します（合計 31 日）。
関連キーワード: PERT、CPM、クリティカルパス、AOA、ダミー作業、最早到達時刻、合流ノード、プロジェクトスケジューリング
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！