Jarバイナリ ソース 説明 分枝限定法を用いた巡回セールスマン問題の厳密解の解法を可視化する。 緩和問題を分割して探索木を構築しながら、長さの上界を使って枝刈りをする。 簡単のため、ユークリッドTSPやメトリックTSPの性質は用いず、また有向辺を用いて書いた。ぶっちゃけ遅いと思うし、いろいろな性質を応用すればより高速化できると思う。 ヒューリスティックも適当。こちらは辺の反射性を利用して交差を無くすという、有向TSPでは使えないロジックも使っている。 ソース汚いけどパラメタ調整が可能な程度には値をまとめてある。
![分枝限定法を利用した巡回セールスマン問題の解法のデモ作った - 簡潔なQ](https://cdn-ak-scissors.b.st-hatena.com/image/square/6ddea31c6976b2423d57cb4f6b864c710b1bf1fe/height=288;version=1;width=512/http%3A%2F%2Fgyazo.com%2Ffc6348e30333913c3eae0fc8c1c95264.png)