2020年6月28日日曜日

Introduction to Heuristics Contest

3問もあるのかと思って大急ぎで雑な焼きなましを書いたりしていた……

  • とりあえず1点更新だけの単純な焼きなましを書いた。(81730043)
  • 温度が適当すぎたので調整する。(99859730)
  • 遷移時のスコア再計算を素朴にやっていたのを速くする。(102493050)
  • 定数倍高速化する。 (104637270)
  • 初期解を貪欲で作る。(112775607)
  • 初期解を2日先読みの貪欲で作る。 (115690469)
  • 初期解を3日先読みの貪欲で作る。(116929121)

単純な先読みは3日が限界なので、次はビームサーチをするべきだろうなと思った。この辺でコンテストが終わった。

  • (焼きなましの)ほかの遷移を考える
  • 遷移の平均計算量は双方向リストっぽい持ち方でもう少し頑張れそう?

Bがチュートリアルとわかった時点で完全に無視していたのだけど、あとでCを見たら、一点更新の焼きなまし自体があまりよくないと書いてあった。そう言われるととそうだなという気持ちにはなるけれど、コンテスト中に見ても手が止まってしまっただけな気がする。