令和6年度 秋期 応用情報技術者試験 午前 問72
製造業のA社では，NC工作機械を用いて，四つの仕事a〜dを行っている。各仕事間の段取り時間は表のとおりである。合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。ここで，仕事はどの順序で行ってもよく，a〜dを一度ずつ行うものとし，FROMからTOへの段取り時間で算出する。
図の説明テキスト
単位 時間
| FROM \ TO | 仕事a | 仕事b | 仕事c | 仕事d |
|---|---|---|---|---|
| 仕事a | 2 | 1 | 2 | |
| 仕事b | 1 | 1 | 2 | |
| 仕事c | 3 | 2 | 2 | |
| 仕事d | 4 | 3 | 2 |
解答・解説
正解: ア. 4
この問題は、4つの仕事（a, b, c, d）をすべて1回ずつ行う際の、段取り時間の合計が最小となる順番を求める問題です。
解法のポイント
仕事の順序は自由であり、4つの仕事を順番に行うための移動（段取り）は合計3回発生します。
全探索（樹形図の作成） などを用いて、すべての順序の組み合わせから段取り時間の合計を計算し、最小となるものを探します。
- 始点の決定: a, b, c, d のいずれかの仕事から開始します。
- 経路の探索: 提示された表の「FROM」から「TO」へ交差するセルの数値を拾い出し、順次足し合わせます。
- 最小値の特定: 各経路の合計時間を比較し、最も短い時間を見つけます。
表の数値に基づいて各ルートを計算すると、合計時間が最も短くなる仕事の順序が存在し、その場合の合計段取り時間が 4時間 となります。
各選択肢の解説
- ア: 正解。条件を満たす最小の合計段取り時間です。
- イ: 誤り。他の順序で実行した場合などの時間であり、最小値ではありません。
- ウ: 誤り。他の順序で実行した場合などの時間であり、最小値ではありません。
- エ: 誤り。他の順序で実行した場合などの時間であり、最小値ではありません。