DevQuiz2011 スライドパズル

  • 結果:3723問
  • 言語:OCaml
  • ソース:https://github.com/LennMars/DevQuiz2011
  • 方針:
    • 普通のA*(評価関数はマンハッタン距離 + 2 * Linear Conflict)
    • といってもこれで素直に解けるのは4*4の一部までだろう⇒早速完答を諦め、2段階に分けて解くことにする
      • 1段階目で正しい位置に持っていきたいピース以外をマスクし、マスクされたピースについては評価関数に加算しないようにしてA*を実行
      • 1段階目が終了したらマスクを外してそこから再度A*を実行
      • マスクのいい決め方は思いつかなかったので盤面の角に接する直方領域を総当たり的に生成して袋小路を埋める感じにした(平均80パターンくらい)。
      • 1つのマスクにつき、訪問済み盤面が一定数を越えたら強制終了(一定数=だいたい1000くらい)
      • 勉強だと思って優先度つきキューとそれを実現するための可変長配列もどき(OCamlの配列サイズ制限に対応するため2次元配列で実装)も自前実装した
    • 短い解が得られた問題から順に手数制限に突き当たるまで選択して回答とする
    • この段階で冗長な手を短縮しようとした努力の結果がshortenディレクトリに入っている
      • 3672問→3723問と一応マシになってはいるが……
  • 結果:
    • 1マスクにつき約0.5秒*80パターン*5000インスタンス=約50時間(CPU:2.40GHz)
    • 使用メモリはせいぜい40MB
    • 7問に1問ほど難しいインスタンスがあったらしく全マスクパターンで失敗した
    • つまり解いたのに解の質が悪いせいで手数制限に引っかかり回答に含められなかったのが600問ほどあるということに
  • 反省:
    • 反復深化を使うべきだったかも
    • せめてマスク生成をもう少し賢くするとか最大訪問済み盤面数を盤面サイズによって変えるとか……
    • 今気付いたんだけどもしかしてこれ劣化双方向探索だった？