广度优先搜索为什么我的队列被清空？

Question

我有一些代码从队列中获取父节点，检查它是否被访问过，如果没有，生成它的子节点，将它们推到队列中，并重复循环，以FIFO方式从队列中获取下一个父节点。不幸的是，我似乎永远无法达到我的目标状态。我实现BFS的方式是否存在结构上的问题？我使用堆栈而不是队列来创建DFS搜索，得到了与此完全相同的代码所需的输出。将“q”更改为队列（FIFO）数据结构实际上是我对这段代码所做的唯一更改。我还有什么要补充的吗？父/子元素被存储为元组，所以可以忽略所有这些工作——这似乎不是问题所在。此外，程序在isGoalState被计算为True之前中断，因此代码似乎也不会导致问题。isGoalState测试给定状态的坐标是否与BFS需要找到的“目标”匹配。get继任者返回元组列表，每个元组代表节点的一个子级。在

while q:
        parent = q.pop()
        print "parent: " + str(parent)
        print str(q)
        if parent[0] in visited: continue
        visited.append(parent[0])
        if problem.isGoalState(parent[0]):
            pathList.append(parent[0])
            while actionMap[parent] is not None:
                actionList.append(actionMap[parent])
                try:
                    pathList.append(parentMap[parent])
                except KeyError:
                    break
                parent = parentMap.get(parent, None)
            actionList.reverse()
        children = problem.getSuccessors(parent[0])
        if children != []:
            for child in children:
                q.push(child)
                parentMap[child] = parent
                actionMap[child] = child[1]

Answer 1

好吧，我的朋友们，案子结束了。在从DFS到BFS的转换中，我在isGoalState条件中的while循环完成后省略了一个return语句。那真是白费脑筋。在