巡回セールスマン問題の意味と2近似アルゴリズム | 高校数学の美しい物語

都市の数 nnn と，二つの都市 iii と jjj の間を移動するのにかかる時間 dijd_{ij}dij​ が与えられる。このとき，全ての都市を巡ってもとの都市に戻ってくるような経路のうち，移動時間が最小なものを求めよ。 図は6都市の場合の例です（移動時間は図に書くのが難しいので，例えば二点間の距離と見てください）。青い経路はそれなりに合理的に見えますが，もっとよい経路があるかもしれません。 なお，グラフ理論の言葉を使うと「重み付きグラフに対して，重み最小のハミルトン閉路を求めよ」と述べることができます。