応用情報技術者 2022年 春期 午前2 問73

段取り時間の最小順序【午前2解説】

正解の理由

• b→a = 1、a→c = 1、c→d = 2 の組合せで合計 $1+1+2=4$。
• 表中の最小値は 1 が複数ありますが、それらだけで 3 を作る（3 個の遷移すべてが 1 で合計 3 になる）ことはできません。1 の遷移は a→c、b→a、b→c の 3 箇所に限られ、これらで d を到達させる連続したハミルトン経路（全ノードを一度ずつ通る経路）を構成できないため、3 は達成不可能です。したがって 4 が最小です。

解法ステップ

1. 問題は「向きありの重み付きグラフで各ノードを一度ずつ通る経路（始点・終点は任意）で遷移重みの和を最小化する」問題（有向ハミルトン経路の最小化）です。仕事数が少ない場合はすべての順列（4! = 24 通り）を試すのが確実です。
2. 表から遷移時間を取り出す：
   • a→b = 2、a→c = 1、a→d = 2
   • b→a = 1、b→c = 1、b→d = 2
   • c→a = 3、c→b = 2、c→d = 2
   • d→a = 4、d→b = 3、d→c = 2
3. 主要な候補順序を評価する（代表的な最小候補のみ示す）：
   • b → a → c → d = $1+1+2=4$
   • a → b → c → d = $2+1+2=5$
   • a → c → b → d = $1+2+2=5$
   • c → b → a → d = $2+1+2=5$
   • d → b → a → c = $3+1+1=5$
4. 比較の結果、最小は 4（b→a→c→d）であると確定する。

選択肢別の誤答解説

• ア（4）: 正答。b→a→c→d の合計 $1+1+2=4$ が最小であるため正しい。
• イ（5）: よくある誤答。a を始点にして a→b→c→d や a→c→b→d のような順序を想定すると 5 になるが、b を始点にすると 4 が得られるため不適切。
• ウ（6）: さらに大きな順序の誤り。複数の順序が 6 になるもの（例：a→b→d→c 等）があるが、最小値ではない。
• エ（7）: 最大側の選択肢の一つ。代表的に遷移に大きな値（例：d→a→... で d→a = 4 を含む順序）を含むと 7 となる順序があるが、最小解ではない。

よくある誤解

• 「単純に表の最小値（1）を3つ選べば最小合計になる」：誤り。遷移の連結性（すべての仕事を一度ずつ通る道になっているか）を満たさないと実現不能です。本問では 1 の遷移は a→c、b→a、b→c のみで、これだけでは d を含む連続経路になりません。
• 「往復（出発地に戻る）を前提にして解く」：本問は始点・終点自由の“1 回ずつ実行”であり、巡回（閉路）への復帰費用を加える必要はありません。復帰を誤って加えると不要に大きな値を得ます。

補足コラム

• 小さなノード数（n ≤ 10 程度）では全順列列挙（O(n!)）で十分です。今回のように 4 ノードなら 24 通りを手で計算しても短時間で最小値が見つかります。
• ノード数が増えると動的計画法（Held–Karp、O(n^2 2^n)）や近似アルゴリズム（貪欲法、局所探索、遺伝的アルゴリズムなど）を検討します。
• 本問は「有向最短ハミルトン経路問題」の一例で、製造現場の段取り最適化など実務的意義が高い問題形式です。