8/13はPaizaの日、ということで、巡回セールスマン問題を出題していました。 Paizaラーニングでも巡回セールスマン問題のさわり(貪欲法)を取り上げていて、 2-OptやSimulatedAnnealing(焼きなまし法)を学んで、 いざ書いてみたんですが、なかなかうまく行きません。 テストデータは有名ドコロがあります。 まずはatt48で2-Optでやってみたものの、 交差線が多く、全然それっぽい経路が得られません。 なんでーーー!? Javaによるまんまのコードがあったので、 読み解いていったんですけど時間かかっちゃって、 結局Paizaの締切9/12に間に合いませんでした... 何たること。

どうも、キモはswapにあるようで、 点を交換すると総延長が短くなる場合、 当然点を交換するんですが、 当該点だけを交換するだけじゃなく、 そこから真ん中へ向かってずっと点を交換していくんですね。 そうかー。

悔しいから、久し振りにPaizaのS問題やってみました。 最も簡単そうな最小辞書順列にしてみました。 けれど、問題の意味を理解するのと、JavaのStreamで書ききったために、 制限の2時間、あっという間に過ぎてしまいました。0点確定です。トホホ。 しかも、提出したコードは、2つの場合だけ通らずに、80点。 どうしてコケる時があるのか、思い当たるフシもなく、未だにわかっていません。 テストデータ、見せて欲しいです。