AHC051解法紹介

Transcript

1. AHC051 1位解法 eijirou 1
2. 問題概要 ごみをできるだけ正しく分別するごみ処理場を建設する問題 2 入力 • 処理装置の場所 • 分別器の場所 • 分別器の種類ごとの識別確率 出力 • 処理装置のごみの種類 • 分別器の種類と行き先 • グラフはDAGにする • 辺が交差してはならない
3. ビジュアライザ 3 搬入口 大きい頂点: 処理装置 小さい頂点: 分別器
4. 方針の概要 1. 初期解の構築 • TSPを解いた結果である細長いグラフを用いる 2. 焼きなまし法 • 近傍は「1つの分別器の種類と行き先を変更する」 • 適当なトポロジカル順序で近傍を生成する • スコアの差分計算を高速化するため • 行き先を固定した後、複数の分別器を試す • 分別器だけを変更するときのスコア計算が高速なため • 108 回ほどのスコア計算が行える • 受理率は1%ほど 4
5. 初期解の構築 解のよさそうな構造 • できるだけ多くの分別器を効率的に使いたい • ある分別器の片方の行き先から到達可能な処理装置が 𝑥 のみの とき、もう片方の行き先から到達可能な処理装置として 𝑥 以外 がないと分別の役割を果たせない • 下のグラフでは分別器を2個とも無駄にしている 5 処理装置
6. 初期解の構築 初期解に求めること • 全ての処理装置に対して到達確率が 𝜖 以上あるとよい • 𝜖 = 0.01 ぐらいのイメージ • 分類成功確率が極端に低いごみがあると、後の焼きなましで改善しづ らい • 短い辺が多い • 後の焼きなましでグラフの自由度を上げるため • 「グラフの自由度を上げるため」は嘘かも （問題や方針によるが、）初期解は生スコアよりも構造が大切 6
7. 初期解の構築 • TSPを解く • 分別器の順序を決める • 始点は搬入口 • 終点は処理装置同士の中で最も距離が短いペアの片方 • 最後の分別器の行き先を両方とも処理装置にするイメージ • 2-optで焼きなました後、辺の交差があれば修正する 7
8. 初期解の構築 • 各処理装置を、できるだけ後ろにある分別器と接続する • 搬入口付近だと分別が難しいため 8
9. 初期解の構築 • 各処理装置にごみの種類を割り当てる • 前の処理装置から貪欲に割り当てる • 評価関数 • 分別器の種類の集合を 𝑆、まだ割り当てていないごみの種類の集合を 𝑊 として argmax 𝑠∈𝑆, 𝑖∈𝑊 ෍ 𝑗∈𝑊 (𝑝𝑠,𝑖 − 𝑝𝑠,𝑗 ) 9
10. 初期解の構築 ごみの種類を割り当てる例 • ごみの種類が0, 1, 2, 3の4種類ある場合 • 評価値を最大化する分類器とごみの種類を求める • 1種類と3種類に分類できそうな分類器を探すことになる • ごみ3が選ばれたとする 10
11. 初期解の構築 ごみの種類を割り当てる例 • ごみの種類が0, 1, 2, 3の4種類ある場合 • 評価値を最大化する分類器とごみの種類を求める • 意図: 1種類と3種類に分類できそうな分類器を探す • ごみ3が選ばれたとする 11
12. 初期解の構築 ごみの種類を割り当てる例 • 評価値を最大化する分類器とごみの種類を求める • 意図: ごみ0, 1, 2から1種類と2種類に分別できそうな分類器を探す • ごみ1が選ばれたとする 12
13. 初期解の構築 ごみの種類を割り当てる例 • 評価値を最大化する分類器とごみの種類を求める • 意図: ごみ0, 2を分別できそうな分類器を探す 13
14. 初期解の構築 ごみの種類を割り当てる例 • 処理装置と接続する分別器には、評価値を最大化するときに 使った分別器の種類を割り当てておく 14
15. 方針の概要 (再) 1. 初期解の構築 • TSPを解いた結果である細長いグラフを用いる 2. 焼きなまし法 • 近傍は「1つの分別器の種類と行き先を変更する」 • 適当なトポロジカル順序で近傍を生成する • スコアの差分計算を高速化するため • 行き先を固定した後、複数の分別器を試す • 分別器だけを変更するときのスコア計算が高速なため • 108 回ほどのスコア計算が行える • 受理率は1%ほど 15
16. 補足: 平面グラフ • 辺が交差することなく平面に埋め込むことが可能な無向グラフ を平面グラフと呼ぶ • 平面に埋め込まれたグラフにおいて、辺に囲まれた領域を面と 呼ぶ • 平面埋め込みの表現方法 • 各頂点について、隣接する頂点を反時計回りに並べた配列をもてばよ い • すなわち、隣接リストを偏角ソートする 16
17. 新しい辺の取得 • 辺を追加する面をランダムに選ぶ 右のグラフで頂点0から伸びる辺を追加 する場合を考える • 隣接リストは [1, 7, 5] なので、辺を追 加する場所は以下の3通り • 頂点1と頂点7の間 • 頂点7と頂点5の間 • 頂点5と頂点1の間 • 頂点5と頂点1の間が選択されたとする 17
18. 新しい辺の取得 • 面を取得する • 隣接リストで前の頂点の次の頂点を見 る • 「接続先の頂点の隣接リストの何番目 に自身が存在するか」を保持すれば、 （次数に関係なく）面を構成する頂点 数に比例した時間で面を取得できる 18
19. 新しい辺の取得 • 面を取得する • 頂点0から頂点1の方向へ進む • 頂点1の隣接リストは [0, 2] なので前 の頂点0の次である頂点2へ進む • 同様に繰り返す • 2: [1, 3] で1の次は3 • 3: [7, 2, 4] で2の次は4 • 4: [3, 5] で3の次は5 • 5: [4, 0, 6] で4の次は0 • 0: [1, 7, 5] で5の次は1で戻るため終了 19
20. 新しい辺の取得 • 追加可能な辺を列挙する • 追加したい辺が面の内側かつ、面を構 成する辺と交差しなければ追加可能 • 辺(0, 2)は追加可能 • 辺(0, 3)は追加できない • 頂点3は、頂点0から見て頂点5と頂点1 の間にないため • 辺(0, 4)は追加できない • 辺(0, 4)は辺(1, 2)と交差するため 20
21. 新しい辺の取得 注意点として、グラフが非連結になる と処理が面倒なので、常に頂点の入次 数が1以上になるようにする • 右の例で辺の向きが0->1->2なら辺 (0, 1)は削除できない 21
22. 確率の差分計算 • ごみ 𝑖 が頂点 𝑣 に到達する確率を 𝑓𝑣,𝑖 とする • トポロジカル順序でdpすることで 𝑓 が求まる • ごみ 𝑖 が頂点 𝑣 にいるときに、ごみ 𝑖 を処理する処理装置に到 達する確率を 𝑔𝑣,𝑖 とする • トポロジカル順序の逆順でdpすることで 𝑔 が求まる • 𝑠 種類目の分別器がごみ 𝑖 を出口1に出す確率を 𝑝𝑠,𝑖 とする • 問題文と同様 • 𝑝𝐾,𝑖 = 1 とする • 分別しない分別器を追加する 22
23. 確率の差分計算 分別器 𝑠 の寄与 Δ𝑏,𝑐,𝑠 = ෍ 𝑖=0 𝑁−1 𝑓𝑎,𝑖 (𝑝𝑠,𝑖 𝑔𝑏,𝑖 + 1 − 𝑝𝑠,𝑖 𝑔𝑐,𝑖 ) 23 • 𝑔 を求めた後、トポロジカル 順序で 𝑓 を更新しながら近 傍を生成することで、1つの 近傍あたり 𝑂(𝑁) で差分計算 できる • 𝑓 と 𝑔 を逆にすることも可能
24. 複数の分別器の種類を試す • 更新前を 𝑏′, 𝑐′, 𝑠′、更新後を 𝑏, 𝑐, 𝑠 とする • スコアの差分 −Δ𝑏′,𝑐′,𝑠′ + Δ𝑏,𝑐,𝑠 • 𝐾 + 1 個の 𝑠 と 𝑏, 𝑐 を入れ換えたものを試す • −Δ𝑏′,𝑐′,𝑠′ は共通なので約2倍の高速化になる 24
25. 複数の分別器の種類を試す Δ𝑏,𝑐,𝑠 = ෍ 𝑖=0 𝑁−1 𝑓𝑎,𝑖 (𝑝𝑠,𝑖 𝑔𝑏,𝑖 + 1 − 𝑝𝑠,𝑖 𝑔𝑐,𝑖 ) = ෍ 𝑖=0 𝑁−1 𝑝𝑠,𝑖 𝑓𝑎,𝑖 𝑔𝑏,𝑖 − 𝑓𝑎,𝑖 𝑔𝑐,𝑖 + 𝑓𝑎,𝑖 𝑔𝑐,𝑖 • 𝑓𝑎,𝑖 𝑔𝑏,𝑖 − 𝑓𝑎,𝑖 𝑔𝑐,𝑖 と 𝑓𝑎,𝑖 𝑔𝑐,𝑖 は 𝑠 によらないので使いまわせる • 演算回数が減る 25
26. 複数の分別器の種類を試す • Δ𝑏,𝑐,𝑠 を試した直後に Δ𝑐,𝑏,𝑠 を試す Δ𝑏,𝑐,𝑠 = ෍ 𝑖=0 𝑁−1 𝑝𝑠,𝑖 𝑓𝑎,𝑖 𝑔𝑏,𝑖 − 𝑓𝑎,𝑖 𝑔𝑐,𝑖 + 𝑓𝑎,𝑖 𝑔𝑐,𝑖 Δ𝑐,𝑏,𝑠 = ෍ 𝑖=0 𝑁−1 𝑝𝑠,𝑖 𝑓𝑎,𝑖 𝑔𝑐,𝑖 − 𝑓𝑎,𝑖 𝑔𝑏,𝑖 + 𝑓𝑎,𝑖 𝑔𝑏,𝑖 = ෍ 𝑖=0 𝑁−1 𝑓𝑎,𝑖 𝑔𝑏,𝑖 − 𝑝𝑠,𝑖 𝑓𝑎,𝑖 𝑔𝑏,𝑖 − 𝑓𝑎,𝑖 𝑔𝑐,𝑖 26
27. SIMD Δ𝑏,𝑐,𝑠 = ෍ 𝑖=0 𝑁−1 𝑝𝑠,𝑖 𝑓𝑎,𝑖 𝑔𝑏,𝑖 − 𝑓𝑎,𝑖 𝑔𝑐,𝑖 + 𝑓𝑎,𝑖 𝑔𝑐,𝑖 • 𝑖 同士は独立なのでSIMD化できる • 単精度でAVX2を使えば8つの要素を同時に処理できる • 𝑁 ≤ 20 なので高々3ループ • 高々3ループなので完全に unroll すると 𝑓𝑎,𝑖 𝑔𝑏,𝑖 − 𝑓𝑎,𝑖 𝑔𝑐,𝑖 や 𝑓𝑎,𝑖 𝑔𝑐,𝑖 はレジスタに乗る • 私は unroll した関数3つを実装しました 27
28. SIMD Δ𝑏,𝑐,𝑠 = ෍ 𝑖=0 𝑁−1 𝑝𝑠,𝑖 𝑓𝑎,𝑖 𝑔𝑏,𝑖 − 𝑓𝑎,𝑖 𝑔𝑐,𝑖 + 𝑓𝑎,𝑖 𝑔𝑐,𝑖 • Σ の計算に min 𝑁, 8 − 1 回の加算が必要で、そこがボトルネッ クの1つだった • seed=0 のスコア計算回数 • （明示的な）SIMD化なし: 9 × 107 • SIMD化あり: 1.7 × 108 • 2倍も速くなってなかった... • SIMD化なしのほうで自動ベクトル化が行われたかも？ 28
29. その他の工夫: トポロジカル順序の決定 • 𝑓 や 𝑔 の更新を1周するごとにトポロジカル順序を計算し直す • DFSでトポロジカル順序を決定する • 2つの行き先のどちらを先に探索するかはランダムに決定する • （BFSではなく）DFSにすることで多様なトポロジカル順序を生成で きる 29
30. その他の工夫: 対数評価 • スコアが低いときに生スコアで評価すると、一部のごみだけが 分類に成功し、他のごみの成功確率が極端に低くなる恐れがあ る • 分類成功確率が著しく低いごみはスコアの差分がほぼ0になるため、そ れ以降も成功確率が低いままになりがち • 序盤は対数和を最大化する ෍ 𝑖=0 𝑁−1 log ごみ 𝑖 の分類成功確率 30
31. その他の工夫: 対数評価 https://lipoyang.hatenablog.com/entry/2021/02/03/202242 • log 𝑥 の（高精度な）計算は重い • SIMD化する場合は自分で実装する必要がある • 粗い近似で高速に求める • 参考: https://lipoyang.hatenablog.com/entry/2021/02/03/202242 • SIMD化も可能 • 対数評価は 0.2秒も行わないので高速化の寄与は小さい 31
32. Ablation Study • 1箇所変えて実験した • 200ケース • どの要素も重要そうだった 32
33. コンテスト中に気づけなかった点 • 𝑓𝑎,𝑖 𝑔𝑐,𝑖 は Σ の外に出せるので先に計算できる • コンテスト終了後、@noshi91 さんに教えていただきました Δ𝑏,𝑐,𝑠 = ෍ 𝑖=0 𝑁−1 𝑝𝑠,𝑖 𝑓𝑎,𝑖 𝑔𝑏,𝑖 − 𝑓𝑎,𝑖 𝑔𝑐,𝑖 + 𝑓𝑎,𝑖 𝑔𝑐,𝑖 = ෍ 𝑖=0 𝑁−1 𝑝𝑠,𝑖 𝑓𝑎,𝑖 𝑔𝑏,𝑖 − 𝑓𝑎,𝑖 𝑔𝑐,𝑖 + ෍ 𝑖=0 𝑁−1 𝑓𝑎,𝑖 𝑔𝑐,𝑖 Δ𝑐,𝑏,𝑠 = ෍ 𝑖=0 𝑁−1 𝑓𝑎,𝑖 𝑔𝑏,𝑖 − ෍ 𝑖=0 𝑁−1 𝑝𝑠,𝑖 𝑓𝑎,𝑖 𝑔𝑏,𝑖 − 𝑓𝑎,𝑖 𝑔𝑐,𝑖 33