text: # search.py
  # ---------
  # Licensing Information:  You are free to use or extend these projects for
  # educational purposes provided that (1) you do not distribute or publish
  # solutions, (2) you retain this notice, and (3) you provide clear
  # attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
  #
  # Attribution Information: The Pacman AI projects were developed at UC Berkeley.
  # The core projects and autograders were primarily created by John DeNero
  # (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
  # Student side autograding was added by Brad Miller, Nick Hay, and
  # Pieter Abbeel (pabbeel@cs.berkeley.edu).
  
  
  """
  In search.py, you will implement generic search algorithms which are called by
  Pacman agents (in searchAgents.py).
  """
  
  import util
  from util import Stack
  from util import Queue
  from util import PriorityQueue
  
  class SearchProblem:
      """
      This class outlines the structure of a search problem, but doesn't implement
      any of the methods (in object-oriented terminology: an abstract class).
  
      You do not need to change anything in this class, ever.
      """
  
      def getStartState(self):
          """
          Returns the start state for the search problem.
          """
          util.raiseNotDefined()
  
      def isGoalState(self, state):
          """
            state: Search state
  
          Returns True if and only if the state is a valid goal state.
          """
          util.raiseNotDefined()
  
      def getSuccessors(self, state):
          """
            state: Search state
  
          For a given state, this should return a list of triples, (successor,
          action, stepCost), where 'successor' is a successor to the current
          state, 'action' is the action required to get there, and 'stepCost' is
          the incremental cost of expanding to that successor.
          """
          util.raiseNotDefined()
  
      def getCostOfActions(self, actions):
          """
           actions: A list of actions to take
  
          This method returns the total cost of a particular sequence of actions.
          The sequence must be composed of legal moves.
          """
          util.raiseNotDefined()
  
  
  def tinyMazeSearch(problem):
      """
      Returns a sequence of moves that solves tinyMaze.  For any other maze, the
      sequence of moves will be incorrect, so only use this for tinyMaze.
      """
      from game import Directions
      s = Directions.SOUTH
      w = Directions.WEST
      return  [s, s, w, s, w, w, s, w]
  
  def depthFirstSearch(problem):
      stack = Stack()
      visited = []
      action = []
      startNode = problem.getStartState()
      stack.push((startNode, action))
  
      while not stack.isEmpty():
          currNode, action = stack.pop()
          if not currNode in visited:
              visited.append(currNode)
              if problem.isGoalState(currNode):
                  return action
              for i, j, k in problem.getSuccessors(currNode):
                  newAction = action + [j]
                  stack.push((i, newAction))
  
      return []
  
  
  
  def breadthFirstSearch(problem):
      queue = Queue()
      visited = []
      action = []
      startNode = problem.getStartState()
      queue.push((startNode, action))
  
      while not queue.isEmpty():
          currNode, action = queue.pop()
          if not currNode in visited:
              visited.append(currNode)
              if problem.isGoalState(currNode):
                  return action
              for i, j, k in problem.getSuccessors(currNode):
                  newAction = action + [j]
                  queue.push((i, newAction))
  
      return []
  
  
  
  def uniformCostSearch(problem):
      startNode = problem.getStartState()
      PrQ = PriorityQueue()
      visited = []
      action = []
      PrQ.push((startNode, action, 0), 0)
  
      while PrQ.isEmpty()==False:
          node, actions, cost = PrQ.pop()
          if node not in visited:
              visited.append(node)
              if problem.isGoalState(node):
                  return actions
              for i, j, k in problem.getSuccessors(node):
                  newAction = actions + [j]
                  newCost = cost + k
                  PrQ.push((i, newAction, newCost), newCost)
  
  
  def nullHeuristic(state, problem=None):
      return 0
  
  def aStarSearch(problem, heuristic=nullHeuristic):
  
      startNode = problem.getStartState()
      PrQ = PriorityQueue()
      visited = []
      action = []
      PrQ.push((startNode, action, 0), 0)
  
      while PrQ.isEmpty()==False:
          node, actions, cost = PrQ.pop()
          if node not in visited:
              visited.append(node)
              if problem.isGoalState(node):
                  return actions
              for i, j, k in problem.getSuccessors(node):
                  newAction = actions + [j]
                  newCost = cost + k
                  h = newCost + heuristic(i, problem)
                  PrQ.push((i, newAction, newCost), h)
  
  
  
  
  # Abbreviations
  bfs = breadthFirstSearch
  dfs = depthFirstSearch
  astar = aStarSearch
  ucs = uniformCostSearch
  