CODEWITHSUNDEEP
pythonalgorithmdepth-first-searchdepth
devii
devii

Reputation: 25

Depth First Search (Graph Method)

I've been working on this problem for a long time and almost have it. Basically, I am implementing a depth first search, keeping track of nodes, in order to find a goal node AND be able to trace a path from the start node to the goal node. I can find the goal node and can keep track of the path, but the issue I am having is this:

When I am trying to recreate my route, I get stuck in an infinite loop where, say, node x1 points to node x2, and node x2 points to node x1. Here is the relevant code (in python):

# Starting position
stack = util.Stack()
currentState = problem.getStartState()
goalState = []
directions = {}
visited = []


if problem.isGoalState(currentState): return []
else:
    stack.push(currentState)

while stack.isEmpty() == False:
    currentState = stack.pop()
    if currentState in visited: 
        continue
    if problem.isGoalState(currentState): 
        goalState = currentState
        break
    visited.append(currentState)
    for state in problem.getSuccessors(currentState):
        stack.push(state[0])
        directions[state[0]] = (currentState, state[1])

print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]

Each state is a tuple of ((coordinate of node), "direction traveled", cost). I understand I need a while loop to properly trace back to the start state, the end part of the code is just to show you guys this output:

(1, 1)
(2, 1)
(2, 2)
(2, 1)
(2, 2)
(2, 1)
(2, 2)

Any help would be GREATLY appreciated! This is my first time posting here so I hope I did everything right.

Upvotes: 2

Views: 1806

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

You need to save the direction when you visit the node, not when you add a node to the stack.

In the current code you will keep overwriting the directions dictionary.

(To fix this, for example, you could save both the new node and the parent node on the stack and then only write the directions dictionary when you visit the node.)

By the way:

  1. testing if nodes are in visited is more efficient if you use a set not a list
  2. if you want a min cost path you may want to look into using a priority queue (such as provided by Python's heapq module) instead of a stack

Upvotes: 1

Related Questions