l8l技術メモ

機械学習・深層学習・組込みとかのメモ

CodinGames The Great Dispatch

Coding Games and Programming Challenges to Code Better

score < 1 が目標だったが score=2 ほどでとりあえず finish。 容量制限付きで、N個の荷物を100個のトラックに分配し、 最も重いトラックと最も軽いトラックの重量差を最小化する。

スポンサーつきのコンテストなのでコードをのせるのはやめておく。

truck から box への refer と、 box から truck への refer を両方つけたデータ構造にすると便利。 焼きなまし法の温度下げないバージョンみたいなのを書いた(焼きつづけ方?) ちゃんとなました方がよいと思う。 焼きなましのあとにビームサーチとかするとスコアが上がるのかな? 50sec もあるのでその場合は時間配分も重要になってきそう。

いまの実装だと時間をかなり無駄にしているはず。戦略を練って上を目指すならビジュアライズなども必要になってくるのかもしれない。 状態遷移としては、 move と swap を実装。この2つがあれば一応全部の状態へと遷移できる。

実装の工夫、 焼きなましの温度や、エネルギー関数(遷移確率関数)の選定(e1>e2のときに遷移確率1にするか否かなどよくわからない)、 数ある遷移方法でなにから探索するか(完全ランダムに遷移を選ぼうとすると種類が多すぎで無駄)、選定の際のアルゴリズム などなど初めて実装したのでいろいろな難しさがあった。

はじめてマラソン系(optimization系)の問題に触れて、焼きなまし法の具体的実装を調べるところから始めて、 初めて(なんちゃって)焼きなまし法を実装した。 正直に言うとかなり時間がかかった。データ構造力やアルゴリズム力がまだまだである。 デバッグ用関数や時間制限の管理などなど基本的なところが初級者レベルにはなれたかなと思う。

自分でやってから読むとためになる記事 焼きなまし法のコツ Ver. 1.2 - じじいのプログラミング