search.py 文件源码

def depthFirstSearch(problem):
  """
  Search the deepest nodes in the search tree first
  [2nd Edition: p 75, 3rd Edition: p 87]

  Your search algorithm needs to return a list of actions that reaches
  the goal.  Make sure to implement a graph search algorithm 
  [2nd Edition: Fig. 3.18, 3rd Edition: Fig 3.7].

  To get started, you might want to try some of these simple commands to
  understand the search problem that is being passed in:

  print "Start:", problem.getStartState()
  print "Is the start a goal?", problem.isGoalState(problem.getStartState())
  print "Start's successors:", problem.getSuccessors(problem.getStartState())
  """
  "*** YOUR CODE HERE ***"

  frontier = util.Stack()
  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 []