3

4クイーンの問題を解決するために、Pythonでバックトラッキングアルゴリズムを実装しようとしています。私は次のクラス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);

浅いコピーは、高次元の配列では機能しません。ディープコピーに問題があると聞いているので、これを行うためのより良い方法はありますか？2Dリスト以外の別のデータ構造を示唆する回答も受け入れられます。

どうもありがとう

4

1 に答える 1

1

ディープコピーには問題はありませんが、かなり遅くなることがあります。この場合、それはとにかく問題ではないかもしれません。しかし、いくつかの選択肢があります。

リストに固執したい場合は、単純に1つの深いコピーを作成できます。

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

ディープコピーは遅いことに注意してください。

[補足：実際、これは2D配列を作成するための私のお気に入りの（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 に答える