Depth-first search


Implement a function depth_first(start, goal, state_graph, return_cost) to search the state space (and step costs) defined by state_graph using depth-first search:


start: initial state (e.g., 'ind')

end: goal state (e.g., 'bos')

state_graph: the dictionary defining the step costs (e.g., map_distances)

return_cost: logical input representing whether or not to return the solution path cost

If True, then the output should be a tuple where the first value is the list representing the solution path and the second value is the path cost

If False, then the only output is the solution path list object

Below is the helper code:


def path(previous, s):

'''

`previous` is a dictionary chaining together the predecessor state that led to each state

`s` will be None for the initial state

otherwise, start from the last state `s` and recursively trace `previous` back to the initial state,

constructing a list of states visited as we go

'''

if s is None:

return []

else:

return path(previous, previous[s])+[s]


def pathcost(path, step_costs):

'''

add up the step costs along a path, which is assumed to be a list output from the `path` function above

'''

cost = 0

for s in range(len(path)-1):

cost += step_costs[path[s]][path[s+1]]

return cost