所以我有一个问题想用深度优先搜索来解决,返回DFS找到的第一个路径。这是我的(不完整的)DFS 函数:
start = problem.getStartState()
stack = Stack()
visited = []
stack.push(start)
if problem.isGoalState(problem.getStartState):
return something
while stack:
parent = stack.pop()
if parent in visited: continue
if problem.isGoalState(parent):
return something
visited.append(parent)
children = problem.getSuccessors(parent)
for child in children:
stack.push(child[0])
startState 和goalState 变量只是x, y 坐标的元组。问题是一个有多种方法的类。这里重要的是 getSuccessors (它以 3 项元组列表的形式返回给定状态的子项。但是对于这部分问题,只有元组的第一个元素 (child[0]),它返回子节点在 x、y 坐标中的状态,很重要)和 isGoalState(它提供目标状态的 x、y 坐标)。
所以我认为(在这一点上很难测试),这个函数,如果正确实现了其他一切,一旦达到目标状态,它就会返回。如果我遗漏了什么,请告诉我。不过,我最大的问题是返回什么。我希望它按从头到尾的顺序输出到达目标状态所需的所有状态的列表。似乎简单地返回我的堆栈并不能解决问题,因为堆栈将包含许多未访问的孩子。我的访问列表也不会产生任何有用的信息,因为可以想象我可能会到达死胡同,不得不回溯,但访问列表中仍然有死胡同。我将如何获得我想要的列表?