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

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



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