-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathparcial.py
302 lines (225 loc) · 10.6 KB
/
parcial.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
291
292
293
294
295
296
297
298
299
300
301
302
"""
TEORIA
1.a) Un ambiente estocastico es aquel en el cual los resultados de las acciones
se conocen con certeza.
Por ejemplo en el problema de las 8 reinas, dada la accion mover la reina_x a
la prosición_y sabemos exactamente que el resultado de esa acción va a tener a la
reina_x en la prosición_y
1.b) Un ambiente es completamente observable cuando tenemos conocimiento del estado completo
Por ejemplo, en el problema de la aspiradora podemos decir que es completamente observable solo si
conocemos en todo momento cuales son los lugares sucios y donde se encuentra la aspiradora
1.c) Un ambiente o problem es secuencial cuando se resuelve en diferentes pasos pasando
por diferentes estados relacionados entre sí. Por ejemplo: una partida de ajedrez teniendo
en cuenta cada jugada como posible paso o secuencia.
2) Un agente reflejo simple tiene mapeadas las acciones a tomar para cada posible observacion.
mientras que un agente basado en modelos decide que acciones tomar en base a distintas
condiciones, llevando en memoria una representación del estado general (no solo de lo
observado en cada iteración).
Una situación resoluble por el segundo es por ejemplo un auto que se maneja solo, y tiene
que observar adelante y atrás antes de decidir si puede girar/avanzar/frenar/etc.
3) La racionalidad depende de que la resolución de un problema sea completa y no viole
ninguna restriccion (??????)
4) La solución de un problema de búsqueda es una suceción de acciones que partiendo
de un estado inicial pueden llegar a un estado meta. Para que una solución sea optima
debe llegar a un estado meta con el menor costo posible.
5) Medidas para comparar performance:
- (d) la distancia máxima entre dos nodos
- (b) el factor de bifurcación
- (m) la altura mínima donde se puede encontrar un estado meta
- ...
Con estas medidas se pueden calcular:
- Complejidad espacial: mide cuánto ocupa como máximo el problema en memoria
- Complejidad temporal: mide cuantas iteraciones como máximo puede demorar en
encontrar una solución
6) Respuesta correcta: O(b**m) el factor de bifurcación elevado a la altura minima de la meta
7) Para ser admisible una heuristica debe cumplir dos condiciones:
- No sobreestimar
- No perder información (heuristica de nodo <= costo_de_ir_a_nodo_hijo + heuristica_de_nodo_hijo)
Si no se utiliza una heuristica admisible en A*, esta estrategia puede no encontrar
la solución más óptima.
8) La mayor diferencia es que la búsqueda por haz local se puede quedar "trabada" en un
mínimo local.
9) Para resolver un problema de CSP es necesario definir las variables, sus posibles
dominios (o valores) y las restricciones.
Se considera solución a la asignación de valores a las variables.
Una solución es completa cuando todas las variables tienen asignado un valor y es
consistente cuando esa asignación no viola ninguna restricción.
10) Dos heuristicas genericas usadas en csp (voy a inventar porque no me acuerdo)
- cantidad de variables no asignadas (puede ser utilizada en estrategias como backtracking)
- cantidad de restricciones violadas (puede ser utilizada en estrategias como min_conflicts)
PRACTICA
"""
DORMITORIO = "dormitorio"
LIVING = "living"
ENTRADA = "entrada"
BAÑO = "baño"
COMEDOR = "comedor"
MOVER = "mover"
APAGAR = "apagar"
ROOM_CONNECTIONS = {
DORMITORIO: [LIVING],
LIVING: [DORMITORIO, COMEDOR, ENTRADA],
ENTRADA: [LIVING],
BAÑO: [COMEDOR],
COMEDOR: [BAÑO, LIVING],
}
INITIAL_STATE = (
# el primer elemento es donde está el bombero
ENTRADA,
# el segundo elemento es una tupla de habitaciones
(
# cada habitación tiene el nombre y los segundos que le lleva apagar el fuego que tenga
(DORMITORIO, 10),
(LIVING, 10),
(ENTRADA, 0),
(BAÑO, 30),
(COMEDOR, 600),
)
)
class SearchProblem:
pass
class ControlDeIncendios(SearchProblem):
def is_goal(self, state):
_, habitaciones = state
fuegos_apagados = sum(habitacion[-1] for habitacion in habitaciones) == 0
return fuegos_apagados
def actions(self, state):
# un action se define como una tupla de dos elementos:
# - el primero puede ser "mover" o "apagar" segun la accion del bombero
# - el segundo es la habitación a la que se mueve o donde apaga el fuego
bombero_position, habitaciones = state
habitaciones = dict(habitaciones)
# acciones de mover
actions = [
(habitacion_conectada, MOVER)
for habitacion_conectada
in ROOM_CONNECTIONS[bombero_position]
]
# accion de apagar incendio, si corresponde
if habitaciones[bombero_position] > 0:
actions.append((APAGAR, bombero_position))
return actions
def result(self, state, action):
bombero_position, habitaciones = state
habitaciones = dict(habitaciones)
action, place = action
if action == MOVER:
bombero_position = place
else:
habitaciones[bombero_position] = 0
habitaciones = tuple(
(habitacion, fuego) for habitacion, fuego in habitaciones.items()
)
return bombero_position,
def cost(self, state, action, state2):
action, place = action
if action == MOVER:
return 5
bombero_position, habitaciones = state
habitaciones = dict(habitaciones)
return habitaciones[bombero_position]
def heuristic(self, state):
bombero_position, habitaciones = state
# costo de apagar los fuegos que quedan prendidos:
cost = sum(hab[1] for hab in habitaciones)
habitaciones_con_fuego = [hab for hab in habitaciones if hab[1] > 0]
# costo de moverse
cost += len(habitaciones_con_fuego) * 5
# si el bombero ya está en una habitación con fuego le restamos el costo de un movimiento
if bombero_position in habitaciones_con_fuego:
cost -= 5
return cost
"""
Resolucion con astar
NODOS
=====
e = entrada
d = dormitorio
l = living
b = baño
c = comedor
m = moverse
a = apagar
Nombre | Pad| Action | Estado | Costo Acum | Heuristica | Coso Ac + Heuristica
| |que | | | |
| |lleva al| | | |
| |nodo | | | |
-------|-------------------------------------------------------------------------------------
N1 | | | (e, ((e, 0), (d, 10), (l, 10), (b, 30), (c, 600)| 0 | 650 + 4*5 (670) | 670
N2 | N1 | m, l | (l, ((e, 0), (d, 10), (l, 10), (b, 30), (c, 600)| 5 | 650 + 3*5 (665) | 670
N3 | N2 | m, e | estado igual a N1 con mayor costo acum, se descarta |
N4 | N2 | m, c | (c, ((e, 0), (d, 10), (l, 10), (b, 30), (c, 600)| 5+5 10 | 650 + 3*5 (665) | 675
N5 | N2 | m, d | (d, ((e, 0), (d, 10), (l, 10), (b, 30), (c, 600)| 5+5 10 | 650 + 3*5 (665) | 675
N6 | N2 | a, l | (l, ((e, 0), (d, 10), (l, 0), (b, 30), (c, 600) | 5+10 15 | 640 + 3*5 (655) | 670
N7 | N6 | m, d | (d, ((e, 0), (d, 10), (l, 0), (b, 30), (c, 600) | 15+5 20 | 640 + 2*5 (650) | 670
N8 | N6 | m, c | (c, ((e, 0), (d, 10), (l, 0), (b, 30), (c, 600) | 15+5 20 | 640 + 2*5 (650) | 670
N9 | N6 | m, e | (e, ((e, 0), (d, 10), (l, 0), (b, 30), (c, 600) | 15+5 20 | 640 + 2*5 (650) | 670
N10 | N7 | m, l | estado igual a N6 con mayor costo acumulado, se descarta
N11 | N7 | a, d | (d, ((e, 0), (d, 0), (l, 0), (b, 30), (c, 600) | 20+10 30 | 630 + 2*5 (640) | 670
N12 | N11| m, l | (l, ((e, 0), (d, 0), (l, 0), (b, 30), (c, 600) | 30+5 35 | 630 + 2*5 (640) | 675
| | | | | |
| | | | | |
ITERACIONES
===========
FRONTERA | NODO ELEGIDO | ES META | HIJOS
------------------------------------------------------------------------------
| N1 | No | N2
| N2 | No | N3, N4, N5, N6
N4, N5 | N6 | No | N7, N8, N9
N8, N9, N4, N5 | N7 | No | N10, N11
N8, N9, N4, N5 | N11 | No | N12
N9, N12, N4, N5 | N8 | |
| | |
"""
# Control de incendios 2 - CSP
VARIABLES = ["central", "aux_a", "aux_b"]
VARIABLES = ["central", "aux_a", "aux_b"]
JULIO_42 = "42_julio"
ESTANDAR_1 = "barrio_estandar_1"
ESTANDAR_2 = "barrio_estandar_2"
ESTANDAR_3 = "barrio_estandar_3"
PARQUE_INDUSTRIAL = "parque_industrial"
CICLOVIALANDIA = "ciclovialandia"
CENTRO = "centro"
QUINTAS = "quintas"
AEROCLUB = "aeroclub"
COSTANERA = "costanera"
BARRIOS_ADYACENTES = {
JULIO_42: [CICLOVIALANDIA, CENTRO, ESTANDAR_2],
ESTANDAR_2: [JULIO_42, CENTRO, ESTANDAR_1],
PARQUE_INDUSTRIAL: [ESTANDAR_1, ESTANDAR_3],
CICLOVIALANDIA: [JULIO_42, CENTRO, QUINTAS],
CENTRO: [CICLOVIALANDIA, JULIO_42, ESTANDAR_1, ESTANDAR_2, COSTANERA, AEROCLUB],
ESTANDAR_1: [ESTANDAR_2, CENTRO, COSTANERA, PARQUE_INDUSTRIAL, ESTANDAR_3],
ESTANDAR_3: [ESTANDAR_1, PARQUE_INDUSTRIAL, COSTANERA],
QUINTAS: [CICLOVIALANDIA],
AEROCLUB: [CENTRO, COSTANERA],
COSTANERA: [CENTRO, AEROCLUB, ESTANDAR_1, ESTANDAR_3],
}
DOMINIOS = {}
DOMINIOS["central"] = [
barrio for barrio, adyacentes in BARRIOS_ADYACENTES.items()
if barrio != CENTRO
and len(adyacentes) >= 3
]
DOMINIOS["aux_b"] = [
barrio for barrio, adyacentes in BARRIOS_ADYACENTES.items()
if barrio not in [CENTRO, PARQUE_INDUSTRIAL, QUINTAS, AEROCLUB]
]
DOMINIOS["aux_a"] = [
barrio for barrio, adyacentes in BARRIOS_ADYACENTES.items()
if CENTRO in adyacentes
and barrio not in [CENTRO, CICLOVIALANDIA]
]
CONSTRAINTS = []
def diferentes(variables, values):
barrio1, barrio2 = values
return barrio1 != barrio2
def no_adyacentes(variables, values):
barrio1, barrio2 = values
return barrio1 not in BARRIOS_ADYACENTES[barrio2]
for par_de_barrios in itertools.combinations(VARIABLES):
CONSTRAINTS.extend([
(par_de_barrios, diferentes),
(par_de_barrios, no_adyacentes),
])