ALDS1_13_C: 15 Puzzle (続き3)

これだけやっても速くなるかもな

試してみよう

MDT[i][j]は位置iに数字jがあるときのマンハッタン距離ってことでいいかな
iとjは対称なんだけど使われ方からして
ただしjは数字から1ひかないといけない
最初っから1引いておけば少し速くなるかな？
TLEになったら試すか

空きの移動先のMDTを引き算して移動元のMDTを足してやれば新しい
マンハッタン距離が出る、と

こんな感じ
こんなところに初期化コード書くの初めてだけどアリなのかな

class State:

    MDT = [[None] * 16 for _ in range(16)]
    for i in range(16):
        for j in range(16):
            MDT[i][j] = abs(i // 4 - j // 4) + abs(i % 4 - j % 4)

    def dist(self):
        return sum(
            [State.MDT[i][self.b[i] - 1] for i in range(16) if self.b[i] != 0]
        )

    def move_zero(self, h):
        ns = self.dup()
        ns.z += h
        ns.d -= State.MDT[ns.z][ns.b[ns.z] - 1]
        ns.d += State.MDT[self.z][ns.b[ns.z] - 1]
        ns.b[self.z], ns.b[ns.z] = ns.b[ns.z], ns.b[self.z]
        ns.c += 1
        return ns

速くなったかな
いいえ同じところ15番(18手)でTLE

12番(15手)で比べてみると 02.02s だったのが 01.59s になってるから
多少速くはなってるんだけど

通ってるケースを見てみると12番(15手)で 01.59s、13番(12手)が 00.24s
3手で7倍 45手だと7^15倍かー
長くなれば枝刈りの効果はあがりそうだけど

ちょっと枝刈りをなくしてみる
まずはifの条件だけ削除

        if t not in hist: # and s.d + s.c <= 45:
            push_hands(q, s)
            hist.add(t)

15番(18手)はTLEだし12番(15手)はやっぱり 01.59s
マンハッタン距離の計算もやめてみる

    def move_zero(self, h):
        ns = self.dup()
        ns.z += h
        # ns.d -= State.MDT[ns.z][ns.b[ns.z] - 1]
        # ns.d += State.MDT[self.z][ns.b[self.z] - 1]
        ns.b[self.z], ns.b[ns.z] = ns.b[ns.z], ns.b[self.z]
        ns.c += 1
        return ns

15番通ったよ 13.11s
この2行でそんなに変わるのか
枝刈りの効果よりこっちの負荷の方が強く出ているんだな

17番(28手)でTLEになってる
45手ははるかかなた
反復深化とくらべて幅優先が遅いってことはない気がするんだけど
実装がおかしいかなあ

Python 3 で AtCoder をするあれこれ - Qiita

a[i][j] みたいな場合、Python は毎回2回リスト(配列)アクセスをするので遅い.

こういうことかね

以下のような2重ループになっている場合には１つ目のリスト(配列)にアクセスしたものを変数に入れておくと速くできる.

これは適用できない