基本情報技術者 2009年 春期 午前（科目A） 問51

アローダイアグラムのクリティカルパス【午前解説】

正解の理由

解法ステップ

1. フォワードパスで各ノードの最早時刻を計算する（前駆の最早時刻＋作業所要日数の最大を取る）。
2. 最終ノード I の最早時刻（プロジェクト所要日数）を求める。
3. 各 A→I 経路の合計日数と最終ノード時刻を比較し，最大値と一致する経路をクリティカルパスとする。
4. ノード H の最早開始日はフォワードパスで求めたノード H の値を採る（複数前駆があれば最大値）。

• E[A]=0
• E[B]=0+3=3
• E[C]=0+1=1
• E[F]=0+2=2
• E[D]=E[C]+6=1+6=7
• E[G]=E[F]+3=2+3=5
• E[E]=max(E[B]+4, E[D]+1)=max(3+4, 7+1)=max(7,8)=8
• E[H]=max(E[D]+1, E[G]+2)=max(7+1,5+2)=max(8,7)=8
• E[I]=max(E[E]+5, E[H]+4)=max(8+5,8+4)=13

選択肢別の誤答解説

• ア（A−B−E−I, H=7）：A−B−E−I の合計は $3+4+5=12$ 日であり，プロジェクト所要日数 13 日と一致しないためクリティカルではありません。H=7 は前駆の最大を取るルールを無視した計算ミスです。
• イ（A−B−E−I, H=8）：経路 A−B−E−I は 12 日でプロジェクト最長ではないため誤り。ただし H=8 は正しい最早時刻なので部分的に正しい認識です。
• ウ（A−C−D−E−I, H=7）：クリティカルパスの指定は正しいが，H の最早開始日を 7 とするのは誤りです。H は D→H（1 日）と G→H（2 日）の両方を考慮し，最遅の到達（=8）を取る必要があります。
• エ（A−C−D−E−I, H=8）：クリティカルパスの合計が 13 日で最終ノード時刻 13 に一致し，H の最早開始日もフォワードパスの結果 8 日なので正解です。

よくある誤解

• 「最短の分岐を選んで H の時刻を決める」：H は複数前駆（D と G）があるため，より遅い方（大きい方）を採る必要があり，単に D 経路を見ればよいわけではありません。
• 「経路の和を単純に足して比較するだけで良い」：経路ごとの所要日数計算は必要ですが，ノードの最早時刻は前駆の最大を取るというルールを忘れると誤答になります。
• 「A−B−E−I を見て I=12 としてしまう」：この経路は 12 日で I に達しますが，プロジェクト全体の最長経路（クリティカル）を見落とすと誤りになります。

補足コラム

• フォワードパス（最早時刻算出）とバックワードパス（最遅時刻算出）を両方使うと，各作業の余裕（スラック）を計算でき，リスクの高い作業に注意できます。
• 本問は AOA（矢線図）形式で示されていますが，考え方は AON（アクティビティオンノード）でも同じ：前駆の完了時刻の最大値を取る点が本質です。
• 実務ではクリティカルパス上の遅延がプロジェクト全体に直結するため，資源の重点配分や代替策（並行作業の検討）が重要です。

FAQ