Skip to content

Instantly share code, notes, and snippets.

@tabris2015
Created March 6, 2020 20:54
Show Gist options
  • Save tabris2015/e18743a870f9a30b0033845c9a80ae69 to your computer and use it in GitHub Desktop.
Save tabris2015/e18743a870f9a30b0033845c9a80ae69 to your computer and use it in GitHub Desktop.
Pista Ejercicio 1 - Laboratorio Algoritmos de Búsqueda
def depthFirstSearch(problem):
"""
Search the deepest nodes in the search tree first.
Your search algorithm needs to return a list of actions that reaches the
goal. Make sure to implement a graph search algorithm.
To get started, you might want to try some of these simple commands to
understand the search problem that is being passed in:
print("Start:", problem.getStartState())
print("Is the start a goal?", problem.isGoalState(problem.getStartState()))
print("Start's successors:", problem.getSuccessors(problem.getStartState()))
"""
closed = set()
fringe = util.Stack()
# cada nodo corresponde a una tupla (state, path)
fringe.push((problem.getStartState(),[]))
while not fringe.isEmpty():
node = fringe.pop()
if problem.isGoalState(node[0]):
return node[1]
if node[0] not in closed:
closed.add(node[0])
for child_state, action, cost in problem.getSuccessors(node[0]):
fringe.push((child_state, node[1] + [action]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment