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

正解：ア

AI解説

この問題は巡回セールスマン問題型の段取り時間最小化であり、4つの仕事の全順列(または効率的な組合せ)を検討して合計段取り時間が最小になる経路を探す。表の数値から最小合計が4時間となる順序が存在し、正解はアである。 ア: 各仕事間のFROM→TO段取り時間表を基に、総和が最小となる巡回順序を選んだ場合の合計時間。これが正解。 イ: 別の順序を選んだ場合の合計時間で、最小値ではない。 ウ: さらに非効率な順序を選んだ場合の合計時間で、最小値ではない。 エ: 最も非効率な順序、あるいは無関係な組合せを選んだ場合の値で、最小値ではない。 💡 段取り時間最小化問題は表の数値を丹念にたどり、全順列(仕事数が少ないので4!=24通り程度)を比較検討するのが確実。実務では巡回セールスマン問題として近似解法も使われる。