做一個BFS時避免深度拷貝

Question

我目前正在解決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不是解決這個問題的正確方法。

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倍。

Answer 2

我改變了對解決

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 i in range(self.dim): 
        for j in range(self.dim): 
         el = c[1].move(i, j) # do the move 
         t = el.tuple() 

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

         c[1].move(i, j) # undo the move 

由於.move(i, j)是其本身的逆。複印件僅在國家未被訪問時才作出。這將時間從7.405s減少到5.671s。但這並沒有預期的那麼大。

然後替換def tuple(self)：其中：

def tuple(self): 
    return tuple(tuple(r) for r in self.matrix) 

減少從5.671s到0.531s的時間。這應該做到這一點。

全面上市：

from copy import deepcopy 
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 solve(self): 
     q = PriorityQueue() 
     v = set() 

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

      if c[1].solved(): 
       return c[0] 
      else: 
       for i in range(self.dim): 
        for j in range(self.dim): 
         el = c[1].move(i, j) # do the move 
         t = el.tuple() 

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

         c[1].move(i, j) # undo the move 

    def tuple(self): 
     return tuple(tuple(r) for r in 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()