Algorithm

バイトニック経路版の平面巡回セールスマン問題

巡回セールスマン問題(TSP)は有名なNP完全問題だが、ユークリッド平面におけるTSPは経路がbitonic tourであるという制約をつければ動的計画法で簡単に解けるようになる。以下そのメモ。 巡回セールスマン問題 - Wikipedia bitonic tourとは bitonic tourとは…