El módulo 8 terminó con una promesa: consolidar con las manos lo que los módulos 3 a 8 dieron en teoría, código y criterio. Empezamos por donde empezó el curso técnico, los algoritmos del módulo 3: búsqueda no informada (BFS, DFS), coste uniforme, A* con heurística, minimax con poda alfa-beta y optimización con búsqueda local, recocido simulado y algoritmos genéticos. Todos los ejercicios usan el mapa de reparto de NovaMarket (GRAFO_CIUDAD y COORDENADAS de 03-02) y la asignación de pedidos entre Getafe y Zaragoza de 03-04, así que las cifras que ya conoces (17,0 km al Retiro, 39,0 km del viajante, 257 € de la asignación) te servirán de vara de medir. Todo es Python puro con la biblioteca estándar.
Cómo trabajar la lección: lee el enunciado y las pistas, intenta resolverlo en tu editor (media hora por ejercicio es razonable; el reto final, una hora), y solo entonces compara con la solución y lee la retroalimentación. Si te atascas, vuelve a la lección de referencia que se indica en cada recordatorio; copiar el código de 03-02 o 03-04 y adaptarlo es exactamente lo que haría un profesional. La dificultad crece del ejercicio 1 al 6.
Contenido
- Preparación común: grafo, coordenadas y utilidades
- Ejercicio 1: BFS y DFS, barrios alcanzables y una calle cortada
- Ejercicio 2: Dijkstra desde el almacén, caminos y el mejor punto de reparto
- Ejercicio 3: A* con un barrio nuevo, admisibilidad y nodos expandidos
- Ejercicio 4: minimax y alfa-beta en la guerra de precios a dos semanas
- Ejercicio 5: viajante con ventanas horarias, ascenso de colina frente a recocido
- Ejercicio 6 (reto): asignación con capacidad y coste de ruta con un algoritmo genético
- Errores Comunes y Consejos
- Conclusión
- Preparación común: grafo, coordenadas y utilidades
Guarda esto como nm_grafo.py (o pégalo al principio de cada script): es el mapa de 03-02 con sus dos utilidades. Todo lo demás se construye encima.
from collections import deque
import heapq, math, random, itertools
GRAFO_CIUDAD = {
"Almacen_Getafe": [("Leganes", 4.5), ("Villaverde", 5.0)],
"Leganes": [("Almacen_Getafe", 4.5), ("Carabanchel", 4.5), ("Villaverde", 6.5)],
"Villaverde": [("Almacen_Getafe", 5.0), ("Leganes", 6.5), ("Usera", 4.5), ("Vallecas", 7.5)],
"Carabanchel": [("Leganes", 4.5), ("Usera", 4.5), ("Arganzuela", 5.0)],
"Usera": [("Villaverde", 4.5), ("Carabanchel", 4.5), ("Arganzuela", 3.5), ("Vallecas", 5.5)],
"Vallecas": [("Villaverde", 7.5), ("Usera", 5.5), ("Retiro", 6.0)],
"Arganzuela": [("Carabanchel", 5.0), ("Usera", 3.5), ("Retiro", 4.0)],
"Retiro": [("Arganzuela", 4.0), ("Vallecas", 6.0)],
}
COORDENADAS = {"Almacen_Getafe": (0, 0), "Leganes": (-3, 3), "Villaverde": (3, 3), "Carabanchel": (-2, 7),
"Usera": (2, 7), "Vallecas": (7, 8), "Arganzuela": (1, 10), "Retiro": (4, 12)}
def reconstruir_camino(padres, objetivo):
camino = [objetivo]
while padres[camino[-1]] is not None:
camino.append(padres[camino[-1]])
return camino[::-1]
def coste_camino(grafo, camino):
return sum(dict(grafo[a])[b] for a, b in zip(camino, camino[1:]))
- Ejercicio 1: BFS y DFS, barrios alcanzables y una calle cortada
Recordatorio (03-02, secciones 5 y 6). BFS usa una cola FIFO y encuentra el camino con menos tramos (no menos kilómetros); DFS usa una pila y devuelve el primer camino que encuentra, con poca memoria y sin garantía de calidad. Ambos usan el diccionario padres como registro de visitados.
Enunciado. Diego quiere saber, para el reparto de esta mañana desde Almacen_Getafe:
- Qué barrios son alcanzables y a cuántos tramos está cada uno (una función
alcanzables_bfs(grafo, inicio)que devuelva{barrio: nº de tramos}). - El camino con menos tramos hasta Vallecas con BFS, y el que devuelve DFS; compara tramos y kilómetros.
- Obras en la M-40 cortan la calle Villaverde–Vallecas. Escribe
sin_arista(grafo, a, b)que devuelva una copia del grafo sin esa calle en los dos sentidos (sin modificar el original) y repite las preguntas 1 y 2. ¿Cuántas calles hay que cortar para que Vallecas deje de ser alcanzable?
Pistas: en la pregunta 1 basta el bucle de BFS anotando tramos[vecino] = tramos[nodo] + 1; para copiar el grafo usa una comprensión de diccionario que filtre la arista {n, v} == {a, b}.
Solución
def alcanzables_bfs(grafo, inicio):
frontera, tramos = deque([inicio]), {inicio: 0}
while frontera:
nodo = frontera.popleft()
for vecino, _ in grafo[nodo]:
if vecino not in tramos: # primera vez que se ve: profundidad mínima
tramos[vecino] = tramos[nodo] + 1
frontera.append(vecino)
return tramos
def bfs(grafo, inicio, objetivo):
frontera, padres, explorados = deque([inicio]), {inicio: None}, []
while frontera:
nodo = frontera.popleft(); explorados.append(nodo)
if nodo == objetivo:
return reconstruir_camino(padres, objetivo), explorados
for vecino, _ in grafo[nodo]:
if vecino not in padres:
padres[vecino] = nodo; frontera.append(vecino)
return None, explorados
def dfs(grafo, inicio, objetivo):
pila, padres, explorados = [inicio], {inicio: None}, []
while pila:
nodo = pila.pop(); explorados.append(nodo)
if nodo == objetivo:
return reconstruir_camino(padres, objetivo), explorados
for vecino, _ in reversed(grafo[nodo]): # reversed: expandir en el orden de la lista
if vecino not in padres:
padres[vecino] = nodo; pila.append(vecino)
return None, explorados
def sin_arista(grafo, a, b):
"""Copia del grafo sin la calle a-b (en ambos sentidos); el original no se toca."""
return {n: [(v, d) for v, d in ady if {n, v} != {a, b}] for n, ady in grafo.items()}
print(alcanzables_bfs(GRAFO_CIUDAD, "Almacen_Getafe"))
for nombre, f in (("BFS", bfs), ("DFS", dfs)):
c, ex = f(GRAFO_CIUDAD, "Almacen_Getafe", "Vallecas")
print(f"{nombre}: {' -> '.join(c)} | tramos {len(c)-1} | km {coste_camino(GRAFO_CIUDAD, c)} | explorados {len(ex)}")
G2 = sin_arista(GRAFO_CIUDAD, "Villaverde", "Vallecas")
print(alcanzables_bfs(G2, "Almacen_Getafe"))
c, ex = bfs(G2, "Almacen_Getafe", "Vallecas")
print(f"BFS sin la calle: {' -> '.join(c)} | tramos {len(c)-1} | km {coste_camino(G2, c)}")
G4 = sin_arista(sin_arista(G2, "Usera", "Vallecas"), "Retiro", "Vallecas")
print(bfs(G4, "Almacen_Getafe", "Vallecas")[0], alcanzables_bfs(G4, "Almacen_Getafe")){'Almacen_Getafe': 0, 'Leganes': 1, 'Villaverde': 1, 'Carabanchel': 2, 'Usera': 2, 'Vallecas': 2, 'Arganzuela': 3, 'Retiro': 3}
BFS: Almacen_Getafe -> Villaverde -> Vallecas | tramos 2 | km 12.5 | explorados 6
DFS: Almacen_Getafe -> Leganes -> Carabanchel -> Usera -> Vallecas | tramos 4 | km 19.0 | explorados 5
{'Almacen_Getafe': 0, 'Leganes': 1, 'Villaverde': 1, 'Carabanchel': 2, 'Usera': 2, 'Arganzuela': 3, 'Vallecas': 3, 'Retiro': 4}
BFS sin la calle: Almacen_Getafe -> Villaverde -> Usera -> Vallecas | tramos 3 | km 15.0
None {'Almacen_Getafe': 0, 'Leganes': 1, 'Villaverde': 1, 'Carabanchel': 2, 'Usera': 2, 'Arganzuela': 3, 'Retiro': 4}Lectura: los 7 barrios son alcanzables (el grafo es conexo) y BFS da la profundidad mínima de cada uno en una sola pasada. A Vallecas se llega en 2 tramos (12,5 km, que aquí coincide con el óptimo en km); DFS explora un nodo menos pero devuelve 4 tramos y 19 km. Con la calle Villaverde–Vallecas cortada, Vallecas pasa a 3 tramos por Usera (15,0 km) y Retiro a 4; y hay que cortar las tres calles de Vallecas (Villaverde, Usera y Retiro) para aislarla: bfs devuelve None y alcanzables_bfs ya no la lista.
Retroalimentación
- Error típico: modificar
GRAFO_CIUDADin situ conremovey "arrastrar" el corte a los ejercicios siguientes; la copia con comprensión evita ese estado oculto. - Otro: quitar la arista en un solo sentido; el grafo es no dirigido y hay que filtrar en las dos listas (por eso comparamos conjuntos
{n, v}). - Variantes: escribe
dfsrecursivo y comprueba que devuelve el mismo camino; calcula el número de cortes mínimo para aislar cada barrio (el grado del nodo es una cota superior); añade abfsun límite de profundidad y observa cuándo deja de encontrar Retiro.
- Ejercicio 2: Dijkstra desde el almacén, caminos y el mejor punto de reparto
Recordatorio (03-02 sección 7 y 03-04 sección 3). La búsqueda de coste uniforme (Dijkstra) expande siempre el nodo de menor coste acumulado g con un montículo (heapq), puede reasignar el padre de un nodo si aparece un camino mejor y descarta las entradas obsoletas del montículo. Ejecutada sin objetivo, da la distancia mínima a todos los nodos.
Enunciado. Escribe dijkstra_completo(grafo, origen) que devuelva (dist, padres, orden_de_cierre) para todos los nodos y úsala para: (a) una tabla con la distancia mínima desde Almacen_Getafe a cada barrio y el camino reconstruido; (b) las aristas del grafo que no usa ningún camino mínimo desde el almacén; (c) la matriz completa de distancias (ejecutando desde cada nodo) y la comprobación de que es simétrica; (d) Marta se pregunta dónde debería estar un punto de reparto urbano si se pudiera elegir libremente entre los 8 nodos: el que minimice la suma de distancias mínimas a todos los demás. ¿Cuál es y cuánto ahorra frente al almacén de Getafe?
Solución
def dijkstra_completo(grafo, origen):
dist, padres, frontera, cerrados = {origen: 0.0}, {origen: None}, [(0.0, origen)], []
while frontera:
g, nodo = heapq.heappop(frontera)
if nodo in cerrados: # entrada obsoleta
continue
cerrados.append(nodo)
for vecino, d in grafo[nodo]:
if vecino not in dist or g + d < dist[vecino]:
dist[vecino], padres[vecino] = g + d, nodo
heapq.heappush(frontera, (g + d, vecino))
return dist, padres, cerrados
dist, padres, orden = dijkstra_completo(GRAFO_CIUDAD, "Almacen_Getafe")
for n in orden:
print(f"| {n} | {dist[n]:.1f} | {' -> '.join(reconstruir_camino(padres, n))} |")
usadas = {frozenset((padres[n], n)) for n in padres if padres[n]}
todas = {frozenset((a, b)) for a in GRAFO_CIUDAD for b, _ in GRAFO_CIUDAD[a]}
print("Aristas no usadas:", sorted(tuple(sorted(e)) for e in todas - usadas))
MATRIZ = {n: dijkstra_completo(GRAFO_CIUDAD, n)[0] for n in GRAFO_CIUDAD}
print("Simétrica:", all(MATRIZ[a][b] == MATRIZ[b][a] for a in MATRIZ for b in MATRIZ))
for n in MATRIZ:
print(f"{n:15s} suma {sum(MATRIZ[n].values()):5.1f} más lejano: {max(MATRIZ[n], key=MATRIZ[n].get)}")| Barrio (orden de cierre) | km | Camino mínimo |
|---|---|---|
| Almacen_Getafe | 0,0 | — |
| Leganes | 4,5 | Getafe → Leganes |
| Villaverde | 5,0 | Getafe → Villaverde |
| Carabanchel | 9,0 | Getafe → Leganes → Carabanchel |
| Usera | 9,5 | Getafe → Villaverde → Usera |
| Vallecas | 12,5 | Getafe → Villaverde → Vallecas |
| Arganzuela | 13,0 | Getafe → Villaverde → Usera → Arganzuela |
| Retiro | 17,0 | Getafe → Villaverde → Usera → Arganzuela → Retiro |
Aristas no usadas: [('Arganzuela', 'Carabanchel'), ('Carabanchel', 'Usera'), ('Leganes', 'Villaverde'), ('Retiro', 'Vallecas'), ('Usera', 'Vallecas')]
Simétrica: True
Almacen_Getafe suma 70.5 más lejano: Retiro
Leganes suma 61.5 más lejano: Vallecas
Villaverde suma 52.5 más lejano: Retiro
Carabanchel suma 51.0 más lejano: Vallecas
Usera suma 44.0 más lejano: Almacen_Getafe
Vallecas suma 64.5 más lejano: Leganes
Arganzuela suma 52.0 más lejano: Almacen_Getafe
Retiro suma 69.0 más lejano: Almacen_GetafeLos caminos mínimos desde el almacén forman un árbol (7 aristas para 7 barrios; las otras 5 del grafo no se usan). Los nodos se cierran en orden creciente de distancia, la propiedad que garantiza el óptimo con costes positivos. La matriz es la de 03-04 y es simétrica porque el grafo es no dirigido. Y el mejor punto de reparto sería Usera (44,0 km de suma frente a 70,5 del almacén): está a menos de 10 km de cualquier barrio; en la práctica es la lógica de los micro-hubs urbanos de última milla.
Retroalimentación
- Error típico: comprobar el objetivo o "cerrar" al generar un nodo en vez de al sacarlo del montículo; en 03-02 vimos que eso devuelve 18,5 km a Retiro en lugar de 17,0. Aquí, además, el
padresdebe poder sobrescribirse: si lo proteges conif vecino not in padrescomo en BFS, Arganzuela se queda con el camino por Carabanchel (14,0) en lugar del de Usera (13,0). - Comparar con el ejercicio 1: BFS y Dijkstra coinciden en tramos salvo en Retiro (3 tramos por Vallecas, 18,5 km, frente a 4 tramos y 17,0 km).
- Variante: convierte los km en minutos con velocidades distintas por calle (por ejemplo, 3 min/km en Usera–Arganzuela por tráfico) y comprueba si cambia el árbol; el algoritmo no cambia, solo los pesos.
- Ejercicio 3: A* con un barrio nuevo, admisibilidad y nodos expandidos
Recordatorio (03-02, secciones 8 y 10). A* expande el nodo de menor f = g + h. Con h admisible (nunca sobreestima) y consistente (h(n) ≤ c(n, n') + h(n'), la desigualdad triangular) es óptimo y expande menos nodos que coste uniforme; h = 0 lo convierte exactamente en coste uniforme.
Enunciado. NovaMarket abre reparto en Moratalaz, en las coordenadas (8, 11), conectado por dos calles nuevas: Vallecas–Moratalaz 3,5 km y Retiro–Moratalaz 4,5 km.
- Escribe
anadir_barrio(grafo, coords, nombre, xy, aristas)que devuelva copias ampliadas del grafo y las coordenadas. - Comprueba que la heurística euclídea sigue siendo consistente: para cada arista a–b, la distancia en línea recta no debe superar los km de la calle. Comprueba también la admisibilidad hacia Moratalaz:
h(n, Moratalaz) ≤ distancia mínima realpara todos los n (usadijkstra_completodesde Moratalaz). - Resuelve Getafe → Moratalaz con coste uniforme y con A*, y compara km y nodos expandidos.
- Diego propone registrar la calle Vallecas–Moratalaz con 3,0 km ("hay un atajo"). ¿Qué pasa con la heurística? ¿Y si en lugar de eso multiplicas
hpor 2 para "acelerar" A*? Busca un par origen-destino en el que A* deje de ser óptimo.
Solución
def anadir_barrio(grafo, coords, nombre, xy, aristas):
g = {n: lista[:] for n, lista in grafo.items()}; c = dict(coords)
g[nombre], c[nombre] = [], xy
for vecino, km in aristas:
g[nombre].append((vecino, km)); g[vecino].append((nombre, km))
return g, c
def heuristica(coords, n, objetivo, w=1.0):
(x1, y1), (x2, y2) = coords[n], coords[objetivo]
return w * math.hypot(x2 - x1, y2 - y1)
def aristas_no_consistentes(grafo, coords):
return [(a, b, km, round(heuristica(coords, a, b), 2)) for a in grafo for b, km in grafo[a]
if heuristica(coords, a, b) > km + 1e-9]
def no_admisibles(grafo, coords, objetivo):
real = dijkstra_completo(grafo, objetivo)[0]
return [(n, round(heuristica(coords, n, objetivo), 2), real[n]) for n in grafo
if heuristica(coords, n, objetivo) > real[n] + 1e-9]
def a_estrella(grafo, coords, inicio, objetivo, w=1.0):
h = lambda n: heuristica(coords, n, objetivo, w) # w=0 -> coste uniforme
frontera, padres, mejor_g, cerrados = [(h(inicio), 0.0, inicio)], {inicio: None}, {inicio: 0.0}, []
while frontera:
f, g, nodo = heapq.heappop(frontera)
if nodo in cerrados: continue
cerrados.append(nodo)
if nodo == objetivo:
return reconstruir_camino(padres, objetivo), g, cerrados
for vecino, d in grafo[nodo]:
if vecino not in mejor_g or g + d < mejor_g[vecino]:
mejor_g[vecino], padres[vecino] = g + d, nodo
heapq.heappush(frontera, (g + d + h(vecino), g + d, vecino))
return None, math.inf, cerrados
G_M, C_M = anadir_barrio(GRAFO_CIUDAD, COORDENADAS, "Moratalaz", (8, 11), [("Vallecas", 3.5), ("Retiro", 4.5)])
print("No consistentes:", aristas_no_consistentes(G_M, C_M), "| no admisibles:", no_admisibles(G_M, C_M, "Moratalaz"))
for nombre, w in (("Coste uniforme", 0.0), ("A*", 1.0)):
c, g, ex = a_estrella(G_M, C_M, "Almacen_Getafe", "Moratalaz", w)
print(f"{nombre}: {' -> '.join(c)} | {g} km | expandidos {len(ex)}: {ex}")
G_3, C_3 = anadir_barrio(GRAFO_CIUDAD, COORDENADAS, "Moratalaz", (8, 11), [("Vallecas", 3.0), ("Retiro", 4.5)])
print("Con 3,0 km:", aristas_no_consistentes(G_3, C_3), no_admisibles(G_3, C_3, "Moratalaz"))
for a in G_M: # heurística inflada (w=2): ¿pierde el óptimo?
for b in G_M:
if a != b and a_estrella(G_M, C_M, a, b, 2.0)[1] > a_estrella(G_M, C_M, a, b, 0.0)[1]:
print("w=2 NO óptimo:", a, "->", b, a_estrella(G_M, C_M, a, b, 2.0)[1], "frente a", a_estrella(G_M, C_M, a, b, 0.0)[1])No consistentes: [] | no admisibles: []
Coste uniforme: Almacen_Getafe -> Villaverde -> Vallecas -> Moratalaz | 16.0 km | expandidos 8: ['Almacen_Getafe', 'Leganes', 'Villaverde', 'Carabanchel', 'Usera', 'Vallecas', 'Arganzuela', 'Moratalaz']
A*: Almacen_Getafe -> Villaverde -> Vallecas -> Moratalaz | 16.0 km | expandidos 4: ['Almacen_Getafe', 'Villaverde', 'Vallecas', 'Moratalaz']
Con 3,0 km: [('Vallecas', 'Moratalaz', 3.0, 3.16), ('Moratalaz', 'Vallecas', 3.0, 3.16)] [('Vallecas', 3.16, 3.0)]
w=2 NO óptimo: Vallecas -> Leganes 14.5 frente a 14.0
w=2 NO óptimo: Moratalaz -> Leganes 18.0 frente a 17.5| Nodo | h(n, Moratalaz) | Distancia real | ¿h ≤ real? |
|---|---|---|---|
| Almacen_Getafe | 13,60 | 16,0 | sí |
| Villaverde | 9,43 | 11,0 | sí |
| Usera | 7,21 | 9,0 | sí |
| Vallecas | 3,16 | 3,5 | sí |
| Retiro | 4,12 | 4,5 | sí |
A* llega a Moratalaz en 16,0 km expandiendo 4 nodos (va derecho por Villaverde y Vallecas) frente a los 8 de coste uniforme, que abre Leganés, Carabanchel, Usera y Arganzuela sin necesidad; sumando los 72 pares origen-destino del grafo ampliado, A* expande 223 nodos y coste uniforme 396. Con el "atajo" de 3,0 km la calle es más corta que la línea recta (3,16 km): la heurística deja de ser consistente y de ser admisible en Vallecas; en este grafo A* sigue acertando (perder la garantía no obliga a fallar), pero ya no está garantizado. Con h × 2 sí falla: de Vallecas a Leganés devuelve 14,5 km en lugar de 14,0, porque la heurística inflada le hace descartar el camino óptimo por parecer caro.
Retroalimentación
- Error típico: guardar en el montículo
(h, nodo)o(g, nodo)en lugar de(f, g, nodo); y olvidar que la comprobación de admisibilidad necesita las distancias reales (Dijkstra desde el objetivo), no las rectas. - La comprobación por aristas (consistencia) es la útil en producción: es local, barata y no depende del objetivo. Si un dato de calle viola la recta, casi siempre es un error de datos (como el "atajo" de Diego), no una carretera mágica.
- Variantes: usa la distancia Manhattan
|dx| + |dy|como heurística y comprueba si es admisible en este mapa (no lo es en general para calles en diagonal); mide expandidos conw = 1,2(A* "ponderado", que sacrifica garantía por velocidad y se usa en videojuegos).
- Ejercicio 4: minimax y alfa-beta en la guerra de precios a dos semanas
Recordatorio (03-03, secciones 4, 6 y 8). Minimax recorre el árbol de juego en profundidad y devuelve el valor que MAX puede garantizarse con un MIN perfecto. La poda alfa-beta da el mismo resultado sin visitar ramas que no pueden cambiar la decisión; su ahorro depende del orden de los hijos. minimax_generico(arbol, utilidades, nodo, es_max) trabaja sobre un árbol de diccionarios.
Enunciado. Marta amplía la guerra de precios del televisor de 03-03 a dos semanas: NovaMarket elige (mantener, bajar 5 %, bajar 10 %); el competidor responde (mantiene, iguala/baja 5 %, baja aún más); y en la segunda semana NovaMarket puede mantener su precio o ajustar (bajar otro 5 %). Las hojas son el margen acumulado de las dos semanas (miles de euros):
| NovaMarket | Competidor | mantener / ajustar |
|---|---|---|
| mantener | mantiene | 24 / 21 |
| mantener | baja 5 % | 10 / 11 |
| mantener | baja 10 % | 5 / 9 |
| bajar 5 % | mantiene | 27 / 22 |
| bajar 5 % | iguala | 15 / 13 |
| bajar 5 % | baja 10 % | 8 / 11 |
| bajar 10 % | mantiene | 25 / 18 |
| bajar 10 % | iguala | 11 / 9 |
| bajar 10 % | baja 15 % | 7 / 6 |
Construye el árbol como diccionarios, calcula el valor minimax de cada opción inicial y la recomendación; escribe alfabeta_generico con un contador de nodos visitados y compara: minimax, alfa-beta con el orden de la tabla, alfa-beta probando primero la opción que ganó en 03-03 (bajar_5), y alfa-beta con el orden perfecto (hijos ordenados por su valor). ¿Cambia la recomendación respecto al juego de una semana (3/5/4)?
Solución
ARBOL = {"inicio": ["mantener", "bajar_5", "bajar_10"],
"mantener": ["m/c_mantiene", "m/c_baja5", "m/c_baja10"],
"bajar_5": ["b5/c_mantiene", "b5/c_iguala", "b5/c_baja10"],
"bajar_10": ["b10/c_mantiene", "b10/c_iguala", "b10/c_baja15"]}
MARGEN = {"m/c_mantiene": (24, 21), "m/c_baja5": (10, 11), "m/c_baja10": (5, 9),
"b5/c_mantiene": (27, 22), "b5/c_iguala": (15, 13), "b5/c_baja10": (8, 11),
"b10/c_mantiene": (25, 18), "b10/c_iguala": (11, 9), "b10/c_baja15": (7, 6)}
UTIL = {}
for resp, (m, a) in MARGEN.items(): # tercer nivel: mantener / ajustar
ARBOL[resp] = [resp + "/mantener", resp + "/ajustar"]
UTIL[resp + "/mantener"], UTIL[resp + "/ajustar"] = m, a
def minimax_generico(arbol, util, nodo, es_max, cont):
cont[0] += 1
if nodo in util: return util[nodo]
valores = [minimax_generico(arbol, util, h, not es_max, cont) for h in arbol[nodo]]
return max(valores) if es_max else min(valores)
def alfabeta_generico(arbol, util, nodo, es_max, cont, alfa=-math.inf, beta=math.inf):
cont[0] += 1
if nodo in util: return util[nodo]
mejor = -math.inf if es_max else math.inf
for h in arbol[nodo]:
v = alfabeta_generico(arbol, util, h, not es_max, cont, alfa, beta)
if es_max: mejor, alfa = max(mejor, v), max(alfa, v)
else: mejor, beta = min(mejor, v), min(beta, v)
if alfa >= beta: break # PODA
return mejor
def ordenar(arbol, util, nodo, es_max):
"""Orden perfecto: hijos de mejor a peor para quien mueve (usa el propio minimax, solo para el experimento)."""
if nodo in util: return util[nodo]
vals = {h: ordenar(arbol, util, h, not es_max) for h in arbol[nodo]}
arbol[nodo] = sorted(arbol[nodo], key=vals.get, reverse=es_max)
return max(vals.values()) if es_max else min(vals.values())
for op in ARBOL["inicio"]:
print(f"{op:9s} -> garantiza {minimax_generico(ARBOL, UTIL, op, False, [0])}")
c = [0]; print("minimax:", minimax_generico(ARBOL, UTIL, "inicio", True, c), "nodos", c[0])
c = [0]; print("alfa-beta orden tabla:", alfabeta_generico(ARBOL, UTIL, "inicio", True, c), "nodos", c[0])
import copy
A2 = copy.deepcopy(ARBOL); A2["inicio"] = ["bajar_5", "mantener", "bajar_10"]
c = [0]; print("alfa-beta bajar_5 primero:", alfabeta_generico(A2, UTIL, "inicio", True, c), "nodos", c[0])
A3 = copy.deepcopy(ARBOL); ordenar(A3, UTIL, "inicio", True)
c = [0]; print("alfa-beta orden perfecto:", alfabeta_generico(A3, UTIL, "inicio", True, c), "nodos", c[0])mantener -> garantiza 9 bajar_5 -> garantiza 11 bajar_10 -> garantiza 7 minimax: 11 nodos 31 alfa-beta orden tabla: 11 nodos 28 alfa-beta bajar_5 primero: 11 nodos 25 alfa-beta orden perfecto: 11 nodos 17
La recomendación sigue siendo bajar un 5 % (garantiza 11.000 € en dos semanas), pero el orden de las otras dos cambia: mantener (9) adelanta a bajar 10 % (7), que en el juego de una semana era la segunda opción; con más horizonte, la bajada agresiva deja sin margen de maniobra en la segunda semana. En cuanto a la poda: el árbol tiene 31 nodos; alfa-beta con el orden de la tabla poda 3 (en bajar_10, cuando c_iguala vale 11 ≤ α = 11 ya no hace falta mirar c_baja15); probar primero la mejor jugada conocida sube el ahorro a 6 nodos, y el orden perfecto casi lo reduce a la mitad (17). Es la regla de 03-03: la poda vale lo que valga la ordenación.
Retroalimentación
- Error típico: usar
>en lugar de>=en la condición de poda (poda menos de lo debido) o actualizar α en nodos MIN y β en nodos MAX (poda de más y devuelve valores incorrectos). Comprueba siempre que alfa-beta devuelve el mismo valor que minimax. ordenarhace trampa (usa el resultado para ordenar); en un motor real la ordenación se basa en heurísticas baratas o en búsquedas anteriores más someras (profundización iterativa).- Variantes: añade a la raíz una cuarta opción "subir 5 %" con hojas que inventes y observa cuánto poda alfa-beta según dónde la coloques; convierte las hojas en valores esperados dando al competidor probabilidades (0,5 / 0,3 / 0,2) en lugar de suponerlo perfecto (expectimax) y compara la recomendación.
- Ejercicio 5: viajante con ventanas horarias, ascenso de colina frente a recocido
Recordatorio (03-04, secciones 3-7). El viajante se representa como una permutación de las entregas; la función objetivo suma la ruta cerrada con la matriz de distancias mínimas (MATRIZ del ejercicio 2). El ascenso de colina por intercambio se atasca en óptimos locales y se rescata con reinicios; el recocido simulado acepta empeoramientos con probabilidad e^(−Δ/T) y enfría poco a poco. Con 7 entregas la fuerza bruta (5.040 permutaciones) da el óptimo exacto para validar.
Enunciado. La furgoneta sale de Getafe a las 8:00 y hace 30 km/h de media (2 min/km). Dos clientes tienen entrega prioritaria: Vallecas antes de las 8:30 (minuto 30) y Carabanchel antes de las 8:50 (minuto 50). Define el coste de una ruta como minutos de la ruta cerrada + 3 × minutos totales de retraso en las prioritarias (llegar tarde cuesta el triple que conducir). (a) Calcula con fuerza bruta la ruta óptima y compárala con la de 39,0 km de 03-04: ¿cuánto se retrasa esa ruta y cuánto cuesta? (b) Resuelve con ascenso de colina simple, con 1/5/10/20 reinicios y con recocido simulado; para cada método, repite con 20 semillas y anota en cuántas alcanza el óptimo y cuántas evaluaciones usa. (c) Si el recocido queda por debajo del ascenso con reinicios, prueba a enfriar más despacio.
Solución
MIN_POR_KM, VENTANAS, PESO_RETRASO = 2.0, {"Vallecas": 30, "Carabanchel": 50}, 3.0
ENTREGAS = [n for n in GRAFO_CIUDAD if n != "Almacen_Getafe"]
def evaluar_ruta(ruta, dist=MATRIZ, origen="Almacen_Getafe", detalle=False):
reloj = retraso = 0.0; llegadas = {}; anterior = origen
for parada in ruta:
reloj += dist[anterior][parada] * MIN_POR_KM; llegadas[parada] = reloj
if parada in VENTANAS: retraso += max(0.0, reloj - VENTANAS[parada])
anterior = parada
reloj += dist[anterior][origen] * MIN_POR_KM
coste = reloj + PESO_RETRASO * retraso
return (coste, reloj, retraso, llegadas) if detalle else coste
def fuerza_bruta(entregas):
return min(((evaluar_ruta(list(o)), list(o)) for o in itertools.permutations(entregas)), key=lambda t: t[0])
def ascenso_colina(ruta):
actual, c_actual, evals = ruta[:], evaluar_ruta(ruta), 1
while True:
mejor, c_mejor = None, c_actual
for i in range(len(actual)):
for j in range(i + 1, len(actual)):
v = actual[:]; v[i], v[j] = v[j], v[i]; c = evaluar_ruta(v); evals += 1
if c < c_mejor: mejor, c_mejor = v, c
if mejor is None: return actual, c_actual, evals
actual, c_actual = mejor, c_mejor
def ascenso_con_reinicios(entregas, n, semilla=0):
rng, mejor, mejor_c, total = random.Random(semilla), None, math.inf, 0
for _ in range(n):
ini = entregas[:]; rng.shuffle(ini); r, c, ev = ascenso_colina(ini); total += ev
if c < mejor_c: mejor, mejor_c = r, c
return mejor, mejor_c, total
def recocido_simulado(ruta, T0=20.0, enfriamiento=0.995, T_min=0.05, semilla=0):
rng = random.Random(semilla); actual, c_actual = ruta[:], evaluar_ruta(ruta)
mejor, mejor_c, T, evals = actual[:], c_actual, T0, 1
while T > T_min:
i, j = sorted(rng.sample(range(len(actual)), 2))
vecino = actual[:]; vecino[i:j + 1] = reversed(vecino[i:j + 1]) # 2-opt
c_v = evaluar_ruta(vecino); evals += 1; delta = c_v - c_actual
if delta < 0 or rng.random() < math.exp(-delta / T):
actual, c_actual = vecino, c_v
if c_actual < mejor_c: mejor, mejor_c = actual[:], c_actual
T *= enfriamiento
return mejor, mejor_c, evals
opt_c, opt = fuerza_bruta(ENTREGAS)
print("Óptimo:", opt_c, opt, evaluar_ruta(opt, detalle=True)[1:])
print("Ruta 39,0 km:", evaluar_ruta(["Leganes", "Carabanchel", "Arganzuela", "Retiro", "Vallecas", "Usera", "Villaverde"], detalle=True))
rng = random.Random(7); ini = ENTREGAS[:]; rng.shuffle(ini)
print("Inicial:", evaluar_ruta(ini), "| ascenso simple:", ascenso_colina(ini)[1:])
for n in (1, 5, 10, 20):
res = [ascenso_con_reinicios(ENTREGAS, n, s) for s in range(20)]
print(f"ascenso {n:2d} reinicios: {sum(r[1] == opt_c for r in res)}/20 óptimos, ~{sum(r[2] for r in res)//20} evaluaciones")
for T0, enf in ((20, 0.995), (20, 0.998), (20, 0.999)):
res = [recocido_simulado(ini, T0, enf, semilla=s) for s in range(20)]
print(f"recocido T0={T0} enfr={enf}: {sum(r[1] == opt_c for r in res)}/20 óptimos, ~{sum(r[2] for r in res)//20} evaluaciones")Óptimo: 99.0 ['Villaverde', 'Vallecas', 'Usera', 'Carabanchel', 'Arganzuela', 'Retiro', 'Leganes'] (99.0, 0.0, {'Villaverde': 10.0, 'Vallecas': 25.0, 'Usera': 36.0, 'Carabanchel': 45.0, 'Arganzuela': 55.0, 'Retiro': 63.0, 'Leganes': 90.0})
Ruta 39,0 km: (132.0, 78.0, 18.0, {'Leganes': 9.0, 'Carabanchel': 18.0, 'Arganzuela': 28.0, 'Retiro': 36.0, 'Vallecas': 48.0, ...})
Inicial: 392.0 | ascenso simple: (109.0, 106)
ascenso 1 reinicios: 3/20 óptimos, ~90 evaluaciones
ascenso 5 reinicios: 15/20 óptimos, ~449 evaluaciones
ascenso 10 reinicios: 20/20 óptimos, ~888 evaluaciones
ascenso 20 reinicios: 20/20 óptimos, ~1818 evaluaciones
recocido T0=20 enfr=0.995: 8/20 óptimos, ~1197 evaluaciones
recocido T0=20 enfr=0.998: 14/20 óptimos, ~2994 evaluaciones
recocido T0=20 enfr=0.999: 19/20 óptimos, ~5990 evaluacionesLas ventanas cambian la ruta por completo: la óptima (99 min = 49,5 km) sale hacia Villaverde y Vallecas (minuto 25), sigue por Usera a Carabanchel (45), y solo después sube a Arganzuela y Retiro para volver por Leganés; cumple las dos ventanas con retraso cero y hay dos rutas empatadas (Arganzuela/Retiro en cualquier orden). La ruta más corta en km (78 min) llega a Vallecas en el minuto 48, 18 tarde: 78 + 3 × 18 = 132. Un ascenso simple desde una ruta aleatoria (392) se queda en 109 (Vallecas–Carabanchel–Retiro…, un óptimo local que ya cumple las ventanas pero da un rodeo); con 10 reinicios acierta siempre con menos de 900 evaluaciones (frente a 5.040 de la fuerza bruta). El recocido con los parámetros de 03-04 solo acierta 8 de 20 veces: la penalización crea un paisaje más "rugoso" (un intercambio puede sumar 3 × 20 minutos de golpe) y hace falta enfriar más despacio: con 0,999 acierta 19 de 20, a cambio de 6.000 evaluaciones. En este problema pequeño, el ascenso con reinicios es el método más eficiente.
Retroalimentación
- Error típico: contar el retraso solo en la última prioritaria o no acumularlo; y calcular la ruta abierta (olvidar la vuelta al almacén), lo que cambia el óptimo.
- Otro: comparar métodos con una semilla. Con una sola ejecución, el recocido de 0,995 puede acertar (la semilla 0 lo hace) y parecer igual de bueno; la tabla de 20 semillas es la única comparación honesta, la misma disciplina que la validación cruzada de 04-05.
- Variantes: penaliza también llegar demasiado pronto (el cliente no está); añade una tercera ventana y observa cuándo deja de existir una ruta sin retraso; usa la instancia de 15 direcciones de 03-04 (
generar_direcciones(15)) con ventanas para dos de ellas, donde la fuerza bruta ya no vale y solo queda comparar métodos entre sí.
- Ejercicio 6 (reto): asignación con capacidad y coste de ruta con un algoritmo genético
Recordatorio (03-04, secciones 8 y 9). En la asignación de pedidos, cada solución es una lista de etiquetas (un almacén por pedido), la restricción de capacidad se convierte en penalización (20 € por caja de exceso) y la búsqueda local cambia un pedido de almacén cada vez. Un algoritmo genético mantiene una población, selecciona por torneo, cruza y muta, y conserva a los mejores por elitismo. Validar en pequeño contra la fuerza bruta es obligatorio.
Enunciado. Sistemas ha añadido al modelo un coste de transporte por zona: cada pareja (almacén, zona) con al menos un pedido asignado abre una ruta con un coste fijo, según la tabla; los costes por caja y las capacidades (Getafe 32, Zaragoza 30) son los de 03-04 (generar_pedidos(20, semilla=11), 60 cajas). Representa cada solución como una lista de 20 bits (0 = Getafe, 1 = Zaragoza).
| Coste fijo de ruta (€) | centro | sur | noreste | levante |
|---|---|---|---|---|
| Getafe | 20 | 20 | 60 | 55 |
| Zaragoza | 55 | 70 | 20 | 30 |
- Escribe
coste_total(genes, pedidos)que devuelva(coste penalizado, envío, rutas, exceso). - Valida el enfoque en pequeño: con los pedidos P007-P014 (8 pedidos, 26 cajas) y capacidades 14/14, enumera las 2⁸ = 256 asignaciones y compara con la solución ingenua ("cada pedido a su almacén más barato").
- Implementa
algoritmo_genetico(pedidos, tam, generaciones, elitismo, p_mut, k, semilla)con cruce de un punto y mutación bit a bit; comprueba en 20 semillas cuántas veces alcanza el óptimo de los 8 pedidos. - Resuélvelo para los 20 pedidos con el genético (10 semillas), con ascenso de colina (20 reinicios) y, como los 2²⁰ ≈ 1 millón de asignaciones se enumeran en unos segundos, comprueba el óptimo exacto. Interpreta la solución en términos de rutas abiertas.
Solución
def generar_pedidos(n, semilla=11): # el de 03-04
rng = random.Random(semilla)
tarifa = {"centro": (4, 7), "sur": (3, 9), "noreste": (9, 4), "levante": (8, 5)} # €/caja (Getafe, Zaragoza)
pedidos = []
for i in range(1, n + 1):
zona = rng.choice(list(tarifa)); cajas = rng.choice([1, 1, 2, 3, 5])
pedidos.append({"id": f"P{i:03d}", "zona": zona, "cajas": cajas,
"coste_getafe": tarifa[zona][0] * cajas, "coste_zaragoza": tarifa[zona][1] * cajas})
return pedidos
PEDIDOS = generar_pedidos(20)
ALMACENES, CAPACIDAD, PENALIZACION = ["Getafe", "Zaragoza"], {"Getafe": 32, "Zaragoza": 30}, 20
COSTE_RUTA = {("Getafe", "centro"): 20, ("Getafe", "sur"): 20, ("Getafe", "noreste"): 60, ("Getafe", "levante"): 55,
("Zaragoza", "centro"): 55, ("Zaragoza", "sur"): 70, ("Zaragoza", "noreste"): 20, ("Zaragoza", "levante"): 30}
def coste_total(genes, pedidos, capacidad=None):
capacidad = capacidad or CAPACIDAD
envio, carga, rutas = 0, [0, 0], set()
for g, p in zip(genes, pedidos):
envio += p["coste_getafe"] if g == 0 else p["coste_zaragoza"]
carga[g] += p["cajas"]; rutas.add((ALMACENES[g], p["zona"]))
exceso = max(0, carga[0] - capacidad["Getafe"]) + max(0, carga[1] - capacidad["Zaragoza"])
fijo = sum(COSTE_RUTA[r] for r in rutas)
return envio + fijo + PENALIZACION * exceso, envio, fijo, exceso
def fuerza_bruta(pedidos, capacidad=None):
return min(((coste_total(g, pedidos, capacidad)[0], list(g)) for g in itertools.product([0, 1], repeat=len(pedidos))))
def rutas_de(genes, pedidos):
r = {}
for g, p in zip(genes, pedidos): r.setdefault((ALMACENES[g], p["zona"]), []).append(p["id"])
return r
def algoritmo_genetico(pedidos, tam=40, generaciones=60, elitismo=2, p_mut=0.05, k=3, semilla=0, capacidad=None):
rng, n = random.Random(semilla), len(pedidos)
apt = lambda ind: coste_total(ind, pedidos, capacidad)[0] # menor coste = más apto
poblacion = [[rng.randint(0, 1) for _ in range(n)] for _ in range(tam)]
historial = []
for _ in range(generaciones):
poblacion.sort(key=apt); historial.append(apt(poblacion[0]))
nueva = [ind[:] for ind in poblacion[:elitismo]] # elitismo
while len(nueva) < tam:
p1, p2 = (min(rng.sample(poblacion, k), key=apt) for _ in range(2)) # torneo
corte = rng.randint(1, n - 1)
hijo = p1[:corte] + p2[corte:] # cruce de un punto
nueva.append([1 - g if rng.random() < p_mut else g for g in hijo]) # mutación bit a bit
poblacion = nueva
mejor = min(poblacion, key=apt)
return mejor, apt(mejor), historial
def ascenso(genes, pedidos):
actual, f = genes[:], coste_total(genes, pedidos)[0]
while True:
vecinos = [actual[:i] + [1 - actual[i]] + actual[i + 1:] for i in range(len(actual))]
mejor = min(vecinos, key=lambda v: coste_total(v, pedidos)[0])
if coste_total(mejor, pedidos)[0] >= f: return actual, f
actual, f = mejor, coste_total(mejor, pedidos)[0]
# 2) validación en pequeño
sub, cap8 = PEDIDOS[6:14], {"Getafe": 14, "Zaragoza": 14}
c8, opt8 = fuerza_bruta(sub, cap8)
ing8 = [0 if p["coste_getafe"] <= p["coste_zaragoza"] else 1 for p in sub]
print("8 pedidos | fuerza bruta:", c8, opt8, coste_total(opt8, sub, cap8), rutas_de(opt8, sub))
print("8 pedidos | ingenua:", coste_total(ing8, sub, cap8))
print("GA en 8:", sum(algoritmo_genetico(sub, 20, 30, semilla=s, capacidad=cap8)[1] == c8 for s in range(20)), "/20 semillas")
# 4) los 20 pedidos
g, c, h = algoritmo_genetico(PEDIDOS, semilla=0)
print("GA 20 semilla 0:", c, coste_total(g, PEDIDOS), "| mejor en la generación", h.index(min(h)))
print("historial:", [(i, h[i]) for i in (0, 5, 10, 15, 20, 59)])
print("GA 10 semillas:", [algoritmo_genetico(PEDIDOS, semilla=s)[1] for s in range(10)])
print("GA pobl. 80, 100 gen, mut 0,08:", [algoritmo_genetico(PEDIDOS, 80, 100, p_mut=0.08, semilla=s)[1] for s in range(10)])
rng = random.Random(0)
print("Ascenso 20 reinicios:", sorted(ascenso([rng.randint(0, 1) for _ in range(20)], PEDIDOS)[1] for _ in range(20)))
c20, opt20 = fuerza_bruta(PEDIDOS)
print("Fuerza bruta 2^20:", c20, coste_total(opt20, PEDIDOS)); print(rutas_de(opt20, PEDIDOS))8 pedidos | fuerza bruta: 251 [0, 1, 1, 0, 1, 0, 0, 0] (251, 126, 125, 0) {('Getafe', 'sur'): ['P007', 'P010', 'P014'], ('Zaragoza', 'centro'): ['P008', 'P011'], ('Zaragoza', 'levante'): ['P009'], ('Getafe', 'centro'): ['P012', 'P013']}
8 pedidos | ingenua: (346, 96, 70, 9)
GA en 8: 16 /20 semillas
GA 20 semilla 0: 402 (402, 257, 145, 0) | mejor en la generación 15
historial: [(0, 517), (5, 496), (10, 435), (15, 402), (20, 402), (59, 402)]
GA 10 semillas: [402, 435, 402, 402, 402, 402, 402, 402, 402, 402]
GA pobl. 80, 100 gen, mut 0,08: [402, 402, 402, 402, 402, 402, 402, 402, 402, 402]
Ascenso 20 reinicios: [402, 402, 402, 402, 402, 402, 402, 435, 435, 435, 435, 435, 493, 496, 506, 581, 590, 602, 608, 608]
Fuerza bruta 2^20: 402 (402, 257, 145, 0)
{('Zaragoza', 'levante'): ['P001', 'P002', 'P004', 'P006', 'P009', 'P019'], ('Getafe', 'sur'): ['P003', 'P005', 'P007', 'P010', 'P014', 'P017', 'P018'], ('Getafe', 'centro'): ['P008', 'P011', 'P012', 'P013'], ('Zaragoza', 'centro'): ['P015', 'P020'], ('Zaragoza', 'noreste'): ['P016']}En pequeño, la ingenua es infactible (9 cajas de exceso, 346 €) y el óptimo (251 €) abre cuatro rutas, incluida una Zaragoza–centro cara (55 €) porque mover P008 y P011 (10 cajas de centro) es la única forma de respetar 14 cajas en Getafe; el genético con población 20 lo encuentra en 16 de 20 semillas (con 256 soluciones, la población inicial ya cubre el 8 % del espacio, así que aquí es un martillo grande para un clavo pequeño: sirve para validar la implementación, no para presumir). En los 20 pedidos, el óptimo exacto es 402 € = 257 € de envío (la misma asignación factible de 03-04) + 145 € de las cinco rutas; el coste fijo no cambia la asignación porque la capacidad ajustada ya obliga a abrir Zaragoza–centro, pero sí cambia el paisaje: el ascenso de colina solo llega al óptimo en 7 de 20 reinicios (cerrar o abrir una ruta exige mover varios pedidos a la vez, y el vecindario de un bit no lo ve), mientras que el genético lo alcanza en 9 de 10 semillas con la configuración básica y en 10 de 10 con más población y mutación, con unas 2.400-8.000 evaluaciones frente al millón de la fuerza bruta.
Retroalimentación
- Error típico: mutar con probabilidad
p_mutal individuo (un bit) en lugar de a cada bit; ambas funcionan, pero cambian el significado del parámetro. Otro: olvidar el elitismo y ver cómo el mejor coste sube de una generación a otra. - Si la penalización por caja fuera menor que el coste de una ruta (por ejemplo, con capacidades 36/36 el óptimo prefiere pagar 2 cajas de exceso, 40 €, antes que abrir Zaragoza–centro por 55 €), el algoritmo hace lo que dice la función objetivo, no lo que Diego quiere: cuando la capacidad es dura, sube la penalización hasta que ninguna solución infactible salga a cuenta.
- Variantes: sustituye el cruce de un punto por cruce uniforme (cada bit del padre 1 o 2 al azar); añade un tercer almacén (representación con 0/1/2); mide, para tamaño 30 y 40 pedidos, el tiempo del genético frente al de la fuerza bruta (2³⁰ ya es inabordable).
Errores Comunes y Consejos
- Copiar el código de 03-02/03-04 sin releer los detalles (test del objetivo al sacar del montículo,
padressobrescribible en Dijkstra,>=en la poda): los errores sutiles del módulo 3 reaparecen aquí. Ten a mano las trazas de aquellas lecciones para comparar. - Validar solo con una ejecución. En todo lo estocástico (reinicios, recocido, genético) compara con muchas semillas y contra la fuerza bruta en una versión reducida; sin eso no sabes si tu implementación es correcta o afortunada.
- Mezclar unidades en la función objetivo (km, minutos, euros): decide una unidad, conviértelo todo a ella (aquí minutos en el ejercicio 5, euros en el 6) y documenta los factores de conversión (
MIN_POR_KM,PESO_RETRASO). - Penalizaciones mal calibradas: demasiado bajas y el algoritmo "compra" la infracción; demasiado altas y aplastan las diferencias reales. Comprueba siempre que la mejor solución encontrada tiene exceso 0 (o que la infracción es deliberada).
- No comprobar la heurística: la consistencia por aristas es un test barato que debería ejecutarse cada vez que cambian los datos del mapa.
- Consejo: guarda cada ejercicio como un script con una función
main()y una comprobación (assert coste == 402); son las pruebas de 07-04 aplicadas a algoritmos.
Conclusión
Has vuelto a recorrer el módulo 3 sin que la lección te llevara de la mano: BFS y DFS con una calle cortada (Vallecas a 3 tramos por Usera; tres cortes para aislarla), Dijkstra con la reconstrucción de los 7 caminos mínimos y el descubrimiento de que Usera sería el mejor punto de reparto (44 km de suma frente a 70,5), A* hacia Moratalaz con 4 nodos expandidos frente a 8, la comprobación de que un "atajo" de 3,0 km rompe la admisibilidad y que una heurística inflada hace perder el óptimo (14,5 frente a 14,0), minimax a dos semanas (bajar 5 % sigue garantizando más, 31 nodos que la poda deja en 28, 25 o 17 según el orden), el viajante con ventanas horarias (99 minutos frente a los 132 de la ruta más corta en km, con el ascenso con reinicios ganando al recocido salvo enfriamiento lento) y el genético para la asignación con coste de ruta (402 €, validado contra 256 y contra el millón de asignaciones). El hilo común: representar bien, definir la función objetivo con sus unidades y penalizaciones, y validar contra un óptimo conocido o contra muchas semillas.
Los siguientes ejercicios cambian de herramienta pero no de disciplina: en 09-02, Prácticas de Machine Learning, trabajarás con los generadores de NovaMarket del módulo 4 (limpieza de un lote sucio, un pipeline de devoluciones con una característica nueva, previsión de demanda con TimeSeriesSplit, segmentación de clientes y ajuste de umbral con comprobación de equidad), siempre con una línea base y una comparación honesta.
Fundamentos de Inteligencia Artificial (IA)
Módulo 1: Introducción a la Inteligencia Artificial
Módulo 2: Principios Básicos de la IA
- Conceptos Fundamentales: Agentes, Entornos y Racionalidad
- Tipos de Inteligencia Artificial
- Los Datos como Materia Prima de la IA
- Ética y Consideraciones en IA
Módulo 3: Algoritmos en IA
- Introducción a los Algoritmos
- Algoritmos de Búsqueda
- Búsqueda con Adversario: Juegos y Minimax
- Algoritmos de Optimización
Módulo 4: Aprendizaje Automático (Machine Learning)
- Conceptos Básicos de Machine Learning
- Tipos de Aprendizaje Automático
- Preparación de Datos y Características
- Algoritmos de Machine Learning
- Evaluación y Validación de Modelos
- Sobreajuste, Regularización y Ajuste de Hiperparámetros
Módulo 5: Redes Neuronales y Deep Learning
- Introducción a las Redes Neuronales
- Arquitectura de Redes Neuronales
- Cómo Aprende una Red: Descenso del Gradiente y Retropropagación
- Deep Learning y sus Aplicaciones
- Transformers, Grandes Modelos de Lenguaje e IA Generativa
Módulo 6: Lógica y Sistemas Expertos
- Lógica en IA
- Sistemas Expertos
- Razonamiento con Incertidumbre: Probabilidad y Redes Bayesianas
- Aplicaciones de Sistemas Expertos
Módulo 7: Herramientas y Lenguajes de Programación en IA
- Lenguajes de Programación para IA
- Python Científico: NumPy, pandas y Matplotlib
- Herramientas y Librerías Populares
- Entornos de Desarrollo
Módulo 8: Proyectos y Casos de Estudio
Módulo 9: Ejercicios y Prácticas
- Ejercicios de Algoritmos
- Prácticas de Machine Learning
- Proyectos de Redes Neuronales
- Proyecto Integrador: de la Idea al Prototipo