Inteligencia Artificial · Capítulo 12
Algoritmos de Búsqueda y Optimización: La Base de la IA Clásica
Cómo los agentes inteligentes encuentran soluciones navegando espacios de estados, desde el puzzle de 8 piezas hasta el juego de ajedrez
Resolución de Problemas como Búsqueda
Antes de que el aprendizaje profundo dominara la IA, el paradigma central era la resolución de problemas mediante búsqueda en espacios de estados. Este enfoque sigue siendo relevante hoy: la planificación de rutas en GPS, los puzzles lógicos, los juegos de estrategia y muchos problemas de optimización industrial se resuelven con variantes de los algoritmos que estudiaremos en este capítulo. Más importante aún: el entrenamiento de cualquier modelo de machine learning es, en su esencia, un problema de optimización.
Componentes formales de un problema de búsqueda:
- Estado: una configuración del problema en un momento dado
- Estado inicial: desde dónde partimos
- Estado(s) objetivo: lo que queremos alcanzar
- Operadores (acciones): transformaciones que llevan de un estado a otro
- Costo de camino: el costo acumulado de la secuencia de acciones
Ejemplo concreto: el puzzle de 8 piezas
El puzzle de 8 piezas consiste en un tablero 3×3 con 8 fichas numeradas y un espacio vacío. El objetivo es llegar a la configuración ordenada (1,2,3 / 4,5,6 / 7,8,_) desde una configuración inicial aleatoria, moviendo fichas al espacio vacío. Este problema tiene 9!/2 = 181.440 estados alcanzables. Aunque manejable para una computadora, ilustra perfectamente los conceptos clave: el espacio de estados es el grafo de todas las configuraciones posibles; los operadores son mover la ficha arriba, abajo, izquierda o derecha; el objetivo es una configuración específica.
Búsqueda No Informada (Ciega)
Los algoritmos de búsqueda no informada exploran el espacio de estados sin conocimiento específico del dominio: solo saben si un estado es el objetivo o no. Su eficiencia depende enteramente de la estructura del problema.
Búsqueda en Anchura (BFS — Breadth-First Search)
BFS expande primero todos los nodos a profundidad 1, luego todos a profundidad 2, y así sucesivamente. Utiliza una cola (FIFO) como estructura de datos.
Propiedades de BFS:
— Completo: Sí (siempre encuentra una solución si existe, en espacios finitos)
— Óptimo: Sí (encuentra el camino más corto en número de pasos)
— Complejidad temporal: O(bd) donde b = factor de ramificación, d = profundidad de la solución
— Complejidad espacial: O(bd) — el problema crítico: con b=10 y d=10, necesita almacenar 10.000 millones de nodos
Conclusión: BFS es óptimo pero con uso de memoria prohibitivo para problemas profundos.
Búsqueda en Profundidad (DFS — Depth-First Search)
DFS expande primero el nodo más profundo del árbol. Utiliza una pila (LIFO) o recursión.
Propiedades de DFS:
— Completo: No en grafos infinitos (puede perderse en ramas infinitas)
— Óptimo: No (puede encontrar soluciones subóptimas)
— Complejidad temporal: O(bm) donde m = profundidad máxima del árbol
— Complejidad espacial: O(b·m) — lineal en profundidad, enorme ventaja sobre BFS
Conclusión: DFS usa poca memoria pero puede no terminar o encontrar soluciones muy largas.
DFS con Profundidad Iterativa (IDDFS)
IDDFS combina lo mejor de ambos mundos: ejecuta DFS repetidamente con un límite de profundidad creciente (1, 2, 3, ...) hasta encontrar la solución. Aunque parece ineficiente por repetir trabajo, el análisis demuestra que la redundancia es mínima: en el caso con b=10, el nivel d tiene 10d nodos, mientras el nivel d-1 tiene 10d-1, que es solo el 10% de d. La expansión repetida de los niveles superiores agrega solo un factor constante.
IDDFS: el algoritmo de búsqueda ciega preferido en la práctica
Completo: Sí | Óptimo: Sí | Temporal: O(bd) | Espacial: O(b·d) — combina la optimalidad de BFS con el uso de memoria de DFS.
Búsqueda de Costo Uniforme (UCS)
UCS generaliza BFS al caso donde los pasos tienen costos distintos: expande siempre el nodo con menor costo de camino acumulado. Es completo y óptimo para costos positivos. Es equivalente al algoritmo de Dijkstra para grafos de caminos mínimos.
Búsqueda Informada (Heurística)
La búsqueda heurística usa conocimiento del dominio para guiar la exploración hacia el objetivo más eficientemente. Una heurística h(n) estima el costo desde el nodo n hasta el objetivo.
El algoritmo A*: el rey de la búsqueda informada
A* (pronunciado "A estrella") combina el costo acumulado g(n) con la estimación heurística h(n) para calcular f(n) = g(n) + h(n), expandiendo siempre el nodo con menor f(n).
Ejemplo paso a paso: Romania de Arad a Bucharest
El mapa de Romania tiene ciudades conectadas por carreteras con distancias conocidas. La heurística h(n) es la distancia en línea recta (distancia aérea) desde cada ciudad hasta Bucharest.
Heurísticas h (distancia aérea a Bucharest):
— Arad: 366 km | Sibiu: 253 km | Rimnicu Vilcea: 193 km | Pitesti: 100 km | Bucharest: 0
Iteración 1: Cola: {Arad: f=0+366=366}
Expandir Arad → vecinos: Zerind (75+374=449), Timisoara (118+329=447), Sibiu (140+253=393)
Cola: {Sibiu:393, Timisoara:447, Zerind:449}
Iteración 2: Expandir Sibiu (f=393) → Rimnicu Vilcea (140+80+193=413), Fagaras (140+99+178=417), Oradea (140+151+380=671)
Cola: {Rimnicu:413, Fagaras:417, Timisoara:447, Zerind:449}
Iteración 3: Expandir Rimnicu Vilcea (f=413) → Pitesti (140+80+97+100=417), Craiova (418+160=738)
Cola: {Fagaras:417, Pitesti:417, Timisoara:447, Zerind:449}
Continuando... A* encuentra el camino Arad→Sibiu→Rimnicu Vilcea→Pitesti→Bucharest con costo total 418 km, que es el óptimo.
Heurísticas admisibles y consistentes:
- Admisible: h(n) nunca sobreestima el costo real al objetivo. Garantiza que A* encuentra la solución óptima.
- Consistente (monotona): h(n) ≤ c(n,a,n') + h(n') para todo sucesor n'. Garantiza que cada nodo se expande como máximo una vez.
- Para el puzzle de 8: h = número de piezas fuera de lugar (admisible pero débil). h = distancia de Manhattan total (suma de desplazamientos horizontal+vertical de cada pieza — admisible y más informativa).
Búsqueda Greedy Best-First
La búsqueda greedy usa solo la heurística h(n) ignorando el costo acumulado g(n). Es muy rápida pero no garantiza soluciones óptimas: puede quedar atrapada en callejones sin salida heurísticos. Funciona bien cuando la heurística es confiable y la solución aproximada es aceptable.
Búsqueda en Juegos: Minimax y Poda Alfa-Beta
El algoritmo Minimax
Los juegos de dos jugadores de suma cero (ajedrez, damas, tres en raya) se modelan como árboles de juego donde los jugadores alternan turnos. El jugador MAX intenta maximizar su puntuación; MIN intenta minimizarla. Minimax asume que ambos jugadores juegan óptimamente.
Ejemplo: árbol minimax para tres en raya (tic-tac-toe)
Desde la posición inicial vacía, MAX (X) tiene 9 opciones. Para cada una, MIN (O) tiene 8 opciones. El árbol completo tiene 9! = 362.880 hojas (en realidad menos por simetría y estados terminales). En estados terminales: X gana = +1, O gana = -1, empate = 0.
Minimax propaga los valores hacia arriba:
— Nodo MIN: devuelve el mínimo de los valores de sus hijos
— Nodo MAX: devuelve el máximo de los valores de sus hijos
La complejidad es O(bm): para ajedrez, b≈35 y m≈80, dando 3580 ≈ 10123 nodos — inmanejable sin optimizaciones.
Poda Alfa-Beta
La poda alfa-beta reduce drásticamente el número de nodos que necesita explorar Minimax, sin afectar el resultado. Mantiene dos valores: α (mejor garantía actual para MAX) y β (mejor garantía actual para MIN). Cuando β ≤ α, la rama se poda porque MIN nunca elegirá este camino.
Eficiencia de la poda alfa-beta:
En el caso ideal (orden perfecto de nodos), la poda alfa-beta reduce la complejidad de O(bm) a O(bm/2). Para ajedrez esto significa que en lugar de explorar bm nodos exploramos bm/2, permitiendo buscar el doble de profundidad con el mismo tiempo. En la práctica con ordenamiento heurístico de movimientos, se logra cerca del caso ideal. Este fue el principio fundamental de Deep Blue de IBM, que derrotó a Garry Kasparov en 1997.
Optimización: Descenso de Gradiente
El descenso de gradiente es el algoritmo de optimización más importante del machine learning moderno. La intuición es simple: imagina que estás en una montaña con niebla espesa y quieres llegar al valle más bajo. No puedes ver lejos, pero puedes sentir el suelo bajo tus pies e identificar en qué dirección está la pendiente más pronunciada. Si siempre caminas "cuesta abajo", eventualmente llegarás a un valle (un mínimo local o global).
Fórmula del descenso de gradiente:
θ ← θ − α · ∇J(θ)
Donde: θ = parámetros del modelo, α = tasa de aprendizaje (learning rate), ∇J(θ) = gradiente de la función de pérdida respecto a los parámetros.
Selección de la tasa de aprendizaje
La tasa de aprendizaje α es el "tamaño del paso" en cada iteración. Su selección es crítica:
- α demasiado grande: el algoritmo oscila alrededor del mínimo o diverge completamente, como si dieras pasos tan grandes que saltas de un lado al otro del valle.
- α demasiado pequeña: el algoritmo converge, pero extremadamente lento. Puede requerir millones de iteraciones para llegar al mínimo.
- α bien calibrada: convergencia suave y razonablemente rápida. En la práctica se usa learning rate scheduling (empezar con α grande y reducirlo gradualmente).
Variantes del descenso de gradiente
| Variante | Datos usados por actualización | Ventaja | Desventaja |
|---|
| Batch GD | Todo el dataset | Gradiente preciso, convergencia suave | Muy lento en datasets grandes |
| Stochastic GD (SGD) | 1 ejemplo aleatorio | Muy rápido, puede escapar mínimos locales | Oscilación ruidosa, no converge exactamente |
| Mini-batch GD | Lote de 32-256 ejemplos | Equilibrio entre precisión y velocidad, paralelizable en GPU | Hiperparámetro adicional (tamaño del lote) |
El mini-batch GD es el estándar en deep learning: permite vectorización eficiente en GPUs y el ruido del gradiente actúa como regularización implícita.
Algoritmos Evolutivos: Algoritmos Genéticos
Los algoritmos genéticos (GA) se inspiran en la evolución darwiniana. Son útiles cuando el espacio de búsqueda es enorme, discontinuo o mal comprendido, y cuando las soluciones pueden representarse como "cromosomas".
GA aplicado al Problema del Viajante (TSP)
El TSP: dado un conjunto de ciudades, encontrar la ruta más corta que visita cada ciudad exactamente una vez y regresa al origen. Con 20 ciudades hay 20!/2 ≈ 1018 rutas posibles — imposible por fuerza bruta.
Representación: una permutación de ciudades = [3,7,1,5,2,8,4,6] representa una ruta
Selección: las rutas más cortas tienen mayor probabilidad de reproducirse (selección por torneo o ruleta)
Cruce (crossover): dos rutas padre generan una hija combinando segmentos: padre1=[1,2,3,4,5,6], padre2=[3,5,2,6,1,4] → hija=[1,2,3,6,4,5] (preservando segmento del padre1 y completando con orden del padre2)
Mutación: con baja probabilidad, intercambiar dos ciudades en la ruta: [1,2,3,6,4,5]→[1,5,3,6,4,2]
Resultado: tras cientos de generaciones, la población converge hacia rutas cortas sin garantizar el óptimo global.
Recocido Simulado (Simulated Annealing)
El recocido simulado se inspira en el proceso metalúrgico de calentar un metal y enfriarlo lentamente para minimizar su energía interna. El algoritmo acepta soluciones peores con una probabilidad que disminuye con el tiempo (temperatura), permitiéndole escapar de mínimos locales al principio y refinar la solución al final.
La probabilidad de aceptar una solución peor es: P = e-ΔE/T, donde ΔE es el empeoramiento de la solución y T es la temperatura actual. Con T alto (inicio), casi cualquier solución se acepta. Con T bajo (final), solo mejoras se aceptan. El recocido simulado garantiza convergencia al óptimo global en tiempo infinito, y es prácticamente efectivo en tiempos razonables para muchos problemas combinatorios.
Satisfacción de Restricciones: Sudoku como CSP
Los Problemas de Satisfacción de Restricciones (CSP) consisten en asignar valores a variables respetando un conjunto de restricciones. El Sudoku es un ejemplo perfecto: 81 variables (cada celda), dominio {1-9}, restricciones de unicidad en filas, columnas y subcuadros 3×3.
Algoritmos para CSP:
Backtracking: asignar un valor a una variable; si viola restricciones, retroceder e intentar el siguiente valor. Para Sudoku fácil puede resolver en milisegundos; para Sudoku extremo puede necesitar millones de intentos.
Forward Checking: al asignar un valor, eliminar inmediatamente los valores incompatibles del dominio de las variables vecinas. Si alguna variable queda sin valores posibles, retroceder antes de seguir explorando — evita muchas ramas fallidas.
Arc Consistency (AC-3): propaga restricciones entre pares de variables hasta alcanzar consistencia. Muchos Sudokus de dificultad media se resuelven completamente solo con AC-3, sin necesidad de búsqueda.
Por Qué Importa: El Entrenamiento de ML es Optimización
La conexión entre búsqueda/optimización y el machine learning moderno es fundamental y directa. Cuando entrenamos una red neuronal, estamos buscando en un espacio de millones o miles de millones de parámetros (pesos) el punto que minimiza la función de pérdida. GPT-4 tiene aproximadamente 1,8 billones de parámetros; optimizar este espacio requiere variantes sofisticadas del descenso de gradiente (Adam, AdamW, LAMB) que adaptan la tasa de aprendizaje individualmente para cada parámetro.
El aprendizaje por refuerzo utiliza explícitamente algoritmos de búsqueda: AlphaGo y AlphaZero de DeepMind combinan redes neuronales con Monte Carlo Tree Search (MCTS), una variante del árbol de juego con exploración aleatoria guiada. Los sistemas de planificación de robots usan A* para encontrar trayectorias en espacios continuos. Los algoritmos de routing de paquetes en internet son variantes del algoritmo de Dijkstra ejecutándose millones de veces por segundo.
Resumen del Capítulo
- Los problemas de búsqueda se definen por estado inicial, operadores, estado objetivo y función de costo; el espacio de estados es el grafo de todas las configuraciones posibles.
- BFS encuentra soluciones óptimas pero con memoria O(bd); DFS usa O(b·m) de memoria pero no es óptimo; IDDFS combina optimalidad de BFS con eficiencia de memoria de DFS.
- A* usa f(n)=g(n)+h(n) con heurística admisible; es completo y óptimo, demostrado en el mapa de Romania Arad→Bucharest.
- Minimax resuelve juegos de suma cero; la poda alfa-beta reduce la complejidad de O(bm) a O(bm/2), base de Deep Blue y los motores de ajedrez modernos.
- El descenso de gradiente —la columna vertebral del ML moderno— busca el mínimo de la función de pérdida ajustando parámetros en la dirección contraria al gradiente.
- Los algoritmos genéticos y el recocido simulado son metaheurísticas para espacios de búsqueda complejos donde el gradiente no existe o no es útil.
- Todo entrenamiento de modelos de ML es un problema de optimización; comprender búsqueda y optimización es comprender la base matemática de la IA moderna.