応用情報技術者 2012年秋期午前2 問73

問題文

製造業のA社では、NC工作機械を用いて、四つの仕事a〜dを行っている。各仕事間の段取り時間は表のとおりである。合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。ここで、仕事はどの順序で行ってもよく、a〜d を一度ずつ行うものとし、FROMからTOへの段取り時間で検討する。

🖊️ 解答を隠して解いてみる

選択肢

ア：4（正解）

イ：5

ウ：6

エ：7

🔒 解説は解答すると表示されます

段取り時間の最小合計【午前2解説】

正解の理由

仕事順序は有向グラフのハミルトンパスに相当し、合計段取り時間は各隣接遷移の和で決まります。最小化するために全順列を検討すると、順序 b→a→c→d の遷移時間が 1（b→a）＋1（a→c）＋2（c→d）＝4 時間となり、これが最小です。したがって正解はアに対応する 4 時間です。

解法ステップ

問題を「4ノードの有向完全グラフで，3本の連続辺（遷移）合計を最小にするハミルトンパスを探す問題」と捉える。各順序の合計は始点から終点までの3つの遷移和。
実務的には全順列（4! = 24）を列挙して合計を計算するか、有望な経路のみを絞り込んで評価する。
表の値を用いて各順序の合計を計算する。代表的な候補を評価すると、b→a→c→d が 1+1+2 = 4 と最小になる。
さらに他の順序（例：a→b→c→d = 2+1+2 = 5、d→c→b→a = 2+2+1 = 5 など）を確認して、4 が最小であることを確かめる。

（検算用の簡単なプログラム例）

import itertools
cost = {
 ('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,
}
names = ['a','b','c','d']
best = (999, None)
for perm in itertools.permutations(names):
    s = sum(cost[(perm[i], perm[i+1])] for i in range(3))
    if s < best[0]:
        best = (s, perm)
best
# 出力: (4, ('b','a','c','d'))

選択肢別の誤答解説

ア（4）: 正しい。b→a（1）＋a→c（1）＋c→d（2）＝4 で、全順列の中で最小になる。
イ（5）: 多くの順序が合計5を与えるため誤答になりやすい（例：a→b→c→d = 2+1+2 = 5、c→b→a→d = 2+1+2 = 5）。しかし 4 より小さくない。
ウ（6）: いくつかの順序では6になる（例：b→c→a→d = 1+3+2 = 6）。だが最小ではない。
エ（7）: 大きめの遷移を含む順序で7になる（例：b→d→a→c = 2+4+1 = 7）。最小値とは差がある。

よくある誤解

表を「無向」または「対称」として扱う誤り：行→列は方向依存（FROM→TO）であり、逆向きの値は別物です。
仕事を複数回行う経路を誤って検討するミス：条件は a〜d を一度ずつ行うことなので、同じ仕事を重複させてはいけません。
最小値の下界（各ノードの最小遷移を単純に足す）だけで答えを決める誤り：単純な下界は到達不可能な組合せを含むため、必ず実現可能性を検証する必要があります。

補足コラム

この種の問題は「非巡回（終端を戻さない）アサイメント」や「有向ハミルトンパスの最小重み問題」に対応します。小規模（小さいノード数）なら全順列の総当たりで十分ですが、ノード数が増えると計算量は階乗的に増大します。大規模な同種問題は巡回セールスマン問題（TSP）の変種として扱われ、動的計画法（Held–Karp アルゴリズム）や近似アルゴリズムが用いられます。

FAQ

Q1: 出発地点や終了地点は指定がないとき、どう扱いますか？
A1: 出発と終了は自由です。すべての始点・終点を含めた順列を評価して、最小の合計を選びます。

Q2: 「戻る」必要がある（巡回）場合はどう計算する？
A2: 巡回（サイクル）で戻る場合は、最後の仕事から最初の仕事への遷移コストも加えて合計を算出します。今回の問題は戻る必要がないため加えません。

Q3: 電卓で素早く候補を絞るコツは？
A3: 各仕事から出る最小遷移値を基に有望な始点を絞り、そこから部分経路を展開して合計値を比較する（すばやく剪定する）と効率的です。

関連キーワード: 組合せ最適化、巡回セールスマン問題、段取り時間、順序最適化

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！