Domina TSP en entrevista con una respuesta clara: definición, NP-hardness, Held-Karp y heurísticas. Aprende qué decir y por qué hacerlo bien.
La mayoría de los candidatos que tienen dificultades con el desempeño en entrevistas sobre el travelling salesperson problem no las tienen porque no sepan qué es TSP. Las tienen porque lo conocen demasiado bien: han leído la página de Wikipedia, han visto la tabla de DP y, cuando aparece la pregunta en una entrevista, empiezan a hablar de bitmask state spaces antes de haber dicho qué problema están resolviendo realmente. El entrevistador pierde el hilo. El candidato pierde el control de la situación.
Este artículo le da la respuesta en el orden que funciona: primero la definición en lenguaje sencillo, luego la elección entre exacto y aproximado, después el recorrido de Held-Karp, y por último las preguntas de seguimiento. Ensaye esa secuencia una vez y la espiral de pánico se detiene.
Diga qué es realmente TSP antes de decir nada ingenioso
Qué significa TSP en lenguaje sencillo
El travelling salesperson problem es esto: dada una lista de ciudades y las distancias entre ellas, encuentre la ruta más corta posible que visite cada ciudad exactamente una vez y regrese al punto de partida. Eso es todo. Una sola frase. Debe poder decirlo en menos de diez segundos sin mirar una pizarra.
La razón por la que los candidatos no lo dicen con tanta claridad es que han interiorizado TSP como un concepto de teoría de grafos en lugar de como un enunciado de problema. Cuando lo interioriza como concepto, recurre a la maquinaria —NP-hardness, programación dinámica, bitmask DP— antes de haber dicho al entrevistador qué está optimizando. Eso está al revés. La definición no es una formalidad que se supera de camino a la respuesta real. Es la base sobre la que se apoya el resto de su respuesta.
Según el tratamiento formal en Introduction to Algorithms (Cormen et al.), TSP se clasifica como NP-hard, lo que significa que no se conoce ningún algoritmo de tiempo polinómico que encuentre la solución óptima para todas las entradas. Esa clasificación importa, pero viene después de la definición, no antes.
Por qué los entrevistadores lo preguntan
La entrevista sobre el travelling salesperson problem no es una prueba de memoria. Los entrevistadores que preguntan TSP buscan algo más específico: ¿puede esta persona traducir un problema de optimización difícil en supuestos claros antes de empezar a resolverlo? ¿Puede tomar una decisión deliberada entre exactitud y practicidad según las restricciones, en lugar de recurrir por defecto al algoritmo que suena más impresionante?
En sesiones de coaching, el modo de fallo más común que he visto es que los candidatos saltan directamente a la programación dinámica antes de haber dicho qué resuelve esa DP. Dicen: “así que usamos bitmask DP sobre subconjuntos de ciudades visitadas” y el entrevistador asiente con cortesía, luego pregunta “¿pero cuál es el problema exacto?” —y el candidato de repente está explicando la definición desde dentro de la solución, lo cual es mucho más difícil. La definición debe ir primero, dicha con calma, como si se la hubiera explicado a un colega durante el almuerzo. Todo lo que viene después resulta más limpio.
Dé la respuesta de 60 segundos sobre TSP que realmente puede decir en voz alta
El guion memorizado que suena natural
Una respuesta sólida de entrevista sobre TSP tiene cuatro movimientos, en ese orden. No necesita más de 90 segundos para los cuatro.
Primero, defina el problema: “TSP es el problema de encontrar la ruta más corta que visita cada nodo exactamente una vez y regresa al origen.” Una frase.
Segundo, nombre la parte difícil: “La dificultad es que el número de rutas posibles crece factorialmente con el número de ciudades, así que la búsqueda por fuerza bruta deja de ser viable muy rápido.”
Tercero, elija su solución según las restricciones: “Para entradas pequeñas —digamos, menos de 20 ciudades— podemos usar programación dinámica exacta con Held-Karp, que ejecuta en O(n² 2ⁿ) de tiempo. Para entradas más grandes, usaríamos una aproximación o una heurística —greedy nearest-neighbor, o Christofides’ algorithm si necesitamos una cota demostrable.”
Cuarto, invite al seguimiento: “¿Quiere que profundice en el enfoque de DP, o le resultaría más útil que explique la parte heurística?”
Ese último movimiento es el que más candidatos omiten. Señala que entiende que hay dos caminos válidos y que no va a obligar al entrevistador a soportar el que no necesita. Según investigaciones sobre desempeño en entrevistas técnicas publicadas por Harvard Business Review, la comunicación estructurada y el planteamiento explícito de compensaciones están entre las señales más fuertes que usan los responsables de contratación para distinguir a un candidato senior de uno de nivel medio.
Cómo se ve esto en la práctica
Imagine que está en la pizarra. El entrevistador dice: “Hábleme del travelling salesperson problem”. Un error común al responder TSP es dibujar de inmediato un grafo con cinco nodos y empezar a etiquetar aristas. No lo haga. Diga primero la definición en voz alta y luego dibuje el grafo. El grafo debe ilustrar la definición, no reemplazarla.
En la práctica, los candidatos que ensayan un guion de cuatro movimientos suenan mucho menos ensayados que los que improvisan, porque la estructura elimina la carga cognitiva de decidir qué decir después. Un candidato al que entrené tenía una sólida comprensión conceptual de TSP, pero se desviaba durante tres o cuatro encuadres distintos antes de decidirse por uno. Después de practicar el guion de cuatro movimientos dos veces, la respuesta quedó tan precisa que el entrevistador pasó directamente a las preguntas de seguimiento —que es exactamente lo que usted quiere, porque las preguntas de seguimiento son donde demuestra profundidad.
Elija entre DP exacta y una heurística en lugar de fingir que existe una sola respuesta correcta
Cuándo la programación dinámica exacta es la opción adecuada
Held-Karp es la respuesta correcta cuando el entrevistador indica que quiere rigor, cuando el tamaño de entrada es pequeño o cuando el problema se plantea como un ejercicio de clase. El método es exacto —encuentra la ruta óptima— y es el enfoque DP estándar para TSP en entornos académicos y de entrevista. El estado codifica qué ciudades han sido visitadas y en qué ciudad termina actualmente la ruta, y la transición va construyendo subrutas óptimas hasta reconstruir la ruta completa.
La limitación estructural es clara: Held-Karp ejecuta en O(n² 2ⁿ) de tiempo y O(n 2ⁿ) de espacio. En n = 20, eso son unos 20 millones de estados, que es manejable. En n = 30, son más de mil millones. La exactitud es útil hasta que el espacio de estados deja de ser práctico, y la respuesta honesta nombra ese límite en lugar de fingir que DP escala para siempre.
Cuándo una heurística es la respuesta más inteligente
Las heurísticas no son respuestas de segunda categoría. Para la aproximación de problemas TSP en entornos del mundo real, a menudo son la única respuesta honesta. Greedy nearest-neighbor es rápido y simple: empiece en una ciudad, muévase siempre a la ciudad no visitada más cercana, regrese al inicio. No garantiza optimalidad, pero ejecuta en O(n²) y produce rutas que a menudo están dentro de un 20–25% de la óptima.
Christofides' algorithm es la opción más fundamentada: garantiza una ruta que no será peor que 1.5× la óptima para metric TSP (donde las distancias satisfacen la desigualdad triangular). Para muchos sistemas de producción, una cota de 1.5× con tiempo de ejecución polinómico es mucho más valiosa que una respuesta exacta que tarda tiempo exponencial en calcularse.
Cómo se ve esto en la práctica
Considere dos escenarios. En el primero, está en una entrevista y el problema se presenta como “doce ciudades, encuentre el recorrido óptimo”. Held-Karp es la respuesta correcta. La entrada es pequeña, el entrevistador quiere ver la estructura de DP y la exactitud es alcanzable.
En el segundo escenario, el problema es “12.000 paradas de entrega, optimice la ruta para una flota de mensajería del mismo día”. Nadie ejecuta Held-Karp sobre 12.000 nodos. La respuesta es una heurística o una metaheurística —simulated annealing, genetic algorithms o un solver comercial. El enrutamiento de placas de circuito y los sistemas de vehicle routing usados en logística, por ejemplo, han dependido de algoritmos de aproximación desde los años setenta precisamente porque los tamaños de entrada hacen que la optimalidad total sea una trampa. El NIST Dictionary of Algorithms and Data Structures documenta el comportamiento de escalado de los algoritmos exactos de TSP y explica por qué los métodos de aproximación dominan en la práctica.
El candidato que puede nombrar esta transición —de exacta a aproximada, y por qué— es el que suena como alguien que ha pensado en el problema más allá del aula.
Explique Held Karp como si estuviera en una pizarra
El estado, la transición y la parte incómoda
La explicación de entrevista del algoritmo Held-Karp funciona mejor cuando la ancla en la definición del estado antes de escribir cualquier transición. El estado es `dp[S][i]`, donde `S` es una bitmask que representa el conjunto de ciudades visitadas hasta ahora, e `i` es la ciudad donde termina la ruta actual. El valor almacenado es el costo mínimo para visitar exactamente las ciudades de `S`, terminando en la ciudad `i`, empezando desde un origen fijo.
La transición es: para extender la ruta a una nueva ciudad `j` que aún no está en `S`, calcule `dp[S | (1 << j)][j] = min(dp[S][i] + dist[i][j])` sobre todos los `i` válidos. Usted se pregunta: ¿cuál es la forma más barata de llegar a la ciudad `j` después de haber visitado exactamente las ciudades de `S`, dado que acabamos de venir de la ciudad `i`?
La parte que la gente suele olvidar —y la que los entrevistadores notan cuando falta— es el paso final: completar el recorrido. Después de llenar la tabla de DP, la respuesta es `min over all i of (dp[(1<<n)-1][i] + dist[i][0])`, que cierra el ciclo de vuelta al origen. Sin ese paso, ha resuelto el Hamiltonian path problem, no TSP.
Cómo se ve esto en la práctica
Tome cuatro ciudades: 0, 1, 2, 3. Empiece en la ciudad 0.
- `dp[{0}][0] = 0` (en el origen, el costo es cero)
- `dp[{0,1}][1] = dist[0][1]` (viajó de 0 a 1)
- `dp[{0,2}][2] = dist[0][2]` (viajó de 0 a 2)
- `dp[{0,1,2}][2] = min(dp[{0,1}][1] + dist[1][2], dp[{0,2}][2] + dist[2][2])` —pero `dist[2][2] = 0` no ayuda, así que tomamos la primera: el costo de llegar a la ciudad 1 y luego moverse a 2.
Dibujar esta tabla en una pizarra —incluso esbozar dos o tres filas— le muestra al entrevistador que entiende cómo la DP construye rutas de manera incremental, en lugar de limitarse a conocer la fórmula.
Complejidad sin evasivas
Held-Karp ejecuta en O(n² 2ⁿ) de tiempo y O(n 2ⁿ) de espacio. La razón por la que se vuelve costoso tan rápido es que el número de subconjuntos de n ciudades es 2ⁿ, y para cada subconjunto se siguen n posibles ciudades finales, lo que da n · 2ⁿ estados. Completar cada estado requiere revisar hasta n transiciones, de ahí el tiempo n² · 2ⁿ. Según el tratamiento canónico en el artículo original de Bellman de 1962 y la formulación posterior de Held-Karp, este es el mejor algoritmo exacto conocido para TSP en términos de complejidad asintótica.
Saber la complejidad importa menos que poder explicar por qué se encarece. “Tenemos exponencialmente muchos subconjuntos y para cada uno estamos rastreando dónde estamos” es una frase que un entrevistador recuerda. “O(n² 2ⁿ)” sin esa explicación es solo una fórmula.
Explique NP hardness como un ingeniero competente, no como una clase magistral
Por qué TSP es difícil desde el principio
NP-hardness, en lenguaje sencillo, significa que no se conoce ningún algoritmo que siempre encuentre la ruta óptima en tiempo polinómico a medida que crece el número de ciudades. No significa que el problema sea irresoluble. Significa que los mejores métodos exactos conocidos escalan exponencialmente y, para entradas grandes, ese crecimiento exponencial los vuelve impracticables. La entrada de la Stanford Encyclopedia of Philosophy sobre computational complexity distingue claramente NP-hard de NP-complete: TSP (versión de decisión) es NP-complete; la versión de optimización es NP-hard.
La consecuencia es lo que importa para el desempeño en entrevistas sobre travelling salesperson problem: no puede hacer brute force de TSP a escala, y no puede resolverlo exactamente en tiempo polinómico con ningún método conocido. Esa es la razón por la que existe la elección de algoritmo.
Cómo decirlo sin sobreexplicar
Una explicación útil en una sola línea: “TSP es NP-hard, lo que significa que los mejores algoritmos exactos conocidos escalan exponencialmente con el número de ciudades, así que para entradas grandes usamos aproximaciones en su lugar.” Eso es todo. No necesita esbozar una reducción desde 3-SAT. No necesita explicar el teorema de Cook-Levin.
La distinción entre “difícil” e “imposible” importa. Los candidatos que dicen “TSP es irresoluble” pierden puntos, no porque el entrevistador sea quisquilloso, sino porque eso señala imprecisión. TSP sí se puede resolver para entradas pequeñas. Held-Karp lo resuelve exactamente para n de hasta aproximadamente 20. “Difícil” significa “no se conoce un algoritmo exacto de tiempo polinómico”, no “nos rendimos”.
Cómo se ve esto en la práctica
Cuando el entrevistador pregunta “¿por qué no fuerza bruta?”, la respuesta conecta el crecimiento factorial con el punto de quiebre práctico: “La fuerza bruta comprueba todas las permutaciones (n-1)!. Con 10 ciudades son 362.880 rutas —manejable. Con 20 ciudades son más de 60 billones. Esa es la razón por la que la búsqueda exacta se desmorona y por la que necesitamos DP o aproximaciones.”
Esa respuesta tiene tres frases. Es precisa, no es dramática y le da al entrevistador exactamente la información que estaba buscando.
Separe TSP de los problemas con los que la gente sigue confundiéndolo
TSP vs shortest path vs traveling postman problem
TSP vs shortest path es una distinción que hace tropezar a más candidatos de lo que debería. Shortest path —Dijkstra’s algorithm, Bellman-Ford— encuentra la ruta de costo mínimo entre dos nodos específicos. TSP encuentra la ruta de costo mínimo que visita todos los nodos exactamente una vez y regresa al inicio. El objetivo es completamente distinto: uno es punto a punto, el otro es un recorrido completo.
El traveling postman problem (también llamado Chinese postman problem) es diferente otra vez: pide la ruta de costo mínimo que recorre cada arista al menos una vez, no cada nodo. Piense en un cartero que necesita caminar por todas las calles, frente a un vendedor que necesita visitar a cada cliente una vez. Mismo grafo, objetivo completamente diferente.
Por qué importan la desigualdad triangular y la asimetría
Metric TSP añade la restricción de que las distancias satisfacen la desigualdad triangular: la distancia directa entre dos ciudades nunca es mayor que la distancia pasando por una tercera ciudad. Esta restricción es lo que hace posible la garantía de aproximación de 1.5× de Christofides' algorithm. Sin ella, no se conoce ninguna aproximación de factor constante a menos que P = NP.
Asymmetric TSP elimina la suposición de que la distancia de la ciudad A a la ciudad B sea igual a la de B a A. Las carreteras de un solo sentido, las rutas aéreas dirigidas y los costos dependientes del tiempo crean instancias asimétricas. El problema es estrictamente más difícil: muchos resultados de aproximación que valen para TSP simétrico no se trasladan.
Cómo se ve esto en la práctica
Considere un grafo de ciudad en el que la carretera A→B toma 10 minutos, pero B→A toma 25 minutos debido a calles de sentido único. Eso es asymmetric TSP. Ahora considere un grafo en el que se cumple la desigualdad triangular —cada atajo es al menos tan bueno como pasar por una ciudad intermedia—. Eso es metric TSP, y ahí Christofides aplica. Saber qué versión está viendo cambia tanto la elección del algoritmo como las garantías de aproximación que puede afirmar.
Responda las preguntas de seguimiento sin dejarse atrapar por el formato
Los supuestos que los entrevistadores quieren que diga en voz alta
Antes de comprometerse con un algoritmo, pregúntese: ¿el grafo es completo? ¿Se conocen todas las distancias por pares? ¿Las distancias son simétricas? ¿Existe una restricción de tiempo que haga aceptable una respuesta aproximada? Estas no son tácticas para ganar tiempo: son las preguntas que separan a un candidato que conoce un algoritmo de TSP de un candidato que entiende el espacio del problema.
Los entrevistadores usan preguntas de seguimiento para comprobar si usted está respondiendo al problema que tiene delante o al problema que estudió. Un candidato que pregunta “¿esto es metric TSP o asymmetric?” antes de elegir un algoritmo está demostrando exactamente el tipo de planteamiento de supuestos que distingue el pensamiento senior del de nivel medio.
Los errores que hacen que una buena respuesta suene débil
El modo de fallo más común: un candidato memoriza “NP-hard” y “programación dinámica”, pero no puede relacionarlos con las restricciones del enunciado. Dice “TSP es NP-hard, así que usamos DP” como si eso fuera una frase completa. No lo es. La NP-hardness explica por qué falla la fuerza bruta. La DP es una respuesta a eso, válida para n pequeño. La conexión entre ambas requiere nombrar la restricción —el tamaño de entrada— que determina qué respuesta es apropiada.
La razón estructural por la que esto perjudica a los candidatos es que suena a que memorizó la respuesta a otra pregunta. El entrevistador preguntó por un problema específico con restricciones específicas; el candidato respondió la versión abstracta. Esa brecha es visible, y los entrevistadores con experiencia la notan de inmediato.
Cómo se ve esto en la práctica
Una buena secuencia de seguimiento se ve así. Entrevistador: “¿Cómo escala esto?” Candidato: “Held-Karp es O(n² 2ⁿ), así que es manejable para n pequeño —digamos, hasta 20 ciudades—, pero se rompe rápidamente más allá de eso.” Entrevistador: “¿Qué haría con una entrada mayor?” Candidato: “Pasaría a una heurística —greedy nearest-neighbor por velocidad, o Christofides si necesito una cota de aproximación demostrable.” Entrevistador: “¿Cuál es la complejidad de Christofides?” Candidato: “O(n³) para los pasos del minimum spanning tree y del matching, en general polinómico, con una garantía de optimalidad de 1.5× para metric TSP.”
El candidato no vuelve a la definición después de cada seguimiento. Permanece dentro del problema y avanza por las capas. Así es como se ve una respuesta sólida sobre TSP bajo presión.
Preguntas frecuentes
P: ¿Cómo explica el travelling salesperson problem en lenguaje sencillo en una entrevista?
Dígalo en una frase: encontrar la ruta más corta que visita cada ciudad exactamente una vez y regresa al inicio. No recurra al vocabulario de teoría de grafos hasta haber dicho esa frase con claridad. La definición es la base: todo lo demás depende de que quede clara primero.
P: ¿Qué hace que TSP sea difícil y cómo debería describir NP-hardness sin sonar pedante?
NP-hardness significa que no se conoce ningún algoritmo que resuelva TSP de forma óptima en tiempo polinómico a medida que crece la entrada. La consecuencia práctica es que la fuerza bruta comprueba (n-1)! rutas —manejable con 10 ciudades, catastrófico con 20. Diga esa consecuencia en voz alta en lugar de recitar la clasificación teórica. “Difícil” significa escalado exponencial, no “imposible”.
P: ¿Cuándo debería mencionar programación dinámica frente a una heurística o aproximación?
Use Held-Karp DP cuando la entrada es pequeña (aproximadamente n ≤ 20) y el entrevistador quiere la respuesta óptima exacta. Use una heurística o una aproximación cuando la entrada es grande, los límites de tiempo son reales o el entrevistador pregunta qué haría en producción. Nombrar el umbral —no solo el algoritmo— es lo que hace que la respuesta sea sólida.
P: ¿Cómo guía a un entrevistador a través del estado, la transición y la complejidad de Held-Karp?
Defina el estado como `dp[S][i]`: costo mínimo para visitar exactamente las ciudades en la bitmask S, terminando en la ciudad i. La transición amplía la ruta a una ciudad j no visitada. La respuesta final cierra el ciclo de regreso al origen. La complejidad es O(n² 2ⁿ) de tiempo y O(n 2ⁿ) de espacio. Explique siempre por qué escala así —exponencialmente muchos subconjuntos, n posibles extremos— y no solo cuál es la fórmula.
P: ¿Qué compensaciones buscan los entrevistadores cuando preguntan sobre TSP?
Quieren ver si usted pondera exactitud frente a escalabilidad, elige un algoritmo según las restricciones declaradas en lugar de por costumbre y reconoce lo que está sacrificando. Elegir Held-Karp sin señalar su costo exponencial, o elegir una heurística sin indicar que es aproximada, ambas cosas sugieren que no ha pensado bien la compensación. La compensación es la respuesta.
P: ¿En qué se diferencia TSP de un problema de shortest path o del traveling postman problem?
Shortest path encuentra la ruta más barata entre dos nodos específicos. TSP encuentra el recorrido completo más barato por todos los nodos. El traveling postman problem cubre cada arista al menos una vez: piense en un cartero cubriendo cada calle, frente a un vendedor visitando a cada cliente. Misma estructura de grafo, objetivo completamente diferente.
P: ¿Cuáles son los errores más comunes que cometen los candidatos al hablar de TSP?
Tres errores dominan: saltar al algoritmo antes de definir el problema, decir “NP-hard” sin relacionarlo con por qué falla la fuerza bruta y responder a la versión abstracta de TSP en lugar de la versión restringida del enunciado. El cuarto, menos obvio: decir que TSP es “irresoluble” en lugar de “difícil”, lo que señala imprecisión a cualquiera que conozca el problema.
P: ¿Cómo puede un reclutador usar esta pregunta para evaluar capacidad de resolución de problemas y comunicación?
TSP es una señal clara para varias dimensiones a la vez: si el candidato define antes de resolver, si nombra los supuestos antes de elegir un algoritmo, si puede explicar las consecuencias de la complejidad en lugar de solo recitarlas y si se mantiene firme bajo la presión de las preguntas de seguimiento. Un candidato que entrega una respuesta estructurada —definición, parte difícil, elección de algoritmo, complejidad— y luego responde seguimientos sin reiniciarse está demostrando exactamente el tipo de pensamiento que se transfiere a problemas de ingeniería reales.
Cómo Verve AI puede ayudarle a prepararse para su entrevista sobre el travelling salesperson problem
El problema estructural de prepararse para TSP es que conocer el algoritmo y ser capaz de explicarlo con claridad bajo presión en vivo son dos habilidades distintas. La mayoría de los candidatos tiene el conocimiento. Lo que se rompe en la entrevista es la secuencia: definición antes que algoritmo, comprobación de restricciones antes que elección de solución, explicación de complejidad antes de que el entrevistador tenga que preguntar, y esa secuencia solo se vuelve fiable mediante repetición con retroalimentación real.
Verve AI Interview Copilot está diseñado precisamente para ese vacío. Escucha en tiempo real su respuesta mientras la da, no un resumen escrito después, y responde a lo que usted realmente dijo, incluidas las partes que pasó por alto o el seguimiento que no anticipó. Si explicó Held-Karp pero omitió el paso final de completar el recorrido, Verve AI Interview Copilot lo detecta. Si dijo “NP-hard” sin conectarlo con el crecimiento factorial, señala la brecha. La retroalimentación es específica para su respuesta, no para una rúbrica genérica de TSP. Verve AI Interview Copilot realiza entrevistas simuladas que reproducen la presión de seguimiento de una criba técnica real —el “¿por qué no fuerza bruta?”, el “¿qué haría a escala?”, el “¿cuál es la complejidad?”— para que la secuencia se vuelva automática en lugar de exigente.
Conclusión
TSP da menos miedo cuando se responde en el orden correcto. Primero la definición, segundo la parte difícil, tercero la elección del algoritmo, cuarto la complejidad. Esa secuencia elimina la espiral porque cada paso tiene un siguiente movimiento claro, y el entrevistador puede seguirle durante todo el camino.
Ensaye el guion de 60 segundos una vez —en voz alta, no en su cabeza—. Después recorra la explicación de Held-Karp una vez con un ejemplo de cuatro ciudades. Esas dos pasadas suelen ser suficientes para detener el pánico y convertir una pregunta que parecía una trampa en una oportunidad para mostrar pensamiento estructurado.
Casey Rivera
Contenido