EvbCFfp1XB

イーブイ進化系 C7BMkOO7Qbmcwck7(AtCoder) dtwYhl0YJqzOnZKi(CodinGame) AnlJ8vIySM8j8Nfq(Codeforces) j8LsXlKzJPRosaXt(Kaggle)

February 2020




Approach 焼きなまし法を使いました。与えられた最短経路について、焼きなましたグラフのPrecisionが0.8以下の時は、最短経路が1の辺だけのグラフを返しました。

  • 評価 : 与えられた最短経路と構成したグラフの最短経路のSSE(sum of squared errors of prediction)  + 使った辺の数
  • 近傍1 : ランダムに1つの辺を追加、削除する
  • 近傍2 : ランダムに2つの辺を追加、削除する
    • 選ぶ辺は、最短経路が1またはInfの頂点のペアを除いた辺から選ぶ。



感想 スコアがF1で機械学習だったので、機械学習かなーと思いながら焼きなました。
SSEが0付近まで減らなかったケースも多かったので、辺の追加削除じゃなくて経路の追加削除しないといけなかったんだと思う。





Approach 焼きなまし法とビームサーチを両方試している間に終わってた。


  • 焼きなまし法
    • 近傍1:同じ方向に平行しているところを90度方向を変える
      RRRR
      RRRR
      ->
      RDDL
      LLRR
    • 近傍2:2か所回り道する、しない
      RRRR
      DRD
      RURR
      ->
      RDRR
      DRU
      RRRR
    • この近傍だと、スコアが大きく変わってしまって、うまく焼きなませてなかった
  • ビームサーチ
    • 頭を角において、とぐろを巻く(頭としっぽの位置が逆だけど)感じ。



↑このページのトップヘ