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