巡回セールスマン問題（じゅんかいセールスマンもんだい、英: Traveling Salesman Problem, TSP）は、数学とコンピュータサイエンスの分野でよく知られている問題です。この問題は、最適化問題の一つであり、特に組合せ最適化の分野で研究されています。
問題の設定は以下の通りです。複数の都市があり、それぞれの都市をちょうど一度ずつ訪れて出発点に戻るという「巡回路」を作る場合、最も短い距離で巡るにはどのような順番で都市を回れば良いのかを求めるというものです。セールスマンが商品を売りに行く際に、無駄なく効率的に移動するための最適なルートを見つけるという状況を想像するとわかりやすいでしょう。
この問題は単純なように見えますが、都市の数が増えるにつれて計算するルートの数が爆発的に増加し、全ての可能性を試すことは非現実的になります。たとえば、4つの都市があれば、3!（3の階乗、つまり3×2×1）＝6通りのルートが考えられますが、20の都市があれば、19!（約1億2千万兆通り）ものルートを計算しなければなりません。このように、少し都市の数が増えるだけで計算量が天文学的数字になるため、効率的なアルゴリズムを考える必要があります。
巡回セールスマン問題はNP困難（エヌピーこんなん）という計算の難易度のクラスに属しています。これは、問題の解を見つけることは難しいが、与えられた解が正しいかどうかを検証することは比較的簡単であるという特徴を持っています。現在までに、この問題に対する効率的で正確な解法は発見されていません。
実用的な観点からは、完全な最適解を求める代わりに、「近似解」を求めるアプローチが取られます。近似解とは、最適解には及ばないものの、実用上十分に近い解を意味します。例えば、特定のヒューリスティック（経験則に基づく方法）や、遺伝的アルゴリズム、シミュレーテッドアニーリングなどの確率的アルゴリズムを使って近似解を求めることができます。
巡回セールスマン問題は、その難易度から数学やコンピュータサイエンスの研究において重要な位置を占めていますが、それだけでなく、物流、製造業、DNA配列決定、航空路の計画など、実世界の多くの分野での応用が考えられています。最適なルートを見つけることで、コスト削減や効率化を図ることができるため、企業や研究者にとっても非常に関心の高い問題です。
まとめると、巡回セールスマン問題は、いくつかの都市を効率的に巡る最短ルートを見つけることを目的とした問題であり、その解法は簡単ではありませんが、様々な分野での応用が可能であり、現代の科学技術において重要な意味を持っています。
