巡回セールスマン問題について - Qiita

最近、仕事の都合で「数理最適化」というものに触れる機会に恵まれています。 折角なので、ちょっとだけプライベートで触れてみた結果を載せてみたいと思います。 やったことは、数理最適化の1例、「巡回セールスマン問題」 これを、なんと無料の環境pulpで実装できるということで、その環境を整えつつ、実装までやってみました。 やってみたい問題は以下のもの。 ◆2.12 巡回セールスマン問題 https://www.msi.co.jp/nuopt/docs/v19/examples/html/02-12-00.html 以下に簡単に絵を描いて見ました。 A,B,C,Dが地図上のポイント。 Aを出発して、一筆書きをして帰ってくるとき、その距離の総和が一番小さいのはどのルートか??? という最適化問題のことを「巡回セールスマン問題」というらしいです。 NP困難と呼ばれて、結構難しいらしい。 しかし、pyth