トップページに戻る
昔つくった数学の問題
↑の答え

巡回セールスマン問題の近似解を遺伝的アルゴリズムを使って求めてみた（前半）
巡回セールスマン問題の近似解を遺伝的アルゴリズムを使って求めてみた（後半）
本実験は，巡回セールスマン問題の厳密解および近似解を求める実験である．巡回セールスマン
問題はNP困難で多項式計算時間内に解決できない問題として知られており，都市数の増加に応じて，
計算量が爆発的に増加する性質を持っている．つまり，効率のよいアルゴリズムを用いなければ，
解を求めるのに数百年かかってしまうということもある．本実験では，厳密解に動的計画法，
近似解に遺伝的アルゴリズムおよび2-opt法を改良したヒューリスティクスな手法を用いることで，
短時間で厳密解や近似解をもとめることができた．本実験を通して，巡回セールスマンを解く手法
を理解するとともにプログラミングの実戦能力や，さまざまなアルゴリズムの考え方を養うことを
目標とした．