0

我有从队列中获取父节点的代码,检查它是否已被访问,如果没有,则生成其子节点,将它们推送到队列,并重复循环,从队列中获取下一个父节点先进先出的时尚。不幸的是,似乎我从未达到我的目标状态。我实施 BFS 的方式在结构上是否有问题?我使用堆栈而不是队列来创建 DFS 搜索,并使用相同的确切代码获得了我想要的输出。将“q”更改为队列 (FIFO) 数据结构实际上是我对这段代码所做的唯一更改。还有什么我应该补充的吗?父母/孩子存储为元组,因此请随意忽略所有这些工作——这似乎不是问题所在。此外,程序在 isGoalState 评估为 True 之前中断,因此代码不会 t 似乎也导致了这个问题。isGoalState 测试给定状态的坐标是否与 BFS 需要找到的“目标”匹配。getSuccessors 返回一个元组列表,每个元组代表节点的一个子节点。

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]
4

1 回答 1

0

好吧,我的朋友们,这个案子已经结案了。在我从 DFS 到 BFS 的转换表格中的某个地方,在 isGoalState 条件中的 while 循环完成后,我省略了一个 return 语句。那真是白费了很多脑筋。

于 2012-10-14T23:14:34.950 回答