巡回セールスマン問題とは、複数の都市と都市間の移動距離が与えられたとき、すべての都市を一度ずつ訪問して出発地に戻る総移動距離が最小の経路を求める組合せ最適化問題です。AI分野では経路探索や物流効率化などで活用されています。
巡回セールスマン問題とは
一言でいうと何かというと、複数の地点をすべて効率よく巡って出発地に戻るための「最も移動距離が短いルート」を見つけ出す問題のことです。
詳しく解説
グラフ理論や組合せ最適化の代表的な問題であり、都市の数が増えるに従って計算量が爆発的に増加するという特徴を持っています。すべての組み合わせをしらみつぶしに計算すると、スーパーコンピュータを使っても現実的な時間内には解ききれなくなります。そのため、AI分野や情報科学においては、遺伝的アルゴリズムや強化学習などのメタヒューリスティクス手法を用いて、最適解に近い「十分良い解」を効率よく探索することが広く研究されてきました。
具体例・使われ方
具体的な利用例としては、宅配便の配送トラックが複数の配達先を回る最適なルートの決定や、プリント基板に穴をあけるドリルヘッドの移動順序の最適化、さらにはロボットアームの効率的な動作制御などに応用されています。
似た用語との違い
最短経路問題が「特定の1地点から別の1地点までの最短ルート」を求めるのに対し、巡回セールスマン問題は「すべての地点を一度ずつ経由して元に戻る周回ルート」を求める点が異なります。
注意点
都市の数がわずか数十個程度であっても計算量が膨大になるため、必ずしも厳密な最適解を常に出力できるとは限りません。AIを用いる場合も、多くは近似解や準最適解の探索にとどまる点に注意が必要です。
この解説は役に立ちましたか？誤りが含まれる場合はご報告いただけますと幸いです。
更新日時: 2026年9月10日 15:31