-
Notifications
You must be signed in to change notification settings - Fork 45
/
busquedas.py
executable file
·290 lines (220 loc) · 8.77 KB
/
busquedas.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
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
busquedas.py
------------
Clases y algoritmos necesarios para desarrollar agentes de
búsquedas en entornos determinísticos conocidos discretos
completamente observables
"""
__author__ = 'juliowaissman'
from collections import deque
import heapq
class ModeloBusqueda:
"""
Clase genérica de un modelo de búsqueda.
Todo modelo de búsqueda debe de tener:
1) Un método que obtenga las acciones legales en cada estado
2) Un método que calcule cual es es siguiente estado
3) Una función de costo local
"""
def acciones_legales(self, estado):
"""
Lista de acciones legales en un estado dado.
@param estado: Una tupla con un estado válido.
@return: Una lista de acciones legales.
"""
raise NotImplementedError("No implementado todavía.")
def sucesor(self, estado, accion):
"""
Estado sucesor
@param estado: Una tupla con un estado válido.
@param accion: Una acción legal en el estado.
@return: Una tupla con el estado sucesor de estado cuando
se aplica la acción.
"""
raise NotImplementedError("No implementado todavía.")
def costo_local(self, estado, accion):
"""
Calcula el costo de realizar una acción en un estado.
@param estado: Una tupla con un estado válido.
@param acción: Una acción legal en estado.
@return: Un número positivo con el costo de realizar
la acción en el estado.
"""
return 1
class ProblemaBusqueda:
"""
Clase genérica de un problema de búsqueda.
Todo problema de búsqueda debe de tener:
a) Un estado inicial
b) Una función que diga si un estado es una meta o no
c) Un modelo para la búsqueda
"""
def __init__(self, x0, meta, modelo):
"""
Inicializa el problema de búsqueda
@param x0: Una tupla con un estado válido del
problema (estado inicial).
@param meta: Una función meta(s) --> bool,
donde meta(s) devuelve True solo
si el estado s es un estado objetivo.
@param modelo: Un objeto de la clase ModeloBusqueda
"""
def es_meta(estado):
self.num_nodos += 1
return meta(estado)
self.es_meta = es_meta
self.x0 = x0
self.modelo = modelo
self.num_nodos = 0 # Solo para efectos medición
class Nodo:
"""
Clase para implementar un árbol como estructura de datos.
"""
def __init__(self, estado, accion=None, padre=None, costo_local=0):
"""
Inicializa un nodo como una estructura
"""
self.estado = estado
self.accion = accion
self.padre = padre
self.costo = 0 if not padre else padre.costo + costo_local
self.profundidad = 0 if not padre else padre.profundidad + 1
self.nodos_visitados = 0
def expande(self, modelo):
"""
Expande un nodo en todos sus nodos hijos de acuerdo al problema pb
@param modelo: Un objeto de una clase heredada de ModeloBusqueda
@return: Una lista de posibles nodos sucesores
"""
return (
Nodo(
modelo.sucesor(self.estado, a),
a,
self,
modelo.costo_local(self.estado, a))
for a in modelo.acciones_legales(self.estado))
def genera_plan(self):
"""
Genera el plan (parcial o completo) que representa el nodo.
@return: Una lista [x0, a1, x1, a2, x2, ..., aT, xT], donde
los x0, x1, ..., xT son tuplas con los estados a
cada paso del plan, mientras que los a1, a2, ..., aT
son las acciónes que hay que implementar para llegar desde
el estado inicial x0 hasta el testado final xT
"""
return ([self.estado] if not self.padre else
self.padre.genera_plan() + [self.accion, self.estado])
def __str__(self):
"""
Muestra el nodo como lo que es en realidad, un plan.
"""
plan = self.genera_plan()
return ("Costo: {}\n".format(self.costo) +
"Profundidad: {}\n".format(self.profundidad) +
"Trayectoria:\n" +
"".join(["en {} hace {} y va a {},\n".format(x, a, xp)
for (x, a, xp)
in zip(plan[:-1:2], plan[1::2], plan[2::2])]))
# Este método de sobrecarga del operador < es necesario
# para poder utilizar los nodos en la heapq
def __lt__(self, other):
return self.profundidad < other.profundidad
def busqueda_ancho(problema):
"""
Búsqueda a lo ancho para un problema de búsquedas dado
@param problema: Un objeto de una clase heredada de ProblemaBusqueda
@return Un objeto tipo Nodo con un plan completo
"""
if problema.es_meta(problema.x0):
return Nodo(problema.x0)
frontera = deque([Nodo(problema.x0)])
visitados = {problema.x0}
while frontera:
nodo = frontera.popleft()
for hijo in nodo.expande(problema.modelo):
if hijo.estado in visitados:
continue
if problema.es_meta(hijo.estado):
hijo.nodos_visitados = problema.num_nodos
return hijo
frontera.append(hijo)
visitados.add(hijo.estado)
return None
def busqueda_profundo(problema, max_profundidad=None):
"""
Búsqueda a lo profundo para un problema de búsquedas dado
@param problema: Un objeto de una clase heredada de ProblemaBusqueda
@param max_profundidad: Máxima profundidad de búsqueda
@return Un objeto tipo Nodo con la estructura completa
"""
frontera = deque([Nodo(problema.x0)])
visitados = {problema.x0: 0}
while frontera:
nodo = frontera.pop()
if problema.es_meta(nodo.estado):
nodo.nodos_visitados = problema.num_nodos
return nodo
if max_profundidad is not None and max_profundidad == nodo.profundidad:
continue
for hijo in nodo.expande(problema.modelo):
# or visitados[hijo.estado] > hijo.profundidad:
if (hijo.estado not in visitados or
visitados[hijo.estado] > hijo.profundidad):
frontera.append(hijo)
visitados[hijo.estado] = hijo.profundidad
return None
def busqueda_profundidad_iterativa(problema, max_profundidad=20):
"""
Búsqueda por profundidad iterativa dado
@param problema: Un objeto de una clase heredada de ProblemaBusqueda
@param max_profundidad: Máxima profundidad de búsqueda
@return Un objeto tipo Nodo con la estructura completa
"""
for profundidad in range(max_profundidad):
resultado = busqueda_profundo(problema, profundidad)
if resultado is not None:
return resultado
return None
def busqueda_costo_uniforme(problema):
"""
Búsqueda por costo uniforme
@param problema: Un objeto de una clase heredada de ProblemaBusqueda
@return Un objeto tipo Nodo con la estructura completa
"""
frontera = []
heapq.heappush(frontera, (0, Nodo(problema.x0)))
visitados = {problema.x0: 0}
while frontera:
(_, nodo) = heapq.heappop(frontera)
if problema.es_meta(nodo.estado):
nodo.nodos_visitados = problema.num_nodos
return nodo
for hijo in nodo.expande(problema.modelo):
if (hijo.estado not in visitados or
visitados[hijo.estado] > hijo.costo):
heapq.heappush(frontera, (hijo.costo, hijo))
visitados[hijo.estado] = hijo.costo
return None
# ---------------------------------------------------------------------
#
# Problema 1: Desarrolla el método de búsqueda de A* siguiendo las
# especificaciones de la función pruebalo con el 8 puzzle
# (ocho_puzzle.py) antes de hacerlo en el Lights_out que es mucho más
# dificl (en el archivo se incluyen las heurísticas del 8 puzzle y el
# resultado esperado)
#
# ---------------------------------------------------------------------
def busqueda_A_estrella(problema, heuristica):
"""
Búsqueda A*
@param problema: Un objeto de una clase heredada de ProblemaBusqueda
@param heuristica: Una funcion de heuristica, esto es, una función
heuristica(nodo), la cual devuelva un número mayor
o igual a cero con el costo esperado desde nodo hasta
un nodo cuyo estado final sea méta.
@return Un objeto tipo Nodo con la estructura completa
"""
raise NotImplementedError('Hay que hacerlo de tarea \
(problema 2 en el archivo busquedas.py)')