AHC003に参加した

「AtCoder Heuristic Contest 003」に参加したので、解法を残しておきます。

問題概要

リンク

30×30 の頂点がグリッド上に並んでいる。各頂点は上下左右の頂点に移動することができるが、移動コスト(辺の長さ)は分かっていない。

あなたは 1000 個のクエリを処理する必要がある。クエリは以下のようなものである。

• スタート地点$(s_i,s_j)$とゴール地点$(t_i,t_j)$が与えられるので、スタート地点からゴール地点に到達する、なるべく総コストが低いルートを示せ。

また、クエリに答えるたびに、提示したルートの実際の距離の情報(ただし、0.9~1.1 倍というノイズが含まれる)が得られる。 クエリ$k$における実際の最短路長を$a_k$、解答した経路長を$b_k$とした時、

${\rm round}(2312311 \times \sum_{k=1}^{1000} 0.998^{1000-k} \frac{a_k}{b_k})$

がなるべく大きくなるアルゴリズムを構築せよ。

自分の解法

2,789~点で、184/1000 でした。平均精度約 93%です。

やったことの時系列

単純な貪欲法

まずはスタートからゴールへの移動でマンハッタン距離が最短になる経路を出力するようにしました。 この解法は 63.5%程度の精度でした。

単純な辺コストの予測＋ダイクストラ法

次に、辺のコストを予測するようにし、その予測を元に経路を作ることを考えました。もし予想が完璧に当たっていれば、ダイクストラ法で真の最短経路が得られます。

辺のコストは初期値を 5000 とし、クエリに答えた後$x=$(実際のコスト/使った辺の数)を計算して使われた辺のコスト$e$を$\frac{e+x}{2}$で置き換えました。

辺の予測更新＋ダイクストラ法により、88%程度の精度になりました。

局所探索法の導入

この問題ではクエリ$k$に答えるたびに、経路に含まれる辺のコストを$e_1,\dots,e_{q_k}$、クエリの実際距離を$R_k$として

$e_1+e_2+\dots+e_{q_k} = R_k$

という関係が得られることになります。この情報を貯めておき、適当なタイミングで各辺のコストを解とした局所探索を行うようにしました。

目的関数は辺$e$の予測コストを$E_{e}$、答えたクエリ数を$d$とした時、以下のように設定しました。

${\rm min} \sum_{k=1}^d |E_1+E_2+\dots+E_{q_k}-R_k|$

基本的に前述の単純な辺の置き換えを行い、300 個目のクエリ で一度だけ時間をかけた局所探索、その後毎クエリ終了時に局所探索を行うようにしました。 この方針は 86.5%程度と、単純な予測だけの解法に劣る結果しか出ませんでした。

目的関数の高速化

目的関数の計算量を改善し、答えたクエリ数を$d$として、$O(d)$で計算できるようにしました。 結果 89%程度の精度が出るようになりました。

初期コストを小さくする

最初の辺のコストを 5000 にしていましたが、3000 にして優先的に未踏の辺を通るようにしたところ、91%程度の精度になりました。

時間をかけた局所探索の時に解をリセット

時間をかけた局所探索を行う前に、全ての辺のコストが 5000 という状態にリセットするようにしました。 91.5%程度の精度になりました。

予測と実際距離の乖離が大きい場合に解を壊す

時間をかけた局所探索後も、予測距離/実際距離の乖離が大きい場合に単純な辺の置き換えを行って解を壊すようにしました。 これで 92.5%程度の精度になりました。

局所探索開始の条件を改善

局所探索を行うタイミングをクエリ数決め打ちにしていましたが、「通ることできた辺の総数が一定以上になったら」という条件に変更しました。 若干スコアが伸びました。

目的関数の改善

目的関数内$|E_1+E_2+\dots+E_{q_k}-R_k|$がノイズの範囲に収まっていないほど大きい場合、ペナルティとして 2 倍するようにしました。これで 92.9%程度の精度になりました。

空振りに終わった試行

• 不確実性を考慮できるロバスト最適化の一般的な目的関数(min-max-regret など)を使ってみたが、改善には至らず。
• 目的関数への寄与がクエリ毎に均等になるようにしてみたが、解が悪化した。
• 局所探索法を焼きなまし法に変えてみたが、結局局所最適解にも到達しないケースが多かったので解が悪化した。
• 時間をかけた局所探索を 2 回行ってみたが、2 回目以降かえって精度が悪化した。
• 近傍の工夫はほとんど効果がなかった。

やらなかったこと(できなかったこと)

• 1 回目のクエリで可能な限り多くの頂点を訪れるようにする。するとこのルートの実績が擬似的な全て辺のコストの総和のようになるので、以降のクエリで補集合の情報も含め 2 倍の情報が得られるようになる。最も訪れる頂点数の多い一筆書きの実装が面倒だったので後回しにし続け、結局やらなかった。
• クエリから得られた情報を線形計画問題の制約に見立て LP ソルバーを使おうと考えたが、ソルバーのライブラリを 1 ファイルに展開するのがうまくいかなかった。

反省

他の方の解を見ると、問題例の生成方法に着目し M=1 か M=2 かを予測してモデルを変えるというものが多かったです。 私はここをちゃんと見ていなかったため、各辺のコストが完全にランダムという認識でアルゴリズムを組んでしまっていました。問題文を隅から隅までしっかり理解して読むようにしたいです。

また、統計的・強化学習的な手法によりノイズの影響を抑えつつデータを扱うことができるらしいのですが、そのあたりの知識が全くありませんでした。勉強します。