Skip to content

AtCoder Heuristic Contest 011

問題概要

  • N * Nのn-puzzle(slide puzzle)が与えられる
  • 各タイルには上下左右方向への線があったりなかったりする絵が描かれている
  • Tターン以内にできるだけ大きな木になるようにタイルを動かせ
  • ただし、全域木ができる場合はターン数、できない場合は木の大きさに基づいてスコアを計算する

時間

199時間

個人的メモ

  • 全域木をどうやって探すか、大きなn-puzzleをどうやって解くか、が難しい問題
  • ざっくり「目標の全域木を探すパート」と「目標の全域木になるようにn-puzzleを解くパート」で考えるのが基本方針だった模様

1. 目標の全域木を探すパート

  • n-puzzleは、作れる状態が n!/2 あり、今回の絵柄の重複を考慮してもかなりの状態数がありえる
    • nは35～99とかなり大きい
  • ただ、visualizer(seed=0)の画像が公開されていたが、全域木になるような配置は複数存在しており、それをどれだけ効率的に探せるかが問題
    • できれば、初期配置から近い配置を探したい

1-1. 全域木を作って、タイル集合が一致するのを目指す焼きなまし

  • 各タイルの中心を頂点として、絵柄は無視していろんな全域木を作り、タイル集合が一致するのを目指す焼きなまし
    • 全域木は、1辺をつないでサイクルをdfsで探し、その中から1辺を削除すると、別の全域木が作れる
    • invalidな状態を許容する焼きなまし
  • 評価関数は、タイルの個数の差の2乗の和、など
  • かなり多くの全域木が得られるようで、良い解を複数次のn-puzzleを解くパートに持っていける

1-2. 2タイルswapする焼きなまし

1-3. 枝刈りDFS/BFS

1-4. 部分領域を全列挙で山登り

2. タイルのマッチング

  • 普通のn-puzzleとは異なり、同じ絵柄が存在して、置換のパリティが一致すれば交換可能
  • できるだけ初期状態に近いと移動距離が少なくて嬉しいので、初期状態と目標状態の各タイルのマッチングを考えられる
  • コストをマンハッタン距離・ユークリッド距離としたマッチング問題を最小費用流やハンガリアン法で解けばよい
    • (自分は、この後のn-puzzleが順番に置いていく方法だったので、greedyに一番近いタイルを割り当てる方法にした、、、)
  • 絵柄は15種類しかないので、(n * m - 1)サイズが15より大きい場合は必ず重複するタイルが存在する
  • 二部マッチングの差分更新も可能

3. n-puzzleを解くパート

3-1. パターンを決めて順番に埋めていく

  • 上の行、左の列、を順番に埋めるような埋め方だと、それぞれ埋めた後はN-1サイズの問題になる
    • Fringe method
    • 大きいNの場合などこれで小さい問題にしてから解くことができる
  • 行(または列)を1行ずつ外側から埋めて、最後の2行は2つずつ左から埋める
    • LBL method
  • 実際のタイルの移動は目的位置への移動パターンをBFSやA*などで探す
  • 車庫入れ
    • 行を埋めるとき、残り2マスは同時に考えないといけない
    • しかし、実際にその動きを実装しようとすると、ハマるパターンが出てしまう
    • 回避の動きを埋め込んでもいいが、無駄にターン数がかかってしまう
  • 端から逆の端に移動するようなパターンは無駄な移動があるので、うねうねさせたり、回転や鏡像などを試すのがよい
  • サイズが小さくなったら最短解を探すなどもできる
  • パターンで埋める場合は、初期状態から目標状態の近さが結構重要

3-2. 枝刈りBFS、A*、IDA*、両側BFS

  • 最短手順を求める
  • ただ、大きいサイズは無理なので、局所的だったり、終盤のサイズが小さくなったりときに適用
    • 2マスずつとかなら、結構高速に見つけられるのでこれを繰り返す

3-3. ビームサーチ、chokudaiサーチ

その他

文献

visualizer

類似の問題

グローバル化

解説

(100位まで&発言を見つけられた方のみ)