Búsqueda en el espacio de estados: BFS, DFS, UCS y A* con animaciones

Fundamentos de inteligencia artificial de forma visual: qué es el espacio de estados, cómo funcionan BFS, DFS, UCS, la búsqueda voraz y A*, qué es una heurística y qué tiene que ver con el aprendizaje automático.

14 minutos Matěj Žalmánek 2026-10-15

Serie Fundamentos de IA Parte 21 de 52

1. Mapa de la inteligencia artificial: qué es cada cosa y cómo encaja todo
2. Breve historia de la inteligencia artificial: de Turing a los modelos de lenguaje
3. Datos, modelo, entrenamiento, inferencia: los conceptos básicos en un solo ejemplo
4. Cómo leer la notación matemática: símbolos, subíndices, sumatorios y cuantificadores
5. Conjuntos y relaciones: las piezas con las que se construyen las definiciones en IA
6. Funciones y aplicaciones: por qué todo modelo de IA es una función
7. Lógica y demostraciones: las reglas con las que se razona en IA
8. Grafos y árboles: la estructura sobre la que se apoyan la búsqueda y las redes neuronales
9. Álgebra lineal para aprendizaje automático: vectores, matrices y por qué la IA sobre todo multiplica
10. Derivadas, gradiente y regla de la cadena: cómo sabe un modelo en qué dirección aprender
11. Descenso de gradiente: cómo aprende un modelo
12. Qué es la probabilidad: del lanzamiento de un dado a los axiomas de Kolmogórov
13. Probabilidad condicionada y teorema de Bayes: cómo cambiar una estimación cuando te enteras de algo nuevo
14. Variable aleatoria y función de distribución: una sola función que lo dice todo sobre la distribución
15. Función de densidad y función de probabilidad: por qué una variable continua tiene probabilidad cero en cada punto
16. Esperanza, varianza y covarianza: dónde está una distribución, qué anchura tiene y qué se relaciona con qué
17. Resumen de las distribuciones de probabilidad: Bernoulli, binomial, Poisson, uniforme, normal y exponencial
18. Ley de los grandes números y teorema central del límite: por qué las medias se comportan de forma tan predecible
19. Estadística y estimación de parámetros: máxima verosimilitud, MAP e intervalos de confianza
20. Teoría de la información: entropía, entropía cruzada y divergencia KL, el origen de las funciones de pérdida
21. Búsqueda en el espacio de estados: BFS, DFS, UCS y A* con animaciones
22. Juegos y adversarios: minimax, poda alfa-beta y Monte Carlo tree search
23. Satisfacción de restricciones: backtracking, propagación de restricciones y AC-3 con un sudoku y un mapa de regiones checas
24. Lógica y sistemas basados en conocimiento: encadenamiento hacia delante y hacia atrás, resolución y sistemas expertos
25. Planificación: STRIPS, el mundo de bloques, heurísticas a partir de la relajación y la planificación en los agentes de IA
26. Búsqueda local y recocido simulado: un viajante por las capitales regionales checas
27. Algoritmos genéticos: población, cruce, mutación y selección en una mochila para la excursión
28. Estrategias evolutivas y programación genética: de la regla de un quinto a la ley de Kepler
29. Optimización por colonia de hormigas: cómo un rastro de feromona encuentra un camino corto
30. Optimización por enjambre de partículas: inercia, experiencia propia y experiencia del enjambre
31. Neuroevolución: evolución de los pesos y la forma de las redes neuronales, y el algoritmo NEAT
32. Conjuntos difusos y funciones de pertenencia: cómo escribir «algo cálido»
33. Lógica difusa y probabilidad: por qué «algo cálido» no significa «probablemente cálido»
34. Lógica difusa: t-normas, implicaciones y reglas SI–ENTONCES
35. Control difuso: Mamdani y Sugeno, del ventilador al péndulo invertido sobre un carro
36. Agrupamiento difuso: el algoritmo fuzzy c-means y los puntos entre clusters
37. Sistemas neuro-difusos (ANFIS): reglas difusas que aprenden de los datos
38. Cadenas de Markov: matriz de transición, distribución estacionaria y PageRank
39. Modelos ocultos de Márkov: el algoritmo de Viterbi y el casino deshonesto
40. Redes bayesianas: por qué está mojada la hierba y qué significa eso para el aspersor
41. El filtro de Kalman: cómo estimar a partir de mediciones imprecisas dónde está un coche y a qué velocidad va
42. Tipos de aprendizaje automático: supervisado, no supervisado, semisupervisado y más
43. Prompts, contexto y RAG: cómo darle a un modelo la información correcta
44. Autocodificadores variacionales (VAE): imágenes nuevas a partir de un espacio latente continuo
45. Redes generativas adversarias (GAN): el falsificador contra el detective
46. Modelos de difusión: cómo el ruido puro se convierte en una imagen
47. Procesos de decisión de Markov: estados, acciones, recompensas y ecuaciones de Bellman
48. Q-learning y DQN: aprender el valor de las acciones, de la tabla a la red neuronal
49. Gradiente de la política y PPO: aprender directamente la política
50. Cómo funciona un agente de IA: un modelo de lenguaje en un bucle con herramientas
51. Programación con agentes de IA: encargo, pruebas y revisión
52. Evaluación y seguridad de los sistemas de IA: cómo medir y cómo vigilar

Temario completo de la serie 52 de 83 temas publicados

Cuando hoy se habla de inteligencia artificial, la mayoría de la gente piensa en redes neuronales y grandes modelos de lenguaje. Pero mucho antes de que las máquinas aprendieran a partir de datos, ya sabían buscar. Navegar por un mapa, elegir una jugada de ajedrez, planificar un robot en un almacén — todo eso es buscar un camino en un espacio de posibilidades. La búsqueda en el espacio de estados es el primer capítulo de cualquier manual de inteligencia artificial, y sus ideas las encontrarás también en el aprendizaje automático: heurísticas, optimización, búsqueda de la mejor solución.

Aquí encontrarás cada concepto dos veces: primero una definición matemática precisa y justo debajo lo mismo dicho de forma sencilla. Todas las animaciones son la ejecución real del algoritmo — nada está dibujado a mano.

1. Qué es el espacio de estados

Antes de buscar nada, tenemos que describir el problema de forma que lo entienda un ordenador. Para eso sirve el problema de búsqueda:

Definición — problema de búsqueda

Un problema de búsqueda es una sextupla P = (S, s₀, A, T, G, c), donde

• S es el conjunto de estados,
• s₀ ∈ S es el estado inicial,
• A(s) es el conjunto de acciones aplicables en el estado s,
• T : S × A → S es la función de transición; el estado s′ = T(s, a) es un sucesor del estado s,
• G ⊆ S es el conjunto de estados objetivo,
• c : S × A → ℝ⁺ es el coste de una acción, siempre positivo.

Definición — camino, solución, óptimo

Un camino de longitud k es una secuencia s₀, a₁, s₁, …, a_k, s_k, donde s_i = T(s_i−1, a_i).

El coste del camino es la suma de los costes de las acciones: g = ∑_i=1^k c(s_i−1, a_i).

Una solución es un camino que termina en un objetivo: s_k ∈ G. Una solución óptima es una solución de coste mínimo; ese coste se escribe C*.

Los estados unidos por acciones forman un grafo dirigido: los estados son los vértices y las acciones, aristas con peso c. Buscar una solución significa, por tanto, encontrar en el grafo un camino desde s₀ hasta algún vértice de G. El ejemplo clásico es el puzle 8: fichas del 1 al 8 en un marco de 3 × 3 y un hueco vacío. Un estado es la colocación de las fichas, una acción es mover el hueco y el objetivo, las fichas ordenadas:

Parece inofensivo, pero el puzle 8 tiene 181 440 estados alcanzables y su hermano mayor, el puzle 15, más de diez billones. Por eso nunca construimos el grafo completo de antemano. El algoritmo lo descubre poco a poco — con la función de transición calcula solo los sucesores del estado en el que se encuentra.

2. Planteamiento: un camino por el laberinto

Veremos todos los algoritmos sobre el mismo problema. Tenemos un laberinto de 9 × 14 casillas y queremos ir de la salida a la meta con el menor coste posible. Primero, qué significa cada casilla:

• Casilla libre — entrar en ella cuesta 1
• Barro — se puede atravesar, pero entrar cuesta 5
• Muro — no se puede entrar
• S Salida (start) — el estado inicial, la casilla (0, 0)
• G Meta (goal) — la casilla (8, 13)
• Casilla explorada — el algoritmo la ha expandido
• Camino encontrado — el resultado del algoritmo

Planteamiento formal

Escribimos una casilla como un par (r, s) — fila r ∈ {0, …, 8}, columna s ∈ {0, …, 13}. Sea Z el conjunto de muros y B el conjunto de casillas con barro.

• Estados: S = {(r, s) : (r, s) ∉ Z} — todas las casillas excepto los muros.
• Estado inicial: s₀ = (0, 0). Objetivo: G = {(8, 13)}.
• Acciones: A = {↑, →, ↓, ←}. Una acción es aplicable en un estado solo si lleva a una casilla dentro de la cuadrícula que no sea un muro.
• Transición: T((r, s), →) = (r, s + 1), y análogamente para las demás direcciones.
• Coste: c(x, a) = 5 si T(x, a) ∈ B, y 1 en caso contrario — se paga por la casilla en la que entramos.
• Tarea: encontrar una solución de coste mínimo C*.

El barro está puesto a propósito en la ruta más directa. Veremos que no todos los algoritmos se dan cuenta: unos solo cuentan pasos, otros el coste real.

3. El esqueleto común de todos los algoritmos

Todos los algoritmos del artículo tienen el mismo esqueleto. Solo se diferencian en una decisión.

Definición — frontera, estados cerrados, expansión

La frontera (frontier) F ⊆ S es el conjunto de estados que el algoritmo ya ha descubierto pero aún no ha expandido.

Los estados cerrados E ⊆ S son los estados ya expandidos.

Expandir un estado s significa calcular todos sus sucesores {T(s, a) : a ∈ A(s)} y añadir a F los que no estén en E.

frontier = [start]
closed = {}
mientras frontier no esté vacía:
    state = choose_from(frontier)  # ← aquí es donde se diferencian los algoritmos
    si state es el objetivo: terminado
    añadir state a closed
    para cada sucesor de state:
        si aún no está cerrado: añadirlo a frontier

Toda la diferencia entre los algoritmos está en una sola línea: qué estado de la frontera elegimos a continuación. Una cola, una pila o una cola de prioridad según algún número. Todo lo demás se apoya en eso.

4. Búsqueda en anchura (BFS)

Definición — BFS

La frontera F es una cola (FIFO): se expande el estado que entró primero en F.

Consecuencia: los estados se expanden por orden de profundidad d(s) — el número de acciones desde s₀. Por eso BFS encuentra la solución con el menor número de acciones.

Si b es el factor de ramificación (el número máximo de sucesores de un estado) y d la profundidad de la solución menos profunda, BFS genera como mucho b + b² + … + b^d = O(b^d) estados y mantiene otros tantos en memoria.

En el laberinto la onda se ve bien — se extiende en todas las direcciones hasta dar con la meta:

Pero fíjate en que el camino pasa directamente por el barro. BFS cuenta acciones, no coste — para él, un paso por el barro es igual que un paso por suelo seco. El camino más corto ha salido de 25 pasos, pero con coste 37. BFS solo es óptimo cuando todas las acciones cuestan lo mismo.

from collections import deque

def bfs(start, goal, successors):
    frontier = deque([start])
    parent = {start: None}
    while frontier:
        state = frontier.popleft()          # cola: el primero en entrar, el primero en salir
        if state == goal:
            return path(parent, goal)
        for nxt in successors(state):
            if nxt not in parent:
                parent[nxt] = state
                frontier.append(nxt)
    return None

def path(parent, state):
    result = []
    while state is not None:
        result.append(state)
        state = parent[state]
    return result[::-1]

5. Búsqueda en profundidad (DFS)

Definición — DFS

La frontera F es una pila (LIFO): se expande el estado que entró en F en último lugar.

Si m es la profundidad máxima del espacio de estados, DFS mantiene en memoria solo la rama actual y sus hermanos: O(b · m) estados. El tiempo, en el peor caso, es O(b^m).

DFS no es óptimo y, en un espacio infinito, ni siquiera es completo — puede descender indefinidamente.

En el árbol se ve por el orden: A, B, D, H, I — y solo después E. En el laberinto:

Aquí DFS ha tenido suerte y ha llegado a la meta sin explorar muchas casillas. Pero el camino es innecesariamente largo — 31 pasos en lugar de 25 y un coste de 59.

Definición — profundización iterativa (IDDFS)

Para ℓ = 0, 1, 2, … ejecuta un DFS que no expande estados más profundos que ℓ. Termina en la primera solución encontrada.

Los estados de profundidad i se generan (d − i + 1) veces, en total ∑_i=1^d (d − i + 1) · bⁱ = O(b^d) — igual que BFS, pero con una memoria de solo O(b · d).

6. Búsqueda de coste uniforme (UCS)

Definición — UCS

Para un estado n, sea g(n) el coste del camino más barato encontrado hasta ahora desde s₀ hasta n.

La frontera es una cola de prioridad ordenada por g: se expande el estado con el menor g(n).

Si todos los costes de las acciones son ≥ ε > 0, UCS expande los estados en orden no decreciente de g y, por tanto, es completo y óptimo. El número de estados expandidos es O(b^{1 + ⌊C*/ε⌋}).

UCS ha rodeado el barro. Ha encontrado un camino con el mismo número de pasos que BFS, pero con coste 25 en lugar de 37 — y ese es con garantía el más barato, es decir, C* = 25. El precio que paga: busca a ciegas en todas direcciones. No sabe dónde está la meta, así que también se extiende en dirección contraria.

7. Heurística: estimar por dónde se llega a la meta

Los algoritmos anteriores son no informados — de la meta solo saben que la reconocerán cuando la pisen. Los algoritmos informados reciben además una estimación de cuánto falta.

Definición — heurística

Sea h*(n) el coste del camino óptimo desde el estado n hasta el objetivo más cercano. Una heurística es una función h : S → ℝ_≥0 que estima h*(n), con h(n) = 0 para n ∈ G.

h es admisible (admissible) si nunca sobrestima: ∀n ∈ S : h(n) ≤ h*(n).

h es consistente si para todo estado n, toda acción a y todo sucesor n′ = T(n, a) se cumple h(n) ≤ c(n, a) + h(n′). Toda heurística consistente es admisible.

En nuestro laberinto lo natural es la distancia Manhattan — el número de casillas en horizontal más en vertical, como cuando caminas por las calles en cuadrícula de Manhattan:

8. Búsqueda voraz

Definición — búsqueda voraz

La frontera es una cola de prioridad según f(n) = h(n): se expande el estado que según la estimación está más cerca de la meta. El coste acumulado g(n) no se tiene en cuenta.

La búsqueda voraz no es óptima; con control de estados repetidos es completa en un espacio finito.

La búsqueda voraz explora pocas casillas, pero va adonde parece más cerca y acaba en un camino largo y caro — 31 pasos, coste 59.

9. A*: lo mejor de ambos mundos

Definición — A*

La frontera es una cola de prioridad según f(n) = g(n) + h(n) — la estimación del coste del camino completo desde la salida, pasando por n, hasta la meta.

Teorema. Si h es consistente, los valores de f no decrecen a lo largo de ningún camino, A* expande los estados en orden no decreciente de f y el primer estado objetivo expandido está en un camino óptimo de coste C*. Al hacerlo, expande todo estado con f(n) < C* y ninguno con f(n) > C*.

Para h ≡ 0, A* es lo mismo que UCS; sin g sería la búsqueda voraz.

El mismo coste 25 que UCS, pero A* ha explorado 37 casillas en lugar de 49. En un laberinto pequeño la diferencia es de unas pocas casillas; en un mapa con millones de cruces es la diferencia entre una respuesta instantánea y un minuto de espera. Por eso encontrarás A* (y sus variantes) en navegadores GPS, en videojuegos y en la planificación de movimiento de robots.

import heapq

def a_star(start, goal, successors, h):
    frontier = [(h(start), 0, start)]        # (f, g, estado)
    g = {start: 0}
    parent = {start: None}
    while frontier:
        _, cost, state = heapq.heappop(frontier)
        if state == goal:
            return path(parent, goal), cost
        if cost > g[state]:
            continue                       # entrada obsoleta, ya conocemos una más barata
        for nxt, step in successors(state):
            new = cost + step
            if new < g.get(nxt, float("inf")):
                g[nxt] = new
                parent[nxt] = state
                heapq.heappush(frontier, (new + h(nxt), new, nxt))
    return None

10. Comparación de algoritmos

Definición — propiedades de un algoritmo

Un algoritmo es completo si, para todo problema que tiene solución, devuelve alguna solución.

Un algoritmo es óptimo si la solución devuelta tiene coste C*.

b — factor de ramificación, d — profundidad de la solución menos profunda, m — profundidad máxima del espacio. O(·) indica cómo crecen el tiempo o la memoria con estos parámetros.

* En un espacio finito con control de estados repetidos siempre encuentran solución. ** Con una heurística consistente.

11. Búsqueda local: cuando no importa el camino

En algunos problemas el camino no nos interesa — solo queremos un buen estado final. Un horario de clases, la colocación de componentes en una placa, el ajuste de parámetros.

Definición — búsqueda local

Se dan una función objetivo f : S → ℝ y un vecindario N(s) ⊆ S de cada estado. Buscamos s* = argmax_{s ∈ S} f(s).

Un estado s es un máximo local si f(s) ≥ f(s′) para todo s′ ∈ N(s), y un máximo global si se cumple para todo s′ ∈ S.

Ascensión de colinas: repite s ← argmax_{s′ ∈ N(s)} f(s′) mientras f aumente.

Para no quedarse atascado se usa el reinicio aleatorio (lanzar al escalador desde distintos puntos), los algoritmos genéticos, que cruzan y mutan toda una población de soluciones, o el recocido simulado:

Recocido simulado

Elige un vecino aleatorio s′ ∈ N(s) y calcula Δ = f(s′) − f(s). Si Δ > 0, pasa a s′; si no, pasa con probabilidad e^Δ/T, donde la «temperatura» T baja poco a poco hacia cero.

Y aquí se cierra el círculo con el aprendizaje automático. Entrenar una red neuronal es una búsqueda local en el espacio de sus pesos θ: el descenso de gradiente repite θ ← θ − η ∇L(θ) — un paso de tamaño η en la dirección en la que la función de error L baja más rápido. Es un escalador puesto del revés que, en lugar de la cima más alta, busca el valle más bajo — y se enfrenta a los mismos problemas: mínimos locales y mesetas.

12. Resumen

• Un problema de búsqueda es una sextupla (S, s₀, A, T, G, c). Una solución es un camino en el grafo de estados, y la solución óptima, el más barato.
• Los algoritmos solo se diferencian en qué estado eligen de la frontera: cola (BFS), pila (DFS), menor g (UCS), menor h (voraz), menor g + h (A*).
• BFS encuentra el menor número de pasos, UCS el menor coste, A* el menor coste explorando lo mínimo — siempre que tenga una heurística consistente.
• Cuando no importa el camino sino el resultado, entra en juego la búsqueda local — y de ahí solo hay un paso al descenso de gradiente y al aprendizaje automático.

¿Quieres probar los algoritmos por ti mismo? Pide a un agente de IA que escriba tu propia visualización — y luego busca en el código esa única línea en la que se diferencian.

¿Lo ves de otra manera? Escribe a support@coden-app.com.