応用情報技術者 2010年 秋期 午前2 問72
問題文
製造業のA社では、NC 工作機械を用いて、四つの仕事を行っている。各仕事間の段取り時間は表のとおりである。合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。ここで、仕事はどの順序で行ってもよいものとし、FROM からTOへの段取り時間で検討する。
選択肢
ア：4（正解）
イ：5
ウ：6
エ：7
🔒 解説は解答すると表示されます
総段取り時間の最小化【午前2解説】
正解の理由
4つの仕事を並べ替えて隣接する仕事間の段取り時間の合計を最小にする問題です。全ての順序候補を比較すると、仕事順序 b→a→c→d のときの段取り時間が
b→a = 1、a→c = 1、c→d = 2 の合計 1+1+2 = 4 で最小になります。したがって、最小合計は ア の 4 時間となります。
b→a = 1、a→c = 1、c→d = 2 の合計 1+1+2 = 4 で最小になります。したがって、最小合計は ア の 4 時間となります。
解法ステップ
- 問題を「有向グラフの頂点を一度ずつ訪れる経路（順序）のうち，隣接辺の重み和を最小化する問題」と捉えます（非巡回の訪問路、始点は任意）。
- 仕事数が 4 と小さいため、全順列（4! = 24 通り）を列挙して各順序の合計段取り時間を計算し、最小値を選ぶのが確実で簡単です。
- 有望な順序の計算例：
- a→b→c→d : a→b(2) + b→c(1) + c→d(2) = 5
- b→a→c→d : b→a(1) + a→c(1) + c→d(2) = 4 ← 最小
- b→a→d→c : b→a(1) + a→d(2) + d→c(2) = 5
- ほかの順序も同様に計算して比較
- 全ての順序を比較して最小値（4）を採用します。
（簡潔化のため代表的な候補のみ示しましたが、実際には全順序を確認して最小であることを確かめます。）
選択肢別の誤答解説
- ア（4）
b→a→c→d の合計が 4 で、他のどの順序より小さいため正しい選択です。 - イ（5）
例えば a→b→c→d や b→a→d→c など多くの順序は合計 5 になりますが、これらは 4 より大きく誤りです。 - ウ（6）
いくつかの順序（例：b→c→a→d = 1+3+2 = 6）で確かに 6 になりますが、最小値ではありません。 - エ（7）
最悪の順序の一部（例：d→a→c→b = 4+1+2 = 7）で 7 となる場合がありますが、求める最小値はより小さい 4 です。
よくある誤解
- 対称だと仮定する誤り：段取り時間は一般に FROM→TO と TO→FROM で異なります（非対称）。対称と仮定すると誤った最小値になることがあります。
- 局所最適への固執：一部の遷移が最小でも全体では最小とならない場合があります。例えば a→b が小さい（2）から a→b→… を選ぶと最終的に最小にならないケースがあります。
- 対角要素の扱い間違い：同一仕事の遷移（対角）は対象外（斜線）であることを忘れると計算が狂います。
補足コラム
本問は「小規模な非対称巡回路（順序）最適化」の典型例です。仕事数が少なければ全順列の総当たりで解けますが、仕事数が増えると計算量は階乗的に増加します。一般に、n 頂点の非対称巡回最適化（アサイメトリックTSP）を最適に解くには次のような手法があります。
- 全探索（ブルートフォース）：n! 通り（小さい n 向け）
- 動的計画法（Held–Karp）：計算量は O(n^2 2^n)、中規模まで実用的
- 分枝限定やヒューリスティック（近似）：大規模問題向け（実用上はこちらが多用される）
数理的には各辺重みの行列を使い、始点を固定して Hamiltonian path（あるいは回路）を探索する考え方が基礎です。
FAQ
Q1. 始めの仕事にも段取り時間はかかりますか？
A1. 本設問では「FROM→TO の段取り時間」だけが与えられ、初期設定時間は指定されていません。したがって最初の仕事に対する特別な初期費用は考慮しません（順序間の遷移だけを合計します）。
A1. 本設問では「FROM→TO の段取り時間」だけが与えられ、初期設定時間は指定されていません。したがって最初の仕事に対する特別な初期費用は考慮しません（順序間の遷移だけを合計します）。
Q2. 複数の順序で同じ最小値になることはありますか？
A2. ありえます。本問では最小値が一意に 4 で、b→a→c→d がその例ですが、別順序で同値があればどちらでも最小となります。
A2. ありえます。本問では最小値が一意に 4 で、b→a→c→d がその例ですが、別順序で同値があればどちらでも最小となります。
Q3. 仕事数が増えたらどう解くべきですか？
A3. 仕事数が小さい場合は全探索で確実に解けますが、n が大きくなると Held–Karp（動的計画法）や分枝限定、実用的には近似アルゴリズム（局所探索、メタヒューリスティック）を用います。
A3. 仕事数が小さい場合は全探索で確実に解けますが、n が大きくなると Held–Karp（動的計画法）や分枝限定、実用的には近似アルゴリズム（局所探索、メタヒューリスティック）を用います。
関連キーワード: 順列最適化、アサイメトリックTSP、段取り時間、組合せ最適化、分枝限定、動的計画法
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！