巡回セールスマン問題

いかがでしたでしょうか.たいていは簡単に正解が求まったと思いますが, 問題によっては一目では正解がわからない場合もあったと思います.

この問題は先ほどでてきた「最短経路問題」とほとんど同じに見えるかも しれませんが,実は巡回セールスマン問題は最短経路問題に比べて 格段に難しく,基本的に「全ての巡回路を調べて,その中から長さが 最小のものを選ぶという解法しかないのではないか」と思われています.

単純に「全ての巡回路を調べる」と言っても,都市の数を N とすれば,巡回路の総数は N の階乗(N!)通りですので その数はすぐに膨大なものになってしまいます. 例えば都市の数 N がさっき遊んだ場合のように 9 であれば,巡回路の総数は 9! = 362880 通りですので,たいしたことはありませんが, 20都市になると,巡回路の数は 20! で約 2.4×1018 となり,例えば,1秒間に1兆(=1012)個の巡回路を調べることのできる コンピュータでも,全ての巡回路を調べるのには

約27日間かかります.

これが,もし24都市になると, 巡回路の総数は 24! = 約 6.2×1023 となり,このコンピュータで全ての巡回路を調べるのには

約1万9千年かかります.

そのため,都市数が多い場合には,厳密な正解を求めることをあきらめて, 必ずしも正解ではないかもしれないが,「正解に近い」解,つまり「近似解」を求める アルゴリズムがたくさん提案されています.

京都大学のグループによる,そのような 近似解を求めるアルゴリズムによるデモンストレーションが,以下にありますので 是非覗いてみてください.532都市の場合の例があります.

京都大学のアルゴリズム工学/アルゴリズムデータベース/巡回セールスマン問題のデモ
最初のページに戻る