python - 如何在 python 中正确实现具有 n 个分支因子的树？

Question

我正在尝试在 python 中实现极小极大算法，但在创建分支树结构时遇到了一些问题。我仍然是一个业余程序员，所以请不要介意我的代码看起来很糟糕。这是我的节点结构

class Node:
    parent = None
    state = None
    pmax = 0        #this represents the MAX player symbol; i.e. SELF
    pmin = 0        #this represents the MIN player symbol; i.e. OPPONENT
    stateCost = 0   #this represents utility cost of leaf nodes based on the matrix state
    bestCost = None    #this represents the chosen path in the minimax algorithm
    children = []

    def __init__(self,mat,up,mx,mn):
        self.parent = up
        self.state = mat
        self.pmax = mx
        self.pmin = mn
        stateCost = 0

    def addChild(self,newState,up):
        n = Node(newState,up,self.pmax,self.pmin)
        self.children.append(n)

    def evaluateChildren(self,minmax):
        ln = len(self.state[0])
        for x in range(ln):
            #newState = insertIntoSink(self.state[0],x)
            cloneState = cloneMatrix(self.state)
            newState = insertIntoSink(cloneState,x,minmax)
            print "state being added"
            for list in newState:
                print list
            self.addChild(newState,self)

        print "done Evaluating CHILDREN"


     def evaluateSubChildren(self,minimax):
        ln = len(self.state[0])

        for l in self.children:
            for x in range(ln):
              cloneState = cloneMatrix(self.state)
              newState = insertIntoSink(cloneState,x,minimax)
              l.addChild(newState,l)

在我正在做的情况下，根节点必须有 7 个子节点，每个子节点应该有 7 个自己的子节点。每个子节点都将有父节点中初始矩阵的修改克隆。

发生的错误是，在添加子子项(即二级子项)后，它们没有被添加到子项列表中，而是被添加到根节点中。

子类的创建调用如下。

 def getBestMove(self):
    move =0
    maxVal = -1;
    i=-1;
    #evaluate all the 7 children

    self.evaluateChildren(2)

    self.evaluateSubChildren(1)

   #more calculations go here

我首先尝试调用相同的 evaluateChildren() 函数，如下所示:

    def getBestMove(self):
    move =0
    maxVal = -1;
    i=-1;
    #evaluate all the 7 children

    self.evaluateChildren(2)


    #evaluate second level children
     for n in self.children:
         print "evaluating SECOND LEVEL CHILDREN"
         n.evaluateChildren()

如果我在评估后检查根节点的子节点数，它应该是 7，但它不断向它添加更多 2 级子节点，这使我的程序陷入无限循环。

请让我知道哪里出错了。请询问是否需要更多信息。

Answer 1

您遇到了 Python 中列表和变量绑定(bind)的常见错误 - 您将 children = [] 设为类变量，这使得它相同的列表 在每个节点中。内存中有一个列表，每个节点都指向它。更改它，所有节点都会看到更改。将其移至 __init__ 以使其成为每个实例的新实例。

Class Node:

    def __init__(self,mat,up,mx,mn):

        self.children = []

各种各样的人都被同一个问题绊倒“很多东西错误地引用了完全相同的列表”，大量讨论发生了什么，为什么，如何避免:

Python Strange Behavior with List & Append

Weird list behavior in python

Python array weird behavior

Some strange behavior Python list and dict

Strange behavior of lists in python

List of lists changes reflected across sublists unexpectedly

Generating sublists using multiplication ( * ) unexpected behavior

List of lists changes reflected across sublists unexpectedly

Nested List Indices

Function changes list values and not variable values in Python

Why does my original list change?

Python: why does my list change when I'm not actually changing it?

python: list changes when global edited

python: changes to my copy variable affect the original variable