python - 进行 BFS 时避免深层复制

Question

我目前正在解决 this assignment 中的第二个练习(这不是作业，我实际上是在尝试解决 this other problem )。我的解决方案使用 BFS 来搜索“熄灯”问题变体的最小解决方案，其中按下一盏灯会翻转同一行和同一列上每个灯的状态。

我认为我的实现是正确的，但它有点太慢了:它目前在我的计算机上运行需要 12 秒以上(这对我的目的来说是 Not Acceptable )。

from copy import deepcopy
from itertools import chain
from Queue import PriorityQueue

# See: http://www.seas.upenn.edu/~cis391/Homework/Homework2.pdf
class Puzzle(object):
    def __init__(self, matrix):
        self.matrix = matrix
        self.dim = len(matrix)

    def __repr__(self):
        return str(self.matrix)

    def solved(self):
        return sum([sum(row) for row in self.matrix]) == 0

    def move(self, i, j):
        for k in range(self.dim):
            self.matrix[i][k] = (self.matrix[i][k] + 1) % 2
            self.matrix[k][j] = (self.matrix[k][j] + 1) % 2
        self.matrix[i][j] = (self.matrix[i][j] + 1) % 2

        return self

    def copy(self):
        return deepcopy(self)

    def next(self):
        result = []

        for i in range(self.dim):
            for j in range(self.dim):
                result.append(self.copy().move(i, j))

        return result

    def solve(self):
        q = PriorityQueue()
        v = set()

        q.put((0, self))
        while True:
            c = q.get()

            if c[1].solved():
                return c[0]
            else:
                for el in c[1].next():
                    t = el.tuple()

                    if t not in v:
                        v.add(t)
                        q.put((c[0] + 1, el))

    def tuple(self):
         return tuple(chain.from_iterable(self.matrix))

根据 cProfile，罪魁祸首似乎是 deepcopy 调用。另一方面，我看不到其他选择:我需要向队列中添加另一个 Puzzle 对象，其中包含 self.matrix 的新副本。

如何加快实现速度？

这是我正在使用的测试用例:

print Puzzle([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]).solve()

应该返回1(我们只需要按下右下角的灯)。

编辑:这是另一个粗糙的测试用例:

print Puzzle([
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
]).solve()

它的解最多为14:按下对角线上所有已经亮着的灯。不幸的是，@zch 令人印象深刻的加速不足以解决这个问题，这让我相信，由于高分支因子，BFS 不是解决这个问题的正确方法。

Answer 1

还有许多优化工作要做。

首先，避免 deepcopy，实现你自己的复制(这本身对我来说快了 5 倍):

class Puzzle(object):
    def __init__(self, matrix):
        self.matrix = [list(row) for row in matrix]
        self.dim = len(matrix)

    def copy(self):
        return Puzzle(self.matrix)

其次，在 BFS 中您不需要优先级队列，使用 Queue 或实现您自己的队列。这提供了一些加速。第三，在将其放入队列之前检查是否已解决，而不是在取出东西之后。这应该可以让您在可比的时间内更深入地学习:

def solve(self):
    v = set()

    q = [(0, self)]
    i = 0
    while True:
        c = q[i]
        i += 1

        for el in c[1].next():
            t = el.tuple()

            if t not in v:
                if el.solved():
                    return c[0] + 1
                v.add(t)
                q.append((c[0] + 1, el))

此外，使用位列表的列表内存效率非常低。您可以将所有位打包成一个整数并获得更快的解决方案。此外，您可以为允许的移动预先计算掩码:

def bits(iterable):
    bit = 1
    res = 0
    for elem in iterable:
        if elem:
            res |= bit
        bit <<= 1
    return res

def mask(dim, i, j):
    res = 0
    for idx in range(dim * i, dim * (i + 1)):
        res |= 1 << idx
    for idx in range(j, dim * dim, dim):
        res |= 1 << idx
    return res

def masks(dim):
    return [mask(dim, i, j) for i in range(dim) for j in range(dim)]

class Puzzle(object):
    def __init__(self, matrix):
        if isinstance(matrix, Puzzle):
            self.matrix = matrix.matrix
            self.dim = matrix.dim
            self.masks = matrix.masks
        else:
            self.matrix = bits(sum(matrix, []))
            self.dim = len(matrix)
            self.masks = masks(len(matrix))

    def __repr__(self):
        return str(self.matrix)

    def solved(self):
        return self.matrix == 0

    def next(self):
        for mask in self.masks:
            puzzle = Puzzle(self)
            puzzle.matrix ^= mask
            yield puzzle

    def solve(self):
        v = set()

        q = [(0, self)]
        i = 0
        while True:
            c = q[i]
            i += 1

            for el in c[1].next():
                t = el.matrix

                if t not in v:
                    if el.solved():
                        return c[0] + 1
                    v.add(t)
                    q.append((c[0] + 1, el))

最后，对于另一个 5 因子，您可以只传递位矩阵，而不是整个 Puzzle 对象，并且另外内联一些最常用的函数。

def solve(self):
    v = set()

    q = [(0, self.matrix)]
    i = 0
    while True:
        dist, matrix = q[i]
        i += 1

        for mask in self.masks:
            t = matrix ^ mask

            if t not in v:
                if t == 0:
                    return dist + 1
                v.add(t)
                q.append((dist + 1, t))

对我来说，这些优化加起来可以提速大约 250 倍。