巡回セールスマン問題
より複雑な定義の問題をあつかう解法としては、欧州では前述した分枝限定法、切除平面法、(前者2つをミックスした)分枝カット法といった厳密解法を用いることが多く、アメリカ合衆国では遺伝的アルゴリズム、タブー探索といった厳密に最適な解を保証しないヒューリスティックアルゴリズムを用いることが多い。
三角不等式が成り立つ TSP については多項式時間近似アルゴリズムが数多く存在する。 たとえば近似アルゴリズムが2(最悪でも出力が最適解の長さの2倍以内である)のアルゴリズム(最近追加法他)や近似度 1.5 のアルゴリズム(クリストフィードのアルゴリズム)が知られている。 近年、平面TSP には、近似率を任意に 1 に近づけることができるアルゴリズム、多項式時間近似戦略 PTAS が Arora によって与えられた。 ハミルトン閉路問題の多項式時間の厳密解が多項式時間で求められない(ハミルトン閉路問題はNP完全なのでP≠NPと同じ)なら三角不等式を満たさないTSPは近似率を保証する多項式時間のアルゴリズムはない。