如何在Python中迭代元组的堆栈

Question

我尝试在Python中使用预定义为的DepthFirstSearch类实现DepthFirstSearch算法：

class Stack:
    def __init__(self):
        self.list = []

    def push(self,item):
        self.list.append(item)

    def pop(self):
        return self.list.pop()

    def isEmpty(self):
        return len(self.list) == 0

我还有一个功能：

^{pr2}$

它返回我们是否处于预定义的目标状态， 功能：

def getStartState(self):
    return self.startState

返回元组(int,int)，代理的位置， 和功能：

def getSuccessors(self, state):
    self._expanded += 1
    return successors

它以((int,int),string,int)的形式返回代理的所有可用的下一个“移动”的元组，其中(int,int)是继任者的状态，string是方向（NSEW），int是继任者的成本。在

到目前为止，我对实现GraphSearch的GraphSearch的实现是这样的：

def depthFirstSearch(problem):
    closed = []
    fringe = util.Stack()
    fringe.push(problem)

    i = 0
    while not fringe.isEmpty():
        currentState = fringe.pop()
        print "current's successors:", currentState.getSuccessors(currentState.getStartState())

        if currentState.isGoalState(currentState.getStartState()):
            return currentState

        if not (currentState in closed):
            closed.append(currentState)
            print "closed now includes:", closed[i].getStartState()

            children = currentState.getSuccessors(currentState.getStartState())
            print "children:", children

            while not children.isEmpty():
               fringe.push(children.pop())

            print "fringe:" fringe

        i += 1

当我意识到这个问题并没有完成时。我完成了第一次迭代，然后第二次就停止了。以下是终端输出：

current's successors: [((5, 4), 'South', 1), ((4, 5), 'West', 1)]
closed now includes: (5, 5)
children: [((5, 4), 'South', 1), ((4, 5), 'West', 1)]
Traceback (most recent call last):
...
...
...
AttributeError: 'list' object has no attribute isEmpty

所以很明显，我没有正确地遍历这个元组的列表，把它们作为两个附加的元组转移到边缘。在

有什么想法我应该如何穿越这个具体的实现？在

Answer 1

getSuccessors弹出列表的一个元素并返回它。列表中的元素本身不是堆栈的实例，因此它们没有isEmpty方法。在

请注意，DFS通常是通过递归实现的；如果这样做，您可能会发现更容易找出哪里出错了。在