ALDS1_13_C: 15 Puzzle (続き2)

サンプルコードを読む

IDA*のサンプルコードから

ふむ
マンハッタン距離を求めるのに、毎回全部計算するんじゃなくて
前回からの差分だけ計算してる
それからひとつずつの距離を求めるのに毎回計算するんじゃなくて
テーブルを使ってる
これだけやっても速くなるかもな
オーダは変わらないけど

枝刈りの基準は似たようなもの

・・・

これ、深さを増やすたびにイチから探索してない？
そんなんでいいの？
読み違えてるかな・・・いやそう見えるけど・・・
反復深化ってそういうもの？

A*

Puzzleの大小が比較できるようになっている
これはマンハッタン距離じゃないな
なんのための比較か

Stateも大小比較してる
こっちはマンハッタン距離だ

状態を優先度キューにつっこんでいるからこれは単なる幅優先探索じゃなくて
ダイクストラなんだろうな（よくわかってない

結局Puzzleのoperator <は何のために定義されてたのか
Mapで必要なのかな