応用情報技術者 2017年 秋期 午前2 問29

永久待ちの判定【午前2解説】

正解の理由

解法ステップ

1. 与えられた有向辺をリスト化する。ここでは
   C→A、C→B、B→D、D→C、D→E、E→G、F→E が与えられている。
2. 有向グラフにおいて、同時に互いに到達可能なノード群（強連結成分）を探す。特に、2点以上で循環する経路（有向サイクル）を検索する。
3. B→D→C→B の経路があり、B, C, D は互いに到達可能でサイクルを成す。これらはデッドロックの当事者（永久待ち）である。
4. 他のノード（E, F, G, A）は、上の辺関係のままではサイクルに入っていないため「サイクルに属する永久待ち」には該当しない。
5. よって、図のままの定義で採ると永久待ちは B, C, D（選択肢イ）。

選択肢別の誤答解説

• ア: A, B, C, D
  • 誤り。A は C によって待たれている（C→A の方向）ので、A が誰かを待っていることを示す矢印はない。A 自身がサイクルに入っておらず、永久待ちとはならない。
• イ: B, C, D
  • 図に示された辺関係に基づく標準的な「デッドロック = 有向サイクル」 の定義では正しい。B→D→C→B のサイクルがこれに該当する。
• ウ: B, C, D, F（問題表の正答）
  • 与えられた辺だけを見ると F はサイクルに含まれない（F→E があるが E→...→F の閉路が示されていない）。したがってそのままでは ウ を支持する根拠がない。ウ を成立させるには図に欠落した辺（例：G→F といった E,G,F 間の閉路をつくる辺、あるいは F→D のように D を含む別の閉路をつくる辺）が追加されている必要がある。
• エ: C, D, E, F, G
  • 誤り。C, D は含まれるが、E と G は与えられた辺だけではサイクルに含まれない（E→G はあるが G→...→E の戻りがない）。そのため E,G を永久待ちと断定するのも誤り。

よくある誤解

• サイクルに「たどり着くだけ」のノードを永久待ちと誤認する
  • 例：D→E とあって D がサイクルにいると、E も永遠に進めないため「永久待ち」と感じやすいが、試験上の「永久待ち」（デッドロック）は「サイクルに属するかどうか」で判定されることが多い。試験問題の文脈で定義を確認すること。
• 矢印の向きを読み間違える
  • X→Y は「X が Y を待っている」。見落としで逆に読むと誤答につながる。
• 図に表示漏れ・表記ミスを見落とす
  • 画像やテキスト化の段階で辺が抜けているケースがある。設問の正答と図が一致しない場合、図に欠落辺がある可能性を検討する。

補足コラム

• 「デッドロック（永久待ち）」の判定はアルゴリズムで効率的に行えます。強連結成分（SCC：strongly connected components）を求める Tarjan 法や Kosaraju 法を用いると、全ノードを O(N + M)（N ノード、M 辺）で判定できます。実務的には次の流れ：待ちグラフを作成 → SCC を抽出 → SCC のサイズが >=2 のコンポーネントがデッドロックの集合です（自己ループがあればサイズ1でもデッドロック）。
• 問題の表記上の齟齬について：提示された選択肢と「図のまま」の解析結果が一致しない場合、
  • (A) 図（または記述）に辺の欠落・誤記がある → 図を修正すると選択肢と一致する場合がある、あるいは
  • (B) 出題側が「永久待ち」を「サイクル以外に、サイクルに依存して進行不能となるノードも含む」と定義している可能性がある。
    どちらかの可能性があるため、必ず設問文の定義を確認するか、図の矢印を精査してください。今回の提示図のみからは選択肢イが妥当です。

FAQ