巡回セールスマン問題と遺伝的アルゴリズム(GA)巡回セールスマン問題と遺伝的アルゴリズム(GA) 巡回セールスマン問題(TSP)とは 巡回セールスマン問題 (Traveling Salesperson Problem : TSP)は、 セールスマンがN個の都市を1回ずつ通って巡回する最短の経路を見つける問題です。 TSPには多くの応用例があり、実用上でも重要な問題です。 例えば、プリント基盤に穴を空ける時の最適の順序はTSPです。 都市数をNとすると、(N-1)!/2種類の巡回経路があります。 したがって、数十都市になるとすべての巡回経路を調べることは 非常に難しく、都市の配置に法則性がなければ厳密解を求めることはできないと 言ってよいと思います。 そこで、近似解法で十分良い解を求めることになります。 近似アルゴリズム TSPを解くための近似アルゴリズムを３つ紹介します。 これらはTSPだけでなく、多くの最適化問題に応用できます。 ラン
