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

AtCoder Heuristic Contest 011 お疲れ様でした。パズル系のAHCも楽しいなと感じました。

暫定テストは39,923,027点で28位でした。システムテストで順位が上がって欲しいところです。

問題概要

スライディングブロックパズルを解く問題です。

$N\times N$ の盤面上に $N^{2}-1$ 個のタイルが敷き詰められていて、各タイルは上下左右の少なくとも1方向に線が伸びています。空きマスへのスライドを最大 $K$ 回繰り返して全域木を構築してください。

全域木を構築できなかった場合は最大の木の大きさが評価され、全域木を構築できた場合はスライド回数の少なさが評価されます。

詳しくは公式の問題文を参照してください。 atcoder.jp

制約

$6 \leq N \leq 10$

$K = 2 \times N^{3}$

方針

次の流れで全域木を構築しました。

辺の追加と閉路の削除を繰り返し、構築可能な全域木を見つける。
初期状態と全域木の間で、タイルのマッチングを求める。
1.と2.を0.7秒ほど繰り返す。
chokudai search (ビームサーチの亜種) で適切にスライドする。

全域木の見つけ方

まず、入力生成方法と同様の方法で木を生成します。

具体的には、全ての辺をシャッフルして、閉路ができないように1本ずつ辺を追加して全域木を生成します。

ここで生成した木はタイルの種類ごとの枚数が合いません。

そこで次の操作を繰り返しました。

辺を1本だけ追加する。新たに閉路が1つできる。
閉路をDFSで検出して、閉路を構成する辺のうち1本を削除する。連結性が保たれており、全域木に戻る。

例えば次の木を最初に得たとします。

青い辺を追加したとします。

下図の黄緑の辺の中から1本選んで削除します。

このような辺の追加と削除を繰り返しました。

ところが上記の操作をランダムに行っても、枚数が完全に一致することはめったにありません。

そこで、タイルの種類ごとに目標枚数と現在の枚数との差分をとって、その値を2乗したものをコストに設定し、コストが小さくなるように辺の追加や削除を行うようにしました。

このようにコストを適切に設定することで、高速に構築可能な木を見つけることができます。 (遅くても0.1秒以内に1個は見つかると思います。)

マッチングの求め方

全域木を見つけても、同じ種類のタイルが複数存在するため、どのタイルをどこに移動させるかは自明ではありません。

後でビームサーチを行うにあたり、タイルの対応を先に決めておくと実装しやすそうです。 (マッチングが動的で、かつ、高速に動作するビームサーチは思いつきませんでした。)

種類ごとの完全二部マッチングとなるので、最小費用流でマッチングを求めました。コストには、マンハッタン距離の2乗を採用しました。

最小費用の完全マッチングが求まったところで、1つ問題が発生します。それは、そのマッチングが実現可能かどうかです。例えば15パズルの14と15を入れ替えたものは解くことができません。スライディングパズルを解くことができるかどうかは有名問題であり、検索したら多くのサイトが見つかりました。例えば次のサイトです。

manabitimes.jp

判定方法はいくつかありますが、私は置換のパリティの偶奇で判定しました。奇数の場合は実現不可能なので、適当に1組を選んで入れ替えました。

ルールベース解法

ビームサーチを紹介する前に、もっと単純で確実に揃える方法を紹介します。

スライディングパズルを手動で解く場合、多くの人は1枚ずつ端のタイルから揃えていくのではないでしょうか。それをプログラムに落とし込むだけです。

角を1枚ずつ揃えるのは非効率で、2マスを一気に揃えるようにしました。その2マスがswapした状態だと面倒で、2マスを入れ替えるように例外処理を書きました。

このような1枚ずつ愚直に揃えるアルゴリズムでも、少なくとも $3.5 \times 10^{7}$ 点ぐらいまで到達できたと思います。

chokudai search

単純な揃え方では、移動中のタイル1枚にしか着目しておらず、効率がいいとは言えません。

そこで探索を行うことを考えます。探索空間について考えると、前と逆方向に移動しても無意味だから、ターン毎に3つほどの選択肢があるため、解答の長さを $l$ として $3^{l}$ ほどになります。 $n$ が小さければA*サーチでうまく枝刈りができるかもしれませんが、今回は計算量的に難しそうです。

そこで chokudai search を使用しました。素朴なビームサーチではなく chokudai search を使用した理由は、時間管理がしやすいからです。

状態のコストには、各タイルから最終位置までのマンハッタン距離の総和を採用しました。距離の総和が0になったとき、全域木が得られたことになります。

ただし、chokudai search をうまく動作させるために、評価関数に3つほど工夫を加えました。

空きマスが自由に移動できるように、空きマス自体にはコストを定めない。
隣り合う2マスがswapした状態から2マス両方を揃えるのは大変なので、その状態にペナルティを課す。
隣り合う2マスがswapした状態になりにくいように、まだ揃っていないマスで、上下または左右のマスが揃っているようなものにペナルティを課す。

2つ目と3つ目は、距離の総和は小さいが、手動で揃えるときに嬉しくないものを低く評価しようと思って追加しました。

chokudai search のデメリットとして、メモリ使用量が大きくなりやすいことが挙げられます。そこで、1つのターンにつき保持する状態の個数に上限を設けて、メモリ使用量が大きくなりすぎることを防止しました。具体的には、SegmentTreeを用いて最もコストが大きいものを書き換え、最もコストが小さいものを採用しました。

問題点

$N$ が大きいときにビームサーチも chokudai search もうまく動作しませんでした。

理由の1つとして、およそ $N^{5}$ に反比例してビーム幅が減ることが挙げられます。状態のコピーがボトルネックになっていそうで、グリッド面積、すなわち $N^{2}$ に計算量が比例します。また、スライド回数は大体 $N^{3}$ に比例します。よって、1本のビームを走らせるのに $N^{5}$ に比例した計算量が必要となります。