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())
"""
# Use the genericSearch method, with the fringe maintained using a Stack
# so that the search proceeds in the order of exploring from the node last
# discovered
return genericSearch(problem, util.Stack())
python类Stack()的实例源码
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())
"""
"*** YOUR CODE HERE ***"
startState = problem.getStartState()
visited = set()
fringe = util.Stack()
fringe.push((startState, ()))
while not fringe.isEmpty():
currNode = fringe.pop()
currState = currNode[0]
currPlan = currNode[1]
if problem.isGoalState(currState):
return list(currPlan)
if not currState in visited:
visited.add(currState)
paths = problem.getSuccessors(currState)
for path in paths:
newPlan = list(currPlan)
newPlan.append(path[1])
nextNode = (path[0], tuple(newPlan))
if not path[0] in visited:
fringe.push(nextNode)
def breadthFirstSearch(problem):
"""Search the shallowest nodes in the search tree first."""
"*** YOUR CODE HERE ***"
"the only change here is that queue structure, so we can search from 1 layer to another layer"
"not like Stack, we pop and search all the way to the goal node, but we need to expand more to find"
"the goal node"
"use queue to store all the same layer node,and always pop first node in the layer"
nodeQueue = util.Queue()
visited = []
path = []
startNode = (problem.getStartState(),path)
nodeQueue.push(startNode)
"start while loop to find the path"
while nodeQueue.isEmpty() is False:
node, path = nodeQueue.pop()
if problem.isGoalState(node):
return path
visited.append(node)
for successor, direction, cost in problem.getSuccessors(node) :
if successor not in visited:
visited.append(successor)
newNode = (successor,path+[direction])
nodeQueue.push(newNode)
return None
util.raiseNotDefined()
def depthFirstSearch(problem):
"""
Search the deepest nodes in the search tree first
[2nd Edition: p 75, 3rd Edition: p 87]
Your search algorithm needs to return a list of actions that reaches
the goal. Make sure to implement a graph search algorithm
[2nd Edition: Fig. 3.18, 3rd Edition: Fig 3.7].
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())
"""
"*** YOUR CODE HERE ***"
frontier = util.Stack()
visited = []
startNode = (problem.getStartState(), None, [])
frontier.push(startNode)
while not frontier.isEmpty():
curr = frontier.pop()
currLoc = curr[0]
currDir = curr[1]
currPath = curr[2]
if(currLoc not in visited):
visited.append(currLoc)
if(problem.isGoalState(currLoc)):
return currPath
successors = problem.getSuccessors(currLoc)
successorsList = list(successors)
for i in successorsList:
if i[0] not in visited:
frontier.push((i[0], i[1], currPath + [i[1]]))
return []
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:"""
loc_stack = Stack()
visited_node = {}
parent_child_map = {}
direction_list = []
start_node = problem.getStartState()
parent_child_map[start_node] = []
loc_stack.push(start_node)
def traverse_path(parent_node):
while True:
map_row = parent_child_map[parent_node]
if (len(map_row) == 2):
parent_node = map_row[0]
direction = map_row[1]
direction_list.append(direction)
else:
break
return direction_list
while (loc_stack.isEmpty() == False):
parent_node = loc_stack.pop()
if (problem.isGoalState(parent_node)):
pathlist = traverse_path(parent_node)
pathlist.reverse()
return pathlist
elif (visited_node.has_key(parent_node) == False):
visited_node[parent_node] = []
sucessor_list = problem.getSuccessors(parent_node)
no_of_child = len(sucessor_list)
if (no_of_child > 0):
temp = 0
while (temp < no_of_child):
child_nodes = sucessor_list[temp]
child_state = child_nodes[0];
child_action = child_nodes[1];
if (visited_node.has_key(child_state) == False):
loc_stack.push(child_state)
parent_child_map[child_state] = [parent_node,child_action]
temp = temp + 1
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:"""
loc_stack = Stack()
visited_node = {}
parent_child_map = {}
direction_list = []
start_node = problem.getStartState()
parent_child_map[start_node] = []
loc_stack.push(start_node)
def traverse_path(parent_node):
while True:
map_row = parent_child_map[parent_node]
if (len(map_row) == 2):
parent_node = map_row[0]
direction = map_row[1]
direction_list.append(direction)
else:
break
return direction_list
while (loc_stack.isEmpty() == False):
parent_node = loc_stack.pop()
if (problem.isGoalState(parent_node)):
pathlist = traverse_path(parent_node)
pathlist.reverse()
return pathlist
elif (visited_node.has_key(parent_node) == False):
visited_node[parent_node] = []
sucessor_list = problem.getSuccessors(parent_node)
no_of_child = len(sucessor_list)
if (no_of_child > 0):
temp = 0
while (temp < no_of_child):
child_nodes = sucessor_list[temp]
child_state = child_nodes[0];
child_action = child_nodes[1];
if (visited_node.has_key(child_state) == False):
loc_stack.push(child_state)
parent_child_map[child_state] = [parent_node,child_action]
temp = temp + 1
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())
"""
"*** YOUR CODE HERE ***"
nodeStack = util.Stack()
visited = []
path = []
startNode = (problem.getStartState(),visited,path)
nodeStack.push(startNode)
"start while loop to find the path"
while nodeStack.isEmpty() is False:
(node, visited, path) = nodeStack.pop()
"check results before go to successors"
if problem.isGoalState(node):
return path
for successor, direction, cost in problem.getSuccessors(node) :
if successor not in visited:
newNode = (successor,visited+[successor],path+[direction])
nodeStack.push(newNode)
return None
util.raiseNotDefined()
