基本情報技術者 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の最早時刻は $0 + 3 = 3$ 。
ノード1からの到達でノード2はB経由で $3 + 6 = 9$ 、E経由（E→下側小円→ダミー→ノード2）は $3 + 5 = 8$ 。ノード2はmax(9,8)=9。
ノード3への到達時間を各経路で求め，最大値を取る：C経由 $9 + 8 = 17$ , F経由 $3 + 14 = 17$ , G経由 $9 + 11 = 20$ → ノード3は20。
ノード4への到達はD経由 $20 + 6 = 26$ ，H経由 $9 + 15 = 24$ → ノード4はmax(26,24)=26。
終了はIを経て $26 + 5 = 31$ 。以上より最短所要日数は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）を表しますが，問題文や図示で作業名と日数が付されている場合は実作業とみなす必要があることがあります。図と凡例を照合して判断して下さい。

Q2. 合流ノードで到着時刻をどう計算しますか？
A2. 合流ノードの最早到達時刻は「すべての先行作業の完了時刻のうち最大値」です。最遅開始の評価でも同様に扱います。

Q3. どの経路がクリティカルパスになりますか？
A3. 本問ではノード2→G(11)→ノード3→D(6)→ノード4→I(5) が遅延要因となり，開始から見るとA(3)→B(6)→G(11)→D(6)→I(5) が実質的にクリティカルパスを構成します（合計31日）。

関連キーワード: PERT、CPM、クリティカルパス、AOA、ダミー作業、最早到達時刻、合流ノード、プロジェクトスケジューリング

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！