都市数が20以下ぐらいであれば、動的計画法を使ってTSPの厳密解を求めることが可能。その概要は以下の通り。state を「到達した都市の状態を表すビット列」、cost[state][i] を「都市 i を訪れて状態 state になったときの最小コスト」とすると、 cost を十…

SuperCon 2007 予選問題（PDF） 「Algorithms with Python / 欲張り法, 動的計画法」を参考にしつつ、動的計画法で普通に実装してみた。「普通に」実装するまでにどんだけ時間かかってるんだ、っていう。確認した限りでは正しい答えを導いてくれるはず。計算…