y_uti https://blog.hatena.ne.jp/y_uti/ y_uti のブログ https://y-uti.hatenablog.jp/ 前回の記事に続き、巡回セールスマン問題の近似解法について調べてみます。前回は、いくつかの近似解法を実装して、問題を解く様子をアニメーションで紹介しました。今回は、それぞれの解法でどのくらい良い解が求められるのかを比較してみます。 巡回セールスマン問題の近似解法を眺める - y_uti のブログまず、サンプルデータを作成します。次のコードを引数 100 として実行し、1 ≤ x, y ≤ 1,000,000 の範囲に 100 都市をランダムに生成します。今回は、これを 100 回実行して 100 個のデータを作成しました。なお、都市の範囲や出力書式は paiza の問題 の設定に合わせたものです… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fy-uti.hatenablog.jp%2Fentry%2F2017%2F11%2F11%2F115549" title="巡回セールスマン問題の近似解法と 2-opt 改善法 - y_uti のブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/y/y_uti/20171109/20171109225258.png Hatena Blog https://hatena.blog 2017-11-11 11:55:49 rich https://y-uti.hatenablog.jp/entry/2017/11/11/115549 1.0 100%