kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_13_C: 15 Puzzle (続き)

あきらめて解説を読む

反復深化
単純に深さ優先探索するとずーっと先まで答えを探しに行って戻ってこないので
ある深さで探索を打ち切り、見つからなかったら1段深くまで探索する
それって幅優先探索と比べたらどこがいいの?

一般的に、反復深化では高速化を図るために探索済みの状態をメモリに記憶しません。

ループの検出はあきらめて、深さのリミットにひっかかることを期待するわけか
深さ優先だからといって状態を記録できないわけじゃないはずだから
ループ分節約するより状態を記憶するのをやめた方が効率的?

ただし、1つ手前への状態に戻らないようにするなど、適宜工夫します。

どういうことかと思ったけど、1を右に動かして次に1を左に動かす、みたいな
動きはやめとくってことね

IDA*
反復深化で推定値を用いて枝を刈る
枝を刈るっていう方針は悪くないんだな

現在の状態の深さgに「ここからあと最低でもh回の状態遷移は必要だろう」というコストhを加えた値が深さの制限dを超えた場合、そこで探索を打ち切ることができます。

それなそれ
そして自分のやった推定値の出し方はマンハッタン距離というらしい
これもよかった模様
じゃなんで自分のコードはTLEなんだ?
幅優先が深さ優先の反復深化よりも遅い理由はあるまい

A*
優先度キューを用いたダイクストラアルゴリズム(または幅優先探索)に
推定値による枝刈りを組み合わせる
これは速くなりそうな感じする

優先度キューはあるかもなとちょっと思ってたけど、
推定値を優先度にすると、場合によっては最短じゃない解を出してしまいそうな
気がして怖かった
大丈夫なんだろうか

ところでダイクストラアルゴリズムってどんなんだっけ
あまりに進捗がゆっくり過ぎて勉強したことをすっかり忘れている
ふむ
最短経路木を求めるアルゴリズム
辺の重みは全部1として見るわけかな