AHC027 参加記 - eijirouの競プロ参加記

HACK TO THE FUTURE 2024 （AtCoder Heuristic Contest 027）お疲れ様でした。

システムテストの得点率が 98.44 % で準優勝しました！

前提知識

木上のビームサーチ
バックトラック法
low-link

問題概要

$N \times N$ マスの二次元グリッドがあり、各マス $(i, j)$ の汚れは毎ターン $d_{i, j}$ だけ増加します。ロボット掃除機が訪れたマスは汚れが 0 になります。ロボットの掃除ルートで、平均汚れができるだけ小さいものを求めてください。

詳細は公式の問題文を参考にしてください。

atcoder.jp

制約

$20 \leq N \leq 40$

方針

ビームサーチで初期解を生成し、焼きなまし法を適用しました。

私が調べた限りでは、bowwowforeach さんや siman さんと大まかな方針は一緒で、他の上位の人は方針が違いそうでした。

ビームサーチ

深さ

深さ¹を $t_{max} := 2.7 \times N^{2}$ に設定しました。

ただし、深さが偶数になるように必要に応じてインクリメントしました。深さを偶数にすることで始点と終点が同じものを得ることができます。

多様性の確保

(現在のマス, 直前にいたマス) をハッシュ値の代わりに使用しました。ビーム幅は $2 N^{2}$ 弱ということになります。

次のノードを選ぶときにソートする必要がなくなるため、ビームサーチが高速になります。

評価関数

4つの項目を評価しました。

影響が大きそうなものから順に説明します。

評価項目1: 汚れの累積和

後述する汚れの総和を毎ターン加算したものです。

評価項目2: 汚れの総和

現在の各マスの汚れの総和です。初期状態における汚れは $4000 \times d_{i, j}$ で初期化しました。

汚れの総和は、直前の汚れの総和と、そのターンに回収した汚れの量から計算することができます。回収した汚れの量を求めるには、各マスについて最後に訪れたターンをメモしておけばよいです。

$d$ の代わりに $\max(d, 5)^{0.85}$ を使うとスコアがよくなりました。 $d$ をそのまま使うと $d$ が大きいマスばかり訪問するのに対し、修正したものを使うと比較的バランスよく訪問していました。

評価項目3: 移動平均

指数移動平均を計算し、絶対値が大きいほどよい評価をしました。

ここでいう指数移動平均とは、 $t$ ターン目の座標の変化量を $Y_{t}$ として

$\sum_{t=0}^{T}{\alpha (1 - \alpha)^{T - t} Y_t}$

を表すものとします。平滑化係数は $\alpha = 0.05$ としました。

更新は

$X_{t} = \alpha Y_{t} + (1 - \alpha) X_{t - 1}$

のように行います。

$d$ が大きい狭い領域に居続けるのがよくないので、移動平均の絶対値が大きいものを優先するとよいと考えられます。

例えば Seed = 25 は、 $d$ が大きい領域が非常に限られており、評価関数によっては中心やや下の領域から出なくなります。

評価項目4: 周期解としての生スコア

汚れの累積和では、掃除ルートが繰り返されることが考慮されていません。そこで、 $t_{max}$ ターン目まで何もしなかった場合の生スコアを評価しました。

各マスを訪問するたびに、訪問時刻を挿入するような感じで差分計算を行うことができます。

未訪問のマスは $2 t_{max}$ ターンの周期で訪問されるものとして計算しました。

差分更新

木上のビームサーチでは、評価の更新に必要な情報を深さ優先探索に沿って更新します。私の実装だと、評価値はノードに保存されるので深さ優先探索では更新する必要がありません。

評価の更新に必要な情報で動的なものは、現在のターンと各マスを最後に訪れた時刻の2つです。これらは $O(1)$ で更新できます。

簡易的な C++ のコードを載せておきます。座標が一次元に平坦化されていることに注意してください。

struct State {
    // 経過したターン数
    int turn;

    // timestamps[i] = マスiを訪問した時刻の配列
    vector<vector<int>> timestamps;

    // 深さ優先探索における子孫への移動
    void move_forward(int position) {
        timestamps[position].push_back(++turn)
    }

    // 深さ優先探索における親への移動
    void move_backward(int position) {
        assert(timestamps[position].back() == turn)
        timestamps[position].pop_back();
        --turn;
    }
}

前回訪問した時刻をノードに保存することで、一次元配列のみで実装することも可能です。²

未訪問頂点の対応

未訪問頂点が減るように評価関数を工夫しているつもりですが、それでも未訪問の頂点が残る場合があります。

なるべく低コストで未訪問頂点を挿入したいので、2マス拡張（後述）を基本として、2マス拡張ができないときは1マス拡張（後述）を行いました。

元々

だった経路を

のように拡張するのが1マス拡張で

のように拡張するのが2マス拡張です。

ビームサーチの結果

コンテスト後にビームサーチのみのコードを提出したところ、44Gほどのスコアが出ていました。

焼きなまし法

3種類の近傍で焼きなまします。

近傍1: L字型の変更

a, b, c を a, d, c のように変更します。L字型の部分を反対側に曲げる感じです。

経路長が変わらないので高速に計算できます。

近傍2: 十字型の解消

掃除ルートが同じマスでクロスしていた場合に、区間の訪問順序を反転させてクロスを解消します。2-optをイメージするとよいかもしれません。

クロスを解消した後にL字型の変更が行われると1マス分得をすることができます。

例えば

の区間を反転させて、クロスしていたところにL字型の変更を施すと

になります。

反転区間の長さが約150以上の場合にはクロスの解消を行いませんでした。区間が長すぎると訪問時間の変更によるデメリットのほうが大きくなります。

近傍3: バックトラック法による破壊再構築

掃除ルートの連続する 4 ~ 8 マスを破壊し、バックトラック法で生成した経路で置き換えます。

バックトラック法の工夫1: 同じマスを通らない

よくあるバックトラック法と同様に、同じマスを複数回通らないようにしました。

ただし、関節点については2回まで同じマスを通ってもよいものとしました。関節点も1回しか通れないようにした場合、関節点の削除はできても挿入はできないので、操作が不可逆的になります。

関節点については、low-link で事前に列挙しました。

バックトラック法の工夫2: 経路長の制限

経路長を無制限にすると探索空間が膨大すぎて計算が終わりません。そこで、経路長は「元の経路長 + 2」までとしました。

バックトラック法の工夫3: 経路長による枝刈り

経路長の最大値を設定したため、経路長による枝刈りができます。

具体的には、現在のパスの長さと現在位置から終点までの距離を足したものが、経路長の最大値よりも大きいならば枝刈りできます。

全頂点から幅優先探索をするのは計算量的に少し重そうだったので、距離はマンハッタン距離で代用しました。

バックトラック法の工夫4: よさそうな頂点から探索する

次の頂点を選ぶときに、訪問したときに得られるスコアの改善量が大きい頂点を優先しました。

具体的にはスコアの改善量を $\delta$ として、 $\delta \times \rm{randint}(10, 50)$ が大きいものから順に探索しました。

工夫できなかったこと

経路長が変わる場合、変更部分以降の時刻が全てずれ、更新の計算量が大きくなりました。

ただ更新するだけだともったいなかったので、経路全体を逆順にしたり、掃除ルートのスタート地点を変更したりしました。ときどきこの処理が行われることを前提とし、各近傍では掃除ルートの終わりと始まりをまたぐような遷移は考えませんでした。

各近傍の選択比率

近傍1, 2, 3 の選択比率は 6 : 3 : 1 としました。選択比率と実行時間は異なることに注意してください。

途中で掃除ルートを2倍にする

焼きなましの実行時間の8割が経過したときに、同じ掃除ルートを2回繰り返したものに変更しました。

掃除ルートが長くなって焼きなましにくくなるデメリットがある一方で、全頂点を2回訪れていると制約が緩くなって焼きなましやすくなったり、汚れやすさが極端に低い頂点の掃除頻度を半減できたりするメリットがありそうです。

試行回数

Seed = 0 ( $N = 20$ ) で約 2,500,000 回のループを回せていました。

日記

暇な人向けです。

12/1

問題を読む。
適当に初期解を作り、破壊再構築の焼きなましをしたい。
- 経路長が変わると差分計算が面倒。
遺伝的アルゴリズムとか使えないかな。無理か。
移動が自由なら Introduction to Heuristic Contest に似ているな。新ジャッジコンで使った貪欲とか活かせるといいな。
掃除ルートの周期性を考えなくても、経路が十分長ければ接続部分は無視できそう。

12/2

BFSに沿ったDPをベースとした貪欲とかがいいのかな。
掃除できた汚れの量を評価関数にしてビームサーチを打つほうがいいか。
- 今のマスをハッシュ値として多様性を確保できる。
  - Sliding Tree Puzzle と一緒だ。
- 差分更新ビームサーチライブラリの出番が来た！
ビームサーチを実装する。
初提出で38G。悪くない。
最初と最後の接続部分を何とかしたい

12/3

汚れの累積値という生スコアを評価していないことに気づいて評価する。
その他にも最適化をして41G。
局所探索で改善できそうなことを確認する。

12/4

未訪問箇所の挿入を改善する。
44G。

12/5

平日で唯一の休み。
焼きなましの遷移をいくつか考える。
L字型変更と十字型解消を実装して45G。
バックトラック法といくつか最適化をして49Gで暫定2位。よし！

12/6, 12/7

ビームサーチで子孫の数を制限して悪化したのでやめる。
過去改変機能をビームサーチに組み込んでも悪化するのでやめる。
- 過去改変した情報を保持しておけば木上のビームサーチでも過去改変できる。
- アイディアとしては面白いと思うが、うまくいかないので諦める。

12/8

プレテストのの分布を雑に確認したところ、が小さいものが多く、しかもが小さいものが得意なことに気づく。
- システムテストで下がるパターンだ。
移動平均をビームサーチの評価関数に組み込んでスコアが上がる。

12/9

朝から微熱が出ていて嫌な気分。
バックトラック法で関節点を2回通れるようにしたらスコアが上がった。
午後に40度の熱が出て寝込む。発熱してもコンテストに参加するつもりだったが、40度までいくと自分には無理だった。
- 調子いいときに発熱するのはやめてほしい。
- まだパラメータ調整してないので明日はコンテストに取り組みたい。