Algoritmos Avanzados en Python

Lectura final y revisión de temas clave

PyEnvíos empezó con cinco problemas: buscar en un catálogo de 100,000 SKUs, saber si un algoritmo escala, decidir qué paquetes caben en la camioneta, moverse por la ciudad y cruzar un barrio con edificios. Cada uno se resolvió con una técnica distinta, pero todas comparten un método: modelar el problema, contar operaciones y elegir el algoritmo cuyo crecimiento aguanta el tamaño real de los datos. Esta lectura junta las piezas antes del proyecto final.

1. Tabla de repaso

2. Las cifras que resumen el curso

Los conteos del curso no dependen de la máquina y cuentan la historia completa. Buscar un SKU: 50,526 comparaciones de media con búsqueda lineal contra 15.7 con binaria. Detectar repetidos en 2000 pedidos: 1,999,000 comparaciones contra 2000 operaciones. Calcular fib(30): 2,692,537 llamadas contra 31 cálculos con lru_cache. La mochila de 50 kg: 625,430 llamadas ingenuas contra 770 estados memoizados, para el mismo óptimo de 10,581 MXN, mientras el voraz por valor/peso se queda en 10,231. En la cuadrícula, A* con Manhattan expande 282 celdas donde Dijkstra expande 635, con el mismo costo de 58.

El caso más extremo es el orden de las paradas. Con fuerza bruta el número de rutas es $n!$; Held-Karp guarda una solución por cada par (subconjunto visitado, última parada), es decir $n \cdot 2^{n-1}$ estados:

import math

for n in (6, 11, 20):
    print(n, f"{math.factorial(n):,}", f"{n * 2 ** (n - 1):,}")
# 6 720 192
# 11 39,916,800 11,264
# 20 2,432,902,008,176,640,000 10,485,760

Cada estado revisa hasta $n$ paradas previas, de ahí el $O(n^2 2^n)$. Sigue siendo exponencial, pero con 20 paradas pasa de trillones de rutas a unos diez millones de estados.

3. Cómo elegir un algoritmo

1. Modela el problema. ¿Es una búsqueda en datos ordenados, un grafo, una decisión de sí o no por elemento? Nombrar la estructura casi siempre señala la familia de algoritmos.
2. Estima el tamaño real. Con $n = 20$ casi cualquier cosa sirve; con $n$ = un millón, solo $O(n)$ u $O(n \log n)$.
3. Busca la propiedad que habilita el atajo: orden (binaria), monotonía (binaria sobre la respuesta), subproblemas repetidos (memoización), pesos no negativos (Dijkstra), heurística admisible (A*).
4. Cuenta antes de cronometrar. Un contador en la operación clave dice más que un timeit.
5. Verifica contra una versión lenta y obvia. La fuerza bruta en un caso pequeño, o networkx en un grafo, atrapa los errores que la lectura no ve.

4. Errores frecuentes

• Buscar con binaria en datos sin ordenar, o con in en una lista que ya está ordenada.
• Un in sobre lista dentro de un ciclo, que vuelve cuadrático un algoritmo lineal.
• Recursión sin memoización con subproblemas repetidos, o recursión tan profunda que supera el límite de 1000 que Python trae por defecto.
• Usar BFS para minimizar minutos, o Dijkstra con pesos negativos.
• Una heurística de A* que sobreestima y entrega rutas que no son óptimas.
• Confiar en una heurística de rutas sin medir su distancia al óptimo: el vecino más cercano quedó 34.6 % arriba en 6 paradas.

5. Caminos para seguir

• Floyd-Warshall: distancias entre todos los pares en $O(V^3)$, una alternativa a correr Dijkstra desde cada nodo.
• Flujo máximo y corte mínimo: capacidad de una red de calles o de una cadena de suministro.
• Programación lineal y entera: asignación de recursos con restricciones, con bibliotecas como PuLP o SciPy.
• Google OR-Tools: resuelve problemas de ruteo de vehículos con capacidades y ventanas de horario, la versión industrial del proyecto de este curso.

Cierre

Antes de abrir el proyecto, toma la tabla de la sección 1 y, para cada fila, escribe de memoria el conteo que la respalda. Si alguna cifra no la puedes explicar, vuelve a su notebook: el proyecto las usa casi todas.