Algoritmos Avanzados en Python

1. En la cuadrícula de PyEnvíos, Dijkstra y A* con distancia Manhattan encuentran un camino de 58 pasos, pero Dijkstra expande 635 celdas y A* 282. ¿Qué explica la diferencia?

• A* usa una cola normal (FIFO) en lugar de una cola de prioridad
• A* prioriza las celdas por g + h, así que deja de explorar celdas que se alejan de la meta
• A* permite moverse en diagonal y por eso visita menos celdas
• A* descarta los caminos de más de 58 pasos antes de empezar

A* ordena la cola por f = g + h: la heurística estima lo que falta y concentra la búsqueda hacia la meta. Con h = 0, A* es exactamente Dijkstra y explora en todas direcciones.

2. Si la camioneta solo se mueve en cuatro direcciones con costo 1 y se multiplica la heurística Manhattan por 3, A* expande 91 celdas pero entrega un camino de 60 pasos en vez de 58. ¿Por qué?

• Multiplicar por 3 convierte a A* en Dijkstra
• La heurística inflada es más informada y por eso encuentra caminos más largos pero correctos
• heapq no admite prioridades mayores que el tamaño de la cuadrícula
• La heurística inflada sobreestima el costo que falta, deja de ser admisible y A* pierde la garantía de encontrar el óptimo

Una heurística admisible nunca sobreestima el costo restante; 3 × Manhattan sí lo sobreestima, así que A* pierde la garantía de optimalidad a cambio de explorar menos.

3. Un catálogo ordenado pasa de 1,000 a 1,000,000 de SKUs. ¿Cómo cambia el peor caso de la búsqueda binaria?

• Pasa de unas 10 a unas 20 comparaciones: multiplicar n por mil suma alrededor de 10
• Se multiplica por mil, igual que la búsqueda lineal
• Se duplica el número de comparaciones por cada SKU nuevo
• No cambia: la búsqueda binaria siempre hace una sola comparación

El peor caso es el techo de log₂(n + 1): cada comparación parte el intervalo a la mitad. Multiplicar los datos por mil (unas 2¹⁰ veces) añade unas 10 comparaciones: de 10 a 20.

4. En una lista ordenada de precios, bisect_left(precios, 450) devuelve 31 y bisect_right(precios, 450) devuelve 34. ¿Qué se puede concluir?

• El precio 450 no está en la lista; 31 y 34 son posiciones aproximadas
• Hay 34 precios iguales a 450
• El precio 450 aparece 3 veces, en las posiciones 31, 32 y 33
• La lista no está ordenada, porque bisect_left y bisect_right deberían coincidir

bisect_left da el punto de inserción antes del primer 450 y bisect_right el punto después del último. La diferencia, 3, es cuántas veces aparece 450, sin recorrer la lista.

5. Para hallar la capacidad mínima de la camioneta que permite entregar los paquetes en orden en 3 viajes, se aplica búsqueda binaria entre 13 y 124 kg. ¿Qué propiedad hace válido este método?

• Los pesos de los paquetes están ordenados de menor a mayor
• La condición es monótona: si una capacidad alcanza, cualquier capacidad mayor también alcanza
• La capacidad mínima siempre es el promedio entre el paquete más pesado y el peso total
• El rango 13-124 tiene una cantidad de valores que es potencia de 2

La búsqueda sobre la respuesta funciona cuando la condición es monótona: si una capacidad alcanza para 3 viajes, cualquier capacidad mayor también alcanza. Así cada prueba descarta la mitad del rango.