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

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

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

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

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

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