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