応用情報技術者試験 令和6年度 秋期 午前 問72

【正解】ア

【解説】 段取り時間の表から，4つの仕事の最適な順序を求めます。

全ての順列を検討し，合計段取り時間が最小のものを見つけます。 例：d→c→b→a: 2+1+1=4時間 例：d→c→a→b: 2+1+2=5時間 例：a→c→b→a のような巡回は不可（各仕事1回ずつ）

d→c→b→aの順序で，段取り時間は： d→c: 2, c→b: 2, b→a: 1 → 合計5時間

c→b→a→d: 2+1+2=5 a→c→d→b: 1+2+3=6

d→c→a→b: 2+3+2=7... いや、d→c=2, c→a=3, a→b=2 → 7

もう一度：b→c→d→a: 1+2+4=7 b→a→c→d: 1+1+2=4

b→a→c→d: FROMがb→TOがa=1, FROMがa→TOがc=1, FROMがc→TOがd=2 → 合計4時間

よって，アの「4」が正解です。

【ポイント】 組合せ最適化の問題では，全ての順列を検討するか，最小コストの遷移を貪欲法で選ぶアプローチが有効です。