python遞歸實例變量共享數據

我試圖做一個遞歸函數來創建一棵樹。每個節點都有一個井字遊戲狀態，每個節點的子節點都是下一個可能的移動。python遞歸實例變量共享數據

我將棋盤的狀態傳遞給遞歸函數。對於每一個可能的舉動，我創建一個狀態的副本，然後做出這一舉動。這個新的狀態被傳遞給遞歸函數。

#XXX 
#O O = state [1,1,1,-1,0,-1,1,1,1] 
#XXX 

playerX = 1 
playerO = -1 

class node: 
    children = [] #holds all the children 
    state = [] #holds the state of the board as a list of ints 
    def __init__(self,st): 
     self.state = st 

    def addChild(self,child): 
     self.children.append(child) #if only giving birth was this easy 

#returns a node with all it's children filled in 
#cState is the state for this node 
#currentPlayer flips sign every function call 
#stateSize is the size of the board 
def makeTreeXO(cState,currentPlayer,stateSize): 
    newNode = node(cState) 
    for i in range(stateSize): 
     print "looking at", i, "in", cState 
     if(cState[i] == 0): #found an open space 
      print "found an empty space" 
      newState = cState #create copy of state 
      newState[i] = currentPlayer #make the available move 
      print "made new state" 
      newNode.addChild(makeTreeXO(newState,currentPlayer*-1,stateSize)) 
    print "Done with this instance" 
    return newNode 

root = makeTreeXO([1,0,0,1,1,1,1,1,1],playerX,9)

輸出：

looking at 0 in [1, 0, 0, 1, 1, 1, 1, 1, 1] 
looking at 1 in [1, 0, 0, 1, 1, 1, 1, 1, 1] 
found an empty space 
made new state 
looking at 0 in [1, 1, 0, 1, 1, 1, 1, 1, 1] 
looking at 1 in [1, 1, 0, 1, 1, 1, 1, 1, 1] 
looking at 2 in [1, 1, 0, 1, 1, 1, 1, 1, 1] 
found an empty space 
made new state 
looking at 0 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 1 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 2 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 3 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 4 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 5 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 6 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 7 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 8 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
Done with this instance 
looking at 3 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 4 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 5 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 6 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 7 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 8 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
Done with this instance 
looking at 2 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 3 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 4 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 5 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 6 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 7 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
looking at 8 in [1, 1, -1, 1, 1, 1, 1, 1, 1] 
Done with this instance

從打印語句很明顯，對國家所作的更改正在被擡回功能的父實例。有誰知道爲什麼？

來源

2013-12-23 David

的一個問題是這一行：

newState = cState

從您的評論它看起來像你試圖複製cState，但是，您只是將參考複製到列表中，而不是列表中的內容。因此，當您修改newState時，您還在修改cState。你應該擁有的是：

newState = cState.copy()

編輯由於這是公認的答案，完整的解決方案還包括設置在節點的構造self.children = []，由@thefourtheye

來源

2013-12-23 07:18:58 Thayne

不是唯一的問題提到的，但重要的一個。這個問題以及這個被發現的類變量問題都是非預期的數據變更錯誤的來源。如果它出現了，具有更復雜數據結構的讀者應該記住'copy（）'是一個淺拷貝 - 對於某些結構，需要'copy.deepcopy'。 –

謝謝。它現在有效。 – David

問題是，您正在修改類變量，它們將被特定類的所有對象共享。爲了解決這個問題，使state和children實例變量這樣

class node: 
    def __init__(self,st): 
     self.state = st 
     self.children = [] 

    def addChild(self,child): 
     self.children.append(child) #if only giving birth was this easy

而且按照這條線，

newState = cState #create copy of state

你要創建的cState副本，並將其存儲在newState。請記住，在Python中，賦值運算符絕不會將一個值複製到另一個值。它只是使左側的變量指向賦值語句的右側表達式的評估結果。

所以，你實際做的是讓newState和cState指向同一個列表。所以，如果您修改newState，它也會影響cState。實際創建列表的副本，您可以用切片運算符，這樣

newState = cState[:] #create copy of state

來源

2013-12-23 07:18:40 thefourtheye

python遞歸實例變量共享數據

回答

相關問題