search.py 文件源码

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