Python中宽度优先算法的问题

Question

[已编辑]我正在尝试用广度优先算法解决Python中的问题。我已经创建了一个类来从给定的节点生成子节点(我知道这可以正常工作，因为我已经测试过用另一个求解器代码调用这个生成器)。所以，我的问题一定在这短短的几行代码中:

def bfs(self, node):
queue=[]
visited_nodes=[]
memory_use = len(visited_nodes)
queue.append(node)
is_solution=False
while not is_solution:
if len(queue)==0:
print('Unsolvable board!')
is_solution=True

else:
s=queue.pop(0)
visited_nodes.append(s)

if s.isWinningState():
is_solution=True
print('Winning state achieved.')
self.showPath(s)
print('Max memory usage: ', memory_use)
else:
children = s.generateChildren()#deque with all possible states/nodes
if len(children) > 0:
for child in children:
if child not in visited_nodes:
queue.append(child) 

尽管没有返回正确的访问节点数，但它需要大约1秒的时间来求解。

提供了第一个代码，它就永远运行了(我在15分钟后关闭了终端)。有人能帮我弄清楚这里出了什么问题吗?

感谢

Answer 1

当遍历子节点时，不应该将子节点附加到visited_nodes。

之前也应该将节点追加到队列中从队列弹出后，将节点附加到visited_nodes

def bfs(self, node):
queue=[]
visited_nodes=[]
memory_use = len(visited_nodes)
queue.append(node)
while queue:
s=queue.pop(0)
visited_nodes.append(s)
if self.finalStateAchieved:
return
if s.isWinningState():
print('Winning state achieved.')
self.showPath(s)
self.finalStateAchieved = True
print('Max memory usage: ', memory_use)
else:
children = s.generateChildren()#list with all possible states/nodes
if len(children) > 0:
for child in children:
if child not in visited_nodes:
queue.append(child)