読者です 読者をやめる 読者になる 読者になる

分枝限定法を利用した巡回セールスマン問題の解法のデモ作った

http://gyazo.com/fc6348e30333913c3eae0fc8c1c95264.png

Jarバイナリ
ソース

説明

分枝限定法を用いた巡回セールスマン問題の厳密解の解法を可視化する。

緩和問題を分割して探索木を構築しながら、長さの上界を使って枝刈りをする。

簡単のため、ユークリッドTSPやメトリックTSPの性質は用いず、また有向辺を用いて書いた。ぶっちゃけ遅いと思うし、いろいろな性質を応用すればより高速化できると思う。

ヒューリスティックも適当。こちらは辺の反射性を利用して交差を無くすという、有向TSPでは使えないロジックも使っている。

ソース汚いけどパラメタ調整が可能な程度には値をまとめてある。