平成21年度春期 応用情報技術者試験 午前 問72

正解：ア

AI解説

これは仕事の実行順序(段取り時間表のFROM→TO)を工夫して合計段取り時間を最小化する組合せ最適化問題であり、考えられる実行順序をしらみつぶしに比較(あるいは近似的に検討)すると、最小の合計段取り時間は4時間になる。 ア: 全ての実行順序を比較検討した結果、段取り時間の合計が最小となる組合せが4時間であり、これが正解である。 イ: 5時間は、最適でない順序(例えば段取り時間の大きい組合せを含む順序)を選んだ場合に生じる値である。 ウ: 6時間も同様に、最適な順序を選ばなかった場合に生じ得る値であり、最小値ではない。 エ: 7時間はさらに非効率な順序を選んだ場合の値であり、最小化された解ではない。 💡 この種の問題は小規模な巡回セールスマン問題(TSP)に相当する。仕事の数が少ない場合は全順列を書き出して合計を比較するのが確実な解法である。