一方で制約のない巡回セールスマン問題の直接の応用事例は無いと言ってもよい。逆に実際の応用事例では、より複雑な定義で配送計画や表面実装ロボットの動作計画などに適用される。あり、都市数の増加に対して時間計算量が急速に増加するため、都市数が20以上になると現実的でない。ある動的計画法を用いたヘルドカープのアルゴリズム(英語版)が存在する。NP困難な問題は、任意の大きさの任意の問題例に対しての多項式時間アルゴリズムが存在しないと考えられているが、巡回セールスマン問題の場合、約2000都市以内の比較的小さい問題例に対して、あるいは問題例によっては解が得られないことがあってもよいのであれば、線形計画法と論理木を組み合わせた分枝限定法や、線形計画法と巡回群を組み合わせた切除平面法により、パーソナルコンピュータでおよそ1日以内で厳密解を得られることが多い。厳密に最適解を求めることを放棄して計算時間を短くする方法は、リン・カーニハン・アルゴリズムなどの局所探索アルゴリズム、焼きなまし法、ホップフィールドネットワークあるいはボルツマン機械などのヒューリスティックアルゴリズムと、出力される解のコストと最適解のコストとの差をなんらかの形で保証する多項式時間近似アルゴリズムの二つに大別できる。(前者2つをミックスした)分枝カット法といった厳密解法を用いることが多く、アメリカ合衆国では遺伝的アルゴリズム、タブー探索といった厳密に最適な解を保証しないヒューリスティックアルゴリズムを用いることが多い。ついては多項式時間近似アルゴリズムが数多く存在する。アルゴリズム(クリストフィードのアルゴリズム)が知られている。問題には、近似アルゴリズムを定数倍以内に保証できる多項式時間アルゴリズムが存在しないことは明らかである。すべての辺(頂点ではなく)を少なくとも1回ずつ通る巡回路でコスト最小のものを求める。こちらは多項式時間で解けることが知られている。配車配送計画ソフト外部リンク[編集]ウィキメディア・コモンズには、巡回セールスマン問題に関連するカテゴリがあります。VLSI)TSPのソースコードへのリンク集この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています(PJ:コンピュータ/P:コンピュータ)。(日時は個人設定で未設定ならばUTC)。表示-継承ライセンスの下で利用可能です。追加の条件が適用される場合があります。詳細は利用規約を参照してください。Cookieに関する声明モバイルビュ。