def breadthFirstSearch(problem):
"""
Search the shallowest nodes in the search tree first.
[2nd Edition: p 73, 3rd Edition: p 82]
"""
"*** YOUR CODE HERE ***"
frontier = util.Queue()
visited = []
startNode = (problem.getStartState(), None, [])
frontier.push(startNode)
while not frontier.isEmpty():
curr = frontier.pop()
currLoc = curr[0]
currDir = curr[1]
currPath = curr[2]
if(currLoc not in visited):
visited.append(currLoc)
if(problem.isGoalState(currLoc)):
return currPath
successors = problem.getSuccessors(currLoc)
successorsList = list(successors)
for i in successorsList:
if i[0] not in visited:
frontier.push((i[0], i[1], currPath + [i[1]]))
return []
评论列表
文章目录