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

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

我认为我的实现是正确的，但是有点太慢了:目前在我的计算机上运行需要12秒钟以上的时间(这对我来说是不可接受的)。

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并不是解决此问题的正确方法。

python大神给出的解决方案

有许多优化要完成。

首先，避免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倍。