🎅

Santa2024上位解法MEMO

2025/02/01に公開

※随時更新していきます

コンペの概要

Santa 2024 - The Perplexity Permutation Puzzle

1st place solution

  • Iterated Local Search(ILS|反復局所探索法)ベース(以下を繰り返す)
    1. 現在の解 (単語列) を局所的に探索して貪欲に改善を図る
    2. 改善できなくなったら kick (perturbation) によって局所解から抜け出す
  • kickでの操作:2単語のswap、連続した区間の抜き出し&挿入など行う
  • 近傍探索での操作:少数の単語抜き出し&挿入
  • 高速化:軽量なNNで有望な近傍を絞りこんで、その後正確なスコアを計算 (NNは強化学習のようにオンラインで最適化)

2nd Place Solution

  • Iterated Local Search(ILS)をベースに、制約付きk-optカスタムキック(Kick) を組み合わせた手法
  • 制約付き K-opt
    • 局所探索アルゴリズムの一種
    • 並びを反転する操作をは以上
    • 移動する単語の数を制限
  • Custom Kick
    • 特定の隣接単語のグループをランダムに選び、並びをシャッフル
    • id5では、ブロック間で単語を移動、交換するCustom Kickを実装

4th Place Solution

  • ビームサーチ
  • 先頭行におくと、valid_length が上がる単語があった
    • id3の場合はmagiを先頭に置いた
  • id3はstopword + Contetnt wordsに分けて最適化
  • id5もstopword + alphabetical block + alphabetical blockに分けて最適化
    • 最後にand and andをstop wordから外す

10th Place Solution

  • シミュレーテッド・アニーリング
  • 以下を初期会にして最適化
    • [stop words("and" を除く)] + [alphabetical block1] + [and and and] + [alphabetical block2]
  • メインの操作は、2単語のswap, 1単語の挿入
    • stop wordのみにも同様の操作を適用

11th Place Solution

  • シミュレーテッド・アニーリング
  • 近傍解の生成手法を色々工夫
    • ランダム挿入
    • 距離ベースの確率的挿入:元の単語位置と近いところに挿入
    • 可変長のランダム挿入:1~4単語をまとめて移動
    • アルファベット順挿入:同じ頭文字の前後に挿入
    • 部分的な並び替え(shuffle):1~4単語のブロックをシャッフル

関連書籍

以上

Discussion