はじめに
ご無沙汰しています。G's ACADEMY LAB12期のkatonyonkoです。12月に技術系スタートアップ（ヒューリスティック最適化を専門に行う会社）に転職し、何かアウトプットしなければと思い、G'sのアドベントカレンダー11日目に手を挙げました。
会社のコア技術であるヒューリスティック最適化の技術を学ぶべく、AtCoder社が月１回程度開催しているAtCoder Heuristic Contest 040に参加しました。
今回の記事はその解法について考察した内容を紹介…と思っていたのですが、正直参加した結果、ほとんど何も有効なアイデアを思いつかず、簡単なヒューリスティック最適化技術の紹介とAtCoder Heuristic Contestの紹介、そして今回考えた解法について（ちょっとだけ）書いてお茶を濁すような感じにしようと思います（次辺りはちゃんと技術っぽいことを書けるようにしたい）。
ヒューリスティック最適化技術について
解の自由度が高く完全最適解を見つけるのが難しい問題（主に現実的には完全最適を求めるのが不可能と言えるような問題）に対するアプローチとして、効率的な探索を行うことで使用するのに十分な精度の解を得る方法、と理解しています。
きちんと理解する場合はこちらの記事がとてもわかりやすいですが、有名なのはこの中でも紹介されている巡回セールスマン問題のようなものです。
巡回セールスマン問題とは以下のような問題を言います。
問題文
$N$個の都市があり、$0,1,…,N−1$ と番号付けられている。全ての異なる 2 都市の間には道が存在し、都市$i$から都市$j$に移動するときのコストは$A_{i,j}$である。
あなたは今都市0にいる。ここから都市0以外の都市をちょうど1回ずつ訪れ、都市0に戻ってくる経路を作りたい。そのような経路における合計コストの最小値を求めよ。
制約
- $2≤N≤13$
- $i≠j$ のとき、$1≤A_{i,j}≤10^9$
- $A_{i,i}=0$
- 入力はすべて整数である。
典型アルゴリズム問題集C-巡回セールスマン問題
いきなり考えたらかなり難しいですし、手作業で13個の都市を回る最適な順番を求めるのは不可能と言ってよいです。
また、コンピュータの力を借りた場合でもこの問題を解くのは簡単ではなく、13個の都市を回る順番というのは全部調べると$13!=6,227,020,800$通り存在するみたいです。
コンピュータの実行速度は人間の計算スピードをはるかに凌駕しますが、それでもこの量の計算を行うのにはそれなりに時間がかかります。
実はこの問題自体にはもう少しだけ計算量を押さえた解き方が知られており、$N=13$程度であれば十分高速に解くことが可能です。
競技プログラミングに一定程度真面目に取り組んでいる層にはこの方法は典型手法の１つに過ぎないのですが、それでも$N$がさらに大きい場合、本当に最適な解を得るのはやはり不可能なレベルに計算量が爆発します。
しかし改めて考えると、現実の問題を解く場合、先ほど挙げた$6,227,020,800$通りの中で本当に一番良い解が必要であるケースというのは稀です。
せいぜい上位10%くらいの効率の解であっても、人間が考える解よりは十分効率的であり、かつそれを自動で時間をかけずに得られるとなればそれで十分嬉しいというケースも往々にしてあると考えられます。
そのような効率的な計画を自動で作成する、というのがヒューリスティック最適化によるソリューション提供です。
AtCoder Heuristic Contestについて
競技プログラミング運営サイトのAtCoderが月に１回程度開催しているヒューリスティック最適化の技術を競うコンテストです。
ヒューリスティック最適化は良さそうな解を効率的に探す手法である性質上、同じ問題に対して様々な解法が存在しうるものであり、アプローチ方法によってより良い解に到達できる良い解法もあれば、効率の悪い探索になってしまってあまり良い解を見つけられない筋の悪い解法もあります。
性質上、これをやればどんな問題に対しても必ずうまくいく、という手法はないのですが、強い人が考えると難しい問題に対しても良いアプローチが見つかることが多いです。
私もここのスキルを磨いていきたいと思って今回の40回目のコンテストに参加したのですが、正直ほとんど何も思いつかず、全然でした。
今回の問題について
説明するのは大変、かつ問題文が公開されているので、リンクのみ貼ります。大分雑に説明すると、たくさん与えられる長方形をなるべく周長の短い長方形の中に詰め込むような問題です。
2024/11/29(金)19:00-2024/12/9(月)19:00の240時間のコンテストでした。参加者約1,000人中暫定483位なので、順位的には真ん中くらい、真面目に取り組んでいた人の中では平均よりも下になっていそうです。
240時間あっても真面目に考えていた時間はそこまで長くないので、もうちょっと頑張る余地はありそうでしたが、終了後に良いやり方として共有されていたものはほとんど何も思いついていなかったので、今回はあたり解法が全然見えていなかった感覚があります。
考えたこと
ちょっと乱雑なメモをそのまま転載するような感じで恐縮ですが、10日間のコンテストでどんなことをやったか・考えたかです。
11/29
- $n<N$とする戦略を考えるのは難しそう。いったん全部置く前提で考えることにする。
- 入力（$N$と$T$）の大きさに合わせて戦略を変えるという方向性はありそう（$N$に対して$T$が大きいときは前半で推定を多めに行って、最後に良い解を出す一方で、$T$が小さめな時は適当でもそれっぽい解をいくつか出すのが良さそう等）。
- 昇順で出力しないといけないという制約は結構厳しい。
- いったん単純化して長方形の大きさが誤差なしにわかっているときに良いと思われる配置を考えてみる。
- まずは貪欲で一番スコア（縦と横の和）を増やさない選択を繰り返す
- 上記を発展させてビームサーチと焼きなましを試してみる
- フィードバックの活かし方も難しそう。
- 単純に１個だけ配置してみて、フィードバックを見て誤差を絞り込むというのはあるけど、感覚的にあまり得られる情報量が多くなさそう
- 時間があれば、過去のコンテストで誤差のある状況を上位解法がどう扱っているかを確認したい
https://atcoder.jp/contests/ahc022/tasks
＜今後試したいこと＞
- ビジュアライザーをいじってどんな解が良さそうか考察
- いったん計算量が重そうな実装をそのまま実装するが、軽くする方法はあとで考えたい
- 評価関数は最初の大きさを信じての単純な縦と横の和だとうまくなさそうなので、なるべく中身が詰まっている状態（隙間ができていない状態）を高く評価するようなものを考えたい
11/30
- 11/29に考えた１回の貪欲の実装ははとりあえずできた（なかなか実装に自信が持てなかったが、同じスコアで何人か固まっていたので大丈夫そうなことを確信）
- Judgeプログラムはちゃんと書いて、考えたアイデアでうまく改善しているか検証できる状態にしたい（この時点ではできていない）
- 貪欲自体はできたので、今後ビームサーチと焼きなましを試したい
12/1
- 単純な縦幅＋横幅だけで評価せず、新しく敷き詰める箱がなるべく左上になるように変更
- 誤差があるので、引っかからないように現在の状態は多少余裕をもって評価（$1\sigma$分）するように変更
- かなり予定が詰まっていて上記以外のことを試す時間はまったくなかったが、一応多少スコアは向上した。
12/2
- 何もできなかった（ちょうど転職初日）
12/3
- 作りたかったジャッジプログラムは完成
- 毎回h,wの値をランダムに少しブラして$T$回貪欲した解を提出したが、これは$T$が大きいケースでTLEになった。
- すごい解法をださないといけないみたいなプレッシャーを勝手に感じていたが、いったん実装が間に合いそうで多分よくなりそうな解法を色々考えて試すという方針に切り替えた。
12/4
- 実装予定の解法の考察のみ（実装はできていない）
- 最初の貪欲から適当に変えて山登りしてみる
- 最初を貪欲じゃなくてビームサーチにする
- ビームサーチの時に毎回全部探索すると計算量が爆発しそうなので、次の候補は適当に間引いて試すのが良いか
- ビームサーチの解から始めて山登りしてみるのも試したい
・過去の解のフィードバックも試したい。最初の方は推定に使って、最後にそれを反映してビームサーチみたいな解法ができたら筋は良さそう。
12/5-7
- 何もできていない
12/8
- 最初の貪欲から適当に変えて山登りはやってみたけど、適当に変えても全然改善しない
- ナイーブな実装でビームサーチを試したが、出力したところ全然解の多様性が確保できておらず、スコアも改善していない。ビームサーチの実装上の工夫が全然できていなさそう。
- とりあえず確実に改善するであろうこととして、これまで$T$回分まったく同じ解を出力していたのを毎回ランダムに少し出力を変えた解を出力するように変更（当然多少はスコアが上がったが、微差）
12/9
- 何もできていない
提出したコード
コード貼っても良いけど、読んでほしいほどの内容でもないので、リンクのみ
反省
そもそもコンテストに取り組む時間があまり確保できていなかったし、取り組み内容を記事化する時間も全然確保できていなかった…
考察パートだと以下のあたりが反省
- まず全体が正方形に近い方が良いというのが、言われれば当たり前だしビジュアライザの観察でもなんとなく気づいていたはずだったが、きちんと言語化できていなかった
→これ気づいていればその方向の貪欲には辿り着いていた気がする。 - 上位解法でも上方向（または左方向）の詰め方のみを考えるという方法があったが、誤差にロバストな方法としてこれを全く思いついていなかった（引っかかってうまくいかないケースが多いのは気づいていたのに）。解の自由度が高い場合でも難しい設定は思い切って切り捨てて単純な問題として考えるというのは汎用的に使えそうな考え方だと思った。
- 縦横に細長く並べたものに対してフィードバックをもらうと情報量が多いというところまでは気づいていたが、何も活かせなかった。
- 行き詰ったところでChatGPTにアイデアをもらう相談をするというのはありだと思った。単純に１人で良くわからない問題を考え続けるのは辛い。
いったん今回は参加の記録を残す程度のもの（自分が次回参加するときに参照するメモ程度のもの）ということでm(__)m
次こそちゃんと上位に入れるような解法を目指します。