我们从Python开源项目中，提取了以下50个代码示例，用于说明如何使用search.py()。
def __init__(self, gameState, costFn = lambda x: 1, goal=(1,1), start=None, warn=True): """ Stores the start and goal. gameState: A GameState object (pacman.py) costFn: A function from a search state (tuple) to a non-negative number goal: A position in the gameState """ self.walls = gameState.getWalls() self.startState = gameState.getPacmanPosition() if start != None: self.startState = start self.goal = goal self.costFn = costFn if warn and (gameState.getNumFood() != 1 or not gameState.hasFood(*goal)): print 'Warning: this does not look like a regular search maze' # For display purposes self._visited, self._visitedlist, self._expanded = {}, [], 0
def registerInitialState(self, state): """ This is the first time that the agent sees the layout of the game board. Here, we choose a path to the goal. In this phase, the agent should compute the path to the goal and store it in a local variable. All of the work is done in this method! state: a GameState object (pacman.py) """ if self.searchFunction == None: raise Exception, "No search function provided for SearchAgent" starttime = time.time() problem = self.searchType(state) # Makes a new search problem self.actions = self.searchFunction(problem) # Find a path totalCost = problem.getCostOfActions(self.actions) print('Path found with total cost of %d in %.1f seconds' % (totalCost, time.time() - starttime)) if '_expanded' in dir(problem): print('Search nodes expanded: %d' % problem._expanded)
def __init__(self, gameState, costFn = lambda x: 1, goal=(1,1), start=None, warn=True, visualize=True): """ Stores the start and goal. gameState: A GameState object (pacman.py) costFn: A function from a search state (tuple) to a non-negative number goal: A position in the gameState """ self.walls = gameState.getWalls() self.startState = gameState.getPacmanPosition() if start != None: self.startState = start self.goal = goal self.costFn = costFn self.visualize = visualize if warn and (gameState.getNumFood() != 1 or not gameState.hasFood(*goal)): print 'Warning: this does not look like a regular search maze' # For display purposes self._visited, self._visitedlist, self._expanded = {}, [], 0 # DO NOT CHANGE
def registerInitialState(self, state): """ This is the first time that the agent sees the layout of the game board. Here, we choose a path to the goal. In this phase, the agent should compute the path to the goal and store it in a local variable. All of the work is done in this method! state: a GameState object (pacman.py) """ if self.searchFunction == None: raise Exception, "No search function provided for PacardAgent" starttime = time.time() problem = self.searchType(state) # Makes a new search problem self.actions = self.searchFunction(problem) # Find a path totalCost = problem.getCostOfActions(self.actions) print('Path found with total cost of %d in %.1f seconds' % (totalCost, time.time() - starttime)) if '_expanded' in dir(problem): print('Search nodes expanded: %d' % problem._expanded)
def cornersHeuristic(state, problem): """ A heuristic for the CornersProblem that you defined. state: The current search state (a data structure you chose in your search problem) problem: The CornersProblem instance for this layout. This function should always return a number that is a lower bound on the shortest path from the state to a goal of the problem; i.e. it should be admissible (as well as consistent). """ corners = problem.corners # These are the corner coordinates walls = problem.walls # These are the walls of the maze, as a Grid (game.py) "*** YOUR CODE HERE ***" return 0 # Default to trivial solution
def getSuccessors(self, state): """ Returns successor states, the actions they require, and a cost of 1. As noted in search.py: For a given state, this should return a list of triples, (successor, action, stepCost), where 'successor' is a successor to the current state, 'action' is the action required to get there, and 'stepCost' is the incremental cost of expanding to that successor """ successors = [] for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]: # Add a successor state to the successor list if the action is legal # Here's a code snippet for figuring out whether a new position hits a wall: # x,y = currentPosition # dx, dy = Actions.directionToVector(action) # nextx, nexty = int(x + dx), int(y + dy) # hitsWall = self.walls[nextx][nexty] "*** YOUR CODE HERE ***" self._expanded += 1 # DO NOT CHANGE return successors
def getAction(self, state): "The agent receives a GameState (defined in pacman.py)." if Directions.WEST in state.getLegalPacmanActions(): return Directions.WEST else: return Directions.STOP ####################################################### # This portion is written for you, but will only work # # after you fill in parts of search.py # #######################################################
def __init__(self, fn='depthFirstSearch', prob='PositionSearchProblem', heuristic='nullHeuristic'): # Warning: some advanced Python magic is employed below to find the right functions and problems # Get the search function from the name and heuristic if fn not in dir(search): raise AttributeError, fn + ' is not a search function in search.py.' func = getattr(search, fn) if 'heuristic' not in func.func_code.co_varnames: print('[SearchAgent] using function ' + fn) self.searchFunction = func else: if heuristic in dir(searchAgents): heur = getattr(searchAgents, heuristic) elif heuristic in dir(search): heur = getattr(search, heuristic) else: raise AttributeError, heuristic + ' is not a function in searchAgents.py or search.py.' print('[SearchAgent] using function %s and heuristic %s' % (fn, heuristic)) # Note: this bit of Python trickery combines the search algorithm and the heuristic self.searchFunction = lambda x: func(x, heuristic=heur) # Get the search problem type from the name if prob not in dir(searchAgents) or not prob.endswith('Problem'): raise AttributeError, prob + ' is not a search problem type in SearchAgents.py.' self.searchType = getattr(searchAgents, prob) print('[SearchAgent] using problem type ' + prob)
def getAction(self, state): """ Returns the next action in the path chosen earlier (in registerInitialState). Return Directions.STOP if there is no further action to take. state: a GameState object (pacman.py) """ if 'actionIndex' not in dir(self): self.actionIndex = 0 i = self.actionIndex self.actionIndex += 1 if i < len(self.actions): return self.actions[i] else: return Directions.STOP
def getSuccessors(self, currentState): """ Returns successor states, the actions they require, and a cost of 1. As noted in search.py: For a given state, this should return a list of triples, (successor, action, stepCost), where 'successor' is a successor to the current state, 'action' is the action required to get there, and 'stepCost' is the incremental cost of expanding to that successor """ successors = [] for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]: x,y = currentState[0] dx, dy = Actions.directionToVector(action) nextx, nexty = int(x + dx), int(y + dy) if not self.walls[nextx][nexty]: #Copies corner visited by node previously to nextState nextState = [(nextx, nexty), currentState[1][:]] if nextState[0] in self.corners and nextState[0] not in nextState[1]: #Add current corner state visited to nextState node nextState[1].append(nextState[0]) successors.append( ( nextState, action, 1) ) # Bookkeeping for display purposes self._expanded += 1 return successors
def cornersHeuristic(state, problem): """ A heuristic for the CornersProblem that you defined. state: The current search state (a data structure you chose in your search problem) problem: The CornersProblem instance for this layout. This function should always return a number that is a lower bound on the shortest path from the state to a goal of the problem; i.e. it should be admissible (as well as consistent). """ corners = problem.corners # These are the corner coordinates walls = problem.walls # These are the walls of the maze, as a Grid (game.py) currentState = state[0] score = 0 #find unvisited corners unvistedList = list() for corner in corners: unvistedList.append(corner) if corner in state[1]: unvistedList.remove(corner) #repeats for all unvisited corners for r in range(len(unvistedList)): smallestManhattan = 99999 #calculate distance to nearest corner for unvistedCorner in unvistedList: dist = manhattanHeuristic(currentState, unvistedCorner) if dist < smallestManhattan: smallestManhattan = dist #set distance to nearest corner nearestCorner = unvistedCorner score += smallestManhattan #add distance to score unvistedList.remove(nearestCorner) #removes corner from unvisited list currentState = nearestCorner #updates position to the nearest corner return score
def getAction(self, state): """ From game.py: The Agent will receive a GameState and must return an action from Directions.{North, South, East, West, Stop} """ "*** YOUR CODE HERE ***" util.raiseNotDefined()
def getSuccessors(self, state): """ Returns successor states, the actions they require, and a cost of 1. As noted in search.py: For a given state, this should return a list of triples, (successor, action, stepCost), where 'successor' is a successor to the current state, 'action' is the action required to get there, and 'stepCost' is the incremental cost of expanding to that successor """ (x,y,c1,c2,c3,c4) = state corners_hist_old = [c1,c2,c3,c4] # corners we have already seen successors = [] for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]: dx, dy = Actions.directionToVector(action) nextx, nexty = int(x + dx), int(y + dy) if not self.walls[nextx][nexty]: nextState = (nextx, nexty) if nextState in self.corners: # we found a corner #print nextState for i in range(4): # determine which corner we hit if nextState == self.corners[i]: corners_hist_new = corners_hist_old[:] corners_hist_new[i] = 1 # mutate the relevant corner nextValue = nextState + tuple(corners_hist_new) else: # we did not hit a corner nextValue = nextState + tuple(corners_hist_old) cost = self.costFn(nextValue) successors.append( ( nextValue, action, cost) ) self._expanded += 1 return successors
def __init__(self, fn='depthFirstSearch', prob='PositionSearchProblem', heuristic='nullHeuristic'): # Warning: some advanced Python magic is employed below to find the right functions and problems # Get the search function from the name and heuristic if fn not in dir(search): raise AttributeError, fn + ' is not a search function in search.py.' func = getattr(search, fn) if 'heuristic' not in func.func_code.co_varnames: print('[SearchAgent] using function ' + fn) self.searchFunction = func else: if heuristic in globals().keys(): heur = globals()[heuristic] elif heuristic in dir(search): heur = getattr(search, heuristic) else: raise AttributeError, heuristic + ' is not a function in searchAgents.py or search.py.' print('[SearchAgent] using function %s and heuristic %s' % (fn, heuristic)) # Note: this bit of Python trickery combines the search algorithm and the heuristic self.searchFunction = lambda x: func(x, heuristic=heur) # Get the search problem type from the name if prob not in globals().keys() or not prob.endswith('Problem'): raise AttributeError, prob + ' is not a search problem type in SearchAgents.py.' self.searchType = globals()[prob] print('[SearchAgent] using problem type ' + prob)
def getSuccessors(self, state): """ Returns successor states, the actions they require, and a cost of 1. As noted in search.py: For a given state, this should return a list of triples, (successor, action, stepCost), where 'successor' is a successor to the current state, 'action' is the action required to get there, and 'stepCost' is the incremental cost of expanding to that successor """ successors = [] for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]: # Add a successor state to the successor list if the action is legal # Here's a code snippet for figuring out whether a new position hits a wall: # x,y = currentPosition # dx, dy = Actions.directionToVector(action) # nextx, nexty = int(x + dx), int(y + dy) # hitsWall = self.walls[nextx][nexty] "*** YOUR CODE HERE ***" cornersNotVisited = state[1] x,y = state[0] dx, dy = Actions.directionToVector(action) nextx, nexty = int(x + dx), int(y + dy) hitsWall = self.walls[nextx][nexty] if not hitsWall: if (nextx, nexty) in state[1]: cornersNotVisited = filter(lambda a: a != (nextx, nexty), cornersNotVisited) #remove visited corner nextState = ((nextx, nexty), cornersNotVisited) cost = 1 successors.append((nextState, action, cost)) self._expanded += 1 # DO NOT CHANGE return successors
def cornersHeuristic(state, problem): """ A heuristic for the CornersProblem that you defined. state: The current search state (a data structure you chose in your search problem) problem: The CornersProblem instance for this layout. This function should always return a number that is a lower bound on the shortest path from the state to a goal of the problem; i.e. it should be admissible (as well as consistent). """ corners = problem.corners # These are the corner coordinates walls = problem.walls # These are the walls of the maze, as a Grid (game.py) #3) manhattan dist to closest + manhattan to the unvisited others , gives: total cost of 106, nodes expanded: 692 pos = state[0] unvisited = list(state[1]) ret = 0 while len(unvisited) > 0: nextPos = closestCorner(pos, unvisited) ret += manhattanDistance(pos, nextPos) pos = nextPos unvisited.remove(nextPos) return ret
def __init__(self, fn='logicBasedSearch', prob='LogicSearchProblem'): # Warning: some advanced Python magic is employed below to find the right functions and problems # Get the search function from the name and heuristic if fn not in dir(pacard): raise AttributeError, fn + ' is not a search function in pacard.py.' func = getattr(pacard, fn) self.searchFunction = func # Get the search problem type from the name if prob not in globals().keys() or not prob.endswith('Problem'): raise AttributeError, prob + ' is not a search problem type in logicAgents.py.' self.searchType = globals()[prob] print('[PacardAgent] using problem type ' + prob)
def __init__(self, gameState, costFn = lambda x: 1, goal=(1,1), start=None, warn=True, visualize=True): """ Stores the start and goal. gameState: A GameState object (pacman.py) costFn: A function from a search state (tuple) to a non-negative number goal: A position in the gameState """ self.walls = gameState.getWalls() self.startState = gameState.getPacmanPosition() self.capsules = gameState.getCapsules() # hacky self.gameState = gameState ghosts = gameState.getGhostPositions() if len(ghosts) != 1: print 'Warning: this does not look a Wumpus maze' self.wumpus = ghosts[0] if start != None: self.startState = start if warn and (gameState.getNumFood() != 1): print 'Warning: this does not look a Wumpus maze' food = gameState.getFood() self.goal = food.asList()[0] self.costFn = costFn self.visualize = visualize # For display purposes self._visited, self._visitedlist, self._expanded = {}, [], 0 # DO NOT CHANGE
def getSuccessors(self, state): """ Returns successor states, the actions they require, and a cost of 1. As noted in search.py: For a given state, this should return a list of triples, (successor, action, stepCost), where 'successor' is a successor to the current state, 'action' is the action required to get there, and 'stepCost' is the incremental cost of expanding to that successor """ successors = [] for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]: x,y = state dx, dy = Actions.directionToVector(action) nextx, nexty = int(x + dx), int(y + dy) if not self.walls[nextx][nexty]: nextState = (nextx, nexty) cost = self.costFn(nextState) successors.append( ( nextState, action, cost) ) # Bookkeeping for display purposes self._expanded += 1 # DO NOT CHANGE if state not in self._visited: self._visited[state] = True self._visitedlist.append(state) return successors
