Python Question

My DFS Algorithm does not work properly on backtracking situations

I have a problem that I need to use DFS to solve. This is my function so far and according to the autograder I'm provided with, it works on 4/5 tests and only fails at backtracking situations:

def depthFirstSearch(problem):

stack=Stack()
if problem.isGoalState(start):
return actions
while stack:
parent=stack.pop()
if flag==1:
action=actionStack.pop()
if parent in visited: continue
visited.add(parent)
if problem.isGoalState(parent):
while parent!=None:
actions.append(action)
parent=parentMap[parent]
action=actionMap[parent]
return actions
children=problem.getSuccessors(parent)
for child in children:
stack.push(child[0])
actionStack.push(child[1])
parentMap[child]=parent
if flag==1:
actionMap[child] = child[1]
flag=1
util.raiseNotDefined()


getSuccessors returns a list of triples (state, action, cost) and I need to return a list of actions to guide an agent from the start to a goal. Sorry in advance, I am new to python. Any hints?

edit: This is the tree that it fails at

FAIL: test_cases/q1/graph_backtrack.test
graph:

B
^
|
*A --> C --> G
|
V
D

A is the start state, G is the goal. Arrows mark
possible state transitions. This tests whether
you extract the sequence of actions correctly even
if your search backtracks. If you fail this, your
nodes are not correctly tracking the sequences of
actions required to reach them.
student solution: ['2:A->D', '1:A->C', '0:C->G']
student expanded_states: ['A', 'D', 'C']

correct solution: ['1:A->C', '0:C->G']
correct expanded_states: ['A', 'D', 'C']
correct rev_solution: ['1:A->C', '0:C->G']
correct rev_expanded_states: ['A', 'B', 'C']

Answer

you have only one set of actions. not an actions per step. if you were travelling below going to 7 then your actions would be 1,2,3,4,5,6,7 when it should be 1,2,3,6,7

1-2-3-4-5
0-0-6-0-0
0-0-7-0-0

Don't be afraid to package the current state with each next move. unless you have a ridiculously large solution space you should be fine.

Comments