Last active
September 26, 2017 15:59
-
-
Save heat/4527298 to your computer and use it in GitHub Desktop.
implementação solução DFS e DBF para pacman. "Artificial Intelligence A Modern Approach"
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# search.py | |
# --------- | |
# Licensing Information: Please do not distribute or publish solutions to this | |
# project. You are free to use and extend these projects for educational | |
# purposes. The Pacman AI projects were developed at UC Berkeley, primarily by | |
# John DeNero (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu). | |
# For more info, see http://inst.eecs.berkeley.edu/~cs188/sp09/pacman.html | |
""" | |
In search.py, you will implement generic search algorithms which are called | |
by Pacman agents (in searchAgents.py). | |
""" | |
import util, pdb | |
class SearchProblem: | |
""" | |
This class outlines the structure of a search problem, but doesn't implement | |
any of the methods (in object-oriented terminology: an abstract class). | |
You do not need to change anything in this class, ever. | |
""" | |
def getStartState(self): | |
""" | |
Returns the start state for the search problem | |
""" | |
util.raiseNotDefined() | |
def isGoalState(self, state): | |
""" | |
state: Search state | |
Returns True if and only if the state is a valid goal state | |
""" | |
util.raiseNotDefined() | |
def getSuccessors(self, state): | |
""" | |
state: Search state | |
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 | |
""" | |
util.raiseNotDefined() | |
def getCostOfActions(self, actions): | |
""" | |
actions: A list of actions to take | |
This method returns the total cost of a particular sequence of actions. The sequence must | |
be composed of legal moves | |
""" | |
util.raiseNotDefined() | |
def tinyMazeSearch(problem): | |
""" | |
Returns a sequence of moves that solves tinyMaze. For any other | |
maze, the sequence of moves will be incorrect, so only use this for tinyMaze | |
""" | |
from game import Directions | |
s = Directions.SOUTH | |
w = Directions.WEST | |
return [s,s,w,s,w,w,s,w] | |
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 ***" | |
def _dfs(borda, visitado): | |
no = borda.pop() | |
state = no[0] | |
visitado.append(state) | |
# parada | |
if problem.isGoalState(state): | |
return [] | |
d = problem.getSuccessors(state) | |
for i in (d): | |
if i[0] not in visitado: | |
borda.push(i) | |
caminho = _dfs(borda, visitado) | |
if (caminho != None): | |
caminho.insert(0,i[1]) | |
return caminho | |
b = util.Stack() | |
v = [] | |
#primeiro no conforme tripla do metodo getSuccessors (sucessor, acao, custo) | |
_primeiro_no = (problem.getStartState(),'',0) | |
b.push( | |
_primeiro_no) | |
return _dfs(b, v) | |
def breadthFirstSearch(problem): | |
""" | |
Search the shallowest nodes in the search tree first. | |
[2nd Edition: p 73, 3rd Edition: p 82] | |
""" | |
"*** YOUR CODE HERE ***" | |
q = util.Queue() | |
mark = [] | |
v = (problem.getStartState(), '', 0) | |
if problem.isGoalState(v[0]): | |
return [] | |
mark.append(v[0]) | |
q.push(v) | |
nos = {str(v[0]): (None, None,)} | |
while q : | |
t = q.pop() | |
print t | |
if problem.isGoalState(t[0]) : | |
v = t; | |
break; | |
for edge in problem.getSuccessors(t[0]): | |
if not edge[0] in mark : | |
mark.append(edge[0]) | |
nos[str(edge[0])] = (edge, t,) | |
q.push(edge) | |
_s = v | |
_q = [] | |
while _s : | |
if nos[str(_s[0])][1] : | |
_q.append(_s[1]) | |
_s = nos[str(_s[0])][1] | |
return _q[::-1] | |
def uniformCostSearch(problem): | |
"Search the node of least total cost first. " | |
q = util.PriorityQueue() | |
visitado = [] | |
q.push( | |
get_node((problem.getStartState(),'',0),None, problem), 0) | |
def solved(s): | |
g = node_array(s) | |
l = [a.areste for a in g if a.areste] | |
print l | |
return l[::-1] | |
while not q.isEmpty() : | |
no = q.pop() | |
visitado.append(no.state) | |
if problem.isGoalState(no.state) : | |
return solved(no) | |
for s in problem.getSuccessors(no.state) : | |
_s = get_node(s, no, problem) | |
if not _s.state in visitado: | |
q.push(_s, _s.custo) | |
return [] | |
def nullHeuristic(state, problem=None): | |
""" | |
A heuristic function estimates the cost from the current state to the nearest | |
goal in the provided SearchProblem. This heuristic is trivial. | |
""" | |
return 0 | |
def aStarSearch(problem, heuristic=nullHeuristic): | |
"Search the node of least total cost first. " | |
q = util.PriorityQueue() | |
visitado = [] | |
q.push( | |
get_node((problem.getStartState(),'',0),None, problem, heuristic=heuristic), 0) | |
def solved(s): | |
g = node_array(s) | |
l = [a.areste for a in g if a.areste] | |
print l | |
return l[::-1] | |
while not q.isEmpty() : | |
no = q.pop() | |
visitado.append(no.state) | |
if problem.isGoalState(no.state) : | |
return solved(no) | |
for s in problem.getSuccessors(no.state) : | |
_s = get_node(s, no, problem, heuristic=heuristic) | |
if not _s.state in visitado: | |
q.push(_s, _s.custo) | |
return [] | |
def node_array(node): | |
_node = node | |
while _node: | |
yield _node | |
_node = _node.raiz | |
def get_node(state, raiz, problem, heuristic=nullHeuristic): | |
custo = state[2] + heuristic(state[0], problem) | |
return Node(state[0], raiz, state[1], custo) | |
class Node: | |
def __init__(self, state, raiz=None,areste=None, custo=0): | |
self.state = state | |
self.raiz = raiz | |
self.areste = areste | |
self.custo = custo | |
# Abbreviations | |
bfs = breadthFirstSearch | |
dfs = depthFirstSearch | |
astar = aStarSearch | |
ucs = uniformCostSearch |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment