解説
解法概要
コンテナを仮置きする場所の集合と、搬入する順番を焼きました(7000iter程度)
上記を元に、最大100ターンシミュレーションを行いスコアを出します
仮置き場所の集合候補
以下のような、6パターン用意しました
搬入が終わった行のも随時仮置き場所になるようにしました
シミュレーションパート
以下の処理を最大で100ターン繰り返して、全て搬出したらそのターン数をスコアとしています
これまでの最短ターン数でシミュレーションを打ち切ることで高速化を図っています
前処理
搬入順の初期解を10000ループ焼きなましで求めます
順に搬入した際に仮置きされるコンテナ番号nの、6-n%5の合計値を最小化します
後に搬出する番号ほど、置いて良いことにすると何故か後の探索が上手くいきやすかったです
搬入処理
の位置にコンテナが無ければ補充します
5*5の2次元配列で、コンテナの有無を管理しています
タスク作成
クレーンに与えるためのタスクを作成します
タスクは、コンテナ番号・優先度・開始位置・終了位置を情報として持たせました
搬入口→仮置き位置、搬入口→搬出口、仮置き位置→搬出口の3種のタスクを作成して、各クレーンとマッチングさせます
搬入する順序に関わらず、搬出できるコンテナは搬出タスクに含まれるようにしています
また、運んでいる番号の次の番号が仮置き中の場合、運んでいる番号より搬出口への距離が遠くなったら搬出タスクに入れるようにしています
タスク割り当て
以下の図のような、最小費用流問題(最小フロー)を解いて、フローが流れた辺をそのまま採用してマッチングしました
たまに空きクレーン数よりタスクの数の方が多くなりますが、タスク→終端のコストをタスクの優先度としているため、自動的に優先度の高い(コストの低い)タスクから取り組まれるようになっています
仮置き位置の最適化でも同様の考え方を使いました
(仮置き位置とコンテナ番号による評価値の差をコストとする)
クレーン移動経路探索
クレーンの持つタスクの優先度順にソートして、その順に各クレーンの停止含む移動5方向を評価値順にdfsして最初に見つかった経路を採用しました
毎ターン、1手先だけ探索するため数ターン単位で見ると無駄な動きも全然あります
移動が干渉しない条件は以下のように書きました（伝われ
搬出判定
次の搬出番号のコンテナが該当する箇所にいる場合、搬出された。としています
その場所に留まって、コンテナを掴む・離す行動が出来る場合、優先度を最高にしているためこのような処理でも問題ありません
提出コード
Nimで書いています
参加記
はじめに
楽しみにしていた久々の長期コンです
また、最初からNimで書き始めるのも初めての試みになります
今回こそ100位以内に入れるように頑張ります！
1.問題
の場所に、
個のコンテナが運び込まれる
台のクレーンを操作して、指定の順に搬出したい
大クレーン1台と小クレーン4台があり、コンテナの上空を通ってコンテナを運ぶことが出来るのは大クレーンのみ
コンテナを掴む、離す動作にも1ターンかかる
クレーンを破壊することもできる
2.最初の考察
問題理解が難しい...
搬出順番は各行ごとに独立していると考えて良さそう
若い番号が最後の方に搬入される場合、その行はそもそも後回しにしたりする戦略が成り立ちそう
クレーン5台を動かすのは、軽く調べた感じマルチエージェントシステムが当てはまりそう
マスターズ予選や2023年クリスマスのコドゲは2つのエージェントを操作する内容だったが、全然上手く扱えなかったのでまずは5台→2台や1台に絞って考えてみたい
運び出す順を検討するフェーズと、実際にクレーンの操作を最適化するフェーズに分ける方針もありそう
通路を確保しつつ、たくさんのコンテナを並べつつ、順に運んでいく？
3.得点計算について
や
は係数が大きすぎるため、
・搬出しないコンテナは作らない
・間違った搬出口から搬出しない
ことは大前提となりそうです
についても、転倒数を作らないために100ターン掛けて良いことが読み取れるため、搬出順も守ることは前提になりそうです
妥協解法でも得点を許してくれる、運営の心遣いを感じますね
4.大クレーンのみ解法
スコア計算が正しく行えるかも兼ねて、大クレーンのみの解法を作ってみます
小クレーンは最初に爆破してしまえば良いです
効率は悪いですが、順番通り搬出することはできました
seed=0~4まで試して全て問題なく搬出できたので、順番通りに搬出できないケースは恐らくないと思われます
そのため、順番通りに搬出したならばターン数だけを気にすれば良いということになります
5.1日目-貪欲解案
1行ずつ搬出する方針はそのままに、小クレーンも利用して運び出すことを考えます
複数のクレーンをどう操作すればよいかが非常に難しいですが、イメージとしては運びたいものと行先をタスクとして作っておいて、それに各クレーンを割り当てていけば良いような気がします
(コンテナを持って、置くまでが1タスク)
まだ期間もあるので、過去の類似コンテストの解説を読んで実装イメージを固めてから取り組みたいと思います
参考：マルチエージェント経路計画の紹介 | Kei18's Note
記事にあるようなマルチエージェント戦略が実装できた場合、コンテナ自体をエージェントとして見立てて、行ごとに強い制約を持たせると良さそうに思えます
実際にはクレーンで運ぶ必要があるため、エージェントはあくまでクレーンになるかもしれません
あと、コンテナを仮置きする場所についても、最短距離でなく評価値マップに近い所などの工夫が効くかもしれません
(例えば、20~24のコンテナを上に避けて仮置きする必要は薄いため)
日を跨いでしまったので、実装は後にして一旦寝ることにします
6.2日目-焼きなまし案
寝て起きて、頭が整理されたのか新しい案が出てきました
どこに仮置きするか、どれを搬出するか、どのクレーンが担当するかを貪欲に決められるのであれば、コンテナを搬入する順を焼きまなすことができるのではと考えました
搬入する順の総数は、で求められます
計算すると、623,360,743,125,120となってしまいました
別の考え方として、でも求められたため、計算すると上記の数字と一致しましたので合ってそうです
案をまとめてみます
[0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4]の様な順列を生成する
手の空いているクレーンの数をとする
新たにタスクを個生成する(開始できていないタスクも含む)
1, 仮置きされているコンテナの内、搬出できるコンテナがあれば搬出する
2, 次の搬入コンテナが搬出可能であれば搬出する
3, 次の搬入コンテナを適当な位置へ仮置きする
タスクに対してクレーンを割り当てる(一旦、距離が近い順に貪欲に)
大変そうですが、やりたいことは出来そうな気がしてきたので頑張って実装します
-------------------- この間約10時間 --------------------
なんとか夕方ごろに実装が完了して、最初の解法の半分程度のスコアまで出ました！
最適化しきれていない処理も多数あるため、見てても無駄がありますが複数のクレーンを操作出来ています
提出しましたが、AC25 WA25と解をちゃんと出せる場合は少ないようでした
焼きなまし案と言っていますが、順列の探索はスコアが出るまで2点swapしているだけになっています
7.バグ修正
色々バグ修正したら、暫定11位まで伸びてしまいました
メイン関数内ベタ書きでひどい状態なので、どうしようか...
少し変えた点としては、遊びクレーンを各クレーンの初期位置を目指すようにしました
ただ、左側にクレーンが集まるため搬入から出たいクレーンと干渉して無駄な場面もありました
また、完了までのターン数が最小の解を出力するようにしたため(山登り)、多少の高速化はあるにせよ、現状の解法の限界な気がします
8.再検討
上位が目指せそうな予感もするため、後半に備えて全部書き直すことにします
再度、持たせたい機能や方針を書きまとめてみます
・搬入する列の順番を探索する方針(焼きなまし)
→初期解として、順番に処理した場合仮置きが最も少なくなるような順番を探索する
・仮置きは 行の
列の6つを基本とする
→搬入が終わり次第、その搬入口も仮置き可能にする
→搬出位置に近い所へ仮置きする
・クレーンは、①コンテナを持って搬出する、②コンテナを持って仮置きする、③次に持つコンテナへ向かう、④指定の箇所へ向かうだけ、の4種タスクを持たせる
・タスクは、搬出の優先度を高く、仮置きの優先度を低くできるように
→ソートしてからクレーンへ割り当てる
・搬出途中のコンテナ番号+1のコンテナが仮置きにいて、距離関係上順番に運べそうなときは搬出タスクへ入れる
・タスクの無いクレーンかつ、他のクレーンの目標地点になってる場合、避けるような場所へ向かう目標地点を持たせる
・クレーンの動きは、持っているタスク優先度でソートして順に探索
→時刻における障害物の有無を下位から
ビット位置の
2bit(上空、地上の有無を01で表現)で管理
32bitなら、16ターン先まで見れる(5*5のマップなら十分?)
・優先度の高いクレーンから経路を決めてしまう
→目標地点への経路が無い場合でも、近づける方向に1マス動けるなら動く
・ラスト5箱になったら、全てのコンテナ上にクレーン移動させたい
平日の業務後に実装することになるので、下手したら次の週末まで終わらないかもしれませんが、今のまま細かい調整をしていても大して伸びないので、また１から頑張ろうと思います
9.7日目-41G到達
上記の解法に加えて、色々と改善を加えたところ41Gまでスコアが伸びました！
特に効果があったのはクレーンの動きの決め方で、大体以下のようにしました
・他のクレーンを無いものとした場合の目的地までの最短距離を計算する
・その場を含む(置かれているコンテナと干渉しない)5方向に進む場合の評価値は最短距離とする
・クレーンの持つタスクの優先度順に枝刈り全探索で合計評価値の最小化をする
1マス進む場合の全体最適を探索(できている)ため、動いたクレーンに追従したり、優先度の高いクレーンのために他のクレーンがどいたり、といった動きも見ることができます
現状の問題としては、計算が重いため搬出順の探索を400回程しか回せていないこと
また、タスクとクレーンのマッチングを貪欲に行っているため、重み付き最大二部マッチング？などのアルゴリズムを用いて、より最適化の余地があります
あとは、仮置き位置の選択も各コンテナをお気持ち評価値による貪欲で決めているため、先読みして全体最適化したらもっと良くなる気がしています
メインの探索処理を関数ごとに累計時間を取ってみました
クレーンの動きを決める所がかなりネックになっており、改善の余地がありそうです
タスクとクレーンのマッチングに、最小費用流を用いたところ43Gまで一気に伸びました（Nim-ACLに感謝）
手元で数ケース回してもそんなに恩恵を感じなかったのですが、効くケースが多かったようです
辺を張る際のコスト何となくで決めているので、後で考え直してみようと思います
10.44G到達
探索回数が明らかに少ないので、高速化のために時間のかかっている箇所を調べた所、1ターン先のクレーン操作を全探索する箇所が処理のほとんどの時間を占めていることがわかりました
の最小値を見つけるために全探索していましたが、ソートしてdfsして見つけた最初の解を採用することにしても大きく劣化しないだろうと思い、実装したところ4000回程度探索が回るようになりました(約10倍！)
この時点で相対スコア44Gで12位とかなりいい所まで来ています
実行する毎にスコアが±3程度ぶれるためそこは何とかしたい所です
ただ、seed=0ではついに80を切る時も出てきて、見ていても無駄がかなり減ってきたのが分かります
仮置きする箇所の最適化として、仮置きできるスペース分だけ先読みして配置の最適化を行い、仮置きするコンテナ番号の予約をするような実装も試してみました
処理が悪いのか、スコアが悪化してしまったため、元の貪欲に戻すなどしました
11.微改善
仮置きする箇所について、タスクとしてある内でまだクレーンが持っていないコンテナについて、再配置するようにしました
各行左が一番大きい数字になるような評価をして、最小費用流でコスト最小化をしました
焼きなましの結果が毎回ばらつくのが嫌だったため、時間でなくループ回数で温度を決定するようにしました
スコア向上につながるかは不明ですが、コードテストの結果が安定するため改善効果の確認には有効だったように思います
最後の週末は、バグ修正やパラメータ調整で終わりそうです
こういう時間の使い方はよくないと分かっていても終盤はやってしまいますね...
12.おわりに
長期AHCはいつものように大変でしたが、今回もとても楽しめました
最終日までは20位以内に大体入っており、戦えているのでは？という競技としての喜びも感じることが出来ていました
今回の反省として、seed0~4を手動でテストしては提出して。を繰り返していたので、総合的に効く工夫なのか全く判断できていませんでした
大量テストケースを回す環境作りも次に向けて取り組みたいなと思っています
システス終わって、2順位下がりの29位フィニッシュでした！
初めての橙パフォ頂けて嬉しいです
毎回上手く上位になれるとは限りませんが、次も頑張ります
