遺伝的アルゴリズムで巡回セールスマン問題を解いてみる(理論編) - Qiita

はじめに 「巡回セールスマン問題 遺伝的アルゴリズム」でググるとたくさんヒットすることを自分でもやってみました。 理論編 Python コード編 実行結果編 概要 巡回セールスマン問題(Traveling Salesman Problem) 巡回セールスマン問題 とは、$N$ 個の点すべてを 1 回ずつ通って元の点に戻る最短の経路を探索する問題です。 $N$ 点を全て通って戻ってくる経路の総数は $(N-1)!/2$ 通りあります。 3 点であれば 1 通りです。 4 点であれば 3 通りです。 5 点であれば 12 通りです。 点が増えると経路の総数は爆発的に増えていきます。 その中から最短の経路を見つけようとすると膨大な時間がかかります。 しかし、条件付きであれば実用的な時間内で経路を見つけられます。 例えば、点が凸多角形の頂点にあると分かっていれば、最短経路はその凸多角形です。 また