Algoritmos modernos que todo programador debería conocer: de los mercados de emparejamiento a HNSW y ARC

TL;DR

• Los algoritmos no son una lista de datos triviales para entrevistas. En sistemas de producción, representan un conjunto recurrente de técnicas de diseño arquitectónico —amortización, subestructura óptima, cotas duales, relajación orientada a objetivos, sketches probabilísticos y ajuste automático en línea— que se reutilizan en motores de emparejamiento, compiladores, routers de red, núcleos de bases de datos e índices vectoriales.
• Elige el algoritmo según el tipo de garantía que necesitas:
  • Estabilidad demostrable: Gale–Shapley (mercados bilaterales, asignación de residencias).
  • Minimización exacta del costo global: Hungarian / Kuhn–Munkres (agrupación de solicitudes de viaje, asignación de tareas).
  • Búsqueda en streaming con garantía en el peor caso: Knuth–Morris–Pratt (analizadores léxicos, exploración con DFA).
  • Exploración práctica de logs con alto throughput: Boyer–Moore–Horspool (grep, ingesta de logs).
  • Firmas de múltiples patrones / ventanas deslizantes: Rabin–Karp (inspección profunda de paquetes, detección de plagio).
  • Asignación exacta de capacidad: 0/1 Knapsack DP con optimización de espacio (planificación de paquetes, presupuestos en la nube).
  • Exploración combinatoria interrumpible en cualquier momento: Ant Colony Optimization (ACO) (rutas logísticas, diseño de circuitos).
  • Clausura de grafos densos entre todos los pares: Floyd–Warshall (matrices de tránsito SD-WAN, clausura de divisas FX).
  • Flujo de red de alto throughput: Push–Relabel / Goldberg–Tarjan (aprovisionamiento de telecomunicaciones, segmentación mediante cortes de grafos).
  • Detección de redes de fraude y comunidades: Bron–Kerbosch con pivote (enumeración de cliques máximas).
  • Camino más corto orientado a un objetivo: A* (robótica, navmeshes de videojuegos, planificadores logísticos).
  • Gestión de memoria con ajuste automático: Adaptive Replacement Cache (ARC) (ZFS ARC, pools de buffers de bases de datos).
  • Cardinalidad con memoria acotada: HyperLogLog (Redis PFCOUNT, motores de análisis, fusión de shards).
  • Búsqueda por similitud en espacios de alta dimensión: HNSW (Milvus, Qdrant, Pinecone, recuperación vectorial para RAG).
• Toda decisión de ingeniería implica compromisos entre optimalidad, sobrecarga de memoria, latencia de indexación y comportamiento ante fallas. Los algoritmos exactos cuentan con demostraciones formales; las heurísticas y los sketches intercambian precisión por escala masiva; las estructuras amortizadas obtienen throughput a costa de una mayor variación en la latencia.

Qué aprenderás aquí

1. Cómo se agrupan catorce algoritmos modernos en seis primitivas arquitectónicas fundamentales que puedes reconocer y reutilizar al diseñar servicios de producción.
2. Análisis detallados de cada algoritmo, con invariantes matemáticos, complejidades Big-O exactas (mejor caso, promedio, peor caso y espacio), matrices de ventajas y desventajas e implementaciones idiomáticas en Python.
3. Flujos de trabajo y máquinas de estados claros en Mermaid que ilustran transiciones de estado y lógica de decisión sin recurrir a diagramas ASCII.
4. Contextos de sistemas reales: dónde se usan exactamente estas primitivas en entornos de producción (ZFS, PostgreSQL, Redis, kernels de Linux, controladores SD-WAN, bases de datos vectoriales para LLM y mercados de emparejamiento).
5. Una matriz universal de selección rápida y un flujo de decisión que relacionan directamente los tipos de problema, las restricciones y los SLO de latencia con los algoritmos recomendados y sus alternativas.
6. Referencias fundacionales primarias a la literatura y los artículos originales.

Parte 1: Fundamentos, problemas de emparejamiento y asignación

1. El lenguaje de los algoritmos: garantías, invariantes y cotas

Antes de analizar rutinas específicas, debemos acordar cómo evalúan los algoritmos los ingenieros de sistemas. En producción, no nos preguntamos solamente «¿es rápido?». Preguntamos:

1. ¿Qué invariante se cumple después de cada iteración? (Corrección inductiva).
2. ¿Cuál es el costo en el peor caso frente al costo amortizado con entradas adversariales? (Resiliencia ante ataques de denegación de servicio).
3. ¿Garantiza optimalidad global, estabilidad local o una aproximación acotada?
4. ¿El consumo de memoria es estático, de streaming o depende de la entrada?

flowchart LR
  subgraph guarantees ["Garantías algorítmicas"]
    direction TB
    G1["Optimalidad demostrable<br/>Hungarian, Knapsack, Floyd-Warshall"]
    G2["Estabilidad según la teoría de juegos<br/>Gale-Shapley"]
    G3["Latencia lineal en el peor caso<br/>KMP, Push-Relabel"]
    G4["Error probabilístico acotado<br/>HyperLogLog, HNSW, Rabin-Karp"]
    G5["Ajuste automático en línea<br/>Caché ARC"]
  end

2. Algoritmo de Gale-Shapley (emparejamiento estable)

Intuición principal e invariante matemático

El algoritmo de Gale–Shapley (1962) resuelve el problema del matrimonio estable (y su generalización para la asignación de hospitales y residentes). Dos conjuntos disjuntos de agentes ordenan por preferencia a todos los miembros del conjunto opuesto. Quienes proponen hacen ofertas siguiendo su lista de preferencias; quienes reciben conservan la mejor oferta recibida hasta el momento (aceptación diferida) y rechazan las ofertas inferiores.

Invariante matemático: Al finalizar, no existe ningún par bloqueante $(A, B)$ en el que quien propone, $A$, prefiera a quien recibe, $B$, sobre su pareja asignada y quien recibe, $B$, prefiera a $A$ sobre su pareja asignada. La formulación orientada a quienes proponen es óptima para quienes proponen (maximiza simultáneamente la utilidad de todos ellos) y a prueba de manipulación estratégica para ellos.

Complejidad Big-O

Nota: $n$ representa el número de agentes por partición. El espacio almacena las listas de preferencias y las matrices de búsqueda inversa.

Ventajas y desventajas

Implementación en Python para producción

from collections import deque
from dataclasses import dataclass
from typing import Mapping, Sequence


@dataclass(frozen=True, slots=True)
class StableMatchingResult:
    """Receiver -> proposer and proposer -> receiver stable matching."""

    matching: dict[str, str]
    inverse_matching: dict[str, str]


def gale_shapley(
    proposers: Sequence[str],
    receivers: Sequence[str],
    proposer_prefs: Mapping[str, Sequence[str]],
    receiver_prefs: Mapping[str, Sequence[str]],
) -> StableMatchingResult:
    """Proposer-optimal Gale–Shapley deferred acceptance."""
    receiver_rank: dict[str, dict[str, int]] = {}
    for receiver in receivers:
        prefs = receiver_prefs.get(receiver, ())
        receiver_rank[receiver] = {p: idx for idx, p in enumerate(prefs)}

    next_proposal_index = {proposer: 0 for proposer in proposers}
    free_proposers: deque[str] = deque(proposers)
    receiver_matches: dict[str, str] = {}

    while free_proposers:
        proposer = free_proposers.popleft()
        prefs = proposer_prefs.get(proposer, ())
        proposal_idx = next_proposal_index[proposer]

        if proposal_idx >= len(prefs):
            continue

        receiver = prefs[proposal_idx]
        next_proposal_index[proposer] = proposal_idx + 1

        incumbent = receiver_matches.get(receiver)
        if incumbent is None:
            receiver_matches[receiver] = proposer
            continue

        ranks = receiver_rank[receiver]
        if ranks.get(proposer, float("inf")) < ranks.get(incumbent, float("inf")):
            receiver_matches[receiver] = proposer
            free_proposers.append(incumbent)
        else:
            free_proposers.append(proposer)

    inverse_matching = {
        proposer: receiver for receiver, proposer in receiver_matches.items()
    }
    return StableMatchingResult(
        matching=receiver_matches,
        inverse_matching=inverse_matching,
    )

Casos de uso reales en producción

• National Resident Matching Program (NRMP): Asigna médicos recién graduados a plazas de residencia en el sistema de salud de Estados Unidos.
• Emparejamiento bipartito de clientes y servidores edge de CDN: Asigna clusters de ISP de clientes a puntos de presencia edge según sus preferencias de latencia y carga.
• Asignación descentralizada de recursos: Asigna instancias spot de VM en la nube, emparejando cargas de trabajo sensibles al costo con nodos de capacidad excedente.

Diagrama de flujo de ejecución en Mermaid

flowchart TD
  Start(["Todos los proponentes encolados como libres"]) --> CheckQueue{"¿Hay proponentes libres?"}
  CheckQueue -- No --> Done(["Devolver emparejamiento estable"])
  CheckQueue -- Sí --> Pop["Extraer al proponente P de la cola"]
  Pop --> Propose["Proponer al siguiente receptor R mejor valorado"]
  Propose --> CheckMatched{"¿R ya está emparejado?"}
  CheckMatched -- No --> Engage["Emparejar P con R"]
  Engage --> CheckQueue
  CheckMatched -- Sí --> Compare{"¿R prefiere a P sobre su pareja actual I?"}
  Compare -- Sí --> Reassign["Emparejar P con R; agregar I a la cola de libres"]
  Reassign --> CheckQueue
  Compare -- No --> Reject["Rechazar P; agregar P a la cola de libres"]
  Reject --> CheckQueue

3. Algoritmo húngaro (asignación bipartita de Kuhn-Munkres)

Intuición principal e invariante matemático

El algoritmo húngaro (Kuhn 1955, Munkres 1957) encuentra el emparejamiento perfecto de peso mínimo en un grafo bipartito completo y ponderado.

Se basa en la dualidad de la programación lineal:

• Mantiene las variables de potencial dual $u_i$ (filas) y $v_j$ (columnas), de modo que los costos reducidos cumplen $c_{ij} - u_i - v_j \ge 0$.
• Por holgura complementaria, un emparejamiento que solo utiliza aristas ajustadas ($c_{ij} - u_i - v_j = 0$) es globalmente óptimo.

Complejidad Big-O

Nota: La formulación original era $O(n^4)$; el seguimiento moderno de potenciales logra $O(n^3)$.

Ventajas y desventajas

Implementación en Python para producción

from dataclasses import dataclass


@dataclass(frozen=True, slots=True)
class AssignmentResult:
    assignment: list[int]
    min_cost: float


def hungarian_assignment(cost_matrix: list[list[float]]) -> AssignmentResult:
    """Minimum-weight perfect matching on an n×n cost matrix (Kuhn–Munkres)."""
    n = len(cost_matrix)
    if n == 0 or any(len(row) != n for row in cost_matrix):
        raise ValueError("Hungarian algorithm requires a non-empty square matrix.")

    u = [0.0] * (n + 1)
    v = [0.0] * (n + 1)
    p = [0] * (n + 1)
    way = [0] * (n + 1)

    for i in range(1, n + 1):
        p[0] = i
        j0 = 0
        minv = [float("inf")] * (n + 1)
        used = [False] * (n + 1)

        while True:
            used[j0] = True
            i0 = p[j0]
            delta = float("inf")
            j1 = 0

            for j in range(1, n + 1):
                if used[j]:
                    continue
                cur = cost_matrix[i0 - 1][j - 1] - u[i0] - v[j]
                if cur < minv[j]:
                    minv[j] = cur
                    way[j] = j0
                if minv[j] < delta:
                    delta = minv[j]
                    j1 = j

            for j in range(n + 1):
                if used[j]:
                    u[p[j]] += delta
                    v[j] -= delta
                else:
                    minv[j] -= delta

            j0 = j1
            if p[j0] == 0:
                break

        while True:
            j1 = way[j0]
            p[j0] = p[j1]
            j0 = j1
            if j0 == 0:
                break

    assignment = [-1] * n
    min_cost = 0.0
    for j in range(1, n + 1):
        row = p[j] - 1
        assignment[row] = j - 1
        min_cost += cost_matrix[row][j - 1]

    return AssignmentResult(assignment=assignment, min_cost=min_cost)

Casos de uso reales en producción

• Despacho de flotas de transporte compartido (Uber / Lyft): Agrupa $N$ conductores y $N$ solicitudes de viaje cada 5 segundos para minimizar el tiempo total de espera hasta la recogida.
• Seguimiento de múltiples objetos por radar / LIDAR (fusión de sensores): Asocia detecciones de cuadros delimitadores entre fotogramas consecutivos de video en conducción autónoma (rastreador SORT).
• Planificación de la distribución de chips semiconductores: Asigna celdas lógicas a pads del circuito con una longitud total de cableado mínima.

Parte 2: Búsqueda de cadenas y patrones de alto rendimiento

flowchart LR
  subgraph stringStrategies ["Compromisos en la búsqueda de cadenas"]
    RK["Rabin-Karp<br/>Hash rodante<br/>Múltiples patrones y huellas digitales"]
    KMP["KMP<br/>DFA de función de prefijo<br/>Streams y garantías lineales"]
    HO["Horspool<br/>Salto por carácter incorrecto de derecha a izquierda<br/>Texto natural y logs"]
  end

4. Algoritmo de Rabin-Karp (búsqueda de subcadenas con hash rodante)

Intuición principal e invariante matemático

Rabin-Karp (1987) utiliza hashing polinomial rodante para comprobar la igualdad de subcadenas en $O(1)$ por desplazamiento. En lugar de comprobar los caracteres secuencialmente, mantiene una ventana deslizante de hash:

$H_{i+1} = \left( (H_i - T[i] \cdot B^{m-1}) \cdot B + T[i+m] \right) \pmod M$

Invariante matemático: Si $H_{\text{window}} \neq H_{\text{pattern}}$, se garantiza que las subcadenas son diferentes. Si los hashes coinciden, se realiza una comparación completa de caracteres para descartar colisiones de hash.

Complejidad Big-O

Ventajas y desventajas

Implementación en Python para producción

def rabin_karp_search(
    text: str,
    pattern: str,
    *,
    base: int = 256,
    modulus: int = 1_000_000_007,
) -> list[int]:
    """Return start indices of all pattern occurrences using Rabin–Karp rolling hash."""
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []

    high_pow = pow(base, m - 1, modulus)
    pattern_hash = 0
    window_hash = 0

    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % modulus
        window_hash = (window_hash * base + ord(text[i])) % modulus

    matches: list[int] = []
    for i in range(n - m + 1):
        if pattern_hash == window_hash and text[i : i + m] == pattern:
            matches.append(i)

        if i < n - m:
            window_hash = (
                (window_hash - ord(text[i]) * high_pow) % modulus
            )
            window_hash = (window_hash * base + ord(text[i + m])) % modulus

    return matches

Casos de uso reales en producción

• Inspección profunda de paquetes (DPI): Busca firmas con hashes rodantes en payloads de red a la velocidad de línea.
• Detección de plagio y duplicados: Calcula hashes de fragmentos de documentos para descubrir duplicados aproximados.
• Indexación de k-mers en bioinformática: Pipelines de alineación de semilla y extensión sobre streams de ADN.

Diagrama de flujo en Mermaid

flowchart TD
  A["Precalcular el hash del patrón y B^m mod M"] --> B["Calcular el hash de la ventana inicial"]
  B --> C{"¿i es como máximo n menos m?"}
  C -- No --> Z["Devolver coincidencias verificadas"]
  C -- Sí --> D{"¿El hash de la ventana es igual al del patrón?"}
  D -- Sí --> E["Verificar caracteres en i"]
  E --> F{"¿Coincidencia exacta?"}
  F -- Sí --> G["Registrar coincidencia en i"]
  F -- No --> H["Deslizar ventana"]
  D -- No --> H
  G --> H
  H --> I["Actualizar hash rodante"]
  I --> J["Incrementar i"]
  J --> C

5. Algoritmo de Knuth-Morris-Pratt (KMP) (DFA de función de prefijo)

Intuición principal e invariante matemático

KMP (1977) elimina el backtracking sobre el texto al analizar la autosimilitud del patrón. Construye una función de prefijo $\pi$ (o tabla LPS: el prefijo propio más largo que también es sufijo). Cuando ocurre una discrepancia después de encontrar $j$ caracteres coincidentes, el cursor del texto nunca retrocede; el cursor del patrón vuelve a $\pi[j - 1]$.

Invariante matemático: $\pi[i] = \max \{ k \mid k < i+1 \text{ and } P[0 \dots k-1] = P[i-(k-1) \dots i] \}$.

Complejidad Big-O

Ventajas y desventajas

Implementación en Python para producción

def build_kmp_prefix_table(pattern: str) -> list[int]:
    """Build KMP longest proper prefix / suffix (pi) table."""
    m = len(pattern)
    pi = [0] * m
    length = 0

    for i in range(1, m):
        while length > 0 and pattern[i] != pattern[length]:
            length = pi[length - 1]
        if pattern[i] == pattern[length]:
            length += 1
        pi[i] = length

    return pi


def kmp_search(text: str, pattern: str) -> list[int]:
    """Search for pattern in text with zero stream backtracking."""
    n, m = len(text), len(pattern)
    if m == 0:
        return []

    pi = build_kmp_prefix_table(pattern)
    matches: list[int] = []
    j = 0

    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            matches.append(i - m + 1)
            j = pi[j - 1]

    return matches

Casos de uso reales en producción

• Detección de intrusiones en streams TCP en vivo: Busca firmas sin retroceder en el stream de bytes cuando los paquetes se fragmentan entre límites.
• Búsqueda de motivos en ADN / proteínas: Alfabetos largos y motivos repetitivos donde las tasas de colisión de Rabin–Karp dominarían el costo de verificación.
• Prevención de backtracking en el analizador léxico de un compilador: Búsquedas de un solo patrón en código fuente generado cuando el tiempo lineal en el peor caso es un requisito contractual.

Diagrama de flujo en Mermaid

flowchart TD
  A["Construir tabla pi a partir del patrón"] --> B["i = 0, j = 0 sobre el texto"]
  B --> C{"¿i es menor que n?"}
  C -- No --> Z["Devolver índices de coincidencias"]
  C -- Sí --> D{"¿El texto en i es igual al patrón en j?"}
  D -- Sí --> E["Incrementar j"]
  E --> F{"¿j es igual a m?"}
  F -- Sí --> G["Registrar coincidencia; j = pi de j menos 1"]
  F -- No --> H["Incrementar i"]
  G --> H
  D -- No --> I{"¿j es mayor que 0?"}
  I -- Sí --> J["j = pi de j menos 1"]
  I -- No --> K["Incrementar i"]
  J --> B
  K --> B
  H --> B

6. Algoritmo de Horspool (desplazamiento por carácter incorrecto de Boyer-Moore-Horspool)

Intuición principal e invariante matemático

Horspool (1980) es una simplificación práctica del algoritmo de Boyer–Moore. Compara el patrón con el texto de derecha a izquierda, pero, ante una discrepancia, desplaza toda la ventana basándose únicamente en el carácter del texto alineado con la última posición del patrón.

Invariante matemático: La tabla de desplazamiento por carácter incorrecto $\text{Shift}[c]$ registra la distancia desde la última aparición del carácter $c$ en $P[0 \dots m-2]$ hasta el final del patrón. Cualquier desplazamiento menor causaría una discrepancia inmediata.

Complejidad Big-O

Nota: $\Sigma$ es el tamaño del alfabeto (256 para streams ASCII/de bytes).

Ventajas y desventajas

Implementación en Python para producción

def build_horspool_table(pattern: str) -> list[int]:
    """Build Boyer–Moore–Horspool bad-character shift table for byte strings."""
    m = len(pattern)
    table = [m] * 256
    for i in range(m - 1):
        table[ord(pattern[i]) & 0xFF] = m - 1 - i
    return table


def horspool_search(text: str, pattern: str) -> list[int]:
    """Find all pattern occurrences using Boyer–Moore–Horspool."""
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []

    shift = build_horspool_table(pattern)
    matches: list[int] = []
    i = m - 1

    while i < n:
        k = 0
        while k < m and pattern[m - 1 - k] == text[i - k]:
            k += 1

        if k == m:
            matches.append(i - m + 1)

        i += shift[ord(text[i]) & 0xFF]

    return matches

Casos de uso reales en producción

• Búsqueda con grep en logs y de patrones en SIEM: Alta tasa de salto en logs ASCII y trazas de pila dentro de pipelines de observabilidad.
• «Buscar en archivos» de un IDE sobre buffers locales: Fragmentos de archivos de acceso aleatorio donde comparar caracteres hacia atrás es poco costoso.
• Exploración de campos de protocolos binarios: Tokens de ancho fijo en capturas de red cuando el caso promedio domina el SLA.

Diagrama de flujo en Mermaid

flowchart TD
  A["Construir tabla de desplazamiento por carácter incorrecto"] --> B["Alinear el final del patrón en el índice i"]
  B --> C{"¿i es menor que n?"}
  C -- No --> Z["Devolver coincidencias"]
  C -- Sí --> D["Comparar patrón de derecha a izquierda"]
  D --> E{"¿Coincidencia completa?"}
  E -- Sí --> F["Registrar índice inicial"]
  E -- No --> G["Desplazar según la tabla de caracteres incorrectos para el texto en i"]
  F --> G
  G --> H["Avanzar i según el desplazamiento"]
  H --> B

Parte 3: Optimización discreta y combinatoria

7. Algoritmo de la mochila 0/1 (programación dinámica con optimización de espacio)

Intuición principal e invariante matemático

Dados $n$ elementos con pesos $w_i$ y valores $v_i$, y una capacidad máxima $W$, selecciona un subconjunto que maximice el valor total sin superar $W$.

Relación de recurrencia: $dp[w] = \max(dp[w], dp[w - w_i] + v_i) \quad \text{for } w = W \text{ down to } w_i$

Invariante: Iterar hacia atrás desde $W$ hasta $w_i$ garantiza que cada elemento se incluya como máximo una vez (restricción $0/1$), mientras se comprime el estado 2D de $O(n \cdot W)$ en un solo arreglo 1D de $O(W)$.

Complejidad Big-O

Nota: Complejidad temporal pseudopolinomial que depende de la capacidad numérica $W$.

Ventajas y desventajas

Implementación en Python para producción

from dataclasses import dataclass


@dataclass(frozen=True, slots=True)
class KnapsackItem:
    id: str
    weight: int
    value: float


@dataclass(frozen=True, slots=True)
class KnapsackResult:
    max_value: float
    selected_items: list[str]


def solve_01_knapsack(items: list[KnapsackItem], capacity: int) -> KnapsackResult:
    """0/1 knapsack with space-optimized DP and exact item reconstruction."""
    if capacity <= 0 or not items:
        return KnapsackResult(max_value=0.0, selected_items=[])

    dp = [0.0] * (capacity + 1)
    choice = [[0] * (capacity + 1) for _ in items]

    for i, item in enumerate(items):
        if item.weight > capacity:
            continue
        for w in range(capacity, item.weight - 1, -1):
            with_item = dp[w - item.weight] + item.value
            if with_item > dp[w]:
                dp[w] = with_item
                choice[i][w] = 1

    selected: list[str] = []
    remaining = capacity
    for i in range(len(items) - 1, -1, -1):
        if choice[i][remaining]:
            selected.append(items[i].id)
            remaining -= items[i].weight

    return KnapsackResult(max_value=dp[capacity], selected_items=list(reversed(selected)))

Casos de uso reales en producción

• Agrupación según costos de nube: Selecciona paquetes de funcionalidades dentro de cuotas de CPU/RAM para trabajos batch o flotas de instancias spot.
• Asignación de presupuestos publicitarios: Campañas discretas con límites de gasto fijos y valores de ROI estimados.
• Preparación de carga y rutas de flotas: Elige envíos dentro de límites de peso antes de resolver el enrutamiento continuo.

Diagrama de flujo en Mermaid

flowchart TD
  A["Para cada elemento i"] --> B["Para w desde W hasta weight_i en orden descendente"]
  B --> C{"¿dp en w menos el peso más el valor es mayor que dp en w?"}
  C -- Sí --> D["Tomar elemento: actualizar dp en w; marcar elección"]
  C -- No --> E["Omitir en capacidad w"]
  D --> B
  E --> B
  B --> F["Siguiente elemento o reconstruir desde la tabla de elecciones"]

8. Optimización por colonia de hormigas (metaheurística ACO)

Intuición principal e invariante matemático

ACO (Dorigo 1992) es una metaheurística poblacional inspirada en la biología para problemas combinatorios NP-hard (como el problema del viajante). Las hormigas artificiales construyen soluciones recorriendo probabilísticamente las aristas de un grafo, influidas por:

1. Intensidad del rastro de feromonas ($\tau_{ij}$): Memoria de soluciones anteriores de alta calidad.
2. Visibilidad heurística ($\eta_{ij} = 1 / d_{ij}$): Estrategia voraz local.

Probabilidad de transición: $P_{ij}^k = \frac{(\tau_{ij})^\alpha \cdot (\eta_{ij})^\beta}{\sum_{l \in \text{allowed}} (\tau_{il})^\alpha \cdot (\eta_{il})^\beta}$

Evaporación y refuerzo de feromonas: $\tau_{ij} \leftarrow (1 - \rho)\tau_{ij} + \sum_{k=1}^m \Delta\tau_{ij}^k, \quad \text{where } \Delta\tau_{ij}^k = \frac{Q}{L_k}$

Complejidad Big-O

Ventajas y desventajas

flowchart TD
  Init["Inicializar feromonas y visibilidad"] --> StepLoop{"¿Iteración por debajo del máximo?"}
  StepLoop -- No --> Done(["Devolver el mejor recorrido encontrado"])
  StepLoop -- Sí --> AntConstruct["Las hormigas construyen recorridos mediante selección por ruleta"]
  AntConstruct --> EvalTours["Evaluar costos L_k de los recorridos"]
  EvalTours --> UpdateBest["Actualizar el mejor recorrido global"]
  UpdateBest --> Evaporation["Evaporar feromonas: tau *= 1 - rho"]
  Evaporation --> Deposit["Depositar feromonas de refuerzo: delta tau = Q / L_k"]
  Deposit --> StepLoop

Casos de uso reales en producción

• Diseño de rutas de entrega de última milla: Inicializa OR-Tools VRP con recorridos de ACO en grafos nocturnos.
• Análisis de escenarios de diseño de redes: Explora diseños de fibra / WAN cuando los costos de las aristas cambian con frecuencia.
• Planificación de plantas industriales: Ordena visitas a máquinas cuando CP-SAT exacto excede el tiempo límite a escala de producción.

Implementación en Python para producción (paso ilustrativo de ACO)

import random


def construct_ant_tour(
    dist: list[list[float]],
    pheromone: list[list[float]],
    alpha: float,
    beta: float,
    rng: random.Random | None = None,
) -> list[int]:
    """One ant tour via roulette edge selection (symmetric TSP-style)."""
    rng = rng or random.Random()
    n = len(dist)
    visited = [False] * n
    tour = [0]
    visited[0] = True

    for _ in range(1, n):
        from_city = tour[-1]
        weights: list[tuple[int, float]] = []
        total = 0.0

        for to_city in range(n):
            if visited[to_city]:
                continue
            tau = pheromone[from_city][to_city] ** alpha
            eta = (1.0 / max(dist[from_city][to_city], 1e-9)) ** beta
            weight = tau * eta
            weights.append((to_city, weight))
            total += weight

        pick = rng.random() * total
        for to_city, weight in weights:
            pick -= weight
            if pick <= 0:
                tour.append(to_city)
                visited[to_city] = True
                break

    return tour

Parte 4: Algoritmos avanzados de grafos y flujo de red

9. Algoritmo de Floyd-Warshall (caminos más cortos entre todos los pares)

Intuición principal e invariante matemático

Floyd-Warshall (1962) calcula los caminos más cortos entre todos los pares de vértices de un grafo dirigido y ponderado (permite aristas negativas, siempre que no existan ciclos negativos).

Formulación de recurrencia: $D^{(k)}[i][j] = \min\left(D^{(k-1)}[i][j], \; D^{(k-1)}[i][k] + D^{(k-1)}[k][j]\right)$

Invariante inductivo: Después de la fase $k$, $D[i][j]$ contiene el camino más corto desde $i$ hasta $j$ que utiliza únicamente vértices intermedios de $\{0, 1, \dots, k\}$.

Complejidad Big-O

Ventajas y desventajas

Implementación en Python para producción

from dataclasses import dataclass
from math import inf
from typing import Callable


@dataclass(frozen=True, slots=True)
class AllPairsResult:
    distance_matrix: list[list[float]]
    has_negative_cycle: bool
    reconstruct_path: Callable[[int, int], list[int] | None]


def floyd_warshall(
    vertex_count: int,
    edges: list[tuple[int, int, float]],
) -> AllPairsResult:
    """All-pairs shortest paths with path reconstruction pointers."""
    n = vertex_count
    dist = [[0.0 if i == j else inf for j in range(n)] for i in range(n)]
    nxt = [[None if i != j else j for j in range(n)] for i in range(n)]

    for u, v, weight in edges:
        if weight < dist[u][v]:
            dist[u][v] = weight
            nxt[u][v] = v

    for k in range(n):
        for i in range(n):
            if dist[i][k] == inf:
                continue
            for j in range(n):
                if dist[k][j] == inf:
                    continue
                candidate = dist[i][k] + dist[k][j]
                if candidate < dist[i][j]:
                    dist[i][j] = candidate
                    nxt[i][j] = nxt[i][k]

    has_negative_cycle = any(dist[i][i] < 0 for i in range(n))

    def reconstruct_path(u: int, v: int) -> list[int] | None:
        if has_negative_cycle or dist[u][v] == inf:
            return None
        path = [u]
        current = u
        while current != v:
            step = nxt[current][v]
            if step is None:
                return None
            current = step
            path.append(current)
        return path

    return AllPairsResult(
        distance_matrix=dist,
        has_negative_cycle=has_negative_cycle,
        reconstruct_path=reconstruct_path,
    )

Casos de uso reales en producción

• Matrices de tránsito de POP / AS de red: Precalcula la latencia entre todos los pares para grafos densos de redes troncales ($V \lesssim 500$).
• Mapas de influencia de IA en videojuegos: Alcanzabilidad en cuadrículas con teletransportadores cuando $V$ es moderado.
• Validación de políticas: Detecta ciclos negativos antes de publicar tablas de enrutamiento ponderadas.

Diagrama de flujo en Mermaid

flowchart TD
  A["Inicializar dist y next a partir de las aristas"] --> B["Para cada intermediario k"]
  B --> C["Relajar todos los pares i,j a través de k"]
  C --> D{"¿Mejoró la distancia?"}
  D -- Sí --> E["Actualizar dist y el puntero next"]
  D -- No --> F["Continuar"]
  E --> F
  F --> G{"¿Se procesaron todos los k?"}
  G -- No --> B
  G -- Sí --> H["Comprobar la diagonal en busca de ciclos negativos"]

10. Algoritmo Push-Relabel (flujo máximo de red de Goldberg-Tarjan)

Intuición principal e invariante matemático

Push-Relabel (Goldberg & Tarjan 1988) se diferencia fundamentalmente de Ford-Fulkerson y Edmonds-Karp al abandonar los aumentos de caminos completos. En su lugar, trabaja localmente mediante un preflujo:

1. Los vértices mantienen un balance de exceso: $e(u) = f_{\text{in}}(u) - f_{\text{out}}(u) \ge 0$.
2. Los vértices mantienen una etiqueta de altura / distancia $h(u)$.
3. Operación push: El flujo se empuja cuesta abajo por aristas residuales donde $h(u) = h(v) + 1$.
4. Operación relabel: Si el vértice $u$ tiene exceso, pero no tiene un vecino residual cuesta abajo, se incrementa su altura: $h(u) \leftarrow 1 + \min \{ h(v) \mid (u,v) \in E_f \}$.

Invariante matemático: Validez de alturas: $h(u) \le h(v) + 1$ para todas las aristas residuales $(u,v) \in E_f$. La conservación del flujo se mantiene en todas partes una vez que el exceso se drena de vuelta al origen o al destino.

stateDiagram-v2
  [*] --> SaturateSourceEdges: Empujar capacidad desde el origen a la altura V
  SaturateSourceEdges --> ActiveVerticesQueue: Exceso en nodos intermedios
  ActiveVerticesQueue --> PushFlow: La altura del vecino es h(u) menos 1 y el residual es positivo
  PushFlow --> ActiveVerticesQueue: Exceso actualizado
  ActiveVerticesQueue --> RelabelHeight: No hay vecino cuesta abajo disponible
  RelabelHeight --> ActiveVerticesQueue: Altura elevada a 1 más la altura mínima de los vecinos
  ActiveVerticesQueue --> [*]: No queda exceso activo

Complejidad Big-O

Ventajas y desventajas

Casos de uso reales en producción

• Control de tráfico saliente de centros de datos: Modelo de flujo máximo de las capacidades de enlaces multipath entre regiones.
• Asignación de anuncios / b-matching: Oferta con capacidad limitada hacia nodos de demanda en grafos de tecnología publicitaria.
• Cortes de grafos al estilo OpenCV: Los pipelines de visión reducen la segmentación a un corte mínimo / flujo máximo s–t.

Implementación en Python para producción (esquema de preflujo push)

def push_flow(
    u: int,
    v: int,
    excess: list[float],
    capacity: list[list[float]],
    flow: list[list[float]],
    height: list[int],
) -> None:
    """Push excess along admissible residual edge (height[u] == height[v] + 1)."""
    residual = capacity[u][v] - flow[u][v]
    if residual <= 0 or height[u] != height[v] + 1:
        return
    delta = min(excess[u], residual)
    flow[u][v] += delta
    flow[v][u] -= delta
    excess[u] -= delta
    excess[v] += delta

11. Algoritmo de Bron-Kerbosch (enumeración de cliques máximas)

Intuición principal e invariante matemático

Una clique es un subgrafo completo en el que cada par de vértices está conectado por una arista. Bron-Kerbosch (1973) es un algoritmo recursivo de backtracking que enumera todas las cliques máximas (cliques que no se pueden extender) mediante tres conjuntos disjuntos de vértices:

• $R$: Clique actual en exploración.
• $P$: Vértices candidatos que pueden expandir $R$.
• $X$: Vértices ya procesados (conjunto de exclusión para evitar resultados duplicados).

Optimización con pivote (Tomita et al.): Selecciona un pivote $u \in P \cup X$. Itera solo sobre los candidatos no conectados al pivote: $v \in P \setminus N(u)$. Esto poda ramas de búsqueda redundantes.

Complejidad Big-O

Ventajas y desventajas

Casos de uso reales en producción

• Redes de fraude financiero: Encuentra clusters de cuentas completamente conectadas en grafos de transacciones.
• Moderación de grafos sociales: Cliques máximas en subgrafos de seguimiento mutuo para detectar bots.
• Bioinformática: Complejos de interacción de proteínas como cuasicliques (con filtrado previo de ruido).

Diagrama de flujo en Mermaid

flowchart TD
  A["Bron-Kerbosch con conjuntos R, P, X"] --> B{"¿P y X están vacíos?"}
  B -- Sí --> C["Reportar clique máxima R"]
  B -- No --> D["Elegir pivote u en la unión de P y X"]
  D --> E["Para v en P menos los vecinos de u"]
  E --> F["Recursión con R más v, P intersección N(v), X intersección N(v)"]
  F --> G["Mover v de P a X"]
  G --> E
  C --> H["Retornar"]

Implementación en Python para producción

def bron_kerbosch(
    adj: list[set[int]],
    r: list[int] | None = None,
    p: list[int] | None = None,
    x: list[int] | None = None,
    out: list[list[int]] | None = None,
) -> list[list[int]]:
    """Enumerate maximal cliques with Bron–Kerbosch (Tomita pivot)."""
    r = r or []
    p = p if p is not None else list(range(len(adj)))
    x = x or []
    out = out if out is not None else []

    if not p and not x:
        out.append(r.copy())
        return out

    pivot = p[0] if p else x[0]
    pivot_neighbors = adj[pivot]
    for v in [node for node in p if node not in pivot_neighbors]:
        neighbors = adj[v]
        bron_kerbosch(
            adj,
            r + [v],
            [node for node in p if node in neighbors],
            [node for node in x if node in neighbors],
            out,
        )
        p = [node for node in p if node != v]
        x = x + [v]

    return out

12. Algoritmo de búsqueda A* (búsqueda heurística de caminos)

Intuición principal e invariante matemático

A* (Hart, Nilsson, Raphael 1968) guía la búsqueda de costo uniforme de Dijkstra hacia el objetivo mediante una heurística admisible:

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

• $g(n)$: Costo exacto del camino desde el inicio hasta $n$.
• $h(n)$: Costo estimado desde $n$ hasta el objetivo.

Admisibilidad y consistencia:

1. Admisible: $h(n) \le h^*(n)$ (nunca sobreestima el costo restante real). Garantiza un camino óptimo.
2. Consistente (monótona): $h(u) \le c(u, v) + h(v)$. Garantiza que la primera vez que se extrae un nodo del conjunto abierto, su $g(n)$ ya es óptimo (no se vuelven a expandir nodos del conjunto cerrado).

Complejidad Big-O

Ventajas y desventajas

Casos de uso reales en producción

• Navmeshes de videojuegos y rutas de NPC: Heurísticas de Manhattan / euclidiana en cuadrículas.
• Enrutamiento de AMR en almacenes: Costos de aristas dependientes del tiempo con mapas estáticos de obstáculos.
• APIs de mapas (a pie / en automóvil): Búsqueda orientada al objetivo en las capas locales de jerarquías de contracción.

Diagrama de flujo en Mermaid

flowchart TD
  A["Agregar inicio con f = g + h"] --> B{"¿Conjunto abierto vacío?"}
  B -- Sí --> Z["No hay camino"]
  B -- No --> C["Extraer nodo n con f mínimo"]
  C --> D{"¿n es el objetivo?"}
  D -- Sí --> Y["Reconstruir camino"]
  D -- No --> E["Para cada vecino v"]
  E --> F["Calcular g tentativo"]
  F --> G{"¿Mejora el valor de g?"}
  G -- Sí --> H["Asignar padre; agregar f = g + h"]
  G -- No --> E
  H --> B

Implementación en Python para producción

from heapq import heappop, heappush
from math import inf
from typing import Callable


def a_star(
    neighbors: Callable[[int], list[tuple[int, float]]],
    h: Callable[[int], float],
    start: int,
    goal: int,
) -> list[int] | None:
    """A* shortest path with admissible heuristic h."""
    open_set: list[tuple[float, int]] = [(h(start), start)]
    g_score = {start: 0.0}
    came_from: dict[int, int] = {}

    while open_set:
        _, current = heappop(open_set)
        if current == goal:
            path = [goal]
            node = goal
            while node != start:
                node = came_from[node]
                path.append(node)
            return list(reversed(path))

        for nxt, cost in neighbors(current):
            tentative = g_score[current] + cost
            if tentative < g_score.get(nxt, inf):
                came_from[nxt] = current
                g_score[nxt] = tentative
                heappush(open_set, (tentative + h(nxt), nxt))

    return None

Parte 5: Algoritmos de sistemas, memoria y caché

13. Adaptive Replacement Cache (ARC)

Intuición principal e invariante matemático

Inventada por Nimrod Megiddo y Dharmendra S. Modha (IBM Almaden, 2003), ARC resuelve el dilema clásico de caché entre acceso reciente (LRU) y frecuencia (LFU).

LRU puro es vulnerable a exploraciones secuenciales de una sola pasada que expulsan el conjunto de trabajo. LFU puro sufre contaminación de caché cuando los elementos históricos acumulan conteos elevados y nunca se expulsan.

ARC mantiene cuatro listas doblemente enlazadas separadas y un parámetro de adaptación dinámico $p$:

• $T_1$: Entradas de caché a las que se accedió una vez recientemente (acceso reciente).
• $T_2$: Entradas de caché a las que se accedió al menos dos veces (frecuencia).
• $B_1$: Lista fantasma que rastrea claves expulsadas recientemente de $T_1$ (solo metadatos, sin payload).
• $B_2$: Lista fantasma que rastrea claves expulsadas recientemente de $T_2$ (solo metadatos, sin payload).

flowchart LR
  subgraph residentCache ["Caché en memoria física (tamaño total C)"]
    T1["T1: Aciertos recientes (tamaño máximo p)"]
    T2["T2: Aciertos frecuentes (tamaño máximo C menos p)"]
  end

  subgraph ghostHistory ["Historial de metadatos fantasma (tamaño máximo C)"]
    B1["B1: Claves fantasma de acceso reciente"]
    B2["B2: Claves fantasma de frecuencia"]
  end

  Miss["Fallo de página"] --> T1
  T1 -- "2.º acierto" --> T2
  T1 -- Expulsión --> B1
  T2 -- Expulsión --> B2
  B1 -- "Acierto fantasma: aumentar p" --> T2
  B2 -- "Acierto fantasma: reducir p" --> T2

La regla de adaptación:

• Si un fallo de caché encuentra la clave en la lista fantasma $B_1$, significa que la caché se vio penalizada por falta de capacidad para accesos recientes. ARC incrementa $p$: $p \leftarrow \min\left(c, \; p + \max\left(1, \frac{|B_2|}{|B_1|}\right)\right)$
• Si un fallo de caché encuentra la clave en la lista fantasma $B_2$, ARC reduce $p$ para ampliar la capacidad destinada a la frecuencia: $p \leftarrow \max\left(0, \; p - \max\left(1, \frac{|B_1|}{|B_2|}\right)\right)$

Complejidad Big-O

Ventajas y desventajas

Implementación en Python para producción

from collections import OrderedDict
from typing import Callable, Generic, TypeVar

K = TypeVar("K")
V = TypeVar("V")


class AdaptiveReplacementCache(Generic[K, V]):
    """Adaptive Replacement Cache (Megiddo & Modha)."""

    def __init__(
        self,
        capacity: int,
        key_serializer: Callable[[K], str] | None = None,
    ) -> None:
        self.c = max(1, capacity)
        self.p = 0
        self._serialize = key_serializer or str

        self.t1: OrderedDict[str, tuple[K, V]] = OrderedDict()
        self.t2: OrderedDict[str, tuple[K, V]] = OrderedDict()
        self.b1: OrderedDict[str, None] = OrderedDict()
        self.b2: OrderedDict[str, None] = OrderedDict()

    def get(self, key: K) -> V | None:
        k_str = self._serialize(key)

        if k_str in self.t1:
            k_obj, value = self.t1.pop(k_str)
            self.t2[k_str] = (k_obj, value)
            return value

        if k_str in self.t2:
            k_obj, value = self.t2.pop(k_str)
            self.t2[k_str] = (k_obj, value)
            return value

        return None

    def set(self, key: K, value: V) -> None:
        k_str = self._serialize(key)

        if k_str in self.t1:
            self.t1.pop(k_str)
            self.t2[k_str] = (key, value)
            return

        if k_str in self.t2:
            self.t2.pop(k_str)
            self.t2[k_str] = (key, value)
            return

        if k_str in self.b1:
            delta = 1 if len(self.b1) >= len(self.b2) else len(self.b2) // max(len(self.b1), 1)
            self.p = min(self.c, self.p + delta)
            self._replace(k_str)
            self.b1.pop(k_str, None)
            self.t2[k_str] = (key, value)
            return

        if k_str in self.b2:
            delta = 1 if len(self.b2) >= len(self.b1) else len(self.b1) // max(len(self.b2), 1)
            self.p = max(0, self.p - delta)
            self._replace(k_str)
            self.b2.pop(k_str, None)
            self.t2[k_str] = (key, value)
            return

        total_resident = len(self.t1) + len(self.t2)
        total_tracking = total_resident + len(self.b1) + len(self.b2)

        if len(self.t1) + len(self.b1) == self.c:
            if len(self.t1) < self.c:
                self._delete_oldest(self.b1)
                self._replace(k_str)
            else:
                self._delete_oldest(self.t1)
        elif total_tracking >= self.c:
            if total_tracking == 2 * self.c:
                self._delete_oldest(self.b2)
            self._replace(k_str)

        self.t1[k_str] = (key, value)

    def _replace(self, incoming_key: str) -> None:
        if self.t1 and (
            len(self.t1) > self.p
            or (incoming_key in self.b2 and len(self.t1) == self.p)
        ):
            evicted = self._delete_oldest(self.t1)
            if evicted is not None:
                self.b1[evicted] = None
        else:
            evicted = self._delete_oldest(self.t2)
            if evicted is not None:
                self.b2[evicted] = None

    @staticmethod
    def _delete_oldest(mapping: OrderedDict) -> str | None:
        if not mapping:
            return None
        key, _ = mapping.popitem(last=False)
        return key

Casos de uso reales en producción

• Pools de buffers de bases de datos: Protegen las páginas activas de índices frente a exploraciones secuenciales de tablas que ocurren una sola vez.
• Cachés de metadatos de CDN / objetos: Patrones de lectura mixtos en claves versionadas.
• Cachés de servicios dentro del proceso: Cuando el tráfico alterna entre modos batch e interactivo.

Parte 6: Fronteras algorítmicas modernas: sketches probabilísticos y búsqueda vectorial

14. HyperLogLog (estimación de cardinalidad HLL)

Intuición principal e invariante matemático

HyperLogLog (Flajolet et al. 2007) resuelve el problema de contar miles de millones de elementos distintos en un stream de alto throughput usando solo 1.5 KB de RAM.

1. Aplica hashes a los elementos en un espacio uniforme de 64 bits.
2. Usa los primeros $b$ bits para seleccionar uno de los $m = 2^b$ buckets de registros.
3. Usa los bits restantes para observar el número de ceros iniciales ($\rho$).
4. Invariante: La posición del primer bit con valor 1 actúa como estimador de probabilidad exponencial ($\mathbb{E}[\text{zeros}] \approx \log_2 N$).
5. Combina los $m$ registros mediante una media armónica para eliminar la varianza de valores atípicos:

$E = \alpha_m \cdot m^2 \cdot \left( \sum_{j=1}^m 2^{-M[j]} \right)^{-1}$

El error estándar está estrechamente acotado: $\text{SE} \approx \frac{1.04}{\sqrt{m}}$. Para $m = 16,384$ ($b = 14$), el error es $\le 0.81\%$.

flowchart TD
  Item["Elemento x del stream"] --> Hash["Hash uniforme de 64 bits"]
  Hash --> Split["Dividir bits: índice de bucket b y sufijo de valor w"]
  Split --> CountZeros["Calcular rho = ceros iniciales más 1"]
  CountZeros --> UpdateRegister{"¿Rho es mayor que el registro M_b?"}
  UpdateRegister -- Sí --> Write["Asignar M_b = rho"]
  UpdateRegister -- No --> Ignore["Sin operación"]
  Write --> HarmonicMean["Al leer: media armónica de todos los registros M"]

Complejidad Big-O

Ventajas y desventajas

Casos de uso reales en producción

• Visitantes únicos / DAU: Fusiona sketches por shard al consultar.
• Telemetría de seguridad: IPs o huellas digitales distintas con alta tasa de ingesta.
• Exposición a experimentos: Seguimiento económico de asignaciones distintas.

Implementación en Python para producción

ALPHA_14 = 0.7213475204444817


class HyperLogLog:
    """HyperLogLog cardinality sketch (precision b => m = 2**b registers)."""

    def __init__(self, precision: int = 14) -> None:
        self.m = 1 << precision
        self.precision = precision
        self.registers = bytearray(self.m)

    def add(self, h64: int) -> None:
        idx = (h64 >> (64 - self.precision)) & (self.m - 1)
        w = ((h64 << self.precision) | 1) & ((1 << 64) - 1)
        rho = 1
        while rho < 64 and ((w >> (63 - rho)) & 1) == 0:
            rho += 1
        if rho > self.registers[idx]:
            self.registers[idx] = rho

    def estimate(self) -> float:
        inv_sum = sum(2.0 ** (-reg) for reg in self.registers)
        return ALPHA_14 * self.m * self.m / inv_sum

15. HNSW: Hierarchical Navigable Small World (búsqueda por similitud vectorial)

Intuición principal e invariante matemático

HNSW (Malkov & Yashunin 2018) es la estructura de indexación estándar de la industria para embeddings vectoriales que impulsan la generación aumentada por recuperación (RAG) y la búsqueda semántica en IA (Qdrant, Milvus, Weaviate).

Crea un grafo geométrico multicapa de tipo skip list:

• Las capas superiores contienen vértices dispersos con aristas de largo alcance para enrutamiento rápido ($O(\log N)$ saltos).
• La capa inferior 0 contiene el grafo denso de proximidad con todos los vectores indexados.
• El recorrido de una consulta ejecuta una búsqueda voraz en la capa superior, desciende al alcanzar mínimos locales y cambia a búsqueda de haz (efSearch) en la capa 0.

flowchart TD
  subgraph layer2 ["Capa 2: vía dispersa de largo alcance"]
    L2_A(("Nodo A")) --- L2_B(("Nodo B"))
  end

  subgraph layer1 ["Capa 1: conexiones de salto intermedias"]
    L1_A(("Nodo A")) --- L1_C(("Nodo C")) --- L1_B(("Nodo B"))
  end

  subgraph layer0 ["Capa 0: grafo de proximidad completo y denso"]
    L0_A(("Nodo A")) --- L0_D(("Nodo D")) --- L0_C(("Nodo C")) --- L0_E(("Nodo E")) --- L0_B(("Nodo B"))
  end

  Query["Vector de consulta Q"] --> L2_A
  L2_A -->|"Salto voraz"| L2_B
  L2_B -->|Descender| L1_B
  L1_B -->|"Salto voraz"| L1_C
  L1_C -->|"Descender a la capa 0"| L0_C
  L0_C -->|"Búsqueda de haz efSearch"| TopK["Devolver los K vecinos más cercanos"]

Complejidad Big-O

Ventajas y desventajas

Casos de uso reales en producción

• Recuperación para RAG: Los $k$ chunks con embeddings más relevantes para las ventanas de contexto de LLM.
• Similitud de medios: Detección de duplicados aproximados en catálogos de imágenes / audio.
• Embeddings de riesgo / fraude: Búsqueda por similitud sobre vectores de transacciones o dispositivos.

Implementación en Python para producción (esquema de capa voraz)

import math
from typing import Sequence


def cosine(a: Sequence[float], b: Sequence[float]) -> float:
    dot = sum(x * y for x, y in zip(a, b))
    na = math.sqrt(sum(x * x for x in a))
    nb = math.sqrt(sum(x * x for x in b))
    return dot / (na * nb + 1e-12)


def greedy_layer_search(
    query: Sequence[float],
    entry_id: int,
    vectors: Sequence[Sequence[float]],
    neighbors: Sequence[Sequence[int]],
) -> int:
    """Greedy search on one HNSW layer; production code stacks layers + efSearch on L0."""
    best = entry_id
    improved = True
    while improved:
        improved = False
        for cand in neighbors[best]:
            if cosine(query, vectors[cand]) > cosine(query, vectors[best]):
                best = cand
                improved = True
    return best

Parte 7: Metasíntesis: ¿qué nos enseñan realmente todos estos algoritmos?

Cuando tomas distancia de los algoritmos individuales, se reducen a seis primitivas arquitectónicas universales:

flowchart TB
  subgraph primitives ["Las 6 primitivas algorítmicas"]
    P1["1. Amortización frente a garantías en el peor caso"]
    P2["2. Programación dinámica y subestructura óptima"]
    P3["3. Cotas duales y relajación"]
    P4["4. Heurísticas orientadas al objetivo frente a búsqueda exacta"]
    P5["5. Sketches probabilísticos frente a estado exacto"]
    P6["6. Ajuste automático en línea y retroalimentación adaptativa"]
  end

  P1 --> Systems["Diseño de sistemas de alto rendimiento"]
  P2 --> Systems
  P3 --> Systems
  P4 --> Systems
  P5 --> Systems
  P6 --> Systems

Las 6 primitivas fundamentales

1. Amortización frente a garantías en el peor caso: KMP y Push-Relabel protegen los SLO estrictos de latencia p99. Horspool y HNSW priorizan un alto throughput promedio.
2. Programación dinámica y subestructura óptima: Resuelve subproblemas superpuestos una sola vez y comprime el estado (iteración hacia atrás de 0/1 Knapsack, clausura mediante vértices intermedios de Floyd-Warshall).
3. Cotas duales y relajación: Mantén invariantes de acotación (precios duales de Hungarian, alturas de Push-Relabel) para podar espacios de búsqueda sin sacrificar las demostraciones de optimalidad.
4. Heurísticas orientadas al objetivo frente a búsqueda exacta: Las heurísticas admisibles (A*) preservan la optimalidad exacta mientras reducen drásticamente la exploración; las metaheurísticas (ACO) intercambian demostraciones por viabilidad en espacios de problemas NP-hard.
5. Sketches probabilísticos frente a almacenamiento exacto: Intercambia un error acotado insignificante por ahorros de memoria de varios órdenes de magnitud (HyperLogLog, hashes rodantes).
6. Ajuste automático en línea y ciclos de retroalimentación: Estructura los sistemas para que se adapten automáticamente al tráfico de producción no estacionario (caché ARC, decaimiento de feromonas de ACO).

Matriz de selección rápida de algoritmos

Fuentes

Emparejamiento y asignación

• Gale, D., & Shapley, L. S. (1962). College Admissions and the Stability of Marriage. American Mathematical Monthly, 69(1), 9–15.
• Kuhn, H. W. (1955). The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly, 2(1–2), 83–97.
• Munkres, J. (1957). Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics, 5(1), 32–38.

Algoritmos de cadenas y búsqueda

• Karp, R. M., & Rabin, M. O. (1987). Efficient Randomized Pattern-Matching Algorithms. IBM Journal of Research and Development, 31(2), 249–260.
• Knuth, D. E., Morris, J. H., & Pratt, V. R. (1977). Fast Pattern Matching in Strings. SIAM Journal on Computing, 6(2), 323–350.
• Horspool, R. N. (1980). Practical Fast Searching in Strings. Software: Practice and Experience, 10(6), 501–506.

Algoritmos de optimización y grafos

• Bellman, R. (1957). Dynamic Programming. Princeton University Press.
• Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 26(1), 29–41.
• Floyd, R. W. (1962). Algorithm 97: Shortest Path. Communications of the ACM, 5(6), 345.
• Goldberg, A. V., & Tarjan, R. E. (1988). A New Approach to the Maximum-Flow Problem. Journal of the ACM, 35(4), 921–940.
• Bron, C., & Kerbosch, J. (1973). Algorithm 457: Finding All Cliques of an Undirected Graph. Communications of the ACM, 16(9), 575–577.
• Hart, P. E., Nilsson, N. J., & 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.

Sistemas, sketches y búsqueda vectorial

• Megiddo, N., & Modha, D. S. (2003). ARC: A Self-Tuning, Low Overhead Replacement Cache. Proceedings of the 2nd USENIX Conference on File and Storage Technologies (FAST ‘03).
• Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007). HyperLogLog: The Analysis of a Near-Optimal Cardinality Estimation Algorithm. AOFA ‘07.
• Malkov, Y. A., & Yashunin, D. A. (2018). Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4), 824–836.