help in executing the code

Question

My code:

      nodes = []
      stack = util.Stack()
      child = []

      currNode = problem.getStartState()
      stack.push(currNode)
      while not stack.isEmpty():
         nodes = stack.pop()
         if problem.isGoalState(nodes):
            return nodes
         else:
            child = problem.getSuccessors(nodes)
            for nodes,_,_ in child:
               stack.push(nodes)
      return None      

The values returned by the functions are:

problem.getStartState() - (5, 5)
problem.isGoalState(problem.getStartState())- False
 problem.getSuccessors(problem.getStartState()) - [((5, 4), 'South', 1), ((4, 5), 'West', 1)]

The code for the successor func is:

def getSuccessors(self, state):
    """
    Returns successor states, the actions they require, and a cost of 1.

     """

    successors = []
    for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]:
      x,y = state
      dx, dy = Actions.directionToVector(action)
      nextx, nexty = int(x + dx), int(y + dy)
      if not self.walls[nextx][nexty]:
        nextState = (nextx, nexty)
        cost = self.costFn(nextState)
        successors.append( ( nextState, action, cost) )


 # Bookkeeping for display purposes
       self._expanded += 1 
       if state not in self._visited:
       self._visited[state] = True
       self._visitedlist.append(state)

    return successors

The code for getcostof action funtion is:

def getCostOfActions(self, actions):
    """
    Returns the cost of a particular sequence of actions.  If those actions
    include an illegal move, return 999999
    """
    if actions == None: return 999999
    x,y= self.getStartState()
    cost = 0
    for action in actions:
      # Check figure out the next state and see whether its' legal
      dx, dy = Actions.directionToVector(action)
      x, y = int(x + dx), int(y + dy)
      if self.walls[x][y]: return 999999
      cost += self.costFn((x,y))
    return cost

I can only change my code, not these functions. I worte the code but when I execute it, it just hanged up. I know, there is some mistake in the logic and I need to find that one. I need to return the list of actions that are listed in achieving the goal.

Answer 1

Ported from dup question posting that has less info than this one (this one at least has code): http://stackoverflow.com/questions/3252163/algorithm-for-dfs/3252365#3252365

The basic difference between DFS and BFS is whether you are checking the area directly around you first, or scouting out at a distance first. Imagine you are on a chessboard at the upper-left corner (0,0). In BFS, you would check the three squares next to you first: (1,0),(1,1),(0,1). Then, you'd check the squares next to (1,0) - making sure that you don't check one that you already checked! (This is important in BFS and DFS.) Then the ones next to (1,1) and the ones next to (0,1). Then you would start checking the next "layer" outwards, until you ran out of things that you haven't checked yet. DFS is similar, but instead of doing things one "layer at a time" outwards from the starting point, you "scout out" as far as possible first.

Another metaphor is imagine that you are paper-wrapping a whole oak tree in a park. If you wrapped things the BFS way, you would wrap the trunk, then all the really thick branches until they were done, then all the thinner branches until they were done, and finally all the leaves. If you did it in the DFS way, you would wrap the trunk, then pick a big branch and wrap that, then wrap the first small branch off that, then the first leaf off that... and then you'd "back off" just a little and wrap the nearby leaves... and then "back off" to the next small branch, and do all its leaves. Et ceteras.