ALDS1_13_C: 15 Puzzle
こんどは普通に15パズル
計算量が上がっているのでありましょう
ためしに8 Puzzleをそのまま15 Puzzle対応にしたら
18手の問題は解けたけど28手の問題でTLE
15手と18手でも大きく所要時間やメモリが異なっている
問題の制約として45手以内に解けることになっているから45手までは解けないといけない
何かオーダを下げないといけない
アルゴリズムの絵は、8 Puzzleの樹形図みたいなのの下に横線があり
樹形図のノードの一つからひょろっと矢印が出て横線を超えて丸を指している
8 Puzzleのコードを活用することはできそうな絵だな
横線は何か
将棋のプログラムなら評価関数を作って枝刈りするところ？
そういう絵に見えないこともないけどどんな評価関数にしたらよいのやら
数字が本来の位置に近ければ近いほどよい、ってわけでもないし？
傾向としてはそれでいいのかな？
なんか外してる気がするなあ
いや待てよ
45手っていう制限、このためにあるのでは
45手を超えそうなのは枝刈り
たとえば1が右上にあったらどうがんばってもあと3手は必要、みたいな
これを1から15まで全部足して45を超えたら足切り
雑かなあ
雑すぎてあんまり枝を刈れないようだと意味ないけど
入力例（答え8）でやってみると・・・8か
ちょっとこれだけだとわからないけど書いてみるか
class State:
...
def dist(self):
s = 0
for i in range(16):
if self.b[i] != 0:
d = abs(self.b[i] - 1 - i)
s += d // 4 + d % 4
return s
def solve(s):
...
while True:
t = tuple(s.b)
if t == end:
return s.c
if t not in hist and s.dist() + s.c < 45:
push_hands(q, s)
hist.add(t)
s = q.popleft()
...さて実行
だめだった
18手のテストケースでTLEだから悪化している
枝を刈ってはいるっぽいんだけどそんなに効果が出てないってことかなあ
数えてみたら枝刈らない版で1656300回の試行が必要なところ
枝刈る版では1500436の試行ですんでいる
うーんそんなに得してないな
このへんはもともとTLEしてなかったところだから
そんなに枝を刈れなくても普通なのかもしれないけど
ところでこのdist()で11問めまではACになるという発見
簡単なうちはけっこう近似できる？
どうでもいいけど
