応用情報技術者 2009年 春期 午前2 問72

最小段取り時間経路【午前2解説】

正解の理由

解法ステップ

1. 各仕事間の段取り時間を行列（または表）で確認する。自己遷移は考慮しない（左上から右下の斜線部分）。
2. 仕事の順序は任意なので、4つの仕事の全順列（4! = 24通り）を考える。
3. 各順列について隣接する仕事間の段取り時間を合計する（長さ4の列なら3つの遷移の和）。
4. すべての合計を比較して最小値を採る。
5. 今回は全列挙の結果、b → a → c → d の合計が最小の $4$ であることが確認できる。

• b → a → c → d の合計は $1+1+2=4$

from itertools import permutations

# cost[from][to]
cost = {
    'a': {'b':2,'c':1,'d':2},
    'b': {'a':1,'c':1,'d':2},
    'c': {'a':3,'b':2,'d':2},
    'd': {'a':4,'b':3,'c':2}
}

min_cost = 999
best = None
for perm in permutations(['a','b','c','d']):
    total = sum(cost[perm[i]][perm[i+1]] for i in range(3))
    if total < min_cost:
        min_cost = total
        best = perm

print(best, min_cost)  # ('b','a','c','d') 4

選択肢別の誤答解説

• ア（4）
  b → a → c → d の合計 $1+1+2=4$ で、全順列の中で最小になるため正しい。
• イ（5）
  合計5になる順序は存在します（例：a → b → c → d は $2+1+2=5$、a → c → b → d は $1+2+2=5$、b → a → d → c は $1+2+2=5$ 等）。しかしさらに小さい4が存在するため最小値ではありません。
• ウ（6）
  合計6の例も複数あります（例：a → b → d → c は $2+2+2=6$、a → d → b → c は $2+3+1=6$ など）。だがこれも最小ではありません。
• エ（7）
  合計7になる順序も存在します（例：b → c → d → a は $1+2+4=7$ 等）。さらに小さい値があるため誤りです。

よくある誤解

• 「対角成分（自己遷移）を0として順序の最初に足す必要がある」と誤解する人がいるが、設問は仕事間の切り替え時間のみを問うため、順序開始時の追加費用は存在しない（自己遷移は無視）。
• 「直感的に見て連続で近い作業を並べれば最短になる」と考えるが、局所的に小さい遷移を並べても全体では最短にならない場合があるため、全体評価が必要。
• 手で計算する際に、順序のうち一部だけ見て決め打ちしてしまい、最小となる別の開始仕事を見落とすことがある（今回の例では b を先頭にする考えを忘れがち）。

補足コラム

FAQ