-
Notifications
You must be signed in to change notification settings - Fork 0
/
search.py
267 lines (229 loc) · 9.33 KB
/
search.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
# search.py
# ---------
# Licensing Information: You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
#
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by John DeNero
# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# Student side autograding was added by Brad Miller, Nick Hay, and
# Pieter Abbeel (pabbeel@cs.berkeley.edu).
# Trabalho FIA
# Grupo: Gabriella Selbach, Geovana Silveira e Luiza Cruz
"""
In search.py, you will implement generic search algorithms which are called by
Pacman agents (in searchAgents.py).
"""
import util
import math
import random
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.
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 ***"
util.raiseNotDefined()
def breadthFirstSearch(problem):
"""Search the shallowest nodes in the search tree first."""
"*** YOUR CODE HERE ***"
util.raiseNotDefined()
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
########################################################################################
""" Busca de Custo Uniforme """
def uniformCostSearch(problem):
"""Search the node of least total cost first."""
# Define o nodo como um conjunto contendo o estado inicial, o custo do caminho e a lista de passos percorridos
nodo = (problem.getStartState(),0,[])
# Cria a fila de prioridade
fila = util.PriorityQueue()
# Insere o nodo e a prioridade definida na fila
fila.push(nodo,problem)
nodosExplorados = []
while True:
# Verifica se a fila estar vazia, se estiver encerrar a iteracao
if fila.isEmpty():
return False
estado, custoMeta, caminho = fila.pop() # Desempilha o estado, o custo, e o elemento com a maior prioridade da fila
if problem.isGoalState(estado): # Verifica se estar no estado meta
return caminho # Retorna o caminho do no inicial ate o estado
if estado not in nodosExplorados:
nodosExplorados.append(estado) # Adiciona o nodo na lista de nodos explorados
sucessores = problem.getSuccessors(estado)
# Percorre os filhos do elemento desempilhado
for sucessor, direcao, custoNo in sucessores:
if sucessor not in nodosExplorados:
custoCaminho = custoMeta + custoNo
# Insere o filho do elemento desempilhado com o menor custo acumulado como prioridade para realizar a expansao
fila.push((sucessor,custoCaminho,caminho+[direcao]), custoCaminho)
#print "Caminho percorrido:\n", caminho
#print "Numero de estados:\n", len(caminho)
return caminho
#########################################################################################
""" Busca A* """
def aStarSearch(problem, heuristic=nullHeuristic):
"""Search the node that has the lowest combined cost and heuristic first."""
# Cria a fila de prioridade
fila = util.PriorityQueue()
# estado inicial do nodo
nodo = problem.getStartState()
#incializo a fila com o primeiro nodo
fila.push((nodo, []), heuristic(nodo, problem))
#todos explorados
nodosExplorados = []
#enquanto a fila nao estiver vazia fico no laco
while True:
if fila.isEmpty():
return False
estado, caminho = fila.pop() # Desempilha o estado atual e o caminho
if problem.isGoalState(estado):
return caminho
if estado not in nodosExplorados:
nodosExplorados.append(estado) # Adiciona o nodo na lista de nodos explorados
sucessores = problem.getSuccessors(estado)
# Percorre os filhos do elemento desempilhado
for sucessor,direcao,custo in sucessores:
if sucessor not in nodosExplorados:
custovizinho = caminho + [direcao]
custoCaminho = problem.getCostOfActions(custovizinho) + heuristic(sucessor, problem)
fila.push((sucessor, custovizinho),custoCaminho)
#print "Caminho percorrido:\n", caminho
#print "Numero de estados:\n", len(caminho)
return caminho
#########################################################################################
""" Busca Tempera Simulada """
def simulatedAnnealingSearch(problem):
caminho = []
direcaoNodo = []
# estado inicial do nodo
nodo = problem.getStartState()
#tempo
t = 1.0
alfa = 1.5
#loop infinito porque o algoritmo teorico mostra que deve ser feito um loop de t=1 ate infinto
while True:
cont = 0
# Cria a fila
fila = util.Queue()
# T = escalonamento(t)
sucessores = problem.getSuccessors(nodo)
for proximo, direcao, cam in sucessores:
fila.push((proximo,[direcao]))
cont = cont + 1
#escolho um valor randomico de 0 ate a quantidade que ja abri
valorRandom = random.randint(0,cont-1)
if valorRandom > 0:
for j in range(0,valorRandom+1):
novoEstado,novaAcao = fila.pop()
else:
novoEstado,novaAcao = fila.pop()
e = problem.getCostOfActions(novaAcao) - problem.getCostOfActions(direcaoNodo)
#e = valor[proximo] - valor[nodo]
if e < 0: #verifica se houve uma reducao de energia,ou seja, a nova solucao eh melhor que a anterior
nodo = novoEstado
direcaoNodo = novaAcao
caminho = caminho + direcaoNodo
else:
#e^e/t
if math.exp(-e/t): #verifica se a temperatura eh alta atraves da funcao de probabilidade da solucao ser aceita
nodo = novoEstado
direcaoNodo = novaAcao
caminho = caminho + direcaoNodo
if problem.isGoalState(nodo):
return caminho
#atualiza a temperatura
t = t * alfa
#print "Caminho percorrido:\n",caminho
#print "Numero de estados:\n",len(caminho)
return caminho
#########################################################################################
""" Busca Subida de Encosta """
def hillClimbingSearch(problem, heuristic = nullHeuristic):
custo = 1 # Para a busca funcionar, o pai precisa comecar sendo maior.
custoFilho = 0
caminho =[]
estado = problem.getStartState()
estado = ((estado, []), heuristic(estado, problem))
while (custo > custoFilho):
queue = util.PriorityQueue()
custo = heuristic(estado,problem)
if problem.isGoalState(estado):
#print "Caminho percorrido: ", caminho
#print "Numero de estados: ", len(caminho)
return caminho
sucessores = problem.getSuccessors(estado[0][0])
for child in sucessores:
custoCaminho = problem.getCostOfActions([child[1]]) + heuristic(child[0], problem)
queue.push((child[0], child[1]), custoCaminho)
estadoProx = queue.pop()
#calcula o custo do proximo nodo
custoFilho = problem.getCostOfActions([estadoProx[1]]) + heuristic(estadoProx[0], problem) - 1
#soma o caminho ja percorrido com o proximo
caminho = caminho + [estadoProx[1]]
estado = ((estadoProx[0], estadoProx[1]), custoFilho)
#print "Caminho percorrido: ", caminho
#print "Numero de estados: ", len(caminho)
return caminho
#########################################################################################
# Abbreviations
bfs = breadthFirstSearch
dfs = depthFirstSearch
astar = aStarSearch
ucs = uniformCostSearch
sa = simulatedAnnealingSearch
hc = hillClimbingSearch