Algorithm Archive

いろいろ工夫して100頂点の巡回セールスマン問題は数秒～数十秒で厳密解法を導けるようになりました。公開済みのTSP ver.1.00よりかなり高速化できてそう。それでも150頂点になるとめっきりダメです。

Continue reading

巡回セールスマン問題のデモプログラムTSP ver.1.00をリリースしました。

実装を始めてから1ヶ月弱ですが、ようやくラグランジュ緩和の下界を用いた分枝限定法による厳密解法を実装しました。これまでの手法と違ってやはり頂点数が増えると爆発的に計算時間が増えています。改良すればまだまだ早くなるとは思いますが。

ちなみに厳密解法としては切除平面法が最速のようです。

TSP ver.1.00

巡回セールスマン問題のデモプログラム、TSP ver.0.09を公開しました。

新たにHeldとKarpによる1-treeからの厳密解法を実装しました。でもラグランジュ乗数をもっとちゃんと決めるか、分枝限定法を実装しないと使いものにならないよう。10000回頑張っても結局解けないことが多いです。

TSP ver.0.09

巡回セールスマン問題のデモプログラム、TSP ver.0.08を公開しました。

新たに最小スパニング木、1-treeを実装しています。

TSP ver.0.08

ぜんさんから教えていただいた方法を取り入れて再度経路探索を行ってみました。予想通り、京都駅、三十三間堂間を徒歩で移動するようになりました。（JR奈良線は30分間隔のため、乗車に20分程度の時間を見積もっています）他には特に経路に変更はありませんでした。

Continue reading