Capítulo 01: Búsqueda: resolver problemas como espacio de estados

Entrando en el tema

A mediados de los años cincuenta, Allen Newell, J. C. Shaw y Herbert Simon mostraron que un programa podía demostrar teoremas explorando sistemáticamente el espacio de posibles deducciones. Poco después formalizaron el General Problem Solver como intento de solucionador general mediante búsqueda en espacios de estados.¹ No usaba redes neuronales. No usaba aprendizaje. Usaba búsqueda.

Siete décadas después, la búsqueda sigue siendo el corazón de sistemas que usas a diario. Un sistema de navegación puede encontrar rutas explorando un espacio donde cada estado es una ubicación y cada acción es una carretera. Un videojuego puede mover personajes con A*, un algoritmo de búsqueda de 1968. Y cuando diseñamos un agente LLM que decide qué herramienta llamar a continuación, podemos modelar esa decisión, de forma implícita y heurística, como un problema de búsqueda.

Este capítulo empieza por el principio: ¿qué es exactamente un problema de búsqueda? ¿Cómo se modela? ¿Y por qué algo tan simple es, al mismo tiempo, tan poderoso y tan peligrosamente costoso?

El vocabulario de la búsqueda

Todo problema de búsqueda empieza con cuatro ideas operativas: estado, acción, meta y coste.² Luego, cuando lo escribimos con notación formal, esas ideas se descomponen un poco más para que no quede nada en el aire.

Estado

Una descripción suficiente de la situación actual. «Estoy en Madrid». «El robot está en la coordenada (3,7) mirando al norte». «El puzzle tiene las piezas en esta configuración».

El estado debe contener todo lo necesario para decidir qué hacer a continuación. Si falta información, el algoritmo tomará decisiones incorrectas. Piensa en el estado como una fotografía del problema en un instante: debe capturar todo lo relevante y nada de lo irrelevante.³

Un error clásico es incluir información redundante en el estado, como «la temperatura ambiente» o «el color del coche», que no afecta a las decisiones pero multiplica el número de estados posibles. Cada bit innecesario en el estado duplica el espacio de búsqueda.

Acción

Una operación que transforma un estado en otro. «Viajar de Madrid a Barcelona» (coste: 620 km). «Avanzar una casilla hacia el norte» (coste: 1 paso). «Mover la pieza A a la posición B» (coste: 1 movimiento).

No todas las acciones están disponibles en todos los estados. Desde Madrid puedes viajar a Barcelona, pero no a Buenos Aires (no hay carretera). Esta restricción, llamada precondición, es lo que diferencia un problema bien modelado de uno imposible. Las acciones definen la topología del espacio de búsqueda: qué estados están conectados y a qué precio.⁴

Meta

La condición que queremos alcanzar. Puede ser un estado concreto («estar en Berlín») o una propiedad («tener todas las cajas en la zona de carga, da igual en qué orden»). La meta puede ser única o múltiple; puede ser un estado exacto o una condición abstracta.

Lo crucial es que la meta sea verificable. Dado un estado, debes poder responder «sí» o «no» a la pregunta «¿es este el objetivo?» sin ambigüedad. Si no puedes verificarlo, no puedes saber cuándo has terminado.⁵

Coste

El precio de cada acción o del camino completo. Distancia, tiempo, dinero, consumo de combustible, tokens de API: cualquier magnitud que queramos minimizar. El coste es lo que convierte «encuentra un camino cualquiera» en «encuentra el mejor camino».

Sin coste, cualquier camino sirve. Con coste, la búsqueda se convierte en optimización: no solo encontrar una solución, sino encontrar la mejor. Esta distinción, satisfacer frente a optimizar, es una de las más importantes de la IA.⁶

Cómo es el espacio de estados

Antes de elegir algoritmo conviene saber con qué tipo de espacio tratamos, porque eso decide qué garantías son posibles. Cuatro ejes lo describen.

Finito o infinito. Un tablero de ajedrez tiene un número enorme pero finito de posiciones. El espacio de las coordenadas de un robot que puede avanzar pasos arbitrarios es infinito. En un espacio infinito, un algoritmo puede no terminar nunca si no se controla la profundidad de la exploración.

Discreto o continuo. Las casillas de un laberinto son discretas: das un paso o no lo das. La posición de un brazo robótico es continua, con infinitos ángulos intermedios. La búsqueda clásica trabaja sobre espacios discretos. Los continuos se suelen discretizar o se atacan con otras técnicas.

Determinista o no determinista. En un espacio determinista, aplicar una acción a un estado produce siempre el mismo estado siguiente. En uno no determinista, la misma acción puede llevar a varios estados, como al tirar un dado o cuando un enemigo se mueve por su cuenta. Casi toda la búsqueda de este bloque asume transiciones deterministas.

Observable o parcialmente observable. Si conoces el estado completo en todo momento, el espacio es observable. Si solo ves una parte, como la niebla de guerra de un videojuego o un sensor con ruido, es parcialmente observable, y el agente debe razonar sobre los estados que cree probables, no sobre el estado real. Esta distinción reaparece cuando hablemos de agentes.

Este capítulo y los dos siguientes asumen el caso más sencillo: espacios discretos, deterministas y observables. Es la base sobre la que después se relajan las suposiciones.

La explosión combinatoria: por qué la búsqueda es difícil

El espacio de estados crece de forma aterradora. Imagina un problema donde cada estado tiene, de media, 10 acciones posibles (factor de ramificación $b = 10$). A profundidad 1, tienes 10 estados. A profundidad 2, 100. A profundidad 5, 100 000. A profundidad 10, diez mil millones.⁷

La forma compacta de verlo es esta:

$$N(d) = \sum_{i=0}^{d} b^i = \frac{b^{d+1} - 1}{b - 1}$$

Símbolo	Significado	Ejemplo
$N(d)$	Número total de nodos que aparecen hasta profundidad $d$, contando la raíz.	Si exploramos hasta profundidad 5, $N(5)$.
$b$	Factor de ramificación medio: cuántas acciones nuevas aparecen desde cada estado.	$b = 10$.
$d$	Profundidad máxima explorada: cuántas acciones tiene el camino más largo considerado.	$d = 5$.
$i$	Nivel concreto del árbol de búsqueda.	$i = 0$ es el estado inicial; $i = 5$, los estados a cinco acciones.

Con números:

$$N(5) = 1 + 10 + 100 + 1\,000 + 10\,000 + 100\,000 = 111\,111$$

Cinco decisiones encadenadas ya generan más de cien mil nodos. Con profundidad 10:

$$N(10) = \frac{10^{11} - 1}{9} = 11\,111\,111\,111$$

Más de once mil millones. Por eso no basta con decir «probemos todas las opciones». La búsqueda clásica consiste, en buena medida, en decidir qué opciones no merece la pena mirar.

Esto es la explosión combinatoria: el número de estados crece exponencialmente con la profundidad. No es un problema de hardware: aunque tuvieras un ordenador mil millones de veces más rápido, solo podrías explorar unos pocos niveles adicionales. La explosión combinatoria es el obstáculo central de la búsqueda.

Por eso los algoritmos de búsqueda no intentan explorar todo el espacio. Usan la frontera para decidir qué explorar a continuación, ignorando la mayor parte del espacio. La diferencia entre un algoritmo que encuentra la solución en segundos y uno que no la encuentra nunca está en cómo gestiona esa frontera.

Árbol de búsqueda vs grafo de estados

Aquí hay una distinción sutil pero crítica. El grafo de estados es el mapa real: todas las configuraciones posibles y cómo se conectan. Es la realidad física del problema. El árbol de búsqueda es lo que el algoritmo construye mientras explora: un registro de los caminos que ha probado.⁸

Imagina un laberinto. El grafo de estados es el laberinto completo, donde cada casilla es un estado y cada pasillo una acción. El árbol de búsqueda es el recorrido que haces al explorar: empiezas en la entrada, pruebas un pasillo, vuelves atrás si no lleva a ningún sitio, pruebas otro. El árbol crece a medida que avanzas, pero nunca ves el grafo completo. Si lo vieras, ya habrías resuelto el problema.

¿Por qué importa esta diferencia? Porque el grafo puede tener ciclos: puedes ir de A a B y de B a A, dando vueltas. El árbol, si no tienes cuidado, puede crecer infinitamente reflejando esos ciclos una y otra vez. Los buenos algoritmos de búsqueda mantienen un conjunto de estados visitados y evitan reexplorarlos. Sin esta precaución, BFS y UCS pueden quedar atrapados en bucles infinitos.⁹

Búsqueda en árbol y búsqueda en grafo

De aquí salen las dos variantes del mismo algoritmo. La búsqueda en árbol (tree search) no recuerda dónde ha estado: expande la frontera sin comprobar si un estado ya había aparecido. Es más simple y gasta menos memoria, pero en un espacio con ciclos puede reexpandir el mismo estado una y otra vez, e incluso no terminar nunca. La búsqueda en grafo (graph search) mantiene un conjunto de estados visitados y descarta los que ya expandió. Nunca repite trabajo ni cae en bucles, a cambio de guardar en memoria todos los estados vistos.

La decisión no es estética: la búsqueda en grafo cambia coste de cómputo por coste de memoria. Evita reexpansiones, pero el conjunto de visitados puede crecer hasta ser tan grande como el propio espacio alcanzable. En problemas con muchos caminos que llevan al mismo sitio, como rejillas o mapas de carreteras, la búsqueda en grafo es casi obligatoria. En árboles sin ciclos reales, la búsqueda en árbol basta y ahorra memoria.

Cómo funciona un algoritmo de búsqueda

Todos los algoritmos de búsqueda clásicos comparten la misma estructura.¹⁰ Mantienen una frontera: el conjunto de estados que han sido descubiertos pero aún no explorados. El bucle es:

1. Extraer un estado de la frontera.
2. Comprobar si es la meta. Si lo es, reconstruir el camino y terminar.
3. Expandir: generar todos los estados alcanzables desde este estado mediante las acciones disponibles.
4. Añadir los nuevos estados a la frontera, siempre que no hayan sido visitados antes.
5. Repetir desde el paso 1.

Eso es todo. Cuatro pasos y un bucle. La diferencia entre BFS, DFS, coste uniforme, greedy y A* está exclusivamente en el paso 1: qué estado extraemos de la frontera. La estructura de datos que usemos (cola, pila, cola de prioridad) determina completamente el comportamiento del algoritmo.

En pseudocódigo, el esqueleto común de la búsqueda en grafo es este:

buscar(problema):
    frontera  ← { nodo(s0, coste=0, padre=None) }
    visitados ← { }
    mientras frontera no esté vacía:
        n ← extraer(frontera)              # aquí decide el algoritmo
        si n.estado ∈ G:
            devolver reconstruir_camino(n)
        si n.estado ∈ visitados:
            continuar
        visitados ← visitados ∪ { n.estado }
        para cada acción a en A(n.estado):
            s' ← f(n.estado, a)
            si s' ∉ visitados:
                g' ← n.coste + c(n.estado, a)
                frontera ← frontera ∪ { nodo(s', g', padre=n) }
    devolver fracaso

La única línea que cambia entre algoritmos es extraer(frontera). Si la frontera es una cola FIFO, sale el nodo más antiguo y tenemos BFS. Si es una pila LIFO, sale el más reciente y tenemos DFS. Si es una cola de prioridad ordenada por coste acumulado, sale el más barato y tenemos coste uniforme. Si se ordena por coste más heurística, tenemos A*. El bucle es idéntico, la política de extracción lo es todo. La función reconstruir_camino sigue los punteros al padre desde la meta hasta el estado inicial para devolver el plan completo.

Definición formal del problema

Conviene fijar la notación con precisión. Un problema de búsqueda se define formalmente como una tupla:¹¹

$$\text{Problema} = (S, A, f, s_0, G, c)$$

Símbolo	Significado	Ejemplo
$S$	Espacio de estados: conjunto de todas las configuraciones posibles.	En un mapa, todos los cruces y ciudades que podrían visitarse.
$A(s)$	Acciones aplicables desde el estado $s$.	Desde Zaragoza, tomar la carretera hacia Barcelona o hacia Madrid.
$f(s, a)$	Función de transición: el estado que aparece al aplicar una acción.	$f(\text{Zaragoza}, \text{ir a Barcelona}) = \text{Barcelona}$.
$s_0$	Estado inicial.	Madrid.
$G$	Conjunto de estados meta.	$\{\text{Barcelona}\}$.
$c(s, a)$	Coste de aplicar la acción $a$ en el estado $s$.	Kilómetros, minutos, euros o tokens consumidos.

La fórmula dice algo bastante sencillo: para resolver el problema necesitamos saber dónde podemos estar, qué podemos hacer, qué ocurre al hacerlo, dónde empezamos, qué cuenta como llegar y cuánto cuesta cada paso. Si falta una de esas piezas, la búsqueda queda coja.

Una solución es una secuencia de acciones:

$$\pi = (a_1, a_2, \ldots, a_n)$$

La letra $\pi$ se lee «pi» y aquí representa un plan: una lista ordenada de acciones. No es todavía «la mejor» solución; solo es una candidata. Para comprobar si realmente sirve, aplicamos cada acción una detrás de otra:

$$s_i = f(s_{i-1}, a_i), \quad i = 1, 2, \ldots, n$$

Símbolo	Significado	Ejemplo
$\pi$	Plan o secuencia de acciones.	$(\text{Madrid} \to \text{Zaragoza}, \text{Zaragoza} \to \text{Barcelona})$.
$a_i$	Acción número $i$ del plan.	$a_1 =$ ir de Madrid a Zaragoza.
$s_i$	Estado alcanzado después de ejecutar $i$ acciones.	$s_1 =$ Zaragoza; $s_2 =$ Barcelona.
$f$	Función de transición que calcula el siguiente estado.	Aplicar «ir a Zaragoza» desde Madrid produce Zaragoza.
$n$	Número total de acciones del plan.	$n = 2$.

El plan es una solución si el último estado pertenece al conjunto de metas:

$$s_n \in G$$

En nuestro ejemplo, $s_2 = \text{Barcelona}$ y $G = \{\text{Barcelona}\}$. Por tanto, el plan llega a la meta.

Ahora falta saber cuánto cuesta. El coste total de un plan es la suma de los costes de cada acción:

$$C(\pi) = \sum_{i=1}^{n} c(s_{i-1}, a_i)$$

Símbolo	Significado	Ejemplo
$C(\pi)$	Coste total del plan $\pi$.	Kilómetros totales recorridos.
$c(s_{i-1}, a_i)$	Coste de ejecutar la acción $a_i$ desde el estado anterior.	$c(\text{Madrid}, \text{ir a Zaragoza}) = 315$ km.
$i$	Índice de la acción dentro del plan.	$i = 1$ para el primer tramo; $i = 2$ para el segundo.
$n$	Número de acciones del plan.	$n = 2$.

Con números:

$$C(\pi) = 315 + 300 = 615$$

Si existe otro plan Madrid → Valencia → Barcelona con coste $720$, ambos llegan a la meta, pero el primero es mejor. Una solución es óptima si minimiza $C(\pi)$ entre todas las soluciones posibles.

Esta formalización permite razonar sobre propiedades como la completitud (¿el algoritmo siempre encuentra solución si existe?), la optimalidad (¿encuentra la mejor?) y la complejidad (¿cuánto tarda y cuánta memoria consume en función del tamaño del problema?).¹²

Las cuatro propiedades de un algoritmo de búsqueda

Cada vez que evaluamos un algoritmo de búsqueda nos hacemos las mismas cuatro preguntas. Son el lenguaje con el que el capítulo 2 compara BFS, DFS y coste uniforme, y el capítulo 3, A*.

Completitud. ¿El algoritmo encuentra una solución siempre que exista? Un algoritmo completo no se queda dando vueltas para siempre ni abandona un problema que sí tenía respuesta. BFS es completo. DFS, en un espacio infinito, no lo es.

Optimalidad. ¿La solución que encuentra es la de menor coste? Un algoritmo puede ser completo pero no óptimo: encuentra una solución, no necesariamente la mejor. BFS es óptimo solo si todas las acciones cuestan lo mismo. El coste uniforme lo es siempre.

Complejidad temporal. ¿Cuántos estados expande en el peor caso? Se mide con el factor de ramificación y la profundidad de la solución.

Complejidad espacial. ¿Cuánta memoria necesita a la vez? Suele ser el tamaño máximo de la frontera más los visitados. En la práctica, la memoria es el límite que primero se alcanza.

Para una búsqueda no informada con factor de ramificación $b$ y profundidad de la solución $d$, las cotas de referencia son:

$$T = O(b^d), \qquad M = O(b^d)$$

Símbolo	Significado	Ejemplo
$T$	Complejidad temporal: orden del número de estados expandidos en el peor caso.	Con $b = 10$ y $d = 8$, del orden de $10^8$.
$M$	Complejidad espacial: orden de la memoria ocupada por la frontera y los visitados.	También $10^8$ si hay que mantener toda la frontera.
$b$	Factor de ramificación medio.	$b = 10$.
$d$	Profundidad de la solución más superficial.	$d = 8$.

En palabras: el tiempo crece de forma exponencial con la profundidad, y la memoria suele crecer igual de rápido, que es la razón de fondo por la que la búsqueda ciega solo sirve para espacios pequeños. La diferencia entre algoritmos está en la constante y, sobre todo, en si la memoria es $O(b^d)$, como en BFS, o solo $O(b \cdot d)$, como en DFS, que guarda únicamente el camino actual. Esa tensión entre tiempo, memoria y garantías es la que ordena todo el resto del bloque.

Búsqueda no informada vs informada

Los algoritmos de búsqueda se dividen en dos familias, y la línea que las separa es la información disponible:

No informados (ciegos). No tienen ninguna pista sobre qué acciones son mejores. Solo conocen el coste de las acciones ya realizadas y la definición de la meta. Son como explorar un laberinto a oscuras, tanteando las paredes. BFS, DFS y coste uniforme pertenecen a esta familia. Su gran ventaja es que no necesitan conocimiento específico del dominio: funcionan para cualquier problema bien definido. Su gran desventaja es la ineficiencia: exploran a ciegas, sin priorizar.¹³

Informados (heurísticos). Disponen de una función heurística $h(n)$ que estima lo lejos que está un estado de la meta. Es una estimación diseñada para ser barata de calcular y suficientemente informativa para ordenar la búsqueda; no sustituye al coste real ni a la prueba de optimalidad. Greedy y A* usan heurísticas para priorizar estados prometedores. Su gran ventaja es la eficiencia: pueden encontrar soluciones explorando órdenes de magnitud menos estados. Su gran desventaja es que necesitan una buena heurística, y diseñar una heurística admisible, que nunca sobreestime el coste real, no siempre es fácil.¹⁴

El resto de este bloque de búsqueda se estructura alrededor de esta división: el capítulo 2 explora los algoritmos ciegos; el capítulo 3, los informados; y el capítulo 4 tiende el puente hacia los agentes modernos.

En el día a día

La búsqueda en espacios de estados no es una reliquia académica: aparece en sistemas reales constantemente. La navegación GPS busca una ruta útil entre dos puntos modelando cada cruce como un estado y cada calle como una acción con un coste, normalmente distancia, tiempo o una combinación de ambas. A* y sus variantes ayudan porque una heurística geométrica permite mirar antes las rutas prometedoras, aunque los sistemas reales añaden tráfico, restricciones de giro, cierres, peajes y optimizaciones de ingeniería.¹⁵

La planificación logística es otro caso cotidiano. Una empresa con 50 paquetes y 5 furgonetas tiene un espacio de estados astronómico, combinatorio y con un factor de ramificación enorme, y aun así los algoritmos de búsqueda heurística encuentran soluciones casi óptimas en segundos. La diferencia entre una ruta óptima y una subóptima son miles de euros al mes en combustible.

Hasta los agentes LLM encajan en este marco. Cuando un agente decide si llamar a search_database o a check_calendar, podemos leer esa decisión como una evaluación de acciones en un espacio de estados implícito, y el propio modelo actúa como heurística: «dado el contexto actual, ¿qué herramienta parece más prometedora?». El sistema que lo rodea debe añadir costes, permisos, observación y un criterio de parada.

Antes del algoritmo: auditar el modelo

Un error muy común es discutir si usar BFS, A* o una heurística sofisticada antes de haber comprobado que el problema está bien definido. En ingeniería, el primer paso no es elegir algoritmo: es validar el contrato de búsqueda.

Pregunta	Qué comprueba	Fallo típico
¿$s_0$ pertenece a $S$?	Que el estado inicial existe en el modelo.	Arrancar desde un identificador que no está en el grafo.
¿$G \subseteq S$?	Que todas las metas son estados válidos.	Definir como meta una etiqueta textual que ninguna transición alcanza.
¿Toda acción tiene origen, destino y coste?	Que $f(s,a)$ y $c(s,a)$ están definidos.	Acción sin coste o transición a estado inexistente.
¿Los costes son no negativos?	Que UCS y A* puedan razonar correctamente.	Costes negativos que rompen garantías de optimalidad.
¿Hay ciclos?	Que el algoritmo necesitará visitados.	Madrid → Zaragoza → Madrid repitiéndose para siempre.
¿Cuál es $b$ y hasta qué profundidad buscarías?	Estimación de explosión combinatoria.	Descubrir tarde que $b^d$ no cabe en memoria.

Esta auditoría parece humilde, pero es exactamente el tipo de trabajo que evita sistemas frágiles. Si el contrato está mal, el algoritmo puede estar perfectamente implementado y aun así devolver basura.

Un plan candidato también se puede comprobar antes de hablar de optimalidad. Un plan no es más que una secuencia de acciones; decimos que es válido (una solución, en el vocabulario de Russell y Norvig) cuando cada acción es aplicable en el estado en que se ejecuta, encadena bien sus transiciones y termina en un estado meta:¹⁶

$$\text{válido}(\pi) \Leftrightarrow s_0 \xrightarrow{a_1} s_1 \xrightarrow{a_2} \cdots \xrightarrow{a_n} s_n \land s_n \in G$$

Símbolo	Significado	Ejemplo
$\pi$	Plan candidato: la secuencia $\langle a_1, \ldots, a_n \rangle$.	Madrid → Zaragoza → Barcelona.
$s_{i-1} \xrightarrow{a_i} s_i$	Cada acción es aplicable y lleva del estado anterior al siguiente.	«ir a Zaragoza» es una transición legal desde Madrid.
$s_n \in G$	El último estado es una meta.	Barcelona pertenece a $G$.
$\Leftrightarrow$	Válido si, y solo si, se cumplen ambas cosas a la vez.	Cadena legal y final en meta.

La doble condición importa: no basta con terminar en meta por casualidad (el camino tiene que ser legal paso a paso), ni basta con encadenar acciones legales que nunca lleguen a $G$. Hacen falta las dos cosas.

Validar es barato; demostrar optimalidad es caro. Comprobar que un plan concreto es válido y medir su coste se hace en tiempo lineal, recorriendo la secuencia una vez. Pero saber que es el mejor plan exige compararlo contra todos los demás, que es justo el trabajo que hacen algoritmos como UCS o A*. Por eso primero se valida y se mide el coste, y solo después se discute optimalidad:

$$C(\pi) = \sum_{i=1}^{n} c(s_{i-1}, a_i)$$

Un plan $\pi^*$ es óptimo cuando ningún plan válido cuesta menos, es decir, $C(\pi^*) \le C(\pi)$ para todo $\pi$ válido. Comparar unos cuantos candidatos te dice cuál es el mejor entre los que tienes; demostrar que es el mejor de todos requiere explorar el espacio con garantías, no solo enumerar algunos. Por eso el lab de este capítulo evalúa planes candidatos pero no presume de optimalidad global: comparar no es demostrar.

Una práctica útil es mantener en tus sistemas una salida trazable: qué estados se recorrieron, qué acción llevó a cada estado, qué coste se acumuló y por qué el plan termina o no en meta. Eso conecta este capítulo con planificación, agentes y evaluación: no basta con “llegó”; hay que poder explicar cómo.

Por qué debería importarte

La búsqueda es el paradigma más antiguo de la IA y, paradójicamente, uno de los más vigentes. No ha sido sustituido por el deep learning: ha sido aumentado por él. Los LLMs no reemplazan la búsqueda; la hacen más inteligente, proporcionando heurísticas donde antes había que diseñarlas a mano.

Entender la búsqueda te da un marco mental para razonar sobre problemas secuenciales: aquellos donde la solución no es una respuesta única, sino una secuencia de decisiones. Y te prepara para los capítulos siguientes: sin entender el vocabulario de estados, acciones y fronteras, no puedes entender CSP, planificación ni juegos. Todo el facsímil 2 se construye sobre este capítulo.

Dónde solía tropezar yo

Error	Por qué es un error	Antídoto
Confundir el grafo de estados con el árbol de búsqueda	El grafo es el mapa completo; el árbol es lo que el algoritmo explora. Tratar el árbol como si fuera el grafo lleva a reexplorar estados innecesariamente y a no detectar ciclos.	Mantén un conjunto visited y nunca reexpandas un estado ya visitado. Es la optimización más rentable en búsqueda.
No definir bien el estado	Si el estado no contiene toda la información necesaria para decidir la siguiente acción, el algoritmo tomará decisiones basadas en información incompleta.	Pregúntate: «con esta información, ¿puedo generar todas las acciones posibles y evaluar si he llegado a la meta?». Si la respuesta es no, tu estado está incompleto.
Subestimar la explosión combinatoria	Un espacio con b=10 y d=10 tiene 10^10 estados. Explorarlos todos es inviable en cualquier hardware. La búsqueda ciega solo funciona para espacios pequeños.	Calcula b y d antes de elegir algoritmo. Si b^d es mayor que unos pocos millones, necesitas una heurística o una poda.
Olvidar el coste	Sin coste, cualquier camino sirve. Con costes variables, el camino más corto en pasos no es necesariamente el más barato. BFS encuentra el primero; UCS encuentra el mejor.	Define el coste de cada acción. Si los costes no son uniformes, usa UCS o A*, no BFS.

Cómo encaja todo

Este mapa se lee de izquierda a derecha: primero defines el problema, después eliges cómo gestionar la frontera, y solo entonces aparecen las garantías de completitud, optimalidad y coste. Los capítulos siguientes cambian la política de frontera, añaden heurísticas o convierten estados en asignaciones, planes y decisiones con otros actores.

La conexión con sistemas modernos no es decorativa: un agente con herramientas también necesita estado, acciones, coste, meta y trazabilidad. Cambia la forma de representar el problema, pero no desaparece el patrón.

graph TD
    subgraph "Capítulo 1: Fundamentos de búsqueda"
        direction TB
        PROBLEMA["Problema = (S, A, f, s₀, G, c)"]
        S_ESPACIO["S: espacio de estados<br/>finito o infinito, discreto o continuo"]
        A_ACCIONES["A(s): acciones aplicables en s<br/>f: S × A → S (función de transición)"]
        S0_INICIAL["s₀ ∈ S: estado inicial"]
        G_META["G ⊆ S: conjunto de estados meta"]
        C_COSTE["c: S × A → ℝ⁺: función de coste"]
        SOLUCION["Solución: secuencia (a₁,…,aₙ) tal que<br/>s₀ →^a₁ s₁ →^a₂ … →^aₙ sₙ ∈ G"]
        OPTIMA["Solución óptima: minimiza Σ c(sᵢ, aᵢ₊₁)"]
    end
    subgraph "Propiedades formales"
        COMPLETITUD[Completitud: ¿encuentra solución si existe?]
        OPTIMALIDAD[Optimalidad: ¿encuentra la de menor coste?]
        COMPLEJIDAD["Complejidad: O(b^d) tiempo, O(b·d) espacio"]
        ADMISIBILIDAD["Admisibilidad: h(s) ≤ h*(s) ∀s"]
    end
    subgraph "Frontera: el núcleo algorítmico"
        FRONTERA[Frontera: estados descubiertos, no expandidos]
        COLA["Cola FIFO → BFS: O(b^d)"]
        PILA["Pila LIFO → DFS: O(b·d)"]
        PRIORIDAD["Cola prioridad por g → UCS"]
        HEURISTICA["Cola prioridad por g+h → A*"]
    end
    subgraph "Conexiones en el facsímil 2"
        CSP["CSP: variables + restricciones<br/>la búsqueda con backtracking"]
        PLANIFICACION["Planificación: PDDL<br/>acciones con precondiciones y efectos"]
        JUEGOS["Juegos: minimax, MCTS<br/>búsqueda con otros actores"]
    end
    subgraph "Conexiones modernas"
        AGENTES_LLM["Agentes LLM: búsqueda implícita<br/>el modelo como heurística aprendida"]
        RAG["RAG: retrieval = búsqueda<br/>en espacio de documentos"]
    end

    PROBLEMA --> S_ESPACIO
    PROBLEMA --> A_ACCIONES
    PROBLEMA --> S0_INICIAL
    PROBLEMA --> G_META
    PROBLEMA --> C_COSTE
    S_ESPACIO --> SOLUCION
    A_ACCIONES --> SOLUCION
    S0_INICIAL --> SOLUCION
    G_META --> SOLUCION
    SOLUCION --> OPTIMA
    C_COSTE --> OPTIMA
    SOLUCION -->|"se encuentra mediante"| FRONTERA
    FRONTERA -->|"implementada como"| COLA
    FRONTERA -->|"implementada como"| PILA
    FRONTERA -->|"implementada como"| PRIORIDAD
    FRONTERA -->|"implementada como"| HEURISTICA
    COLA -->|"garantiza"| COMPLETITUD
    PRIORIDAD -->|"garantiza"| OPTIMALIDAD
    HEURISTICA -->|"con h admisible"| OPTIMALIDAD
    HEURISTICA -->|"requiere"| ADMISIBILIDAD
    COLA -->|"complejidad"| COMPLEJIDAD
    PILA -->|"complejidad"| COMPLEJIDAD
    COMPLETITUD -->|"hereda"| CSP
    OPTIMALIDAD -->|"extiende a"| PLANIFICACION
    FRONTERA -->|"fundamento de"| JUEGOS
    HEURISTICA -->|"inspira"| AGENTES_LLM
    COLA -->|"análogo a"| RAG

    style PROBLEMA fill:#F5F5F5,stroke:#000000,stroke-width:2
    style FRONTERA fill:#F5F5F5,stroke:#000000,stroke-width:2
    style HEURISTICA fill:#F5F5F5,stroke:#000000,stroke-width:2
    style CSP stroke-dasharray: 5 5
    style PLANIFICACION stroke-dasharray: 5 5
    style JUEGOS stroke-dasharray: 5 5
    style AGENTES_LLM stroke-dasharray: 5 5
    style RAG stroke-dasharray: 5 5

Vocabulario aprendido

Término	Definición
Estado	Descripción suficiente de la situación actual del problema en un momento dado.
Espacio de estados	Conjunto de todas las configuraciones posibles que puede alcanzar el problema.
Árbol de búsqueda	Estructura que el algoritmo construye al explorar, donde cada nodo es un estado y cada rama una acción.
Frontera	Conjunto de estados descubiertos pero aún no explorados. Su estructura determina el algoritmo.
Factor de ramificación	Número medio de acciones disponibles en cada estado. Determina la explosión combinatoria.
Heurística	Función que estima la distancia de un estado a la meta, guiando la búsqueda informada.
Contrato de búsqueda	Definición verificable de estados, acciones, transición, estado inicial, metas y costes.
Plan candidato	Secuencia de acciones que debe poder ejecutarse desde $s_0$ y terminar en $G$ para ser solución.
Estado visitado	Estado ya revisado para evitar ciclos y reexpansiones innecesarias.
Búsqueda en grafo	Variante que guarda los estados visitados para no repetirlos, frente a la búsqueda en árbol, que no los recuerda.
Completitud	Propiedad de un algoritmo que encuentra solución siempre que exista.
Optimalidad	Propiedad de un algoritmo que encuentra la solución de menor coste.

Antes de pasar página

• ¿Puedo definir los cuatro ingredientes de un problema de búsqueda y poner un ejemplo concreto de cada uno? (Si no, vuelve a «El vocabulario de la búsqueda».)
• ¿Entiendo por qué la explosión combinatoria hace que la búsqueda ciega sea inviable para espacios grandes? (Si no, vuelve a «La explosión combinatoria».)
• ¿Sé diferenciar el grafo de estados del árbol de búsqueda y explicar por qué importa la diferencia? (Si no, vuelve a «Árbol de búsqueda vs grafo de estados».)
• ¿Puedo explicar el bucle genérico de un algoritmo de búsqueda y qué línea cambia entre BFS, DFS, UCS y A*? (Si no, vuelve a «Cómo funciona un algoritmo de búsqueda».)
• ¿Puedo nombrar las cuatro propiedades de un algoritmo de búsqueda y decir qué pregunta responde cada una? (Si no, vuelve a «Las cuatro propiedades de un algoritmo de búsqueda».)
• ¿Sé la diferencia entre búsqueda en árbol y búsqueda en grafo, y por qué importa visited? (Si no, vuelve a «Árbol de búsqueda vs grafo de estados».)
• ¿Entiendo la diferencia entre búsqueda no informada e informada? (Si no, vuelve a «Búsqueda no informada vs informada».)
• ¿Puedo auditar si un problema está bien definido antes de elegir algoritmo? (Si no, vuelve a «Antes del algoritmo: auditar el modelo».)
• ¿Sé distinguir un plan válido de uno inválido en un problema de búsqueda bien definido? (Si no, vuelve a «Definición formal del problema».)

En resumen

Idea fuerza	Detalle
Todo problema de búsqueda se define con estados, acciones, meta y coste.	Si no puedes definir estos cuatro elementos, no tienes un problema de búsqueda. Si tu estado contiene información irrelevante, tu espacio de búsqueda explota innecesariamente.
La explosión combinatoria es el obstáculo central.	El espacio crece exponencialmente con la profundidad. Más hardware ayuda poco si el modelo explora ramas inútiles. La defensa es modelar mejor, podar, usar heurísticas y medir costes.
La frontera es el corazón del algoritmo.	Qué estado extraes de la frontera determina si estás haciendo BFS, DFS, UCS o A*. Todo lo demás es el mismo bucle.
El contrato del problema va antes del algoritmo.	Si estados, acciones, transición, meta o coste están mal definidos, ningún algoritmo arregla el modelo.
La búsqueda no ha muerto: ha evolucionado.	Los LLMs no reemplazan la búsqueda; pueden aportar heurísticas aprendidas dentro de sistemas con estado, acciones, validación y trazas. El patrón viene de la IA clásica.

Para saber más

Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136

Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson.

Newell, A., Shaw, J. C. y Simon, H. A. (1959). Report on a general problem-solving program. En Proceedings of the International Conference on Information Processing (pp. 256-264). UNESCO.

Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann.

Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley.

Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press.

Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill.

Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. https://aima.cs.berkeley.edu/

Notas

1. Newell, A., Shaw, J. C. y Simon, H. A. (1959). Report on a general problem-solving program. En Proceedings of the International Conference on Information Processing (pp. 256-264). UNESCO. ↩

2. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. Los capítulos 3 y 4 abordan la resolución de problemas mediante búsqueda, estableciendo el marco conceptual de estados, acciones, metas y costes que sigue siendo la base de la IA moderna. ↩

3. Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann. El capítulo 7 presenta los fundamentos de la búsqueda en espacios de estados, incluyendo la distinción entre búsqueda ciega y búsqueda heurística. ↩

4. Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill. El capítulo 2 describe cómo modelar problemas como espacios de estados, enfatizando la importancia de definir correctamente las precondiciones de cada acción. ↩

5. Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press. La sección 3.3 analiza cómo definir metas verificables y su papel en la terminación correcta de los algoritmos de búsqueda. ↩

6. Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson. El capítulo 3 desarrolla la distinción entre búsqueda de cualquier solución y búsqueda de la solución óptima, y cómo el coste transforma el problema. ↩

7. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. La sección 3.3 introduce el concepto de complejidad de la búsqueda y analiza cómo el factor de ramificación y la profundidad determinan la viabilidad de los algoritmos. ↩

8. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. La sección 3.3 detalla la diferencia entre el grafo de estados y el árbol de búsqueda. ↩

9. Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press. El capítulo 3 aborda la detección de ciclos como una optimización crítica para la viabilidad práctica de los algoritmos de búsqueda. ↩

10. Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann. El capítulo 7 presenta un marco unificado donde la única diferencia entre algoritmos es la política de extracción de la frontera. ↩

11. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. La sección 3.1 introduce la definición formal del problema de búsqueda, incluyendo la notación de espacios de estados, función de transición, y función de coste. ↩

12. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. El capítulo 2 formaliza las propiedades de los algoritmos de búsqueda en términos de completitud, admisibilidad y optimalidad. ↩

13. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. La sección 3.4 clasifica los algoritmos de búsqueda no informada y analiza sus propiedades de completitud, optimalidad y complejidad. ↩

14. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. Pearl estableció las bases teóricas de la búsqueda heurística, incluyendo las propiedades de admisibilidad y consistencia que garantizan la optimalidad de A*, y el concepto de poder heurístico que permite comparar la eficiencia de distintas heurísticas. ↩

15. Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136. ↩

16. Russell, S. y Norvig, P. (2021). Artificial Intelligence: A Modern Approach (4.ª ed.). Pearson. Una solución de un problema de búsqueda se define como una secuencia de acciones que lleva del estado inicial a un estado objetivo. ↩

Capítulo 02: BFS, DFS y coste uniforme: los algoritmos ciegos

Entrando en el tema

En el capítulo anterior definiste el problema: estados, acciones, meta y coste. Construiste el vocabulario. Ahora necesitas algoritmos que resuelvan ese problema sin pistas del dominio y sin función heurística. A ciegas.

Tres algoritmos compiten por el título de «mejor búsqueda ciega». Los tres usan exactamente el mismo bucle (extraer, comprobar, expandir, añadir). La única diferencia entre ellos es la estructura de datos de la frontera.¹ Una cola produce BFS. Una pila produce DFS. Una cola de prioridad produce UCS. El resto es el mismo código.

Este capítulo desmenuza los tres. Con pseudocódigo. Con análisis de complejidad. Con ejemplos trazados paso a paso. Porque si no entiendes por qué BFS consume memoria exponencial y DFS puede perderse para siempre, no entenderás por qué A* (el algoritmo del próximo capítulo) fue una revolución.

El bucle genérico

Antes de entrar en cada algoritmo, fijemos el pseudocódigo común.² Los tres algoritmos ejecutan exactamente esto:

función BÚSQUEDA(problema):
    frontera ← [s₀]                    // estructura depende del algoritmo
    visitados ← {s₀}
    
    mientras frontera no esté vacía:
        s ← EXTRAER(frontera)          // ← aquí está toda la diferencia
        si ES-META(s):
            return RECONSTRUIR-CAMINO(s)
        para cada acción a en A(s):
            s' ← f(s, a)
            si s' ∉ visitados:
                visitados ← visitados ∪ {s'}
                AÑADIR(frontera, s')
    
    return FRACASO

La línea s ← EXTRAER(frontera) es la única que cambia entre algoritmos.³ En BFS, EXTRAER es dequeue (el primero que entró). En DFS, es pop (el último que entró). En UCS, es extract-min (el de menor coste). Tres implementaciones. Tres comportamientos radicalmente distintos.

La forma matemática de decirlo es: en cada iteración elegimos un nodo de la frontera según una política $\pi$:

$$n_t = \operatorname{extraer}_{\pi}(F_t)$$

Símbolo	Significado	Ejemplo
$F_t$	Frontera en el instante $t$: nodos descubiertos pero no expandidos.	$[B, C, D]$.
$n_t$	Nodo elegido para expandir en la iteración $t$.	En BFS sería $B$; en DFS podría ser $D$.
$\pi$	Política de extracción de la frontera.	FIFO, LIFO o menor coste $g(n)$.
$\operatorname{extraer}_{\pi}$	Operación que aplica esa política.	dequeue, pop o extract-min.

Y el resto del bucle actualiza frontera y visitados:

$$F_{t+1} = \left(F_t \setminus \{n_t\}\right) \cup \left(\operatorname{Succ}(n_t) \setminus V_t\right)$$

Símbolo	Significado	Ejemplo
$\operatorname{Succ}(n_t)$	Sucesores generados al expandir $n_t$.	Si $n_t=B$, quizá $\{D,E\}$.
$V_t$	Estados ya visitados antes de la iteración $t$.	$\{A,B\}$.
$\setminus$	Diferencia de conjuntos: quitar elementos ya presentes.	No reañadir estados visitados.

Así que los tres algoritmos se reducen a tres políticas:

$$\pi_{\text{BFS}} = \text{FIFO}, \qquad \pi_{\text{DFS}} = \text{LIFO}, \qquad \pi_{\text{UCS}}(n) = \arg\min_{n \in F} g(n)$$

BFS: explorar por niveles

Algoritmo

BFS usa una cola (FIFO: first in, first out). Cuando expandimos un estado a profundidad $d$, sus sucesores se añaden al final de la cola, detrás de todos los estados de profundidad $d$ que aún no se han expandido. El resultado es una exploración por niveles concéntricos.⁴

Frontera: [A]           → dequeue A, enqueue(B, C)
Frontera: [B, C]        → dequeue B, enqueue(D, E)
Frontera: [C, D, E]     → dequeue C, enqueue(F)
Frontera: [D, E, F]     → ...

Propiedades formales

Para un espacio de búsqueda con factor de ramificación $b$ y profundidad de la solución más superficial $d$:⁵

Propiedad	Valor	Explicación
Completitud	Sí (si $b$ es finito)	Si existe solución, BFS la encuentra porque explora sistemáticamente todos los nodos por niveles.
Optimalidad	Sí (si coste = 1)	BFS encuentra el camino con menos pasos porque el primer nodo meta que descubre está a la profundidad mínima.
Tiempo	$O(b^d)$	En el peor caso, explora todos los nodos hasta profundidad $d$. Con $b=10, d=10$: $10^{10}$ expansiones.
Espacio	$O(b^d)$	Almacena todos los nodos del nivel actual en la frontera. Este es su talón de Aquiles.

El conteo de nodos de BFS sale de la suma de niveles del árbol:

$$N_{\text{BFS}}(d) = \sum_{i=0}^{d} b^i = \frac{b^{d+1}-1}{b-1}$$

Símbolo	Significado	Ejemplo
$N_{\text{BFS}}(d)$	Nodos generados hasta profundidad $d$.	Si $d=6$, todos los niveles de 0 a 6.
$b$	Factor de ramificación medio.	$b=10$.
$d$	Profundidad de la solución más superficial.	$d=6$.
$i$	Nivel del árbol de búsqueda.	$i=0$ es el estado inicial.

Con $b=10$ y $d=6$:

$$N_{\text{BFS}}(6) = 1 + 10 + 10^2 + 10^3 + 10^4 + 10^5 + 10^6 = 1\,111\,111$$

La memoria se aproxima por el tamaño del nivel más profundo que queda en la frontera:

$$M_{\text{BFS}}(d) \approx b^d$$

Con $b=10$ y $d=12$, BFS puede necesitar almacenar alrededor de $10^{12}$ nodos. A 1 KB por nodo, eso ronda $10^{15}$ bytes: aproximadamente 1 PB, no “un ordenador grande”. Imposible para la mayoría de problemas reales.⁶

DFS: lanzarse en profundidad

Algoritmo

DFS usa una pila (LIFO: last in, first out). Cuando expandimos un estado, sus sucesores se colocan en el tope de la pila, y el algoritmo explora inmediatamente el que queda arriba. El resultado es una inmersión profunda por la primera rama disponible.⁷

Convención: el tope de la pila está a la izquierda.

Frontera: [A]           → pop A, push(C), push(B)
Frontera: [B, C]        → pop B (tope de la pila), push(E), push(D)
Frontera: [D, E, C]     → pop D
Frontera: [E, C]        → ...

DFS es inherentemente recursivo. De hecho, la implementación más natural de DFS es recursiva, sin frontera explícita:

función DFS-RECURSIVO(s, visitados):
    si ES-META(s): return s
    visitados ← visitados ∪ {s}
    para cada acción a en A(s):
        s' ← f(s, a)
        si s' ∉ visitados:
            resultado ← DFS-RECURSIVO(s', visitados)
            si resultado ≠ FRACASO: return resultado
    return FRACASO

La pila de llamadas de la recursión es la frontera. Cada llamada anidada es un paso más en profundidad.⁸

Propiedades formales

Propiedad	Valor	Explicación
Completitud	No (sin límite)	En espacios infinitos, DFS puede perderse por una rama infinita sin retroceder nunca. Con límite de profundidad, es completo.
Optimalidad	No	Encuentra el primer camino, no el más corto. Puede devolver uno de 50 pasos cuando existe uno de 3.
Tiempo	$O(b^m)$	$m$ es la profundidad máxima. Peor que BFS si $m \gg d$.
Espacio	$O(b \cdot m)$	Solo almacena el camino actual y sus hermanos no explorados. Esta es su gran ventaja.

La diferencia entre tiempo y memoria se ve mejor separando las dos fórmulas:

$$T_{\text{DFS}}(m) = O(b^m)$$ $$M_{\text{DFS}}(m) = O(b \cdot m)$$

Símbolo	Significado	Ejemplo
$T_{\text{DFS}}(m)$	Trabajo máximo si DFS baja hasta profundidad $m$.	Puede ser enorme si la rama mala es muy profunda.
$M_{\text{DFS}}(m)$	Memoria necesaria para camino actual y alternativas pendientes.	Con $b=10, m=20$, unos $200$ nodos.
$m$	Profundidad máxima explorada.	$m=20$.

La ventaja de memoria de DFS es dramática. Con $b=10, m=20$, DFS mantiene del orden de:

$$b \cdot m = 10 \cdot 20 = 200$$

nodos de memoria. BFS para una frontera comparable podría necesitar $10^{20}$ nodos. DFS es el único algoritmo viable para espacios profundos sin heurística, pero esa frugalidad se paga con ausencia de optimalidad y riesgo de perderse.⁹

DLS: DFS con un límite

Antes de IDS conviene nombrar la pieza que lo sostiene: la búsqueda con límite de profundidad (depth-limited search, DLS). Es DFS con una frontera artificial: explora en profundidad, pero nunca baja más allá de un límite $L$. Si alcanza $L$ sin encontrar la meta, da marcha atrás como si esa rama se hubiera agotado.

función DLS(s, L, visitados):
    si ES-META(s): return s
    si L = 0: return CORTE                  // límite alcanzado
    para cada acción a en A(s):
        s' ← f(s, a)
        si s' ∉ visitados:
            r ← DLS(s', L - 1, visitados ∪ {s'})
            si r ≠ FRACASO y r ≠ CORTE: return r
    return CORTE si alguna rama tocó el límite, si no FRACASO

DLS resuelve el problema de las ramas infinitas de DFS, porque con un $L$ finito siempre termina, pero introduce otro: si eliges $L$ menor que la profundidad de la solución, no la encuentras; si lo eliges demasiado grande, vuelves a pagar tiempo y memoria de más. Es completo solo cuando $L \geq d$. La distinción entre CORTE (se alcanzó el límite y quizá había solución más abajo) y FRACASO (la rama se agotó de verdad) es justo lo que permite a IDS decidir si merece la pena subir el límite una vuelta más.

IDS: lo mejor de dos mundos

El Iterative Deepening Search (IDS) combina la optimalidad de BFS con la memoria de DFS.¹⁰ La idea es simple: ejecuta DFS con límite de profundidad $L = 0, 1, 2, \ldots$ hasta encontrar la solución:

función IDS(problema):
    para L = 0, 1, 2, ... hasta ∞:
        resultado ← DFS-LIMITADO(s₀, L)
        si resultado ≠ FRACASO: return resultado

Parece ineficiente, porque cada iteración reexplora los niveles anteriores, pero el coste de la reexploración es sorprendentemente bajo: los niveles profundos dominan el coste total. El número aproximado de nodos expandidos por IDS hasta profundidad $d$ es:

$$N_{\text{IDS}}(d) = \sum_{\ell=0}^{d} (d-\ell+1)b^\ell$$

Símbolo	Significado	Ejemplo
$\ell$	Nivel del árbol que se reexplora en varias iteraciones.	El nivel 0 se toca $d+1$ veces.
$d-\ell+1$	Número de veces que IDS vuelve a visitar el nivel $\ell$.	Si $d=3$, el nivel 1 se visita 3 veces.
$b^\ell$	Nodos aproximados del nivel $\ell$.	Con $b=10$, el nivel 3 tiene $1\,000$ nodos.

Comparado con BFS:

$$\frac{N_{\text{IDS}}}{N_{\text{BFS}}} \approx \frac{b}{b-1}$$

Para $b=10$:

$$\frac{10}{9} \approx 1.11$$

IDS explora aproximadamente un 11 % más de nodos que BFS, pero con un consumo de memoria $O(b \cdot d)$ en lugar de $O(b^d)$.¹¹ Es el algoritmo preferido cuando el espacio de búsqueda es grande, la profundidad de la solución es desconocida y no hay heurística disponible.

UCS: cuando cada paso cuesta distinto

BFS asume que todos los pasos cuestan lo mismo. Pero en el mundo real, un paso puede costar 5 y otro 500. BFS encuentra el camino con menos pasos, no el más barato.

UCS generaliza BFS reemplazando la cola por una cola de prioridad ordenada por $g(n)$, el coste acumulado desde el estado inicial hasta $n$.¹² En cada paso, UCS expande el nodo con menor $g(n)$:

$$g(n) = \sum_{i=1}^{k} c(s_{i-1}, a_i)$$

Símbolo	Significado	Ejemplo
$g(n)$	Coste acumulado desde el estado inicial hasta el nodo $n$.	Llegar a $D$ cuesta 7.
$c(s_{i-1}, a_i)$	Coste de aplicar la acción $a_i$ desde el estado anterior.	Una carretera de 5 km o una acción con coste 5.
$k$	Número de acciones del camino hasta $n$.	Tres movimientos: $k=3$.
$s_0 \to s_1 \to \ldots \to s_k$	Secuencia de estados recorrida hasta llegar a $n$.	$A \to C \to D$.

La política de extracción queda así:

$$n_t = \arg\min_{n \in F_t} g(n)$$

Si dos caminos llegan al mismo estado, UCS conserva el de menor coste:

$$g_{\text{nuevo}}(s') = g(n_t) + c(n_t, a)$$ $$g(s') \leftarrow \min\left(g(s'), g_{\text{nuevo}}(s')\right)$$

Símbolo	Significado	Ejemplo
$n_t$	Nodo extraído de la frontera en la iteración $t$.	$C$, porque $g(C)=2$.
$F_t$	Frontera ordenada por coste acumulado.	$[(C,2), (B,5)]$.
$g_{\text{nuevo}}(s')$	Coste candidato para llegar a un sucesor.	Si $g(C)=2$ y $c(C,D)=5$, entonces $g_{\text{nuevo}}(D)=7$.
$\min$	Operación que se queda con el camino más barato conocido.	Si ya había $D=9$, se reemplaza por $D=7$.

Ejemplo concreto:

Frontera: [(A, g=0)]            → extraer A, añadir B(g=5), C(g=2)
Frontera: [(C, g=2), (B, g=5)]  → extraer C (menor coste), añadir D(g=7)
Frontera: [(B, g=5), (D, g=7)]  → extraer B, añadir E(g=11)

Observa que B se descubrió antes que C, pero C se expandió primero porque su coste acumulado era menor. UCS no discrimina por antigüedad: solo le importa el coste.

Propiedades formales

Propiedad	Valor	Condición
Completitud	Sí	Todos los costes $c(s,a) \geq \epsilon > 0$
Optimalidad	Sí	El primer nodo meta extraído es óptimo
Tiempo	$O(b^{1 + \lfloor C^*/\epsilon \rfloor})$	$C^*$ = coste solución óptima, $\epsilon$ = coste mínimo
Espacio	$O(b^{1 + \lfloor C^*/\epsilon \rfloor})$	Similar al tiempo en el peor caso

BFS es un caso especial de UCS donde $c(s,a) = 1$ para toda acción. En ese caso, $g(n) = \text{profundidad}(n)$ y UCS se comporta exactamente como BFS.¹³

Búsqueda bidireccional

Hay una idea que reduce el coste de la búsqueda ciega de forma espectacular: buscar desde los dos extremos a la vez. En lugar de explorar solo desde el estado inicial hacia la meta, la búsqueda bidireccional lanza dos búsquedas simultáneas, una hacia delante desde $s_0$ y otra hacia atrás desde la meta, y para en cuanto las dos fronteras se tocan.

La razón por la que ayuda tanto es geométrica. Una búsqueda que llega a profundidad $d$ explora del orden de $b^d$ nodos. Dos búsquedas que se encuentran en el medio llegan cada una solo a profundidad $d/2$:

$$b^{d/2} + b^{d/2} = 2\,b^{d/2} \ll b^d$$

Símbolo	Significado	Ejemplo
$b$	Factor de ramificación medio.	$b = 10$.
$d$	Profundidad de la solución.	$d = 6$.
$b^{d/2}$	Nodos que explora cada una de las dos mitades.	$10^3 = 1\,000$ por lado.
$2\,b^{d/2}$	Coste total aproximado de las dos búsquedas.	$2\,000$ frente a $10^6$.

En palabras: con $b=10$ y $d=6$, una búsqueda normal toca del orden de un millón de nodos; dos búsquedas que se encuentran en el medio tocan unos dos mil. La diferencia entre $b^d$ y $b^{d/2}$ es la diferencia entre inviable y trivial.

El precio es que no siempre se puede aplicar. Hace falta poder buscar hacia atrás desde la meta, es decir, conocer los predecesores de un estado; que la meta sea un estado concreto y no una propiedad abstracta; y comprobar de forma eficiente si las dos fronteras ya se han tocado. Cuando se cumplen esas condiciones, es difícil de batir.

Comparar búsquedas como ingeniero

Una comparación útil no se queda en “este algoritmo encuentra camino”. Debe registrar la traza de expansión y métricas mínimas. Si no las registras, no puedes explicar por qué BFS encontró una solución rápida pero cara, por qué DFS tuvo suerte o por qué UCS tardó más pero devolvió menor coste.

Métrica	Qué mide	Por qué importa
Estados expandidos	Cuántas veces sacaste un nodo de la frontera.	Aproxima trabajo computacional.
Estados generados	Cuántos sucesores se produjeron.	Mide cuánto crece el árbol aunque no todo se expanda.
Frontera máxima	Máximo tamaño de la frontera.	Aproxima presión de memoria.
Profundidad de solución	Número de acciones del camino devuelto.	BFS optimiza esto si los costes son uniformes.
Coste de solución	Suma de costes $g(n)$.	UCS optimiza esto si los costes son positivos.
Traza	Orden exacto de expansión.	Permite revisar empates, ciclos y decisiones de frontera.

También hay un detalle profesional que suele pasarse por alto: el desempate. Si dos nodos tienen el mismo coste, la implementación debe decidir cuál sale primero. Dos implementaciones correctas de UCS pueden expandir nodos en orden distinto si no fijan una regla estable de desempate. Para comparar runs, fija el orden de sucesores y el criterio de desempate.

Un ejemplo trazado

Veámoslo sobre un grafo concreto. Cinco estados, con estos costes por arista y orden de sucesores alfabético:

• A → B (coste 1), A → C (coste 5)
• B → D (coste 1)
• C → E (coste 1)
• D → E (coste 1)

El estado inicial es A y la meta es E. Hay dos caminos: A → C → E, con dos pasos y coste 6, y A → B → D → E, con tres pasos y coste 3. El más corto en pasos no es el más barato.

Algoritmo	Orden de expansión	Camino devuelto	Pasos	Coste
BFS	A, B, C, D, E	A → C → E	2	6
DFS	A, B, D, E	A → B → D → E	3	3
UCS	A, B, D, E	A → B → D → E	3	3

BFS descubre la meta por la rama más corta en pasos (A → C → E) y devuelve un camino caro. UCS ordena por coste acumulado, así que expande A, B y D, y saca E con $g=3$ antes de mirar siquiera C, que tiene $g=5$: devuelve el camino óptimo en coste. DFS, con este orden de sucesores, coincide con UCS por suerte; cambia el orden de las aristas y devolverá otra cosa, porque no tiene ninguna garantía. Es exactamente la comparación que puedes reproducir en el cuaderno del facsímil.

Tabla comparativa

Algoritmo	Frontera	Completo	Óptimo	Tiempo	Espacio
BFS	Cola (FIFO)	Sí	Sí (costes = 1)	$O(b^d)$	$O(b^d)$
DFS	Pila (LIFO)	No (sin lím.)	No	$O(b^m)$	$O(b \cdot m)$
UCS	Cola prioridad ($g$)	Sí	Sí	$O(b^{1+\lfloor C^*/\epsilon \rfloor})$	$O(b^{1+\lfloor C^*/\epsilon \rfloor})$
IDS	Pila (LIFO, repetido)	Sí	Sí (costes = 1)	$O(b^d)$	$O(b \cdot d)$
Bidireccional	Dos colas (FIFO)	Sí	Sí (costes = 1)	$O(b^{d/2})$	$O(b^{d/2})$

Donde $b$ = factor de ramificación, $d$ = profundidad de la solución más superficial, $m$ = profundidad máxima, $C^*$ = coste de la solución óptima, $\epsilon$ = coste mínimo de cualquier acción.

En el día a día

BFS es la base del web crawling, donde se explora internet por niveles de enlaces, de los algoritmos de «seis grados de separación» en redes sociales y de cualquier problema donde necesites garantizar el camino más corto en un grafo no ponderado. Siempre que «más cerca» signifique «menos saltos», BFS es la herramienta natural.

DFS aparece en los analizadores sintácticos, que recorren el árbol de sintaxis en profundidad, en la resolución de laberintos con poca memoria y como base del backtracking que veremos en el capítulo 7 sobre CSP. También es el algoritmo natural para generar permutaciones y combinaciones, donde interesa agotar una rama antes de probar la siguiente.

UCS está en el corazón de los sistemas de navegación. Google Maps no usa BFS, porque las carreteras no miden todas lo mismo: usa UCS, o A*, que es UCS con heurística, para encontrar rutas óptimas en grafos con pesos. En cuanto el coste deja de ser uniforme, UCS es el mínimo imprescindible.

IDS es el algoritmo preferido en motores de ajedrez y otros juegos con espacio de búsqueda profundo y factor de ramificación alto, donde BFS se queda sin memoria y DFS sin garantías. La búsqueda bidireccional, por su parte, aparece cuando se conoce la meta y se puede ir hacia atrás, por ejemplo al resolver un cubo de Rubik desde el estado actual y desde el resuelto a la vez.

Por qué debería importarte

BFS, DFS y UCS no son algoritmos para memorizar: son patrones de diseño algorítmico. El patrón es «frontera + bucle». La elección de la estructura de datos para la frontera es la decisión de diseño que determina todas las propiedades del algoritmo resultante.

Este principio, una decisión de implementación aparentemente menor que determina propiedades asintóticas, es recurrente en informática. Y en IA, es la base sobre la que se construye A*: UCS con una heurística añadida a la prioridad. Si no entiendes por qué BFS explora por niveles y DFS se lanza en profundidad, no entenderás por qué A* es mejor que ambos.¹⁴

Dónde solía tropezar yo

Error	Por qué es un error	Antídoto
Usar DFS sin límite en espacios infinitos	DFS se pierde por una rama infinita sin retroceder. El algoritmo nunca termina.	Usa IDS o establece un límite de profundidad basado en el conocimiento del dominio.
Asumir que BFS es siempre mejor que DFS	BFS garantiza optimalidad pero su consumo de memoria es exponencial. Para $b=10, d=15$, BFS necesita petabytes de RAM.	Evalúa $b$ y $d$ antes de elegir. Si $b^d$ supera la memoria disponible, usa IDS o DFS con límite.
Usar BFS con costes no uniformes	BFS optimiza el número de pasos, no el coste. Si las acciones tienen costes distintos, BFS no encuentra el camino óptimo.	Usa UCS. BFS es UCS con $c(s,a)=1$; fuera de ese caso, UCS es la herramienta correcta.
No detectar estados repetidos	Sin un conjunto visitados, los tres algoritmos pueden quedar atrapados en ciclos infinitos.	Mantén visitados y comprueba antes de añadir a la frontera. Es la optimización más rentable en búsqueda.

Cómo encaja todo

El capítulo anterior definió el contrato del problema. Este capítulo enseña que, una vez tienes estados y acciones, la decisión crítica es la política de frontera. Cambiar una cola por una pila o por una cola de prioridad cambia garantías, memoria y coste encontrado.

Esto prepara el salto al capítulo 3: A* no aparece de la nada. Es UCS con una estimación del coste restante. Primero entiendes $g(n)$; después podrás entender $g(n)+h(n)$.

graph TD
    subgraph "Capítulo 2: Algoritmos ciegos"
        GEN["Bucle genérico:<br/>extraer → comprobar → expandir → añadir"]
        FRONTERA["Frontera: núcleo del algoritmo"]
        COLA["Cola FIFO"]
        PILA["Pila LIFO"]
        CPRIOR["Cola prioridad por g(n)"]
    end
    subgraph "Propiedades formales"
        COMPLETITUD["Completitud: ¿siempre encuentra solución?"]
        OPTIMALIDAD["Optimalidad: ¿encuentra la mejor?"]
        COMPLEJIDAD["Complejidad: O(b^d) vs O(b·m)"]
    end
    subgraph "Algoritmos resultantes"
        BFS["BFS: completo, óptimo, O(b^d) espacio"]
        DFS["DFS: no completo, no óptimo, O(b·m) espacio"]
        UCS["UCS: completo, óptimo, generaliza BFS"]
        IDS["IDS: completo, óptimo, O(b·d) espacio"]
    end
    subgraph "Conexiones"
        CAP1["Espacio de estados (cap. 1)"]
        ASTAR["A* (cap. 3)"]
        BACKTRACK["Backtracking CSP (cap. 7)"]
    end

    GEN --> FRONTERA
    FRONTERA -->|"implementada con"| COLA
    FRONTERA -->|"implementada con"| PILA
    FRONTERA -->|"implementada con"| CPRIOR
    COLA -->|"produce"| BFS
    PILA -->|"produce"| DFS
    PILA -->|"con límites crecientes produce"| IDS
    CPRIOR -->|"produce"| UCS
    BFS -->|"garantiza"| COMPLETITUD
    BFS -->|"garantiza"| OPTIMALIDAD
    BFS -->|"tiene"| COMPLEJIDAD
    DFS -->|"tiene"| COMPLEJIDAD
    UCS -->|"garantiza"| OPTIMALIDAD
    CAP1 -.->|"define los"| GEN
    UCS -.->|"base de"| ASTAR
    DFS -.->|"base de"| BACKTRACK
    IDS -.->|"inspira"| ASTAR

    style CAP1 stroke-dasharray: 5 5
    style ASTAR stroke-dasharray: 5 5
    style BACKTRACK stroke-dasharray: 5 5
    style FRONTERA fill:#F5F5F5,stroke:#000000,stroke-width:2
    style UCS fill:#F5F5F5,stroke:#000000,stroke-width:2

Vocabulario aprendido

Término	Definición
BFS	Algoritmo de búsqueda por niveles con cola FIFO. Completo y óptimo para costes uniformes. $O(b^d)$ en tiempo y espacio.
DFS	Algoritmo de búsqueda en profundidad con pila LIFO. $O(b \cdot m)$ en espacio pero no es completo ni óptimo sin límite.
UCS	Algoritmo con cola de prioridad por $g(n)$. Generaliza BFS para costes no uniformes. Óptimo con costes positivos.
IDS	DFS repetido con límites crecientes. Combina optimalidad de BFS con bajo consumo de memoria de DFS.
DLS	DFS con un límite de profundidad fijo. Completo solo si el límite es mayor o igual que la profundidad de la solución.
Búsqueda bidireccional	Dos búsquedas simultáneas, desde el inicio y desde la meta, que se encuentran en el medio. Coste $O(b^{d/2})$.
Factor de ramificación ($b$)	Número medio de sucesores por estado. Determina la complejidad exponencial de la búsqueda.
Traza de expansión	Orden en el que el algoritmo extrae estados de la frontera. Permite auditar la búsqueda.
Frontera máxima	Tamaño máximo que alcanza la frontera durante la ejecución. Aproxima presión de memoria.
Coste acumulado	$g(n)$: suma de costes desde el estado inicial hasta el nodo actual.

Antes de pasar página

• ¿Puedo escribir el pseudocódigo del bucle genérico de búsqueda? (Si no, vuelve a «El bucle genérico».)
• ¿Sé qué estructura de datos usa la frontera en BFS, DFS y UCS? (Cola, pila, cola de prioridad.)
• ¿Puedo explicar las propiedades formales (completitud, optimalidad, complejidad) de cada algoritmo? (Si no, vuelve a las tablas de propiedades.)
• ¿Entiendo por qué IDS es preferible a BFS en espacios profundos, y qué papel juega el DLS dentro de él? (Si no, vuelve a «DLS» e «IDS: lo mejor de dos mundos».)
• ¿Sé cuándo se puede aplicar la búsqueda bidireccional y por qué pasa de $b^d$ a $b^{d/2}$? (Si no, vuelve a «Búsqueda bidireccional».)
• ¿Sé explicar camino, coste, nodos expandidos y frontera máxima de una búsqueda? (Si no, vuelve a «Comparar búsquedas como ingeniero».)

En resumen

Idea fuerza	Detalle
La frontera lo decide todo.	Una cola produce BFS. Una pila produce DFS. Una cola de prioridad por $g(n)$ produce UCS. El resto del bucle es idéntico.
BFS es óptimo en pasos pero devorador de memoria. DFS es frugal en memoria pero ni completo ni óptimo.	IDS combina lo mejor de ambos: optimalidad de BFS con memoria de DFS, a costa de reexplorar (~11 % más de nodos).
UCS es BFS generalizado: optimiza coste, no pasos.	Con costes uniformes, UCS = BFS. Con costes variables, solo UCS (o A*) garantiza optimalidad.
Una búsqueda seria deja traza.	Sin orden de expansión, frontera máxima y coste acumulado no puedes comparar algoritmos de forma profesional.

Para saber más

Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136

Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson.

Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann.

Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley.

Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press.

Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill.

Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. https://aima.cs.berkeley.edu/

Notas

1. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. La sección 3.4 demuestra que todos los algoritmos de búsqueda no informada comparten la misma estructura algorítmica y que su comportamiento queda completamente determinado por la política de extracción de la frontera. ↩

2. Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann. El capítulo 7 presenta el algoritmo genérico de búsqueda en grafos que unifica BFS, DFS y UCS. ↩

3. Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press. El capítulo 3 presenta este marco unificado y demuestra que encapsula toda la familia de algoritmos de búsqueda no informada. ↩

4. Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill. El capítulo 3 analiza BFS en detalle, incluyendo su implementación con cola y el análisis de complejidad. ↩

5. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. ↩

6. Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson. La sección 3.2 cuantifica el problema de memoria de BFS y motiva la necesidad de DFS e IDS. ↩

7. Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press. ↩

8. Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann. El capítulo 7 explica la equivalencia entre DFS con pila explícita y DFS recursivo, y analiza las implicaciones para el consumo de memoria. ↩

9. Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill. ↩

10. Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson. ↩

11. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. ↩

12. Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136 ↩

13. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. El capítulo 2 demuestra formalmente que UCS es una generalización de BFS y que A* es a su vez una generalización de UCS. ↩

14. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. El capítulo 3 demuestra cómo A* emerge naturalmente de UCS al incorporar una heurística en la función de evaluación. ↩

Capítulo 03: Greedy, A* y heurísticas: buscar con estimaciones

Entrando en el tema

Hasta ahora has explorado a ciegas. BFS, DFS, UCS: algoritmos que no saben nada del problema salvo qué acciones existen y cuánto cuestan. Funcionan, pero son terriblemente ineficientes: exploran miles de estados que no llevan a ninguna parte.

Ahora imagina que tienes una estimación matemática barata. Una función $h(n)$ que, para cualquier estado $n$, estima cuánto falta para llegar a la meta. No es exacta, porque si lo fuera ya habrías resuelto el problema, pero es útil. Con esa estimación, puedes priorizar los estados que parecen más prometedores e ignorar los que se alejan. Puedes encontrar la solución explorando cientos de estados en vez de millones.

Esa función se llama heurística. Y los algoritmos que la usan, Greedy y A*, son piezas centrales de la búsqueda informada.¹ Sin heurísticas, muchos problemas de rutas, planificación y videojuegos tendrían que mirar demasiadas opciones antes de responder.

Greedy best-first: seguir solo la estimación

El algoritmo greedy best-first search es el más simple de los informados. Evalúa cada estado exclusivamente con la heurística $h(n)$, la estimación de lo que falta hasta la meta, e ignora completamente el coste acumulado $g(n)$.²

Es como ir de Madrid a Berlín mirando exclusivamente la distancia en línea recta: «Barcelona está más cerca de Berlín que Lisboa, voy a Barcelona. París está más cerca que Roma, voy a París». Nunca mira hacia atrás. Nunca considera si el camino acumulado es bueno o si la ruta aparente esconde un desvío enorme.

Formalmente, Greedy usa esta función de evaluación:

$$f_{\text{Greedy}}(n) = h(n)$$

Y en cada iteración extrae de la frontera el nodo que parece más cercano a la meta:

$$n_t = \arg\min_{n \in F_t} h(n)$$

Símbolo	Significado	Ejemplo
$f_{\text{Greedy}}(n)$	Prioridad que Greedy asigna al nodo $n$.	Si $h(B)=3$, la prioridad de $B$ es 3.
$h(n)$	Estimación de coste desde $n$ hasta la meta.	Distancia Manhattan hasta la salida.
$F_t$	Frontera en la iteración $t$.	$\{B,C,D\}$.
$\arg\min$	Operación que devuelve el elemento con menor valor.	Si $h(C)=2$, Greedy elige $C$.

Mira el detalle peligroso: no aparece $g(n)$. Si llegar hasta $C$ ya te ha costado 40 pasos y llegar hasta $B$ solo 2, Greedy no lo ve. Solo pregunta: «¿cuál parece más cerca de la meta desde aquí?».

Ventaja: velocidad. Si $h(n)$ es razonablemente buena, Greedy encuentra una solución explorando muy pocos estados. En navegación con distancia euclídea, suele ir directo al destino.

Riesgo: no es ni completo ni óptimo. Puede quedarse atascado en un mínimo local, eligiendo repetidamente estados que parecen buenos según $h$ pero que no llevan a ninguna parte. Y el camino que encuentra rara vez es el mejor: la heurística puede empujarte hacia una montaña, porque en línea recta parece más corta, cuando el camino óptimo da un rodeo por el valle.³

En agentes LLM modernos, Greedy equivale a elegir la tool que parece obvia sin verificar restricciones: «¿cuál es la respuesta? Voy a buscar en la base de datos». Pero quizás antes necesitabas comprobar permisos. La heurística te empujó en una dirección que parecía correcta pero no lo era.

La tabla de propiedades queda así:

Propiedad	Valor	Por qué
Completitud	No en general	Puede entrar en ciclos o perseguir una rama infinita que parece prometedora.
Optimalidad	No	Ignora el coste acumulado $g(n)$.
Tiempo	$O(b^m)$ en el peor caso	Si la heurística engaña, puede explorar una rama profunda entera.
Espacio	$O(b^m)$ en el peor caso	Mantiene frontera y visitados como otros algoritmos de búsqueda en grafos.

A*: coste real + estimación

A* corrige el defecto fundamental de Greedy combinando dos piezas de información en una sola función de evaluación:⁴

$$f(n) = g(n) + h(n)$$

Símbolo	Significado	Cálculo
$f(n)$	Coste total estimado del camino óptimo que pasa por $n$	$g(n) + h(n)$
$g(n)$	Coste real acumulado desde el inicio hasta $n$	$\sum c(s_{i-1}, a_i)$
$h(n)$	Heurística: coste estimado desde $n$ hasta la meta	Específica del problema
$h^*(n)$	Coste real óptimo desde $n$ hasta la meta	Desconocido (es lo que buscamos)

$g(n)$ es lo que ya has pagado. $h(n)$ es lo que estimas que te queda. $f(n)$ es el total estimado. A* expande siempre el nodo con menor $f(n)$.⁵

La política de extracción de A* es:

$$n_t = \arg\min_{n \in F_t} \left(g(n) + h(n)\right)$$

Nodo	$g(n)$: coste ya pagado	$h(n)$: estimación restante	$f(n)=g(n)+h(n)$	Quién lo elegiría
$B$	8	2	10	Greedy, porque $h(B)$ es menor.
$C$	3	4	7	A*, porque $f(C)$ es menor.

Este ejemplo pequeño captura toda la diferencia. Greedy ve $2 < 4$ y elige $B$. A* ve $10 > 7$ y elige $C$, porque entiende que lo que ya has pagado también cuenta.

Esto resuelve el problema de Greedy. Si la heurística te empuja hacia un camino que parece corto pero es caro, $g(n)$, el coste real acumulado, penaliza esa decisión. A* no solo mira lo prometedor: también penaliza los caminos que ya han costado demasiado.⁶

Propiedades formales de A*

Admisibilidad. Una heurística $h(n)$ es admisible si nunca sobreestima el coste real hasta la meta. Formalmente:

$$0 \leq h(n) \leq h^*(n)$$

Símbolo	Significado	Ejemplo
$h(n)$	Estimación que calculas rápido.	Distancia en línea recta: 12 km.
$h^*(n)$	Coste real óptimo desde $n$ hasta la meta.	Mejor carretera real: 15 km.
$0 \leq h(n)$	La heurística no puede ser negativa.	No tiene sentido decir “faltan -3 km”.
$h(n) \leq h^*(n)$	La heurística no promete más de lo que existe.	12 km no sobreestima 15 km.

La distancia en línea recta es admisible porque ningún camino por carreteras puede ser más corto que la línea recta. Una heurística que estime tiempos ignorando semáforos, cuestas o peajes puede dejar de ser admisible si promete rutas demasiado optimistas.⁷

Teorema de optimalidad. En búsqueda en árbol, si $h(n)$ es admisible, A* encuentra un camino de coste mínimo. En búsqueda en grafo, la garantía requiere además gestionar correctamente reaperturas de estados o trabajar con una heurística consistente. La demostración se basa en que A* no termina hasta haber descartado los nodos que podrían tener $f(n) < C^*$ (el coste óptimo) y, cuando encuentra la meta, su $f$ es igual a $g$ porque $h(\text{meta}) = 0$.

Consistencia (monotonicidad). Una propiedad más fuerte que la admisibilidad:

$$h(n) \leq c(n,a,n') + h(n')$$

Símbolo	Significado	Ejemplo
$c(n,a,n')$	Coste de ir de $n$ a $n'$ aplicando $a$.	Moverte una casilla cuesta 1.
$h(n)$	Estimación antes de moverte.	Faltan 8 pasos estimados.
$h(n')$	Estimación después de moverte.	Faltan 7 pasos estimados.

La lectura es sencilla: la estimación desde $n$ no puede ser mayor que «lo que cuesta dar un paso» más «lo que estimas desde el siguiente estado». Si $h$ es consistente, entonces $f(n)$ nunca baja a lo largo de un camino:

$$f(n') = g(n) + c(n,a,n') + h(n') \geq g(n) + h(n) = f(n)$$

Por eso A* con heurística consistente puede tratar los estados como cerrados la primera vez que los expande: no necesitará reabrirlos más tarde con un coste mejor.⁸

Un ejemplo trazado de A*

Veamos A* completo sobre un grafo pequeño. Cuatro estados, con estos costes y esta heurística admisible:

• A → B (coste 1), A → C (coste 4)
• B → D (coste 5), C → D (coste 1)
• $h(A)=4$, $h(B)=4$, $h(C)=1$, $h(D)=0$

El estado inicial es A y la meta es D. A* expande siempre el nodo de menor $f=g+h$:

Paso	Se extrae ($f$)	Frontera resultante
1	A, $f=0+4=4$	B ($f=5$), C ($f=5$)
2	B, $f=1+4=5$	C ($f=5$), D ($f=6$)
3	C, $f=4+1=5$	D ($f=5$, actualizado desde 6)
4	D, $f=5$	meta: camino A → C → D, coste 5

Fíjate en el paso 3. Al expandir B, A* descubre D con $f=6$, por el camino A → B → D, que cuesta 6. Pero al expandir C encuentra un camino mejor a D, con $f=5$, por A → C → D, que cuesta 5, y actualiza su coste. Cuando por fin saca D, lo hace con el coste óptimo. Greedy, que solo mira $h$, habría ido directo a C y luego a D sin dudar; A* da el mismo resultado aquí, pero porque ha tenido en cuenta $g$, no por suerte. Es la misma traza que puedes reproducir en el cuaderno del facsímil.

Heurísticas: el arte de saber qué ignorar

Una heurística es una función $h: S \to \mathbb{R}^+_0$ que, dado un estado, devuelve una estimación. Diseñar una buena heurística exige escoger información que aporte señal, sea barata de calcular y no rompa las garantías que quieres conservar.⁹

En una rejilla, dos heurísticas clásicas son:

$$h_{\text{Manhattan}}(n) = |x_n - x_{\text{meta}}| + |y_n - y_{\text{meta}}|$$ $$h_{\text{Euclidea}}(n) = \sqrt{(x_n - x_{\text{meta}})^2 + (y_n - y_{\text{meta}})^2}$$

Símbolo	Significado	Ejemplo
$x_n, y_n$	Coordenadas del estado actual.	$n=(2,3)$.
$x_{\text{meta}}, y_{\text{meta}}$	Coordenadas de la meta.	$\text{meta}=(7,6)$.
$	x_n-x_{\text{meta}}	$
$	y_n-y_{\text{meta}}	$

Con esos números:

$$h_{\text{Manhattan}}(n) = 5 + 3 = 8$$ $$h_{\text{Euclidea}}(n) = \sqrt{5^2 + 3^2} = \sqrt{34} \approx 5.83$$

Si solo puedes moverte en horizontal y vertical, Manhattan suele ser más informativa. Si puedes moverte en cualquier dirección, la euclídea encaja mejor.

Tipo	Ejemplo	Admisible	Informativa
Buena	Distancia euclídea en navegación	Sí	Alta
Aceptable	Distancia Manhattan en rejilla	Sí	Media
Mala	«Dificultad del examen = páginas del temario»	No	Baja
Engañosa	«Número de paquetes que faltan»	No	Engaña

La diferencia entre una heurística buena y una mala puede ser la diferencia entre explorar 100 estados y 100 000. Una heurística perfecta, con $h(n) = h^*(n)$, haría que A* fuera directamente a la solución sin explorar nada más, pero calcular $h^*(n)$ es tan difícil como resolver el problema original. El arte está en aproximar $h^*(n)$ sin calcularla exactamente.

Una técnica clásica es relajar el problema: eliminar alguna restricción para crear una versión más fácil. La solución del problema relajado es una heurística admisible para el problema original.¹⁰ Por ejemplo, la distancia en línea recta es la solución al problema de navegación relajado donde ignoras los obstáculos y las carreteras.

También comparamos heurísticas por dominancia:

$$h_1 \succeq h_2 \quad \Longleftrightarrow \quad \forall n,\; h_1(n) \geq h_2(n)$$

siempre que ambas sigan siendo admisibles. Si $h_1$ domina a $h_2$, A* con $h_1$ no expande más nodos que A* con $h_2$. Dicho en castellano: cuanto más cerca esté $h(n)$ de $h^*(n)$ sin pasarse, menos trabajo hace A*.

Auditar una heurística antes de usarla

Una heurística no se acepta porque “suena razonable”. Se audita. Para problemas pequeños, puedes calcular $h^*(n)$, el coste óptimo real desde cada estado hasta la meta, y comparar.

Prueba	Fórmula	Qué detecta
No negatividad	$h(n)\geq0$	Estimaciones sin sentido.
Meta a cero	$h(\text{meta})=0$	Heurísticas que penalizan llegar.
Admisibilidad	$h(n)\leq h^*(n)$	Sobreestimaciones que rompen optimalidad de A*.
Consistencia	$h(n)\leq c(n,a,n')+h(n')$	Necesidad de reabrir nodos en grafos.
Dominancia	$h_1(n)\geq h_2(n)$ para todo $n$	Qué heurística informará más a A* sin perder garantías.

En producción no siempre puedes conocer $h^*(n)$; si pudieras, ya tendrías resuelto el problema. Pero en entornos pequeños, tests, mapas de juguete o fixtures, esta auditoría es oro: te permite validar que tu heurística no está metiendo una promesa falsa en el algoritmo.

También conviene medir el coste de calcular $h(n)$. Una heurística brillante pero carísima puede perder contra una heurística sencilla si cada evaluación tarda demasiado. A* no solo paga expansiones; también paga evaluaciones de heurística.

Variantes de A*: cuando la memoria o la velocidad aprietan

A* es óptimo, pero tiene un punto débil que comparte con BFS: la memoria. A* guarda en la frontera y en los visitados todos los nodos que descubre, así que en el peor caso necesita espacio exponencial, del orden de $O(b^d)$. En problemas grandes, A* se queda sin memoria mucho antes que sin tiempo. De ese problema nacen dos variantes habituales.

IDA* (A* con profundización iterativa). Aplica a A* la idea del IDS del capítulo anterior. En lugar de un límite de profundidad, usa un límite sobre $f$. Hace una búsqueda en profundidad podando toda rama cuyo $f(n)$ supere el umbral; si no encuentra la meta, sube el umbral al menor $f$ que se pasó del límite y repite. Conserva la optimalidad de A* con heurística admisible, pero su memoria baja a $O(b \cdot d)$, la de DFS. El precio, como en IDS, es reexplorar niveles.

Weighted A*. Da más peso a la heurística para correr más, a cambio de renunciar a la optimalidad garantizada:

$$f(n) = g(n) + w \cdot h(n), \qquad w \geq 1$$

Símbolo	Significado	Ejemplo
$w$	Peso que se da a la heurística.	$w=1$ es A*; $w=2$ confía el doble en la estimación.
$g(n)$	Coste real acumulado.	Lo que ya has pagado.
$h(n)$	Heurística admisible.	Lo que estimas que falta.
$w \cdot h(n)$	Estimación amplificada.	Empuja la búsqueda hacia la meta más agresivamente.

En palabras: cuanto mayor es $w$, más se parece A* a Greedy y menos nodos expande, pero la solución deja de ser óptima. La buena noticia es que el desvío está acotado: con una heurística admisible, Weighted A* devuelve un camino que cuesta como mucho $w$ veces el óptimo. Es un mando con el que cambias calidad por velocidad de forma controlada: en $w=1$ tienes A* y la solución óptima, y subiendo $w$ ganas velocidad aceptando soluciones algo peores.

De hecho, los tres algoritmos del capítulo, junto a UCS, son el mismo esquema con distinto peso sobre la heurística:

En el día a día

En GPS y navegación, A* con $h(n)$ igual a la distancia euclídea es una simplificación útil para entender la idea. Los sistemas reales añaden datos de tráfico, restricciones de giro, jerarquías de carretera y cachés, pero el mecanismo permanece: una heurística buena reduce mucho el espacio que hay que mirar.

En videojuegos, el pathfinding de los personajes no jugadores usa A* con distancia Manhattan para moverse por la rejilla del escenario. Sin una búsqueda informada, los personajes se quedarían atascados contra las paredes o tomarían rutas absurdas que rompen la sensación de inteligencia.

En agentes LLM, una decisión de herramienta puede modelarse como un paso de búsqueda. El modelo propone qué herramienta parece más prometedora, que es el papel de $h(n)$, pero el sistema debería añadir coste acumulado, riesgo, permisos y observación. Si penalizas los caminos que ya han consumido demasiados tokens o llamadas caras, estás metiendo una idea parecida a $g(n)$ en el diseño, justo lo que separa a A* de Greedy.

Por qué debería importarte

A* es uno de los algoritmos centrales de la IA clásica: combina coste real y estimación futura de una forma sorprendentemente clara. La ecuación $f(n) = g(n) + h(n)$ resume décadas de investigación. Pero la lección más profunda no es memorizar el algoritmo: es aprender a diseñar heurísticas que ahorran búsqueda sin romper las garantías que necesitas.

Y este concepto trasciende la IA: en optimización, en diseño de algoritmos, en toma de decisiones, la habilidad de encontrar atajos informados que no comprometan la calidad de la solución es universal. A* formaliza esa tensión entre coste observado y estimación restante.

Dónde solía tropezar yo

Error	Por qué es un error	Antídoto
Heurística no admisible con A*	Si $h(n)$ sobreestima el coste real, A* puede pasar de largo la solución óptima.	Verifica $0 \leq h(n) \leq h^*(n)$. La distancia euclídea y Manhattan son admisibles. Las heurísticas basadas en «coste medio» no lo son.
Confundir Greedy con A*	Greedy ignora $g(n)$: no garantiza optimalidad. A* usa $g(n) + h(n)$: sí la garantiza con $h$ admisible.	Usa A* si necesitas optimalidad. Greedy solo si necesitas una solución rápida y la calidad no es crítica.
Heurística demasiado cara de calcular	Evaluar $h(n)$ cuesta tiempo. Si calcular $h$ tarda más que expandir unos cientos de nodos extra con una heurística más simple, estás perdiendo eficiencia neta.	Mide el tiempo de $h(n)$. Si es más lento que expandir ~100 nodos, simplifica la heurística.

Cómo encaja todo

Este capítulo añade una pieza nueva a la frontera del capítulo 02: ya no ordenas solo por antigüedad o por coste real acumulado. Ahora introduces una estimación del futuro. Esa estimación puede ahorrar muchísimo trabajo, pero solo mantiene garantías si se comporta matemáticamente bien.

La idea seguirá viva en planificación, juegos y agentes: muchas decisiones inteligentes son una mezcla de coste pagado, coste esperado, riesgo y una función de evaluación.

graph TD
    subgraph sgcap["Capítulo 3: Búsqueda informada"]
        FN["Función de evaluación:<br/>coste pagado + estimación"]
        GREEDY["Greedy:<br/>solo la estimación"]
        ASTAR["A*:<br/>coste real + estimación"]
        ADM["Admisibilidad:<br/>nunca sobreestima"]
        CONS["Consistencia:<br/>f no decrece en el camino"]
        WA["Weighted A*:<br/>velocidad por optimalidad"]
        IDA["IDA*:<br/>la memoria de DFS"]
    end
    subgraph sgprev["Capítulos previos"]
        UCS["UCS:<br/>solo coste real (cap. 2)"]
    end
    subgraph sgconex["Conexiones"]
        PLAN["Planificación heurística (cap. 10)"]
        AGENTES["Agentes LLM (cap. 4, fasc. 5)"]
        JUEGOS["Juegos: evaluación heurística (cap. 11)"]
    end

    UCS -->|"añade la estimación"| FN
    FN -->|"ignora el coste"| GREEDY
    FN -->|"suma ambos"| ASTAR
    ASTAR -->|"requiere"| ADM
    CONS -->|"implica"| ADM
    ASTAR -->|"con peso w"| WA
    ASTAR -->|"con poca memoria"| IDA
    ASTAR -->|"fundamento de"| PLAN
    GREEDY -->|"patrón en"| AGENTES
    FN -->|"inspira evaluación en"| JUEGOS

    classDef default fill:#f5f5f5,stroke:#777777,color:#111111;
    style sgcap fill:#fafafa,stroke:#777777,color:#111111
    style sgprev fill:#fafafa,stroke:#777777,color:#111111
    style sgconex fill:#fafafa,stroke:#777777,color:#111111
    style UCS stroke-dasharray: 5 5
    style PLAN stroke-dasharray: 5 5
    style AGENTES stroke-dasharray: 5 5
    style JUEGOS stroke-dasharray: 5 5
    style FN fill:#F5F5F5,stroke:#000000,stroke-width:2
    style ASTAR fill:#F5F5F5,stroke:#000000,stroke-width:2

Vocabulario aprendido

Término	Definición
A*	$f(n)=g(n)+h(n)$. Óptimo si $h$ es admisible.
Heurística admisible	Nunca sobreestima: $0 \leq h(n) \leq h^*(n)$.
Greedy best-first	Solo $h(n)$. Rápido, no óptimo.
Consistencia	$h(n) \leq c(n,a,n') + h(n')$. Más fuerte que admisibilidad.
Relajación	Simplificar el problema para obtener una heurística admisible.
Dominancia heurística	Una heurística admisible domina a otra si estima siempre igual o más sin sobreestimar. Suele reducir expansiones.
Weighted A*	Variante $f(n)=g(n)+w h(n)$. Con $w>1$ puede ser más rápida, pero pierde optimalidad garantizada (coste hasta $w$ veces el óptimo).
IDA*	A* con profundización iterativa sobre $f$. Memoria $O(b \cdot d)$ como DFS, manteniendo la optimalidad con $h$ admisible.

Antes de pasar página

• ¿Puedo escribir $f(n) = g(n) + h(n)$ y explicar cada término? (Si no, vuelve a «A*: coste real + estimación».)
• ¿Entiendo qué significa que $h$ sea admisible? (Si no, vuelve a «Propiedades formales de A*».)
• ¿Sé diferenciar Greedy de A*? (Si no, vuelve a «Greedy best-first» y «A*: coste real + estimación».)
• ¿Puedo auditar una heurística con admisibilidad, consistencia y dominancia? (Si no, vuelve a «Auditar una heurística antes de usarla».)
• ¿Entiendo por qué A* consume memoria exponencial y qué resuelve IDA*? (Si no, vuelve a «Variantes de A*».)
• ¿Sé qué hace Weighted A* con el peso $w$ y qué garantía pierde y conserva? (Si no, vuelve a «Variantes de A*».)
• ¿Sé explicar por qué Weighted A* puede perder optimalidad? (Si no, vuelve a «Variantes de A*: cuando la memoria o la velocidad aprietan».)

En resumen

Idea fuerza	Detalle
A* = UCS + heurística.	$g(n)$ garantiza optimalidad; $h(n)$ añade eficiencia.
Admisibilidad abre la puerta a la optimalidad.	$h(n) \leq h^*(n)$ es la condición suficiente que A* necesita en búsqueda en árbol; en grafos, la consistencia evita reexpansiones.
La heurística lo es todo.	De millones de estados a cientos. El arte está en el equilibrio entre precisión y coste.
Las heurísticas también se testean.	No basta con una estimación plausible: admisibilidad, consistencia, dominancia y coste de cálculo son parte del contrato.

Para saber más

Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136

Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson.

Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann.

Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley.

Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press.

Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill.

Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. https://aima.cs.berkeley.edu/

Notas

1. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. Pearl estableció las bases teóricas de la búsqueda heurística, formalizando conceptos como admisibilidad, consistencia y poder heurístico que permiten comparar rigurosamente distintas heurísticas. ↩

2. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. La sección 3.5 presenta greedy best-first como el primer algoritmo informado, destacando que su velocidad tiene como contrapartida la ausencia de garantías de optimalidad. ↩

3. Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann. La sección 8.2 analiza las limitaciones de Greedy y demuestra con ejemplos concretos por qué ignorar el coste del camino puede llevar a soluciones arbitrariamente malas. ↩

4. Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136. Este artículo presentó A* y demostró formalmente que, con heurística admisible, el algoritmo es óptimo y expande el mínimo número de nodos entre todos los algoritmos óptimos que usan la misma heurística. ↩

5. Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press. ↩

6. Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson. ↩

7. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. El capítulo 3 demuestra el teorema de optimalidad de A*: si $h$ es admisible, A* es óptimo en búsqueda en árbol. ↩

8. Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill. ↩

9. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. Pearl introdujo el concepto de poder heurístico: una heurística $h_1$ domina a $h_2$ si $h_1(n) \geq h_2(n)$ para todo $n$, y una heurística más informada produce una búsqueda más eficiente. ↩

10. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. La sección 3.6 explica cómo derivar heurísticas admisibles a partir de versiones relajadas del problema, siendo la distancia en línea recta el ejemplo canónico (ignorar obstáculos es la relajación). ↩

Capítulo 04: Búsqueda en agentes modernos: del algoritmo a la política

Entrando en el tema

Has aprendido a formular un problema como estados, acciones, meta y coste. Has visto qué ocurre cuando exploras a ciegas con BFS, DFS y UCS. Después has añadido estimaciones heurísticas con Greedy y A*. Ahora toca cerrar este recorrido con una pregunta muy práctica: ¿por qué importa todo esto si hoy hablamos de LLMs, agentes y tools?

Porque muchas decisiones de un agente moderno pueden modelarse como decisiones en un espacio de posibilidades. Puede que no dibuje un árbol de búsqueda en pantalla. Puede que no tenga una cola de prioridad explícita llamada frontier. Pero cuando decide si debe leer un archivo, consultar una base de datos, llamar a una API, pedir aclaración o responder, está eligiendo una acción desde un estado, con costes, restricciones y una meta.¹

El tema central es ese: leer un agente moderno con el lenguaje de la búsqueda clásica, para diseñarlo y auditarlo sin confundir fluidez con buen criterio. Este capítulo cierra los cuatro primeros, que han tratado todos sobre búsqueda, y el siguiente cambia de herramienta hacia las restricciones. Por eso, al final, recogeremos en pocas líneas lo esencial de esos cuatro capítulos: no para terminar, sino para llegar al capítulo de CSP con los cimientos firmes.

El agente racional

La pregunta de fondo no es solo «cómo busca un agente», sino «qué significa que un agente decida bien». Russell y Norvig dan una respuesta precisa: un agente racional selecciona, en cada momento, la acción que maximiza su medida de rendimiento esperada dada la evidencia de que dispone.² No se trata de adivinar el futuro ni de no equivocarse nunca, sino de elegir lo mejor posible con lo que se sabe. La herramienta matemática que formaliza esa idea es la teoría de la decisión y, en concreto, el principio de la utilidad esperada:

$$a^* = \arg\max_{a} \; \mathbb{E}[\,U(\text{resultado}) \mid a, e\,]$$

Símbolo	Significado	Ejemplo
$a^*$	Acción que el agente debería elegir.	Leer la consola antes que editar código.
$U(\cdot)$	Utilidad: cómo de bueno es un resultado para el objetivo.	Resolver el ticket bien, barato y sin romper nada.
$\mathbb{E}[\cdot]$	Valor esperado: promedio ponderado por la probabilidad de cada resultado.	Promedia los desenlaces posibles de una acción incierta.
$e$	Evidencia disponible en ese momento.	Logs leídos, respuestas de herramientas, mensajes previos.

En palabras: de todas las acciones posibles, el agente elige la que, en promedio y dada la evidencia que tiene, conduce a los mejores resultados según su medida de utilidad.

Esto sustituye a la antigua plantilla $F=G+H+R$, que sumaba coste, avance y riesgo a mano. En el marco real, esos tres factores no son sumandos arbitrarios: son componentes de la utilidad $U$. El coste (tokens, latencia, dinero) entra como utilidad negativa, el avance hacia la meta entra como utilidad positiva, y el riesgo entra a través de los resultados malos que una acción puede provocar y de su probabilidad. La diferencia es importante: en lugar de inventar una fórmula propia, se usa el lenguaje estándar con el que la inteligencia artificial razona sobre decisiones desde hace décadas.

Piensa en un agente de soporte que recibe un ticket. Puede responder con una solución inmediata, pedir más datos al cliente o escalar a un humano. La respuesta inmediata es barata pero arriesgada si no entiende bien el problema; escalar es seguro pero lento y caro. Un agente racional no elige por intuición: estima, para cada acción, la utilidad esperada (probabilidad de resolver bien el ticket, descontando coste y descontando el daño esperado de equivocarse) y se queda con la de mayor valor. Esa es la brújula que recorre todo el capítulo.

Decidir cuando el resultado es incierto: el MDP

La fórmula de la utilidad esperada describe una decisión aislada. Pero un agente real encadena muchas decisiones, y cada acción cambia el mundo de forma a veces incierta: ejecutar un test puede pasar o fallar, llamar a una API puede devolver datos o un error. Cuando hay incertidumbre en los resultados y recompensas que se acumulan a lo largo del tiempo, el marco oficial es el Proceso de Decisión de Markov (MDP), una tupla de cinco elementos:

$$\text{MDP} = (S, A, P(s' \mid s,a), R(s,a), \gamma)$$

Símbolo	Significado	Ejemplo
$S$	Conjunto de estados posibles.	Situaciones del agente: ticket sin diagnosticar, test ya ejecutado, etc.
$A$	Conjunto de acciones disponibles.	Leer logs, ejecutar test, responder, escalar.
$P(s' \mid s,a)$	Probabilidad de pasar al estado $s'$ tras hacer $a$ en $s$.	El test falla el 30 % de las veces aunque el arreglo parezca correcto.
$R(s,a)$	Recompensa inmediata de hacer $a$ en $s$.	Premio por resolver, penalización por gastar tokens.
$\gamma$	Factor de descuento entre 0 y 1 que pesa el futuro.	$\gamma=0{,}9$: el futuro importa, pero menos que el presente.

En palabras: un MDP describe un mundo donde el agente está en un estado, elige una acción, recibe una recompensa y salta a un nuevo estado según una probabilidad, una y otra vez, intentando acumular la mayor recompensa posible.

La regla que dice qué hacer en cada estado se llama política, escrita $\pi(s)$: una función que asigna a cada estado la acción a tomar. Para saber cómo de buena es cada situación se usa la función de valor $V^*(s)$, que mide la recompensa total esperada si se actúa de forma óptima desde $s$ en adelante. Esa función cumple la ecuación de Bellman, una de las piezas centrales de la teoría:^{3 4}

$$V^*(s) = \max_{a}\Big[ R(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V^*(s') \Big]$$

Símbolo	Significado	Ejemplo
$V^*(s)$	Valor óptimo de estar en el estado $s$.	Cómo de prometedora es la situación actual.
$\max_{a}$	Se elige la mejor acción posible.	La que maximiza recompensa inmediata más futuro.
$R(s,a)$	Recompensa inmediata.	Lo que se gana ahora mismo.
$\gamma \sum_{s'} P(s'\mid s,a)\,V^*(s')$	Valor futuro descontado y promediado sobre los estados a los que se podría llegar.	El bien que vendrá después, ponderado por su probabilidad.

En palabras: el valor de un estado es la mejor recompensa que puedes conseguir ahora más el valor (descontado) de los estados a los que esa acción te puede llevar, promediado según su probabilidad. La decisión presente y el futuro quedan ligados en una sola ecuación recursiva.

Esto es una presentación introductoria; la resolución de MDP y el aprendizaje de políticas se trata a fondo en el fascículo de aprendizaje por refuerzo.⁵ Aquí basta con ver la conexión con la búsqueda clásica de los capítulos anteriores: A* y UCS son, de hecho, el caso particular del MDP en que el mundo es determinista (cada acción lleva siempre al mismo estado, así que $P$ vale 1 para un único $s'$) y conocido (sabes de antemano el efecto de cada acción). Cuando el resultado deja de ser seguro, la búsqueda de caminos se generaliza al MDP. Imagina un robot de almacén que ordena «avanzar»: el suelo resbala y el 10 % de las veces acaba en la casilla equivocada. Ya no hay un camino fijo que seguir; hay una política que dice, en cada casilla, hacia dónde moverse para maximizar la recompensa esperada a pesar del azar.

Cuando no se ve todo: POMDP y belief state

Hay un detalle que el MDP da por supuesto y que casi nunca se cumple en un agente real: que el agente sabe en qué estado está. Un agente LLM no observa el estado verdadero del mundo. Solo recibe señales parciales: el texto de un log, la respuesta de una herramienta, un mensaje del usuario. El estado real (qué falla exactamente, qué quiere de verdad el cliente) permanece oculto. El marco que añade esta capa es el POMDP, el Proceso de Decisión de Markov parcialmente observable, que incorpora observaciones y obliga al agente a razonar sobre lo que no ve.⁶

Como el estado real es desconocido, el agente mantiene un belief state (estado de creencia): una distribución de probabilidad sobre todos los estados en los que podría estar. En vez de afirmar «el bug está en el módulo de pago», el agente sostiene algo más honesto: «hay un 60 % de probabilidad de que esté en el pago, un 30 % en la red y un 10 % en la base de datos». Cada vez que actúa y observa algo nuevo, recalcula esa creencia con la regla de actualización bayesiana:

$$b'(s') = \eta \, P(o \mid s')\sum_{s} P(s' \mid s,a)\, b(s)$$

Símbolo	Significado	Ejemplo
$b(s)$	Creencia actual: probabilidad de estar en el estado $s$.	60 % pago, 30 % red, 10 % base de datos.
$b'(s')$	Creencia actualizada tras actuar y observar.	Tras leer el log, sube la probabilidad del módulo de red.
$o$	Observación recibida del entorno.	El mensaje de error concreto que devuelve el sistema.
$P(o \mid s')$	Probabilidad de ver esa observación si el estado fuese $s'$.	Cómo de típico es ese error en cada hipótesis de fallo.
$\eta$	Constante de normalización para que las probabilidades sumen 1.	Reescala el resultado a una distribución válida.

En palabras: la nueva creencia combina lo que el agente ya pensaba, hacia dónde le lleva su acción y cómo de compatible es lo que acaba de observar con cada hipótesis; después se renormaliza para que siga siendo una distribución de probabilidad.

Esto sustituye al antiguo $s_t=(m,o,r,q)$, que fingía que el estado del agente era una fotografía exacta y cerrada de lo que sabe. El estado real de un agente que no lo ve todo no es un dato fijo: es una creencia que se actualiza con cada observación. Y esa lectura cambia la forma de diseñarlo, porque obliga a representar la incertidumbre en vez de esconderla.⁷ Un agente de código no «ve» el bug directamente. Mantiene hipótesis sobre dónde está, ejecuta una acción barata para conseguir evidencia (leer el error, correr un test mínimo) y, al observar el resultado, sube la probabilidad de unas hipótesis y baja la de otras. Diagnosticar es, literalmente, actualizar un belief state hasta que una hipótesis domina lo suficiente para actuar sobre ella.

Buscar en el árbol de decisiones: MCTS

Saber que existe una utilidad esperada o una función de valor no dice cómo calcularla cuando el árbol de posibilidades es gigantesco. Los agentes modernos más potentes usan un algoritmo de búsqueda concreto para ello: Monte Carlo Tree Search (MCTS), búsqueda en árbol por muestreo aleatorio. Es el algoritmo detrás de AlphaGo y de varios agentes que exploran cadenas de razonamiento antes de comprometerse con una.⁸ En lugar de explorar el árbol entero, MCTS construye poco a poco las ramas más prometedoras repitiendo cuatro fases.

Las cuatro fases son: selección (bajar por el árbol existente eligiendo acciones según un criterio), expansión (añadir un nodo nuevo al llegar a una rama poco explorada), simulación o rollout (jugar al azar o con una política rápida hasta el final para estimar el resultado) y retropropagación (subir ese resultado por las ramas visitadas, actualizando sus estadísticas). Repetidas miles de veces, estas fases concentran el esfuerzo en las jugadas que de verdad importan.

La pieza clave es cómo se elige qué rama explorar en la fase de selección. MCTS usa la fórmula UCT (el criterio UCB aplicado a árboles), que equilibra explotar lo que ya parece bueno con explorar lo poco visitado:⁹

$$\text{UCT}(s,a) = Q(s,a) + c\,\sqrt{\frac{\ln N(s)}{N(s,a)}}$$

Símbolo	Significado	Ejemplo
$Q(s,a)$	Valor medio estimado de la acción $a$ en $s$ (lo bueno que ha resultado).	Una jugada que ha ganado el 70 % de las simulaciones.
$N(s)$	Número de veces que se ha visitado el estado $s$.	Cuántas simulaciones han pasado por esta posición.
$N(s,a)$	Número de veces que se ha probado la acción $a$ en $s$.	Cuántas veces se exploró esta jugada concreta.
$c$	Constante de exploración que regula el equilibrio.	Más alta: explora más; más baja: explota más.

En palabras: para cada acción se suma lo bueno que ha resultado hasta ahora ($Q$) más un premio a las acciones poco probadas (el segundo término crece cuando $N(s,a)$ es pequeño); así el algoritmo no se obsesiona con la primera opción que pareció buena ni malgasta tiempo en ramas ya descartadas.

Esto es búsqueda en árbol, igual que BFS o A* de los capítulos anteriores, pero guiada por muestreo aleatorio y estadística en vez de por una heurística fija. Encaja de lleno en este recorrido por la búsqueda, y reaparece a fondo en el capítulo 11, dedicado a los juegos, donde MCTS y la elección de jugadas entre varios actores se ven en detalle. En un agente LLM, la misma idea aparece cuando explora varias cadenas de razonamiento como ramas de un árbol, estima cuál promete más a base de pequeñas pruebas y solo entonces se compromete con un camino.

Agentes LLM: razonar y actuar

Todo lo anterior se materializa en patrones concretos de ingeniería. El primero y más extendido es ReAct, que intercala pensamiento y acción: el modelo escribe un razonamiento breve, decide una acción (llamar a una herramienta), observa el resultado y vuelve a razonar con esa información nueva.¹⁰ El bucle pensar, actuar, observar, repetir es exactamente el ciclo de un agente que actualiza su creencia tras cada observación, descrito antes con el belief state.

El segundo patrón lleva la búsqueda al razonamiento mismo. Tree of Thoughts trata las distintas líneas de razonamiento como ramas de un árbol: el modelo genera varias continuaciones posibles de un razonamiento, evalúa cuáles prometen y explora las mejores, descartando las que llevan a callejones sin salida.¹¹ Es la misma búsqueda en árbol de la sección anterior, ahora con los «estados» siendo pasos de un razonamiento en vez de posiciones de un juego.

Visto con el lenguaje de los MDP, el LLM cumple dos papeles. Funciona como una política aprendida: dado el estado (la conversación y las observaciones), propone la siguiente acción plausible, igual que $\pi(s)$ elige una acción en cada estado. Y a veces funciona como un modelo de valor heurístico: estima si una rama de razonamiento promete o no, jugando el papel de $V^*(s)$ sin calcularla de forma exacta. El LLM no es el agente entero: es el corazón que propone y evalúa dentro de un sistema mayor.

Ese sistema alrededor es ingeniería pura, y es lo que separa un buen agente de un prompt con herramientas. Añade el control de coste (presupuesto de tokens, llamadas y tiempo), los permisos (qué acciones requieren aprobación), la captura de observaciones (registrar la fuente y el contenido de cada resultado) y, sobre todo, un criterio de parada (cuándo responder, cuándo pedir ayuda, cuándo escalar). Un agente de código real funciona así: razona sobre la causa probable del fallo, actúa con una acción barata (lee el error, ejecuta un test mínimo), observa lo que devuelve, actualiza su hipótesis y repite, hasta que tiene evidencia suficiente para arreglar y verificar. Razonar, actuar, observar y repetir, dentro de un contrato que pone límites.

Diseñar una política que se pueda auditar

En ingeniería no basta con decir «el agente decide». Una decisión de agente debería poder reconstruirse después: qué sabía, qué acciones podía ejecutar, cuáles estaban bloqueadas, qué coste esperaba pagar, qué riesgo aceptaba y por qué eligió una opción concreta. Si no puedes reconstruir esa historia, tienes una caja negra operativa. Por eso conviene separar lo que se puede ejecutar de lo que conviene ejecutar, y dejar traza de ambas decisiones.

La primera capa, filtrar las acciones que no son válidas en este momento, tiene nombre propio en el campo: action masking (enmascarado de acciones), una técnica estándar en aprendizaje por refuerzo para impedir que el agente siquiera considere acciones imposibles o prohibidas. Cuando esas prohibiciones son restricciones duras que nunca deben violarse (no tocar producción sin evidencia, no consultar datos personales sin permiso), el marco formal es el constrained MDP (MDP con restricciones), un MDP donde, además de maximizar la recompensa, hay límites que no se pueden cruzar. La idea de fondo es la misma que verás en el próximo capítulo, sobre restricciones: hay cosas que no se negocian con una puntuación.

La segunda capa, ordenar las acciones permitidas, es una utilidad esperada simplificada. En la práctica se puntúa cada acción combinando su coste, su avance esperado hacia la meta y su riesgo, y se elige la mejor. Eso no es una fórmula propia: es una forma concreta y manejable de la utilidad esperada de la primera sección, con la utilidad expresada como un valor a minimizar (coste y riesgo suman, el avance resta). Conviene mantener separadas las dos capas y dejar registro de todo:

Capa	Pregunta	Ejemplo
Elegibilidad (action masking)	¿Se puede ejecutar esta acción ahora?	No editar producción sin evidencia; no consultar datos personales sin permiso.
Ranking (utilidad simplificada)	Entre las acciones permitidas, ¿cuál conviene primero?	Leer consola cuesta poco y reduce incertidumbre: buena primera acción.
Parada	¿Cuándo dejo de buscar?	Responder si hay evidencia suficiente; pedir aprobación si la acción siguiente es destructiva.
Trazabilidad	¿Qué debería quedar registrado?	Estado inicial, acciones candidatas, puntuación, bloqueos, observaciones y decisión.

Esta separación evita dos errores frecuentes. El primero es usar una puntuación blanda para permitir acciones que deberían estar prohibidas: si una acción requiere aprobación, no debería «ganar» por tener buena puntuación, sino quedar bloqueada hasta tener autorización. El segundo es esconder las razones de la política dentro de un prompt: puedes usar un LLM como parte del sistema, pero el contrato operativo (presupuestos, permisos, formato, evidencias mínimas y criterios de parada) debe existir fuera del texto improvisado. Esta trazabilidad también sirve para depurar: si el agente gastó diez llamadas antes de leer el error principal, el problema no era «el modelo», era la política; si editó código antes de mirar una prueba mínima, el problema no era «la IA», era que faltaba una precondición de evidencia.

Un ejemplo trazado del ranking

Imagina la incidencia «la página de checkout falla». El agente tiene cuatro acciones candidatas. Primero se aplica la elegibilidad (el action masking) y después se ordenan las elegibles por una puntuación que combina coste, avance estimado y riesgo (menor es mejor). Esa puntuación es una utilidad negativa simplificada: una forma concreta de la utilidad esperada de la primera sección, no una fórmula propia del capítulo. Llamamos a sus tres componentes coste, avance y riesgo:

Acción	Elegible	Coste	Avance	Riesgo	Puntuación
Leer la consola del navegador	sí	1	2	0	3
Ejecutar el test del checkout	sí	3	2	0	5
Preguntar al usuario	sí	2	4	0	6
Editar el código del pago	no (bloqueada)	2	1	10	no se rankea

Fíjate en la trampa. «Editar el código del pago» tiene el menor componente de avance pendiente (parece la que más acerca a la meta), y un agente puramente codicioso la elegiría. Pero su riesgo es enorme, porque tocaría producción sin evidencia, así que la capa de elegibilidad la bloquea antes de rankear nada. Entre las acciones permitidas gana «leer la consola» con puntuación 3: es barata y reduce mucho la incertidumbre. La elegibilidad va siempre antes que el ranking, y combinar coste, avance y riesgo evita que lo aparentemente directo se imponga a lo prudente. Es exactamente la clase de decisión que un agente bien diseñado debe poder justificar.

En el día a día

Imagina un agente de código que recibe: “la página falla al cargar”. Puede hacer muchas cosas. Leer el error de consola. Abrir el navegador. Buscar en el repositorio. Ejecutar tests. Mirar el último commit. Preguntar al usuario. Todas son acciones válidas, pero no todas son igual de buenas.

Una política Greedy elegiría lo que parece más directo: “abrir el navegador”. Puede funcionar. Pero si no mira los logs, quizá pierda diez minutos en la pantalla equivocada. Una política tipo A* ponderaría el coste y la información esperada: “leer el error de consola cuesta poco y reduce mucho la incertidumbre; hagamos eso primero”.

En producción, esta diferencia se traduce en dinero y fiabilidad. Un agente que llama a diez herramientas para resolver una pregunta sencilla no solo es más lento: también introduce más puntos de fallo. Un agente que responde demasiado pronto parece rápido, pero puede inventar. El buen diseño está en equilibrar información, coste y riesgo.¹²

Por qué debería importarte

La búsqueda clásica te da un vocabulario para diseñar agentes modernos sin confundir una salida fluida con una decisión controlada. Si defines mal el estado, el agente se pierde. Si defines mal las acciones, no puede llegar a la solución. Si ignoras el coste, se vuelve caro. Si ignoras el riesgo, se vuelve peligroso. Si la heurística es mala, parece inteligente mientras da vueltas.

Esto es especialmente importante porque los LLMs son convincentes. Pueden explicar una decisión con mucha seguridad aunque la decisión sea mala. La estructura de búsqueda te obliga a preguntar: ¿qué estado tenía?, ¿qué acciones consideró?, ¿qué coste pagó?, ¿qué evidencia observó?, ¿por qué eligió esa acción y no otra?

Dónde solía tropezar yo

Error	Por qué es un error	Antídoto
Llamar “agente” a cualquier prompt con herramientas	Tener tools no basta. Un agente necesita estado, acciones, criterio de decisión y actualización tras observar resultados.	Dibuja $s_t$, $A(s_t)$, $a_t$ y $s_{t+1}$. Si no puedes, todavía no hay diseño de agente.
Hacer tool selection puramente codiciosa	La herramienta obvia puede ser cara, arriesgada o prematura.	Mete el coste y el riesgo dentro de la utilidad esperada, no solo el avance hacia la meta.
No modelar el coste en tokens y latencia	Un agente puede ser correcto y aun así inviable si tarda demasiado o cuesta demasiado.	Define presupuesto antes de ejecutar: tokens máximos, llamadas máximas y tiempo máximo.
Confundir observación con verdad	Una tool puede devolver datos incompletos, antiguos o mal interpretados.	Guarda la fuente de cada observación y verifica las decisiones importantes.
Recapitular sin comprobar	Leer “ya lo entiendo” no equivale a poder reconstruirlo.	Usa las preguntas de revisión activa; si fallas una, vuelve al capítulo concreto.

Antes de seguir: la búsqueda en limpio

El próximo capítulo cambia de herramienta: pasamos de buscar caminos a satisfacer restricciones (CSP). Antes de ese salto conviene tener firmes los cuatro capítulos de búsqueda. Esto no es un resumen para leer rápido, sino una revisión activa: si una idea no te sale, vuelve al capítulo indicado y sigue.

1. Búsqueda como espacio de estados

El concepto. Un problema de búsqueda se define con estado inicial, acciones, función de transición, prueba de meta y coste. Si una de esas piezas está borrosa, el algoritmo no tiene dónde agarrarse.¹³

Para recordar. El estado no es “todo lo que existe”: es solo la información necesaria para decidir la siguiente acción. Meter información irrelevante infla el espacio de búsqueda.

Ejemplo fresco. En un laberinto, el estado puede ser la coordenada $(x,y)$. No necesitas guardar el color de la pared ni la hora del día. En un agente de código, el estado puede incluir error, archivos leídos y tests ejecutados; no necesita recordar cada token de una conversación si ya tiene un resumen fiable.

Vuelve al capítulo 1 si: no puedes definir estado, acción, meta y coste para un problema cotidiano.

2. BFS, DFS, UCS e IDS

El concepto. La frontera determina el algoritmo. Cola FIFO produce BFS. Pila LIFO produce DFS. Cola de prioridad por $g(n)$ produce UCS. DFS con límites crecientes produce IDS.¹⁴

Para recordar. BFS es completo y óptimo con costes uniformes, pero consume memoria $O(b^d)$. DFS consume mucha menos memoria, $O(b \cdot m)$, pero no garantiza optimalidad. UCS generaliza BFS cuando las acciones cuestan distinto. Y cuando se conoce la meta y se puede buscar hacia atrás, la búsqueda bidireccional baja el coste de $O(b^d)$ a $O(b^{d/2})$.

Ejemplo fresco. Si todas las calles pesan igual, BFS encuentra el camino con menos cruces. Si unas calles son autopistas y otras caminos lentos, necesitas UCS. Si el espacio es enorme y solo quieres no quedarte sin memoria, IDS es el puente.

Vuelve al capítulo 2 si: no puedes explicar por qué cambiar cola por pila cambia completamente el comportamiento.

3. Greedy, A* y heurísticas

El concepto. Greedy usa $f(n)=h(n)$. A* usa $f(n)=g(n)+h(n)$. La heurística $h(n)$ es una estimación de lo que falta, y su calidad decide cuántos estados se exploran.¹⁵

Para recordar. Greedy es rápido porque ignora el coste acumulado. A* es más disciplinado porque suma lo que ya pagaste y lo que estimas que falta. Si la memoria aprieta, IDA* da la optimalidad de A* con la memoria de DFS; si prima la velocidad, Weighted A* la cambia por una solución aproximada. Con $h$ admisible, A* conserva garantías de optimalidad.¹⁶

Ejemplo fresco. En una rejilla, Manhattan puede decirte cuántos pasos mínimos faltan si solo te mueves en horizontal y vertical. Esa estimación no resuelve el problema, pero evita explorar media ciudad.

Vuelve al capítulo 3 si: no puedes explicar admisibilidad, consistencia y dominancia de heurísticas.

4. Agentes modernos

El concepto. Un agente moderno selecciona acciones en un estado parcialmente observado, ejecuta herramientas, recibe observaciones y actualiza su estado. La búsqueda puede ser implícita, pero sigue estando ahí.

Para recordar. “LLM + tools” no es automáticamente un buen agente. Hace falta una política: cuándo usar herramientas, cuáles priorizar, cuándo parar, cuándo pedir aclaración y cuándo responder.

Ejemplo fresco. Ante un fallo de build, un agente prudente no edita a ciegas. Primero lee el error, identifica el archivo probable, ejecuta el test mínimo, modifica, y vuelve a verificar. Eso es búsqueda guiada por evidencia.

Vuelve a este capítulo si: no puedes mapear un agente a $s_t$, $A(s_t)$, $a_t$, observación y $s_{t+1}$.

Cómo encaja todo

Con este capítulo se cierran los cuatro primeros, todos sobre búsqueda, y el capítulo 5 cambia de pregunta. Los capítulos 1, 2 y 3 nos dieron el lenguaje clásico (estado, frontera, coste real y heurística) y aquí lo hemos usado para leer un agente moderno sin caer en la fantasía de que todo ocurre dentro del modelo. El capítulo 5 reutiliza ese mismo lenguaje, pero la pregunta deja de ser «qué camino» y pasa a ser «qué asignación cumple todas las reglas».

La decisión nueva es separar propuesta, elegibilidad, puntuación, ejecución y observación. Esa separación volverá en restricciones, planificación, agentes de software y operación.

graph TD
    subgraph "Capítulos 1-3: búsqueda explícita"
        C01["Cap. 1: estado, acción, meta y coste"]
        C02["Cap. 2: frontera FIFO, LIFO y g(n)"]
        C03["Cap. 3: h(n), admisibilidad y A*"]
    end
    subgraph "Capítulo 4: agente como búsqueda implícita"
        STATE["Estado s_t: memoria, observaciones, restricciones y objetivo"]
        CANDIDATES["A(s_t): acciones candidatas"]
        ELIGIBILITY["E(a|s_t): permisos, presupuesto y precondiciones"]
        SCORE["Decisión: maximizar<br/>la utilidad esperada"]
        TOOL["Tool ejecutada"]
        OBS["Observación nueva"]
        STOP["Criterio de parada o siguiente iteración"]
    end
    subgraph "Lo que viene después"
        CSP["Cap. 5-8: restricciones y guardrails"]
        PLAN["Cap. 9-10: planificación"]
        GAMES["Cap. 11: otros actores eligen"]
        SYMBOLIC["Cap. 12: conocimiento simbólico"]
        AGENTS["Fasc. 5: agentes de software"]
    end

    C01 --> STATE
    C02 --> CANDIDATES
    C03 --> SCORE
    STATE --> CANDIDATES
    CANDIDATES --> ELIGIBILITY
    ELIGIBILITY --> SCORE
    SCORE --> TOOL
    TOOL --> OBS
    OBS --> STATE
    OBS --> STOP
    ELIGIBILITY --> CSP
    STOP --> PLAN
    SCORE --> GAMES
    OBS --> SYMBOLIC
    TOOL --> AGENTS

    style STATE fill:#F5F5F5,stroke:#000000,stroke-width:2
    style ELIGIBILITY fill:#F5F5F5,stroke:#000000,stroke-width:2
    style SCORE fill:#F5F5F5,stroke:#000000,stroke-width:2
    style CSP stroke-dasharray: 5 5
    style PLAN stroke-dasharray: 5 5
    style GAMES stroke-dasharray: 5 5
    style SYMBOLIC stroke-dasharray: 5 5
    style AGENTS stroke-dasharray: 5 5

Vocabulario aprendido

Término	Definición
Agente de búsqueda	Sistema que elige acciones para avanzar desde un estado hacia una meta.
Agente racional	Sistema que elige la acción que maximiza su medida de rendimiento esperada dada la evidencia.
Utilidad esperada	Valor medio de los resultados de una acción, ponderado por la probabilidad de cada uno.
MDP	Proceso de Decisión de Markov: marco $(S, A, P, R, \gamma)$ para decidir bajo incertidumbre con recompensas en el tiempo.
Política	Regla $\pi(s)$ que asigna a cada estado la acción a tomar.
Función de valor	Recompensa total esperada de actuar de forma óptima desde un estado en adelante.
Ecuación de Bellman	Relación recursiva que liga el valor de un estado con el valor de los estados siguientes.
POMDP	MDP parcialmente observable: el agente no ve el estado real, solo observaciones.
Belief state	Distribución de probabilidad sobre los estados posibles, actualizada con cada observación.
MCTS	Monte Carlo Tree Search: búsqueda en árbol por muestreo con selección, expansión, simulación y retropropagación.
ReAct	Patrón de agente LLM que intercala razonamiento y acciones sobre herramientas.
Tool selection	Elección de la siguiente herramienta o acción que conviene ejecutar.
Coste operacional	Tokens, latencia, dinero, riesgo y complejidad acumulados al actuar.
Heurística aprendida	Estimación producida por un modelo o regla para priorizar acciones.
Política de decisión	Regla que transforma estado y acciones disponibles en una acción concreta.
Criterio de parada	Condición que decide si el agente responde, pide aprobación, sigue buscando o escala.
Trazabilidad de decisión	Registro de estado, acciones candidatas, bloqueos, puntuaciones y observaciones.

Antes de pasar página

• ¿Puedo escribir la fórmula de la utilidad esperada y explicar qué es un agente racional? (Si no, vuelve a «El agente racional».)
• ¿Sé qué cinco elementos forman un MDP y qué dice la ecuación de Bellman? (Si no, vuelve a «Decidir cuando el resultado es incierto: el MDP».)
• ¿Entiendo por qué un agente LLM trabaja con un belief state y no con un estado exacto? (Si no, vuelve a «Cuando no se ve todo: POMDP y belief state».)
• ¿Puedo nombrar las cuatro fases de MCTS y para qué sirve la fórmula UCT? (Si no, vuelve a «Buscar en el árbol de decisiones: MCTS».)
• ¿Sé qué hacen ReAct y Tree of Thoughts y cómo el LLM actúa como política y como valor? (Si no, vuelve a «Agentes LLM: razonar y actuar».)
• ¿Puedo separar acciones bloqueadas de acciones elegibles antes de rankear? (Si no, vuelve a «Diseñar una política que se pueda auditar».)
• ¿Puedo recapitular BFS, DFS, UCS, Greedy y A* sin mirar? (Si no, vuelve a «Antes de seguir: la búsqueda en limpio».)
• ¿Entiendo por qué el siguiente capítulo, CSP, sigue siendo búsqueda pero con restricciones? (Si no, vuelve a «Cómo encaja todo».)

En resumen

Idea fuerza	Detalle
Los agentes modernos no eliminan la búsqueda: la esconden.	Cada decisión de tool es una elección entre acciones candidatas.
El estado decide lo que el agente puede razonar.	Si el estado omite información relevante, la política tomará malas decisiones.
La utilidad esperada es la brújula del agente.	Maximizar $\mathbb{E}[U]$, con coste, avance y riesgo dentro de la utilidad, da agentes menos impulsivos que un Greedy puro.
La elegibilidad va antes que el ranking.	Una acción prohibida o sin permisos no debería ganar por tener buen score.
La búsqueda queda recogida; el capítulo 5 cambia a las restricciones.	Estados, frontera, coste, heurística y política quedan listos para CSP (cap. 5), planificación y juegos.

Para saber más

Bellman, R. (1957). Dynamic programming. Princeton University Press.

Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S. y Colton, S. (2012). A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1-43. https://doi.org/10.1109/TCIAIG.2012.2186810

Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136

Kocsis, L. y Szepesvári, C. (2006). Bandit based Monte-Carlo planning. En Machine Learning: ECML 2006 (pp. 282-293). Springer. https://doi.org/10.1007/11871842_29

Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson.

Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann.

Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley.

Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press.

Puterman, M. L. (1994). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons. https://doi.org/10.1002/9780470316887

Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill.

Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. https://aima.cs.berkeley.edu/

Sutton, R. S. y Barto, A. G. (2018). Reinforcement learning: an introduction (2.ª ed.). MIT Press. https://incompleteideas.net/book/the-book-2nd.html

Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T. L., Cao, Y. y Narasimhan, K. (2023). Tree of thoughts: deliberate problem solving with large language models. https://arxiv.org/abs/2305.10601

Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K. y Cao, Y. (2023). ReAct: synergizing reasoning and acting in language models. International Conference on Learning Representations. https://arxiv.org/abs/2210.03629

Notas

1. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. El capítulo 2 define los agentes racionales como sistemas que seleccionan acciones para maximizar una medida de rendimiento, una idea que conecta directamente con la búsqueda como selección de acciones. ↩

2. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. El capítulo 2 define al agente racional como el que elige la acción que maximiza el valor esperado de su medida de rendimiento, dada la secuencia de percepciones hasta ese momento. Es la definición de referencia del campo. ↩

3. Bellman, R. (1957). Dynamic programming. Princeton University Press. Bellman introdujo la programación dinámica y la ecuación recursiva que lleva su nombre, base de casi toda la teoría de decisión secuencial. ↩

4. Puterman, M. L. (1994). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons. Tratado de referencia sobre la formulación y resolución de los MDP. ↩

5. Sutton, R. S. y Barto, A. G. (2018). Reinforcement learning: an introduction (2.ª ed.). MIT Press. Texto canónico del aprendizaje por refuerzo, donde los MDP son el marco formal de partida. ↩

6. Puterman, M. L. (1994). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons. La observabilidad parcial extiende el MDP estándar añadiendo un espacio de observaciones y la actualización de creencias. ↩

7. Sutton, R. S. y Barto, A. G. (2018). Reinforcement learning: an introduction (2.ª ed.). MIT Press. El capítulo sobre estados y aproximación discute cómo un agente con percepción limitada debe trabajar con representaciones que resumen su historia de observaciones. ↩

8. Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S. y Colton, S. (2012). A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1), 1-43. https://doi.org/10.1109/TCIAIG.2012.2186810. Revisión de referencia sobre MCTS, su variante UCT y aplicaciones, incluido el juego de Go que llevó a AlphaGo. ↩

9. Kocsis, L. y Szepesvári, C. (2006). Bandit based Monte-Carlo planning. En Machine Learning: ECML 2006 (pp. 282-293). Springer. https://doi.org/10.1007/11871842_29. Artículo que introduce UCT, la aplicación del algoritmo UCB de bandidos a la búsqueda en árbol. ↩

10. Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K. y Cao, Y. (2023). ReAct: synergizing reasoning and acting in language models. En International Conference on Learning Representations. https://arxiv.org/abs/2210.03629. Propone alternar trazas de razonamiento y acciones sobre herramientas, lo que mejora la fiabilidad frente a razonar o actuar por separado. ↩

11. Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T. L., Cao, Y. y Narasimhan, K. (2023). Tree of thoughts: deliberate problem solving with large language models. https://arxiv.org/abs/2305.10601. Generaliza el razonamiento en cadena a una búsqueda en árbol sobre pasos intermedios, con evaluación y vuelta atrás. ↩

12. Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson. El capítulo 3 insiste en que la eficiencia de una búsqueda depende tanto de la representación del problema como de la estrategia de control. ↩

13. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. ↩

14. Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press. ↩

15. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. ↩

16. Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136. ↩