応用情報技術者 2009年 春期 午前2 問72
問題文
製造業のA社では、NC工作機械を用いて、四つの仕事a,b,c,dを行っている。各仕事間の段取り時間は表のとおりである。合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。ここで、仕事はどの順序で行ってもよいものとし、FROMからTOへの段取り時間で検討する。
選択肢
ア：4（正解）
イ：5
ウ：6
エ：7
製造業の段取り時間最小化問題【午前2 解説】
要点まとめ
- 結論：仕事の順序を工夫し、合計段取り時間を最小の4時間にできる。
- 根拠：各仕事間の段取り時間をグラフの重みとみなし、全仕事を一度ずつ訪れる最短経路を求める問題だから。
- 差がつくポイント：単純な合計ではなく、順序を変えて段取り時間の合計を最小化する「巡回セールスマン問題」の考え方を理解しているか。
正解の理由
選択肢アの4時間は、仕事の順序を「a → c → b → d」などに設定した場合に得られる最小の合計段取り時間です。
例えば、a→cは1時間、c→bは2時間、b→dは2時間で合計5時間ですが、a→b→c→dの順序では段取り時間がもっと大きくなります。
最適な順序を見つけることで、合計段取り時間を4時間に抑えられるため、アが正解です。
例えば、a→cは1時間、c→bは2時間、b→dは2時間で合計5時間ですが、a→b→c→dの順序では段取り時間がもっと大きくなります。
最適な順序を見つけることで、合計段取り時間を4時間に抑えられるため、アが正解です。
よくある誤解
段取り時間の合計を単純に足し合わせてしまい、順序を変えずに計算する誤りが多いです。
また、往復を考慮する必要がない点を見落とし、無駄な計算をすることもあります。
また、往復を考慮する必要がない点を見落とし、無駄な計算をすることもあります。
解法ステップ
- 各仕事間の段取り時間を表にまとめる。
- すべての仕事を一度ずつ訪れる順序の候補を列挙する（順列）。
- 各順序の段取り時間合計を計算する。
- 最小の合計段取り時間を持つ順序を特定する。
- 最小値を選択肢と照合し、正解を決定する。
選択肢別の誤答解説
- ア: 4 → 正解。最適な順序で段取り時間を最小化できる。
- イ: 5 → 順序によっては5時間になるが、最小ではない。
- ウ: 6 → さらに非効率な順序の合計時間。
- エ: 7 → 最も非効率な順序の合計時間で誤り。
補足コラム
この問題は「巡回セールスマン問題（TSP）」の一種で、仕事間の移動コスト（段取り時間）を最小化する経路を求めるものです。
小規模な問題では全順列を試す全探索が可能ですが、仕事数が増えると計算量が爆発的に増加するため、ヒューリスティックや近似アルゴリズムが用いられます。
小規模な問題では全順列を試す全探索が可能ですが、仕事数が増えると計算量が爆発的に増加するため、ヒューリスティックや近似アルゴリズムが用いられます。
FAQ
Q: なぜ仕事の順序を変えるだけで段取り時間が変わるのですか？
A: 各仕事間の段取り時間は異なるため、順序によって合計の切り替え時間が変わるからです。
A: 各仕事間の段取り時間は異なるため、順序によって合計の切り替え時間が変わるからです。
Q: すべての順序を試す必要がありますか？
A: 仕事数が少なければ全順列を試すのが確実ですが、多い場合は効率的なアルゴリズムを使います。
A: 仕事数が少なければ全順列を試すのが確実ですが、多い場合は効率的なアルゴリズムを使います。
関連キーワード: 段取り時間、順序最適化、巡回セールスマン問題、最小化問題、組合せ最適化
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！