巡回セールスマン問題は結構難しそう ―― 一目では正解がわからないときもある

どうやって解くか？
単純に「全ての巡回路を調べる」 非常に時間がかかる！

• 都市の数が Ｎ のとき、巡回路の総数は Ｎ の階乗（Ｎ！）通り

• Ｎ ＝ ８ のとき、巡回路の総数＝ ８！ ＝ 40320 通り、たいしたことはない

• Ｎ ＝ ２０ のとき、巡回路の総数＝ ２０！ ＝ 約 2.4×10¹⁸ 通り
  1秒間に1兆(=10¹²)個の巡回路を調べることのできる コンピュータでも 約27日間 必要

• Ｎ ＝ ２４ のとき、巡回路の総数＝ ２４！ ＝ 約 6.2×10²³ 通り
  同じコンピュータで 約1万9千年 必要！