我有从队列中获取父节点的代码,检查它是否已被访问,如果没有,则生成其子节点,将它们推送到队列,并重复循环,从队列中获取下一个父节点先进先出的时尚。不幸的是,似乎我从未达到我的目标状态。我实施 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]