我们从Python开源项目中，提取了以下8个代码示例，用于说明如何使用util.Queue()。
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)
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 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
