巡回セールスマン問題
全ての経路を計算することで最適解を得る手法は時間計算量は O ( n ! ) {\displaystyle O(n!)} であり、都市数の増加に対して時間計算量が急速に増加するため、都市数が20以上になると現実的でない。 比較的効率的なアルゴリズムとしては時間計算量と空間計算量が共に O ( n 2 2 n ) {\displaystyle O(n^{2}2^{n})} である動的計画法を用いたヘルドカープのアルゴリズム(英語版)が存在する。
NP困難な問題は、任意の大きさの任意の問題例に対しての多項式時間アルゴリズムが存在しないと考えられているが、巡回セールスマン問題の場合、約2000都市以内の比較的小さい問題例に対して、あるいは問題例によっては解が得られないことがあってもよいのであれば、線形計画法と論理木を組み合わせた分枝限定法や、線形計画法と巡回群を組み合わせた切除平面法により、パーソナルコンピュータでおよそ1日以内で厳密解を得られることが多い。
厳密に最適解を求めることを放棄して計算時間を短くする方法は、リン・カーニハン・アルゴリズムなどの局所探索アルゴリズム、焼きなまし法、ホップフィールドネットワークあるいはボルツマン機械などのヒューリスティックアルゴリズムと、出力される解のコストと最適解のコストとの差をなんらかの形で保証する多項式時間近似アルゴリズムの二つに大別できる。
問題例の大きさは、都市の数で表される。この問題は、計算複雑性理論においてNP困難と呼ばれる問題のクラスに属する。すなわち、問題例の大きさに関する決定性の多項式時間アルゴリズムが見つかりそうにない、計算量的に困難な問題である。なお、この問題の特殊ケースとして考えられるハミルトン閉路問題は、NP困難であると共にNP完全と呼ばれるクラスにも属するので、扱いが異なる。
都市間の移動コストが三角不等式を満たす、すなわち移動コストを距離と呼べる部分問題(あるいは制約つき問題)も、NP困難である。都市を平面上の点、都市間の距離を平面上のユークリッド距離とする部分問題は最も直感的で理解しやすいが、これも NP困難である。この部分問題は平面TSPなどと呼ばれ、実用上の応用も多く、またベンチマークの問題例としても距離関数の定義が自明なため頻繁に現れる。 都市の間の移動コストを 1 または 2 に制限しても、この問題は NP困難である。ハミルトン閉路問題は、移動コストを 1 または無限大に制限した TSP とみなすことができる。
一方で制約のない巡回セールスマン問題の直接の応用事例は無いと言ってもよい。逆に実際の応用事例では、より複雑な定義で配送計画や表面実装ロボットの動作計画などに適用される。