🚀 Técnicas de Búsqueda Avanzadas

De A* e IDA* a algoritmos genéticos, annealing y Q-learning — cómo elegir y entender el algoritmo correcto para tu problema.

↩ Volver al índice de módulos

📚 Contenido

5.1 Panorama de Búsqueda Avanzada 5.2 Búsqueda Heurística (A* vs Greedy vs BFS) 5.3 Backtracking, Bitmask & Branch-and-Bound 5.4 Meet-in-the-Middle 5.5 Gradient Descent & Ascent 5.6 Local Search & Hill Climbing 5.7 Simulated Annealing 5.8 Genetic Algorithms 5.9 Reinforcement Learning & Q-Learning 5.10 Complejidad & Garantías 📝 Quiz

🧭 5.1 Panorama de Búsqueda Avanzada

            Modelo general: un problema de búsqueda es un 5-tuple
            ⟨S, A, s₀, T, c⟩ con estados, acciones, estado inicial, metas y costos.
        

Los algoritmos de este módulo comparten la misma idea base: explorar el espacio de estados buscando una solución barata, pero varían en:

Garantías: ¿encuentran siempre la solución? ¿es óptima?
Costos: tiempo y memoria (típicamente exponenciales en la profundidad d).
Información: usan heurísticas, gradientes, muestras aleatorias, o recompensas.

🔍 Búsqueda Determinista

A*, IDA*, UCS, B&B: exploran sistemáticamente el espacio.

Garantías fuertes (completud, optimalidad) pero costo exponencial.

🎲 Búsqueda Estocástica

SA, GA, Monte Carlo, RL: exploran con azar.

Escalan mejor, pero ofrecen convergencia en probabilidad, no certeza absoluta.

📉 Optimización Continua

Gradient Descent/Ascent y variantes.

Excelente para modelos diferenciables (deep learning, control).

⭐ 5.2 Búsqueda Heurística: BFS vs Greedy vs A*

            Idea: usar una heurística h(s) para estimar la distancia restante al objetivo y dirigir la búsqueda.
        

Definiciones clave

Heurística h(s): estimación del costo desde s hasta un objetivo.
Admisible: 0 ≤ h(s) ≤ h\*(s) (nunca sobreestima).
Consistente: h(s) ≤ c(s, a, s′) + h(s′) (monotonía en f=g+h).

Algoritmo	Función de prioridad	Completitud	Optimalidad
BFS (unit costs)	Profundidad g(s)	✔ Sí	✔ Sí (costos iguales)
Greedy Best-First	h(s)	✖ No siempre	✖ No
A*	f(s)=g(s)+h(s)	✔ Sí	✔ Sí (h admisible)

Visual: comparación lado a lado

BFS (onda uniforme)

Greedy Best-First (persigue la meta)

A* (equilibrio g+h)

Verde = camino final, azul = nodos explorados. Usa "⚡ Comparar los 3" para ver las diferencias en tiempo real.

Pseudocódigo A*

def astar(start, is_goal, neighbors, cost, h):
    open = PriorityQueue()
    open.push((h(start), 0, start))
    g = {start: 0.0}
    parent = {start: None}

    while open:
        f, gs, s = open.pop_min()
        if is_goal(s):
            return reconstruct(parent, s), g[s]
        if gs > g[s]:
            continue
        for t in neighbors(s):
            c = gs + cost(s, t)
            if t not in g or c < g[t]:
                g[t] = c
                parent[t] = s
                open.push((c + h(t), c, t))
    return None, inf

🌳 5.3 Backtracking, Bitmask & Branch-and-Bound

            Backtracking: generar y probar (search tree) + podas para evitar subárboles imposibles o inútiles.
        

Bitmask: representar subconjuntos en un entero

Cada elemento i es un bit: 1 = incluido, 0 = excluido.
Operaciones O(1): activar, desactivar, probar pertenencia.

// i-th bit set?
bool has(int mask, int i) { return mask & (1 << i); }

// add i
int add(int mask, int i) { return mask | (1 << i); }

// remove i
int rem(int mask, int i) { return mask & ~(1 << i); }

Branch-and-Bound sobre mochila 0/1 (idea)

Ordenar items por densidad valor/peso.
Explorar recursivamente el árbol "tomo / no tomo".
Usar un upper bound fraccional para podar nodos que nunca superarán el mejor valor.

Árbol de decisiones para 4 ítems: verde = mejor solución actual, gris = podado por bound.

⚖️ 5.4 Meet-in-the-Middle (MitM)

            Idea: partir la búsqueda en dos mitades de profundidad d/2 y "encontrarse en la mitad".
        

Ejemplo clásico: Subset Sum.

Dividir el arreglo en L y R.
Enumerar todas las sumas posibles de L → SL.
Enumerar todas las sumas de R → SR.
Quieres sL + sR ≈ T. Ordenas SR y haces búsqueda binaria sobre T − sL.

Enfoque	Tiempo	Memoria
Fuerza bruta	O(2ⁿ)	O(1)
MitM balanceado	O(2ⁿ⁄² · n)	O(2ⁿ⁄²)

Visual: Subset Sum con Meet-in-the-Middle

Arreglo de ejemplo: [3, 9, 10, 15, 20, 7], objetivo T = 25.

Sigue los pasos para ver cómo MitM evita revisar las 2⁶ combinaciones una por una.

📉 5.5 Gradient Descent & Ascent

Actualización básica:

Descenso: xᵏ⁺¹ = xᵏ − η ∇f(xᵏ) Ascenso: xᵏ⁺¹ = xᵏ + η ∇f(xᵏ)

En mínimos locales, el gradiente es 0. En funciones convexas suaves, GD converge al mínimo global con una tasa O(1/k) (o lineal si es fuertemente convexa).

Visual: descenso por contornos

Función de juguete: f(x, y) = x² + 0.5 y². Empezamos lejos del mínimo y seguimos −∇f.

Círculos = curvas de nivel; punto naranja = posición actual; trazo verde = trayectoria.

Template minimalista (Python)

def grad_descent(grad, x0, step=1e-2, iters=1000, tol=1e-6):
    x = x0
    for k in range(iters):
        g = grad(x)
        if (g * g).sum()**0.5 < tol:
            break
        x = x - step * g
    return x

⛰️ 5.6 Local Search & Hill Climbing

            Local search: mantener una sola solución x y movernos en un vecindario N(x) buscando bajar E(x).
        

Hill climbing es la versión codiciosa: siempre tomamos el mejor vecino que mejore la energía (o costo).

Visual: paisaje 1D (solo Hill Climbing)

Función rugosa f(x) = x²/8 + 0.5 sin(3x) + 0.2 cos(5x). Observa cómo hill climbing puede quedarse atrapado.

Curva blanca = f(x); punto naranja = posición; puntos verdes = trayecto del algoritmo.

🔥 5.7 Simulated Annealing (SA)

            Aceptar peores movimientos con probabilidad e^{-ΔE/T} permite escapar de mínimos locales.
        

P(aceptar) = 1 si ΔE ≤ 0, P(aceptar) = exp(-ΔE / T) si ΔE > 0

La temperatura T controla cuánto exploramos. Al inicio T alta ⇒ más azar; al final T baja ⇒ comportamiento tipo hill climbing.

Visual: Hill vs SA en el mismo paisaje

Compara trayectorias: hill (verde) vs SA (morado) en un paisaje con muchos mínimos locales.

🧬 5.8 Genetic Algorithms (GA)

            Idea: mantener una población de soluciones y aplicar selección, cruce y mutación para mejorar fitness.
        

Loop canónico

Inicializar población P₀.
Evaluar fitness F(x) para todos.
Seleccionar padres (p. ej. torneo).
Aplicar crossover + mutación → nueva población.
Reemplazar y repetir por T generaciones.

Visual: población moviéndose hacia el mínimo

Usamos la misma función 1D rugosa. Cada punto es un individuo.

Blanco = paisaje; azul = población; verde = mejor individuo actual.

GA binario minimalista (Python)

def ga_binary(fitness, d, pop=100, gens=200, pc=0.9, pm=None, elite=2):
    import random
    pm = (1.0/d) if pm is None else pm
    P = [[random.randint(0,1) for _ in range(d)] for _ in range(pop)]

    def tournament(P, k=3):
        cand = random.sample(P, k)
        return max(cand, key=fitness)

    def crossover(p, q):
        if random.random() > pc: return p[:], q[:]
        i = random.randint(1, d-1)
        return p[:i] + q[i:], q[:i] + p[i:]

    def mutate(x):
        for i in range(d):
            if random.random() < pm:
                x[i] ^= 1

    for _ in range(gens):
        P.sort(key=fitness, reverse=True)
        nextP = P[:elite]
        while len(nextP) < pop:
            p, q = tournament(P), tournament(P)
            c1, c2 = crossover(p, q)
            mutate(c1); mutate(c2)
            nextP += [c1, c2]
        P = nextP[:pop]
    best = max(P, key=fitness)
    return best, fitness(best)

🎮 5.9 Reinforcement Learning & Q-Learning

            Idea general: en RL un agente aprende por prueba y error a tomar decisiones en un ambiente, usando recompensas como señal de qué tan buena fue cada acción.
        

5.9.1 ¿Qué es RL?

Piensa en un videojuego tipo CartPole o Pong. El agente no tiene una lista de "si pasa esto, haz esto". En vez de eso:

Componente RL	¿Qué significa?	Ejemplo intuitivo
Estado s	Lo que el agente observa del mundo en este instante.	En CartPole: posición del carrito, ángulo y velocidad de la barra.
Acción a	Decisión que el agente puede tomar.	Empujar el carrito a la izquierda o derecha.
Recompensa r	Número que dice qué tan buena fue esa acción.	+1 por cada timestep que la barra siga arriba; 0 si se cae.
Política π(a\|s)	Regla que dice qué acción tomar en cada estado.	"Si la barra se inclina a la derecha, empujo a la derecha" (pero aprendida, no programada a mano).

            Objetivo de RL: aprender una política π(a|s) que maximice la suma de recompensas futuras (jugar bien a largo plazo, no sólo en un paso).
        

5.9.2 Ejemplo RL: CartPole

El agente observa el estado (posición y ángulo).
Toma acciones (empujar izq/der) según su política actual.
Recibe recompensas (+1 por timestep vivo).
Actualiza internamente sus parámetros para repetir acciones que llevaron a episodios más largos.

No necesariamente usa Q-learning; puede usar Policy Gradients, PPO, etc. Q-learning es sólo una forma concreta de hacer RL.

5.9.3 ¿Qué es Q-learning exactamente?

Q-learning intenta aprender una función Q(s,a) que diga: "Si estoy en el estado s y tomo la acción a, ¿cuál será mi recompensa total esperada (hacia el futuro)?".

Q(s,a) ← Q(s,a) + α · [ r + γ · max_a′ Q(s′,a′) − Q(s,a) ]

Q(s,a): valor actual que creemos que tiene hacer a en s.
r: recompensa inmediata observada.
γ: factor de descuento (qué tanto nos importan recompensas futuras).
max_a′ Q(s′,a′): mejor valor futuro desde el nuevo estado s′.
α: tasa de aprendizaje (qué tanto ajustamos).

            Traducción mental: "Sube o baja Q(s,a) para acercarlo a <recompensa inmediata + mejor valor futuro>."
        

5.9.4 Mini ejemplo con Q-table

Supón un pasillo lineal con 3 estados:

S1: inicio
S2: estás cerca de la meta
G: goal (ya ganaste)

Acciones posibles: Izq o Der. Solo en G obtienes recompensa +1.

Estado	Q(·, Izq)	Q(·, Der)	Mejor acción (política π)
S1	0.05	0.40	Der (ir hacia S2)
S2	0.10	0.80	Der (ir a G)
G	0.00	0.00	No importa (episodio termina)

Así se interpreta una Q-table: en cada fila (estado), elegimos la acción con Q más alta como la acción "natural" de la política.

5.9.5 Visual: Gridworld con Q-learning (ahora paso a paso)

Ambiente mini 4×4:

S (naranja) = estado inicial.
G (morado) = meta (recompensa +1).
El resto son celdas neutras con una pequeña penalización por paso (para que busque la ruta corta).

Paso 1: reinicia Q. Paso 2: entrena. Paso 3: ve la ruta aprendida (verde) de S a G.

            Resumen rápido: RL = "aprender a tomar decisiones con recompensas". Q-learning = "una forma concreta de RL donde aprendemos la tabla Q(s,a)". Cuando la tabla es muy grande, se reemplaza por una red neuronal (DQN, etc.).
        

📊 5.10 Complejidad, Garantías & Elección del Algoritmo

Familia	Ejemplos	Garantía	Escalabilidad
Determinista óptimo	A, IDA, UCS	Óptimo global	Exponencial
Acotado / podas	Branch-and-Bound, MitM	Óptimo si bounds sólidos	Mejor, depende de bounds
Local / heurístico	Hill Climb, GD	Mínimos locales	Muy escalable
Estocástico	SA, GA, RL	Óptimo en probabilidad	Poly–Exp

            Regla de oro: si puedes modelar el mundo con precisión, planea (A*, B&B). Si no, aprende (GA, SA, RL). En la práctica, combina ambas ideas.
        