Jarバイナリ
ソース
説明
分枝限定法を用いた巡回セールスマン問題の厳密解の解法を可視化する。
緩和問題を分割して探索木を構築しながら、長さの上界を使って枝刈りをする。
簡単のため、ユークリッドTSPやメトリックTSPの性質は用いず、また有向辺を用いて書いた。ぶっちゃけ遅いと思うし、いろいろな性質を応用すればより高速化できると思う。
ヒューリスティックも適当。こちらは辺の反射性を利用して交差を無くすという、有向TSPでは使えないロジックも使っている。
ソース汚いけどパラメタ調整が可能な程度には値をまとめてある。