💻 computer science

Connected by Construction: Learning Tractable Near-Tour Marginals for Traveling Salesman Problems

El artículo propone C2TSP, un flujo de trabajo de aprendizaje no supervisado de extremo a extremo que aprende directamente estructuras hamiltonianas interpretables para el Problema del Viajante mediante una familia de Gibbs de 1-árbol con raíz conectada por construcción, logrando un sólido rendimiento de las rutas mientras preserva la información estructural a través de perturbaciones de aristas residuales y un refinamiento guiado por certificados.

Autores originales: Ke Sun, Xinyuan Zhang, Xinwu Qian

Publicado 2026-07-15

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Ke Sun, Xinyuan Zhang, Xinwu Qian

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando resolver el rompecabezas definitivo de rutas de entrega: el Problema del Viajante (TSP, por sus siglas en inglés). Tienes una lista de ciudades y necesitas encontrar la ruta más corta que visite cada una de ellas exactamente una vez y regrese al punto de origen. Es un acertijo clásico que se vuelve increíblemente difícil a medida que añades más ciudades.

Durante mucho tiempo, los científicos de la computación han intentado enseñar a las máquinas a resolver esto usando métodos basados en el "aprendizaje". Piensa en estos métodos como un estudiante al que se le da un mapa y se le pide que adivine la mejor ruta. Pero aquí está el truco: la mayoría de estos estudiantes en realidad están adivinando un "mapa de calor" (una imagen borrosa que muestra qué caminos podrían ser buenos) o una lista de "reglas de construcción" (cómo construir la ruta paso a paso). No sostienen el bucle terminado y conectado en sus manos hasta el final, cuando intentan decodificar su suposición en una ruta real. Es como intentar hornear un pastel adivinando solo los ingredientes y esperando que el horno mágicamente los convierta en un pastel perfecto al final.

Los autores de este artículo, Ke Sun, Xinyuan Zhang y Xinwu Qian, dicen: "Un momento. Si no sabemos cómo se ve el pastel antes de que entre al horno, ¿cómo sabemos si estamos aprendiendo lo correcto?".

La Gran Idea: Construir un Esqueleto Conectado Primero

En lugar de adivinar un mapa de calor borroso, los autores proponen una nueva forma de aprender llamada C2TSP. Su ingrediente secreto es un concepto que llaman "conectado por construcción".

Imagina que estás construyendo un modelo de la red de carreteras de una ciudad. La mayoría de los métodos intentan dibujar líneas en un papel y esperan que se conecten más tarde. C2TSP comienza construyendo un esqueleto específico y robusto llamado árbol-1 enraizado.

El Esqueleto: Imagina un centro neurálgico (la ciudad "raíz") conectado a dos carreteras. Luego, imagina un árbol de caminos que conecta todas las demás ciudades con ese centro.
La Magia: Al construirlo de esta manera, se garantiza que esté conectado. No puedes dibujar accidentalmente una carretera que no lleve a ninguna parte o dividir la ciudad en dos islas. Es como construir una casa con un cimiento que asegura que las paredes siempre toquen el techo.

Lo único que le falta a este esqueleto para convertirse en un recorrido perfecto (un ciclo hamiltoniano) es que cada ciudad necesita exactamente dos carreteras conectadas a ella (una de entrada, una de salida). En el árbol-1, el centro tiene dos carreteras, pero las otras ciudades podrían tener tres o solo una.

La Solución: Una Capa de "Equilibrio"

Para arreglar el exceso o la falta de carreteras, el equipo utiliza un trucción ingeniosa que llaman capa de equilibrado suavizada de Held–Karp.

Piensa en esto como un controlador de tráfico muy inteligente. El modelo observa el esqueleto del árbol-1 y pregunta: "Oye, la Ciudad A tiene tres carreteras, pero solo necesita dos. La Ciudad B tiene una, pero necesita dos". El controlador no solo borra carreteras; ajusta los "precios" de las carreteras. Hace que las carreteras sobrantes sean caras y las que faltan sean baratas, empujando al sistema hasta que, en promedio, cada ciudad tenga exactamente dos carreteras.

Esto es algo muy importante porque, a diferencia de otros métodos que intentan adivinar toda la ruta a la vez, este método calcula la probabilidad exacta de que cada carretera sea parte de la solución mientras mantiene la estructura conectada. Demostraron matemáticamente que pueden realizar este cálculo perfectamente, algo que antes se consideraba imposible para el problema del recorrido completo.

El "Certificado": Una Red de Seguridad

Incluso después del equilibrio, todavía puede quedar un poco de "desorden" restante. El esqueleto está conectado y equilibrado en promedio, pero puede que aún no sea un bucle perfecto.

Los autores introducen un certificado, que es como una red de seguridad o una etiqueta de advertencia. Mide exactamente cuánto "desorden" (o masa de no-recorrido) queda en el sistema. Es una garantía matemática que dice: "Sabemos que la estructura está un 99% lista, y aquí está el número exacto para el 1% restante".

Usando este certificado, aplican un paso final llamado perfeccionamiento (sharpening). Imagina que tienes una foto ligeramente borrosa de una ruta. El paso de perfeccionamiento hace que las buenas carreteras se vean súper brillantes y las malas se vean oscuras, empujando al modelo hacia un bucle perfecto y nítido.

Lo Que Encontraron

El equipo probó su método con acertijos de 50, 100, 200, 500 e incluso 1,000 ciudades. Aquí está lo que muestran los números:

Decodificación Pura: Cuando dejaron que el modelo simplemente eligiera la mejor ruta sin ayuda adicional (como la intervención de un humano), C2TSP fue increíblemente fuerte. En un acertijo de 100 ciudades, encontró una ruta con una brecha de optimalidad de solo un 1.90% tras 100 rondas de búsqueda local, y un 4.83% con solo una simple suposición de "elegir la mejor".
Comparación: Otros métodos populares, como DIFUSCO o Fast-T2T, a menudo tuvieron dificultades cuando los acertijos se hacían grandes (500+ ciudades) a menos que utilizaran mucho tiempo de búsqueda adicional. C2TSP se mantuvo constante.
La Prueba de "Ablación": Para demostrar que sus ideas funcionaban, quitaron partes de su sistema.
- Sin la perturbación de bordes (la parte que aprende a ajustar los precios de las carreteras), el error saltó del 1.55% al 12.74%.
- Sin el perfeccionamiento, el modelo aprendió una estructura conectada pero no se acercó tanto al bucle perfecto.
- Esto demuestra que tanto el aprendizaje de los precios de las carreteras como el paso final de perfeccionamiento son necesarios para obtener los mejores resultados.

Lo Que No Reclaman

Es importante notar lo que este artículo no dice. No afirman haber resuelto el Problema del Viajante de una vez por todas. Declaran explícitamente que su método depende de un "sustituto tratable": una aproximación inteligente. El árbol-1 enraizado es un sustituto del recorrido perfecto. Aunque se acerca mucho, el artículo admite que el "desorden de grados" restante (las pequeñas imperfecciones donde una ciudad podría tener 3 carreteras en lugar de 2) se controla y se reduce, pero no siempre se elimina exactamente.

También señalan que para acertijos muy grandes (como 1,000 ciudades), otros métodos que utilizan mucha búsqueda local (como DIMES) aún pueden funcionar bien, pero C2TSP destaca cuando quieres un punto de partida que ya sea estructuralmente sólido.

La Conclusión

En términos sencillos, C2TSP es como enseñarle a un robot a construir un recorrido obligándolo primero a construir un esqueleto conectado, luego enseñándole a equilibrar las carreteras y, finalmente, dándole un certificado para que revise su trabajo. En lugar de adivinar una imagen borrosa y esperar que se convierta en una ruta, el robot aprende la forma de la ruta misma. Los resultados sugieren que este enfoque de "conectado por construcción" hace que el proceso de aprendizaje sea más estable y que las rutas finales sean mucho mejores, especialmente cuando los acertijos se vuelven grandes y complicados.

Resumen Técnico: Connected by Construction (C2TSP)

Definición del Problema

El artículo aborda el Problema del Viajante (TSP), un problema de optimización combinatoria canónico que requiere una solución que satisfaga dos restricciones estructurales: restricciones de grado local (cada nodo debe tener grado dos) y conectividad global (los bordes seleccionados deben formar un único ciclo hamiltoniano).

Los métodos actuales basados en aprendizaje para el TSP suelen fallar al intentar representar esta estructura conectada global directamente dentro del objeto aprendido. En su lugar, dependen de:

Construcción autorregresiva: Generación secuencial de recorridos mediante enmascaramiento procedimental.
Enfoques basados en mapas de calor: Predicción de puntuaciones de bordes y dependencia de procesos posteriores de reparación, muestreo o búsqueda para obtener un recorrido válido.
Relajaciones en el espacio de asignación: Modelado de objetos suaves de tipo permutación que no capturan directamente la estructura de adyacencia de bordes que determina el costo del recorrido.

Estos enfoques sufren de dos limitaciones primarias: no proporcionan una distribución global tratable sobre objetos combinatorios conectados, y su rendimiento está estrechamente ligado a los procesos de decodificación o búsqueda posteriores, lo que dificulta separar la calidad de la representación aprendida de los efectos del post-procesamiento.

Metodología: C2TSP

Los autores proponen C2TSP (Connected by Construction), un flujo de trabajo de aprendizaje no supervisado de extremo a extremo que aprende el TSP a través de un objeto latente estructuralmente significativo: el 1-árbol enraizado.

1. El sustituto del 1-árbol enraizado

En lugar de intentar aprender un ciclo hamiltoniano directamente (el cual posee una función de partición intratable), el modelo opera sobre la familia de los 1-árboles enraizados.

Definición: Un 1-árbol enraizado consiste en un árbol de expansión sobre todos los nodos que no son la raíz ( $\bar{V}$ ) más exactamente dos bordes incidentes a un nodo raíz fijo ( $r$ ).
Garantía Estructural: Por construcción, cada configuración en esta familia está globalmente conectada y satisface la restricía de grado de la raíz ( $d_r = 2$ ).
Tractabilidad: A diferencia de la distribución de Gibbs del ciclo hamiltoniano, la familia de Gibbs del 1-árbol enraizado admite una factorización exacta. Esto permite el cómputo exacto de la función de partición $Z_r(\eta)$ , las marginales de los bordes $\mu(\eta)$ y los momentos de grado, permitiendo el entrenamiento del costo esperado sin necesidad de muestreo.

2. Equilibrio de Held–Karp suavizado

El defecto estructural principal de un 1-árbre enraizado es que los nodos que no son la raíz pueden no tener grado dos. Para corregir esto, los autores introducen una capa de equilibrio de Held–Karp (HK) suavizada.

Esta capa resuelve las variables duales aditivas por nodo ( $\lambda$ ) que sesgan los costos de los bordes de modo que el grado esperado de cada nodo que no es la raíz sea igual a dos bajo la distribución de Gibbs modificada.
La capa se entrena de extremo a extremo utilizando diferenciación implícita a través del mapa de equilibrio, siguiendo el paradigma de las capas de optimización implícita.
Este proceso asegura que la distribución aprendida esté equilibrada en grado en términos de expectativa, eliminando el "defecto de grado" mientras mantiene la conectividad.

3. Refinamiento guiado por certificados

Incluso después del equilibrio de HK, la distribución puede contener masa de probabilidad en estructuras que no son recorridos (1-árboles enraizados que no son ciclos hamiltonianos).

Certificado: Los autores derivan un certificado que acota esta "masa de no-recorrido" ( $\gamma(q)$ ) utilizando la varianza total de los grados de los nodos que no son la raíz: $\gamma(q) \leq \frac{1}{2} \sum \text{Var}(d_i)$ .
Refinamiento: Un paso de refinamiento guiado por certificados utiliza la derivada de un certificado de cota superior de Bernoulli para empujar la distribución marginal hacia estructuras más similares a recorridos. Esto actúa como un refinamiento determinista que penaliza los bordes de baja probabilidad y recompensa los bordes de alta probabilidad, reduciendo la cota superior certificada de la masa de no-recorrido.

4. Flujo de aprendizaje

El flujo de trabajo aprende perturbaciones residuales de bordes ( $\Gamma_\theta$ ) a partir del costo imparcial del TSP.

Paso hacia adelante (Forward Pass): Los costos brutos son perturbados, proyectados para eliminar componentes aditivos por nodo, pasados a través de la capa de equilibrio de HK y refinados mediante el refinamiento guiado por certificados.
Función de pérdida: El modelo se entrena utilizando una pérdida no supervisada basada en el costo esperado del TSP de las marginales de bordes aprendidas, sin términos de penalización explícitos para las restricciones estructurales (ya que estas son impuestas por la arquitectura).

Contribuciones Clave

Representación de 1-árbol enraizado tratable: El artículo introduce una representación que asegura la conectividad global por construcción mientras admite el cómputo exacto de las marginales para el entrenamiento.
Pipeline C2TSP: Un marco de extremo a extremo no supervisado que combina una Red Neuronal de Grafos (GNN) para la perturbación residual de bordes y una capa de Held–Karp suavizada para el equilibrio de grados.
Certificado de masa de no-recorrido: La derivación de un certificado que acota la brecha estructural residual, el cual es utilizado para guiar un mecanismo de refinamiento que empuja la distribución hacia ciclos hamiltonianos.
Validación Empírica: Demostración de que la representación del 1-árbol enraizado produce un rendimiento de decodificación pura fuerte y permanece robusta cuando se integra en solvers clásicos como LKH-3, a diferencia de varios baselines basados en mapas de calor que se degradan en escalas mayores.

Resultados Experimentales

Los autores evaluaron C2TSP en instancias de TSP euclidiano simétrico en 2-D (TSP-50 a TSP-1000) contra baselines que incluyen DIFUSCO, DIMES, Fast-T2T, UTSP y NeuroLKH.

Decodificación Pura: C2TSP logró el menor gap de optimalidad en 20 de las 25 configuraciones probadas (variando el tamaño del problema y el nivel de decodificador). Notablemente, funcionó mejor en regímenes con presupuestos pesados de búsqueda local (por ejemplo, 100 iteraciones de 2-opt), lo que sugiere que la distribución aprendida ya codifica una estructura fuerte de tipo recorrido.
Integración con LKH: Cuando se utilizó como fuente de candidatos para el solver LKH-3, C2TSP se mantuvo robusto en todos los tamaños de problema, manteniéndose dentro de aproximadamente 1 parte por diez mil (‱) del LKH-3 original. En contraste, los métodos basados en mapas de calor (DIFUSCO, Fast-T2T, UTSP) se degradaron significativamente en tamaños mayores ( $n \geq 500$ ) al integrarse con LKH.
Estudios de Ablación:
- La eliminación de la perturbación de bordes causó una caída sustancial en el rendimiento (el gap promedio aumentó de 1.55% a 12.74%), indicando la necesidad de aprender la geometría residual de los bordes.
- El refinamiento guiado por certificados mejoró aún más el rendimiento al refinar la distribución marginal, confirmando que un bajo costo relajado por sí solo es insuficiente para una decodificación de alta calidad.

Significado y Reivindicaciones

El artículo sostiene que el objeto latente diferenciable es una elección de modelado central para el aprendizaje del TSP. Al codificar la conectividad antes de la decodificación, C2TSP expone una "marginal de casi-recorrido" cuya evolución estructural puede ser entrenada, certificada y analizada.

Los autores posicionan su trabajo como un cambio desde el aprendizaje de puntuaciones de bordes sin restricciones hacia el aprendizaje de una marginal de casi-recorrido tratable con significado estructural explícito. Argumentan que este enfoque separa la representación aprendida del post-procesamiento, permitiendo que el modelo proporcione un punto de partida globalmente consistente para los procedimientos de búsqueda local.

El artículo reconoce una limitación inherente a su elección de diseño: el 1-árbol enraizado relaja el soporte exacto del ciclo hamiltoniano. Si bien la conectividad se impone y el equilibrio de grados se restaura en términos de expectativa, las fluctuaciones de grado restantes se controlan mediante equilibrio y refinamiento en lugar de eliminarse exactamente. Los autores sugieren que esto abre direcciones para actualizaciones más estrictas dirigidas por certificados y familias conectadas más ricas y tratables.