平成22年度 秋期 応用情報技術者試験 午前 問72
ストラテジ／企業活動製造業のA社では，NC工作機械を用いて，四つの仕事a～dを行っている。各仕事間の段取り時間は表のとおりである。合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。ここで，仕事はどの順序で行ってもよいものとし，FROMからTOへの段取り時間で検討する。 〔段取り時間〕（単位 時間） FROM仕事a→TO：仕事b 2，仕事c 1，仕事d 2 FROM仕事b→TO：仕事a 1，仕事c 1，仕事d 2 FROM仕事c→TO：仕事a 3，仕事b 2，仕事d 2 FROM仕事d→TO：仕事a 4，仕事b 3，仕事c 2 （注：本サイトでは原問題の表を文字表記に変換しています）
出典：平成22年度 秋期 応用情報技術者試験 午前 問72
- ア4
- イ5
- ウ6
- エ7
正解：ア
解説
四つの仕事を1回ずつ行う順序（ハミルトン路）をすべて検討すると，b→a→c→dの順序で行った場合の合計段取り時間が，b→a＝1，a→c＝1，c→d＝2の合計4時間となり，これが最小です。
選択肢ごとの解説
- ア正しい。仕事をb→a→c→dの順に行うと，段取り時間はそれぞれ1，1，2で合計4時間となり，これが最小の合計段取り時間です。
- イ誤り。5時間になる順序（例えばa→b→c→dなど）は存在しますが，これは最小の組合せではありません。
- ウ誤り。6時間になる順序も存在しますが，より少ない段取り時間で済む順序があるため最小ではありません。
- エ誤り。7時間は，段取り時間の大きい組合せを含む順序で行った場合の値であり，最小の合計段取り時間ではありません。