基本情報技術者 2018年 秋期 午前（科目A） 問52

プロジェクトの日程計画の所要日数算出【午前2 解説】

要点まとめ

• 結論：プロジェクトの所要日数は55日。クリティカルパスは S→A→D→（ダミー）→E→M→H を含む経路です。
• 根拠：フォワード解析で各ノードの最早到達時刻を求めると，合流点 M の最早時刻が45日で，最後の H（10日）を加えて55日になります。
• 差がつくポイント：破線（ダミー）は所要日数0でも優先順序を作り最長経路に影響するため，無視せず合流点では最大値を取ること。

正解の理由

よくある誤解

• ダミー作業は0日だから「無視して良い」と考えてしまう誤り。矢印が示す前後関係が変わると最長経路は変わります。
• 合流点で単に「経路の和」を取ってしまう誤り。合流点では入射経路の最大値（最早到達時刻）を採用します。
• 「最短経路」や「最小合計」などと混同し，クリティカル（最長）を求めるべきところを誤るミス。

解法ステップ

1. 各ノードの最早到達時刻（Earliest Time）をフォワードで計算する。開始ノードを0日とする。
2. 各作業の所要日数を足し，その到達先ノードの最早時刻を更新する。合流点では入射経路の最大値を採用。
3. 最終ノード到達時刻がプロジェクトの所要日数となる（ここでは合流点 M の最早時刻＋ H の所要日数）。
4. 必要ならバックワードで余裕（フロート）を算出するが，本問は所要日数（総工期）算出が目的。

• S（開始） = 0
• Node1（A後） = 0 + A(10) = 10
• Node2（B後）候補 = 0 + B(5) = 5，ただし Node1→Node2（ダミー0）経由だと 10 + 0 = 10 → より大きい方を採用して Node2 = 10
• Node3（D後） = Node1 + D(15) = 10 + 15 = 25
• NodeTop（C後）候補 = Node1 + C(10) = 20，かつ Node3→NodeTop（ダミー0）経由 = 25 + 0 = 25 → 最大で NodeTop = 25
• 合流点 M へ到達する経路の最早到達時刻：
  • A→D→F→M = 10 + 15 + 15 = 40
  • A→C→E→M = NodeTop(25) + E(20) = 45（※D→ダミー→Topが影響）
  • B→G→M = Node2(10) + 25 = 35
    よって M = max(40, 45, 35) = 45
• 最終（Finish）= M + H(10) = 45 + 10 = 55

選択肢別の誤答解説

• ア：40 — A→D→F→M（または A→C→E→M をそれぞれ 40 と見なす誤り。合流点 M をプロジェクト完了と誤認し，最後の H(10)を加えていない、あるいは D→ダミー→E 経路を見落としている。
• イ：45 — これは合流点 M の最早到達時刻（45日）であり，最終作業 H(10) を加え忘れた結果。最終ノード到達日が正解。
• ウ：50 — M を 40 と見なして H(10) を足した場合に出やすい値。すなわち D→ダミー→E の経路（NodeTop を遅らせる要因）を考慮していないミス。
• エ：55 — 正解。合流点で最大を取り、ダミー経路による遅延を反映した結果、最終完了は 55 日となる。

補足コラム

• 破線（ダミー）作業の役割：ダミーは所要日数0で論理的な依存関係を表現します。ネットワークのトポロジーを正確に表すため，クリティカルパスやフロート計算に影響を与えます。
• CPM/PERT の考え方：プロジェクト全体の所要日数は「全始点から終点までの最長経路の長さ」です。合流点では最大値を採るのは，すべての先行作業が完了するまで後続は始められないためです。
• 簡単な自動計算（例：Python で有向非巡回グラフの最長経路を求めるコード例）

# DAG を辞書で表し，重み付き辺で最長距離を求める（トポロジカル順序が既知の場合）
graph = {
    'S': [('A',10), ('B',5)],
    'A': [('C',10), ('D',15), ('B',0)], # A->B はダミー0
    'B': [('M',25)],
    'C': [('M',20)],
    'D': [('M_via_F',15), ('C',0)], # D->C はダミー0
    'M_via_F': [('M',0)],
    'M': [('T',10)],
    'T': []
}
# 単純化のための実装は省略。トポロジカルソート後，前方伝播で最長距離を計算。

FAQ