Cerramos el módulo 2 con una promesa: dejar de describir sistemas y empezar a construirlos. Esta lección es el primer escalón de esa construcción. Antes de programar cómo un agente encuentra por sí mismo el camino hacia su meta (03-02), cómo decide frente a un adversario (03-03) o cómo optimiza cuando el espacio de soluciones es inabarcable (03-04), necesitamos hablar con precisión de la herramienta común a todo ello: el algoritmo. Veremos qué es exactamente un algoritmo y qué propiedades debe cumplir, las cuatro formas habituales de expresarlo, por qué la IA se puede resumir como "algoritmos + datos + representación", qué estructuras de datos usan una y otra vez los algoritmos de IA, y cómo se mide el coste de un algoritmo con la notación O grande. Con esas herramientas retomaremos la formulación de problemas de 02-01 y formalizaremos como grafo el problema de rutas de NovaMarket: definiremos el grafo de barrios que la furgoneta de Getafe recorrerá durante todo el módulo y comprobaremos, con un programa de fuerza bruta, por qué "probar todas las rutas" deja de ser una opción en cuanto Diego añade unas pocas entregas más. Esa explosión combinatoria es la razón de ser de todo lo que viene después.

1. Qué es un algoritmo y qué propiedades debe cumplir
2. Formas de expresar un algoritmo: lenguaje natural, pseudocódigo, diagrama de flujo, código
3. La IA como algoritmos + datos + representación
4. Estructuras de datos básicas en IA: listas, colas, pilas, diccionarios y grafos
5. Complejidad y notación O grande, a nivel intuitivo
6. La explosión combinatoria: cuántas rutas puede hacer la furgoneta de Getafe
7. Familias de algoritmos en IA y dónde se ven en el curso
8. Del problema al grafo: GRAFO_CIUDAD, el mapa que usará todo el módulo
9. Ejemplo en Python: representar el grafo, recorrer vecinos y enumerar rutas por fuerza bruta

Un algoritmo es una secuencia finita y precisa de pasos que, a partir de unos datos de entrada, produce un resultado de salida. La palabra viene del matemático persa al-Juarismi (siglo IX), pero la idea es la de cualquier receta o instrucción bien escrita: alguien (o algo) que no entiende el problema puede seguir los pasos y obtener el resultado correcto. Marta lo resume así en las reuniones con Diego: "un algoritmo es una receta que un ordenador puede seguir sin preguntar nada".

Para que una secuencia de pasos merezca el nombre de algoritmo debe cumplir cinco propiedades clásicas:

Dos observaciones importantes para lo que viene:

• Un algoritmo es independiente del lenguaje en que se escribe. La búsqueda en anchura de 03-02 es el mismo algoritmo en Python, en Java o explicada en una pizarra.
• Muchas "recetas" útiles en IA no garantizan el mejor resultado, sino uno bueno en un tiempo razonable. Siguen siendo algoritmos (son finitos, precisos, efectivos), pero se llaman heurísticos o aproximados. Distinguir cuándo se puede exigir la solución óptima y cuándo hay que conformarse con una buena es una de las lecciones centrales de este módulo.

El mismo algoritmo se puede escribir con distintos grados de formalidad. Vamos a expresar de cuatro maneras una regla sencilla del caso 6 (asignación de pedidos a almacenes): decidir desde qué almacén se sirve un pedido.

Lenguaje natural (cómo lo explicaría Diego): "Si el almacén más cercano al cliente tiene el producto, sale de ahí. Si no, sale del otro almacén. Si ninguno lo tiene, el pedido queda pendiente de stock".

Pseudocódigo (más preciso, sin sintaxis de ningún lenguaje):

Diagrama de flujo (visual; útil para validar la lógica con personas no técnicas):

Código (ejecutable; la única forma que el ordenador entiende):

Explicación línea a línea: stock es un diccionario de diccionarios (almacén → producto → unidades). El método .get(producto, 0) devuelve 0 si el producto no existe en ese almacén, lo que evita un error y trata "no está en el catálogo del almacén" igual que "hay cero unidades". Las dos condiciones if siguen exactamente el orden del pseudocódigo. Fíjate en que este algoritmo cumple las cinco propiedades: entrada (producto, stock, almacén más cercano), salida (un nombre), precisión (no hay ambigüedad), finitud (como mucho dos comparaciones) y efectividad (cada paso es trivial).

Es habitual usar las cuatro formas en un mismo proyecto: lenguaje natural para acordar la regla con negocio, diagrama de flujo para revisarla, pseudocódigo para diseñarla y código para ejecutarla. En este curso emplearemos sobre todo pseudocódigo breve, diagramas mermaid y código Python.

En 01-02 adoptamos la definición de IA como "sistemas que actúan racionalmente" y en 02-01 describimos esos sistemas como agentes. Desde el punto de vista de la ingeniería, todo agente de IA se construye con tres ingredientes:

• Algoritmos: los procedimientos que deciden (buscar un camino, elegir una jugada, ajustar un modelo, encadenar reglas).
• Datos: la materia prima de 02-03, tanto los que describen el problema (el mapa, las entregas, el stock) como los que sirven para aprender (historiales de pedidos, reseñas).
• Representación: la forma en que traducimos el mundo a estructuras que un algoritmo pueda manipular. Un barrio pasa a ser un nodo; una calle, una arista con un número; un pedido, una fila con columnas; una jugada, un cambio en una lista.

De los tres, la representación es el ingrediente que más se subestima. El mismo algoritmo de búsqueda funciona sobre un mapa de ciudad, sobre un tablero de tres en raya o sobre las causas posibles de una incidencia siempre que representemos cada uno de esos mundos como estados y transiciones. Por eso 02-01 insistía en la formulación del problema: elegir la representación es media solución. La regla de la sección 2 solo funciona porque decidimos representar el stock como diccionario de diccionarios; con otra representación (una lista de textos libres) el mismo algoritmo sería impracticable.

Las estructuras de datos son las "formas" en que guardamos la información para que los algoritmos la usen con eficiencia. En este módulo aparecerán una y otra vez cinco de ellas, todas disponibles en la biblioteca estándar de Python.

Veamos las tres primeras en acción, con un ejemplo mínimo de cada una:

deque (cola de doble extremo) es la forma correcta de hacer una cola en Python: popleft() es inmediato, mientras que lista.pop(0) obliga a desplazar todos los elementos y se vuelve lento con muchos pedidos. La pila no necesita nada especial: append y pop sobre una lista ya operan por el final. Guarda mentalmente esta pareja cola/pila: en 03-02 verás que cambiar una por otra transforma la búsqueda en anchura en búsqueda en profundidad, sin tocar nada más.

Un grafo es la estructura estrella de este módulo. Se compone de nodos (también llamados vértices) y aristas que los conectan; si cada arista lleva un número (distancia, tiempo, coste) hablamos de grafo ponderado; si las aristas se pueden recorrer en ambos sentidos, es no dirigido. El mapa de una ciudad es un grafo ponderado no dirigido: barrios como nodos, tramos de carretera como aristas con su longitud.

Hay dos representaciones habituales:

En IA casi siempre se usa la lista de adyacencia, porque los algoritmos de búsqueda preguntan una y otra vez "¿a dónde puedo ir desde aquí?". En Python se escribe como un diccionario cuyo valor es una lista de tuplas (vecino, peso). Lo construiremos en la sección 8.

Dos algoritmos correctos pueden diferir enormemente en el tiempo que tardan. La complejidad temporal describe cómo crece el tiempo de ejecución al crecer el tamaño de la entrada (n), y la notación O grande (big-O) resume ese crecimiento quedándose con el término dominante e ignorando constantes: no dice "tarda 3 segundos", sino "si duplico n, el tiempo se duplica" (O(n)) o "se cuadruplica" (O(n²)). Es la herramienta con la que Marta responde a la pregunta favorita de Diego: "¿y esto qué pasará cuando tengamos el doble de pedidos?".

Tres ideas para quedarse:

• Hasta O(n log n) todo es "escalable": duplicar los datos cuesta poco más del doble.
• O(n²) es aceptable para miles de elementos, incómodo para cientos de miles e imposible para millones.
• O(2ⁿ) y O(n!) son la frontera de lo imposible: a partir de unas pocas decenas de elementos ningún ordenador del mundo termina. Es exactamente lo que ocurre con las rutas de reparto, como vamos a comprobar.

También existe la complejidad espacial (cuánta memoria hace falta); en 03-02 veremos que algunos algoritmos de búsqueda son rápidos pero devoran memoria, y otros al revés.

Volvamos a la furgoneta que sale del almacén de Getafe. Si tiene que hacer n entregas y volver, ¿cuántos órdenes distintos puede seguir? La primera parada se elige entre n, la segunda entre las n−1 restantes, y así sucesivamente: n × (n−1) × … × 1 = n! (factorial de n). La tabla siguiente, calculada con math.factorial, muestra cuántas rutas hay y cuánto tardaría en probarlas todas un ordenador capaz de evaluar un millón de rutas por segundo:

Una furgoneta de NovaMarket hace habitualmente entre 30 y 60 entregas por jornada. Para 30 entregas, 30! es un número de 33 cifras: ni siquiera con todos los ordenadores del planeta durante toda la edad del universo se probarían todas las rutas. Y esto es un solo vehículo en una sola ciudad; NovaMarket mueve ~3.000 pedidos diarios.

De aquí nacen las dos estrategias que estructuran el resto del módulo:

• Búsqueda inteligente (03-02): no enumerar todas las soluciones, sino construirlas paso a paso desde el estado inicial, descartando pronto lo que no puede ser bueno y usando heurísticas (estimaciones informadas, como la distancia en línea recta) para dirigir la exploración hacia la meta.
• Optimización aproximada (03-04): cuando ni siquiera eso es viable, partir de una solución cualquiera e ir mejorándola, aceptando una ruta muy buena en segundos en lugar de la ruta perfecta en siglos.

Diego lo formuló a su manera: "No necesito la mejor ruta del mundo; necesito una ruta un 15 % mejor que la que hacen mis conductores de memoria, y la necesito antes de las 8 de la mañana". Esa frase es, en el fondo, la definición de una heurística útil.

Los algoritmos de IA se pueden agrupar en cuatro grandes familias según la pregunta a la que responden. La tabla sirve también de mapa del resto del curso:

Las fronteras no son rígidas: entrenar un modelo de aprendizaje es, por dentro, un problema de optimización (lo veremos al final de 03-04), y muchos sistemas modernos combinan las cuatro familias. Pero la clasificación ayuda a elegir el punto de partida: cuando Diego describe un problema, la primera pregunta de Marta es siempre "¿esto es buscar un camino, optimizar una asignación, aprender de un histórico o razonar con reglas?".

Retomemos la formulación de 02-01 y apliquémosla al problema más simple del planificador de rutas: llevar la furgoneta desde el almacén de Getafe hasta un barrio concreto por el camino más corto. Los cinco componentes quedan así:

Con esta formulación, el espacio de estados es exactamente un grafo: cada barrio es un nodo, cada carretera entre barrios es una arista y su longitud es el peso. Vamos a fijar el mapa (ficticio, con distancias inventadas pero verosímiles) del sur de Madrid que servirá para todo el módulo: el almacén de Getafe y siete barrios donde NovaMarket hace reparto propio.

Ocho nodos, doce aristas, distancias en kilómetros. Es un grafo pequeño a propósito: lo bastante rico para que existan varios caminos entre dos puntos (y no siempre gane el que tiene menos tramos), y lo bastante pequeño para que puedas seguir a mano las trazas de 03-02. En 03-02 añadiremos las coordenadas de cada nodo para calcular distancias en línea recta, y en 03-04 lo usaremos como base del problema del viajante.

Cada clave es un nodo y su valor, la lista de tuplas (vecino, kilómetros). Como el grafo es no dirigido, cada carretera aparece dos veces (en la lista de cada extremo): ("Leganes", 4.5) está en Almacen_Getafe y ("Almacen_Getafe", 4.5) está en Leganes. Es un pequeño coste de duplicación a cambio de que la pregunta "¿a dónde puedo ir desde aquí?" se responda con una sola consulta al diccionario.

Salida:

vecinos es O(1): una consulta al diccionario. distancia_directa recorre la lista de vecinos de a (como mucho cuatro elementos aquí), que es el inconveniente de la lista de adyacencia mencionado en la sección 4; en un mapa real, con pocos vecinos por cruce, sigue siendo despreciable. Observa que Usera y Retiro no están conectados directamente (None): para ir de uno a otro hay que pasar por Arganzuela o por Vallecas, y decidir cuál conviene es precisamente lo que hará la búsqueda de 03-02.

Ahora el problema completo del reparto: la furgoneta sale del almacén, visita una lista de barrios (uno por entrega) y vuelve. La estrategia más ingenua es la fuerza bruta: generar todos los órdenes posibles, calcular el coste de cada uno y quedarse con el menor. itertools.permutations genera exactamente esos n! órdenes.

Para simplificar (y porque todavía no sabemos calcular el camino más corto entre dos barrios no vecinos), en esta primera versión exigimos que cada tramo de la ruta sea una carretera directa del grafo; si dos paradas consecutivas no están conectadas, la ruta se declara imposible con coste infinito. En 03-04 levantaremos esa restricción usando los caminos más cortos de 03-02.

Salida:

Cómo funciona el código:

• zip(ruta, ruta[1:]) empareja cada parada con la siguiente; es la forma idiomática en Python de recorrer "tramos".
• itertools.permutations(entregas) produce cada orden posible como tupla, sin cargarlos todos en memoria a la vez (es un generador), pero sí los recorre todos: 24, 120 y 5.040 iteraciones.
• La ruta se construye concatenando tuplas: (origen,) + orden + (origen,).
• Guardamos el mejor coste visto hasta el momento y lo sustituimos solo si aparece uno menor: el patrón clásico de "quedarse con el mínimo".

Lo que enseña la salida es más importante que la ruta concreta:

1. El número de rutas evaluadas es exactamente n!, independientemente de lo que sepa el algoritmo del problema. Con 7 entregas ya son 5.040 evaluaciones; con 12 serían 479 millones.
2. Casi todas las rutas evaluadas son imposibles (2 factibles de 120): la fuerza bruta no sabe nada del grafo, así que gasta el 98 % del esfuerzo en combinaciones que un conductor descartaría al instante. Los algoritmos de búsqueda de 03-02 evitan esto construyendo las rutas paso a paso solo a través de aristas válidas.
3. Las dos rutas factibles de cada caso son la misma en los dos sentidos: la fuerza bruta ni siquiera reconoce esa simetría, un ejemplo más de conocimiento del problema que un algoritmo inteligente puede explotar.

Prueba a añadir un import time y medir cuánto tarda el caso de 7 entregas (en un portátil actual, unas milésimas de segundo) y calcula, con la tabla de la sección 6, cuánto tardaría con 15. Ese cálculo es la mejor motivación posible para la siguiente lección.

• Confundir "algoritmo" con "código": el código es una de las formas de expresar un algoritmo. Diseña primero en pseudocódigo o diagrama, y programa después; ahorrarás muchos errores de lógica.
• Usar lista.pop(0) como cola: funciona, pero es O(n) en cada extracción. Usa collections.deque y popleft(); con miles de nodos en la frontera de una búsqueda la diferencia es enorme.
• Olvidar la simetría al construir un grafo no dirigido a mano: si añades ("Leganes", 4.5) a Almacen_Getafe pero no el recíproco, la furgoneta podrá ir a Leganés pero nunca volver. Una comprobación automática (recorrer todas las aristas y verificar que existe la inversa con el mismo peso) evita horas de depuración.
• Fiarse de la intuición sobre la complejidad: "son solo 12 entregas" suena poco, y son 479 millones de rutas. Calcula siempre el tamaño del espacio de soluciones antes de elegir estrategia.
• Interpretar mal la notación O grande: O(n²) no significa "lento", significa "crece cuadráticamente". Para 100 elementos puede ser instantáneo; el problema aparece al escalar. Al revés, un O(n log n) con constantes enormes puede ser más lento que un O(n²) sencillo para entradas pequeñas.
• Elegir la representación sin pensar en las operaciones: antes de decidir entre lista y matriz de adyacencia (o entre lista y diccionario), pregúntate qué operación va a hacer el algoritmo millones de veces y optimiza esa.

Diego propone esta regla para elegir la siguiente parada: "ir siempre a la entrega que más prisa tenga, y si hay empate, a la que le parezca mejor al conductor". Indica cuál de las cinco propiedades de la sección 1 no cumple y reescríbela (en pseudocódigo) para que sí las cumpla todas.

Escribe una función es_simetrico(grafo) que devuelva True si para toda arista (a, b, d) existe la arista (b, a, d). Comprueba GRAFO_CIUDAD; supón después que se abre una nueva vía rápida directa entre Almacen_Getafe y Usera de 8,0 km, añádela (en ambos sentidos) y vuelve a ejecutar la fuerza bruta con las 4 entregas ["Leganes", "Carabanchel", "Usera", "Villaverde"]. ¿Cuántas rutas factibles hay ahora, cuáles son y cuál es la mejor? Modifica fuerza_bruta (o escribe un bucle aparte) para imprimir todas las rutas factibles.

Usando math.factorial, escribe un programa que, para n de 5 a 20 entregas, imprima el número de rutas y el tiempo estimado suponiendo 10 millones de evaluaciones por segundo (un ordenador diez veces más rápido que el de la sección 6). ¿A partir de qué n el tiempo supera una jornada laboral de 8 horas? ¿Cambia mucho la respuesta con un ordenador diez veces más rápido?

Solución 1. No cumple la precisión: "la que le parezca mejor al conductor" es ambiguo, dos conductores harían cosas distintas y un programa no puede ejecutarlo. Una versión precisa:

El desempate final por identificador garantiza que nunca queda una decisión sin definir. Nota que ahora sí es un algoritmo, aunque no sea necesariamente el mejor (es una heurística "voraz": elige lo que parece mejor ahora sin mirar más allá; volveremos sobre esa idea en 03-02).

Solución 2.

Salida del bucle final:

La nueva vía crea dos rutas factibles más (las que salen o vuelven por Usera), pero la mejor sigue siendo la de 23,0 km: una carretera nueva amplía las opciones, no necesariamente mejora el óptimo. Recuerda deshacer el cambio (o volver a definir GRAFO_CIUDAD como en la sección 9.1) antes de seguir con las lecciones siguientes, que usan el grafo original de 12 aristas.

Solución 3.

Con 10 millones de rutas por segundo, 13 entregas tardan unos 10 minutos, 14 entregas unas 2,4 horas y 15 entregas ya superan la jornada (1,5 días). Un ordenador diez veces más rápido solo desplaza la frontera en una entrega (de 14 a 15), porque cada entrega adicional multiplica el trabajo por n: la solución no es más hardware, sino un algoritmo mejor.

En esta lección hemos puesto los cimientos técnicos del módulo. Hemos definido el algoritmo como una secuencia finita, precisa y efectiva de pasos con entrada y salida, y hemos visto que se puede expresar en lenguaje natural, pseudocódigo, diagrama de flujo o código, cada forma con su utilidad. Hemos resumido la ingeniería de la IA como algoritmos + datos + representación y hemos repasado las estructuras de datos que aparecerán constantemente (listas, colas, pilas, diccionarios y, sobre todo, grafos representados con listas de adyacencia). Con la notación O grande hemos aprendido a razonar sobre cómo escala un algoritmo y hemos comprobado con números que el reparto de NovaMarket sufre una explosión combinatoria (n! rutas) que hace inviable la fuerza bruta a partir de una docena de entregas. Por último, hemos retomado la formulación de problemas de 02-01 para convertir el mapa de la ciudad en el grafo GRAFO_CIUDAD, y hemos escrito el código que lo representa, lo recorre y enumera rutas por fuerza bruta.

En la siguiente lección, Algoritmos de Búsqueda, resolveremos sobre ese mismo grafo el primer problema de verdad: encontrar el mejor camino desde Almacen_Getafe hasta un barrio de destino sin enumerar todas las posibilidades. Veremos que cambiar la cola por una pila convierte la búsqueda en anchura en búsqueda en profundidad, que una cola de prioridad nos da el camino más corto (coste uniforme), y que una heurística tan simple como la distancia en línea recta permite a A* llegar a la meta explorando una fracción del mapa.