[PYTHON] AtCoder AGC 041 C - Ich war süchtig nach der vollständigen Suche nach Domino-Qualität

Überblick

• Es hat lange gedauert, nach Domino zu suchen, wenn N = 7 und Qualität = 3. -Wenn Sie die Suche nach $ 2 ^ {49} \ fallenddotseq 10 ^ {15} $ implementieren, müssen Sie die Zweige gut beschneiden
• Python ist unter bestimmten Bedingungen mehr als 20 Mal langsamer als C ++

Bei der Suche nach der Platzierung von N = 7 und Quality = 3 in Python

Platziere Domino von (0,0) und probiere es aus. Die Reihenfolge zu versuchen

1. Vertikale Ausrichtung
2. Seitwärts
3. Nicht setzen

Es dauerte ** ungefähr 740 [s] **, um eine geeignete Platzierung zu finden.

findPattern.py

import sys
import numpy as np
import datetime

sys.setrecursionlimit(10 ** 7)


def cntQuality(N, grids, num, axis):
    q = 0

    if axis == 0:
        g = grids[num, :]
    else:
        g = grids[:, num]

    last = -1

    for i in range(N):
        d = g[i]

        if last == d or d == 0:
            continue

        q += 1
        last = d

    return q


def dfs(N, grids, pos, num, q):
    x = pos // N
    y = pos % N


    if y == 0 and x != 0:
        qx = cntQuality(N, grids, x-1, 0)
        if qx != q:
            return False

    # end grids
    if x == N and y == 0:
        # valid
        for i in range(N):
            qy = cntQuality(N, grids, i, 1)
            if qy != q:
                return False
        return grids

    # not yet
    pos += 1

    # put vertical
    if y < N-1 and grids[x][y] == 0 and grids[x][y+1] == 0:
        v_num = num + 1
        # v_grids = copy.copy(grids)
        grids[x][y] = v_num
        grids[x][y+1] = v_num
        g = dfs(N, grids, pos, v_num, q)
        if g is not False:
            return g
        grids[x][y] = 0
        grids[x][y+1] = 0

    # put horizontal
    if x < N-1 and grids[x][y] == 0 and grids[x+1][y] == 0:
        h_num = num + 1
        # h_grids = copy.copy(grids)
        grids[x][y] = h_num
        grids[x+1][y] = h_num
        g = dfs(N, grids, pos, h_num, q)
        if g is not False:
            return g
        grids[x][y] = 0
        grids[x+1][y] = 0

    # dont put domino
    g = dfs(N, grids, pos, num, q)
    if g is not False:
        return g

    return False


start = datetime.datetime.now()
print("start", start)


N = 7
q = 3
grids = np.zeros((N, N))
g = dfs(N, grids, 0, 0, q)
end = datetime.datetime.now()
print("end", end)

print(g)

Ausführungsergebnis.txt

start 2020-01-07 18:13:18.477510
end 2020-01-07 18:22:35.768316
[[  1.   1.   2.   2.   3.   3.   0.]
 [  4.   4.   5.   5.   6.   0.   0.]
 [  7.   7.   0.   0.   6.   8.   8.]
 [  0.   0.   9.  10.   0.   0.  11.]
 [  0.   0.   9.  10.   0.   0.  11.]
 [  0.   0.   0.   0.  12.  13.  14.]
 [  0.   0.   0.   0.  12.  13.  14.]]

Warum hat es 740 [s] gekostet?

Es scheint, dass die Reihenfolge der Suche schlecht war.

1. Seitwärts
2. Vertikale Ausrichtung
3. Nicht setzen

Bei der Suche mit wurde die Anordnung innerhalb von 1 [s] gefunden. Vielleicht gibt es in dieser Suchreihenfolge passende Filialen in der Nähe.

Ich habe einige Muster in Python und C ++ ausprobiert

• Ich habe es nur einmal ausprobiert, daher denke ich, dass es einige Unschärfen gibt.

Fazit

――Wenn Sie nicht gut beschneiden können, gibt es je nach Suchreihenfolge einen erheblichen Zeitunterschied. ――Es scheint besser zu sein, C ++ als Python für diese Reihenfolge zu verwenden.