8/13はPaizaの日、ということで、巡回セールスマン問題を出題していました。
Paizaラーニングでも巡回セールスマン問題のさわり(貪欲法)を取り上げていて、
2-OptやSimulatedAnnealing(焼きなまし法)を学んで、
いざ書いてみたんですが、なかなかうまく行きません。
テストデータは有名ドコロがあります。
まずはatt48で2-Optでやってみたものの、
交差線が多く、全然それっぽい経路が得られません。
なんでーーー!?
Javaによるまんまのコードがあったので、
読み解いていったんですけど時間かかっちゃって、
結局Paizaの締切9/12に間に合いませんでした…
何たること。
どうも、キモはswapにあるようで、
点を交換すると総延長が短くなる場合、
当然点を交換するんですが、
当該点だけを交換するだけじゃなく、
そこから真ん中へ向かってずっと点を交換していくんですね。
そうかー。
悔しいから、久し振りにPaizaのS問題やってみました。
最も簡単そうな最小辞書順列にしてみました。
けれど、問題の意味を理解するのと、JavaのStreamで書ききったために、
制限の2時間、あっという間に過ぎてしまいました。0点確定です。トホホ。
しかも、提出したコードは、2つの場合だけ通らずに、80点。
どうしてコケる時があるのか、思い当たるフシもなく、未だにわかっていません。
テストデータ、見せて欲しいです。