3

我正在尝试在 Python 中实现回溯算法来解决 4 个皇后问题。我创建了一个具有以下内容的 Queens 类：

def __init__(self, board_size=4):
    self.board  = [[0 for i in xrange(0,board_size)] for i in xrange(0,board_size)];

但是当我实现递归回溯时，由于通过引用传递，董事会在所有访问过的地方都充满了 1。

def backtrack(self, board, next_column):
            (algorithm here) ...
            board[i][column] = 1 ... #to indicate a placed queen
            self.backtrack(board, next_column + 1);
            (rest of algorithm)

我知道我能做到

new_board = copy.deepcopy(board);

浅拷贝不适用于高维数组。有没有更好的方法来做到这一点，因为我听说 deepcopy 存在一些问题？建议除了二维列表之外的不同数据结构的答案也是可以接受的。

非常感谢

4

1 回答 1

1

实际上，deepcopy 没有问题，只是它有时会很慢。在这种情况下，无论如何这可能都不是问题。但是有几种选择。

如果你想坚持使用列表，你可以简单地制作一个深拷贝：

In [63]: n = 8

In [64]: board  = [[0 for i in range(n)] for i in range(n)]

In [65]: timeit board2 = [r[:] for r in board]
100000 loops, best of 3: 3.24 us per loop

In [66]: timeit board2 = copy.deepcopy(board)
10000 loops, best of 3: 92.8 us per loop

请注意，deepcopy 很慢。

[旁注：实际上，这是我最喜欢的（非numpy）用于制作二维数组的习语：

In [69]: board = [x[:] for x in [[0]*n]*n]

但是很多人不喜欢它，因为它太接近错误的东西，即使它自己工作，从这个意义上说不是很健壮。]

但也许更好的方法是使用字典：

In [79]: board = {(i,j): 0 for i in range(n) for j in range(n)}

In [80]: timeit board2 = board.copy()
100000 loops, best of 3: 3.46 us per loop
于 2012-10-28T02:29:01.440 回答