ある物流会社が、1台のトラックで倉庫を出発し、複数の配送先を1回ずつ回る順序を決めるシステムを作っている。担当者は、考えられる回り方をすべて列挙し、総移動距離が最短のものを選ぶブルートフォースの方法を検討している。この方法に関する説明として、最も適切なものを1つ選べ。
正解と解説を見る
解説
正解 A
この問題の論点：ブルートフォースと組合せ爆発
ポイント
ブルートフォースは必ず最適解を見つけますが、候補の数が組合せ爆発で急増するため、規模の大きい問題では現実的でなくなります。
選択肢ごとの解説
- A
適切 正解
配送先がn件なら順序はnの階乗通りで、10件では3,628,800通り、20件では約2.4×10の18乗（約243京）通りです。件数が1つ増えるたびに候補が掛け算で増える現象を組合せ爆発といい、総当たりの大きな弱点です。
- B
不適切
ブルートフォースはすべての候補を調べるため、計算さえ終われば必ず最短の回り方が得られます。弱点は解の質ではなく、候補の数が急激に増えて計算が終わらなくなることです。
- C
不適切
配送先が5件なら回る順序は5の階乗で120通りしかなく、総当たりでもすぐに最短の回り方が求まります。小さな問題では、実装が簡単で最適解が確実に得られる有力な方法です。
- D
不適切
深さ優先探索で最初に見つかるのは、最初にたどった枝の先にある回り方にすぎません。調べる順番が変わるだけなので、最短かどうかはほかの回り方と比べなければ確かめられません。
補足
複数の地点を1回ずつ回る最短の経路を求める問題は、巡回セールスマン問題と呼ばれます。実務では、最短の保証はなくても良い解を短時間で求めるヒューリスティックな方法（近い配送先から順に回る、得られた経路を少しずつ入れ替えて改善する、など）がよく使われます。
試験での狙われ方
総当たりで最適解が得られるかどうかと、問題の規模による計算量の増え方を組み合わせて問う形がよく見られます。
参考
- G検定 試験出題範囲（シラバス2024）第1.4版 （技術分野 項目3 探索・推論）