企業活動
基本情報技術者試験 科目A免除 修了試験 20140727 実施分 問71
製造業の A 社では，NC 工作機械を用いて，四つの仕事 a～d を行っている。各仕事間の段取り時間は表のとおりである。合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。ここで，仕事はどの順序で行ってもよく，a～d を一度ずつ行うものとし，FROM から TO への段取り時間で検討する。
単位 時間（行=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
- イ 5
- ウ 6
- エ 7
出典：基本情報技術者試験 科目A免除 修了試験 20140727 実施分 問71
答えと解説を見る
正解：ア
覚える知識
段取り時間最小の作業順序(巡回問題)
段取り時間の合計が最小になる作業順序は、全経路を比較して求める。
この問題で必要なこと
4仕事を一度ずつ行う全順序を比較する。b→a→c→dで1+1+2=4時間が最小。
ひっかけ
各ステップで最小値を選ぶ貪欲法では最適にならない場合がある。FROMとTOの向きの取り違えも誤りを招く。
この知識の出題：本試験系 0 回・免除試験 8 回（公開問題での観測値）