def breadthFirstSearch(problem):
"""Search the shallowest nodes in the search tree first."""
"*** YOUR CODE HERE ***"
startState = problem.getStartState()
visited = set()
fringe = util.Queue()
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)
python类Queue()的实例源码
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 breadthFirstSearch(problem):
"""
Search the shallowest nodes in the search tree first.
[2nd Edition: p 73, 3rd Edition: p 82]
"""
"*** YOUR CODE HERE ***"
frontier = util.Queue()
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 breadthFirstSearch(problem):
"""
Search the shallowest nodes in the search tree first.
"""
# Use the genericSearch method, with the fringe maintained with a Queue so
# that all nodes on the same level are explored before the next level is
# explored. This will find the optimal solution, because each level is
# explored before the next, so the first time the goal is reached will be
# the shortest path to the goal.
return genericSearch(problem, util.Queue())
def constrainedBreadthFirstSearch(problem, legalStates):
"""
A breadth-first search that finds a shortest path to a
state going only through given states.
"""
# we need a set to remember all visited states
visitedStates = set()
# DFS works in LIFO fashion
searchQueue = Queue()
# add an initial state so the stack is not empty
startState = problem.getStartState()
startNode = SearchNode(startState)
searchQueue.push(startNode)
# iterate until completion
while not searchQueue.isEmpty():
currentNode = searchQueue.pop()
currentState = currentNode.position
# check for end
if problem.isGoalState(currentState):
return currentNode.backtrack()
if currentState in visitedStates:
continue
visitedStates.add(currentState)
for futureState, move, _ in problem.getSuccessors(currentState):
if futureState not in visitedStates and futureState in legalStates:
futureNode = SearchNode(futureState, parent=currentNode, transition=move)
searchQueue.push(futureNode)
print "Search finished, final state not found!"
return
def constrainedBreadthFirstSearch(problem, legalStates):
"""
A breadth-first search that finds a shortest path to a
state going only through given states.
"""
# we need a set to remember all visited states
visitedStates = set()
# DFS works in LIFO fashion
searchQueue = Queue()
# add an initial state so the stack is not empty
startState = problem.getStartState()
startNode = SearchNode(startState)
searchQueue.push(startNode)
# iterate until completion
while not searchQueue.isEmpty():
currentNode = searchQueue.pop()
currentState = currentNode.position
# check for end
if problem.isGoalState(currentState):
return currentNode.backtrack()
if currentState in visitedStates:
continue
visitedStates.add(currentState)
for futureState, move, _ in problem.getSuccessors(currentState):
if futureState not in visitedStates and futureState in legalStates:
futureNode = SearchNode(futureState, parent=currentNode, transition=move)
searchQueue.push(futureNode)
print "Search finished, final state not found!"
return
def breadthFirstSearch(problem):
"""Search the shallowest nodes in the search tree first."""
loc_queue = Queue()
visited_node = {}
parent_child_map = {}
direction_list = []
start_node = problem.getStartState()
parent_child_map[start_node] = []
loc_queue.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_queue.isEmpty() == False):
parent_node = loc_queue.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_queue.push(child_state)
if (parent_child_map.has_key(child_state) == False):
parent_child_map[child_state] = [parent_node,child_action]
temp = temp + 1
def breadthFirstSearch(problem):
"""Search the shallowest nodes in the search tree first."""
loc_queue = Queue()
visited_node = {}
parent_child_map = {}
direction_list = []
start_node = problem.getStartState()
parent_child_map[start_node] = []
loc_queue.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_queue.isEmpty() == False):
parent_node = loc_queue.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_queue.push(child_state)
if (parent_child_map.has_key(child_state) == False):
parent_child_map[child_state] = [parent_node,child_action]
temp = temp + 1
