¿Cómo puedo verificar una solución para el Problema del vendedor ambulante en tiempo polinómico?

Respuestas:

20

Para ser más precisos, no sabemos si TSP está en . Es posible que pueda resolverse en tiempo polinómico, aunque quizás la creencia común sea que . Ahora, recuerde lo que significa que un problema sea -hard y -complete, vea por ejemplo mi respuesta aquí . Creo que su fuente de confusión proviene de las definiciones: un difícil no está necesariamente en .PN P N P N PPPNPNPNPN PNPNP

Como usted y la página de Wikipedia que vincula, el problema de decisión es -completo: dados los costos y un número entero , decida si hay un recorrido más barato que . Una forma de ver el problema es en es ver que, dada una solución, es fácil verificar en tiempo polinómico si la solución es más barata que . ¿Cómo puedes hacer esto? Simplemente siga el recorrido dado, registre su costo total y finalmente compare el costo total con .x x N P x xNPxxNPxx

Juho
fuente
"Simplemente siga el recorrido dado, registre su costo total y finalmente compare el costo total con x". -> Sí, ¡pero hay un número exponencial de recorridos para verificar!
Lazer
2
Parecía que era un poco demasiado lento. ;-)
Niel de Beaudrap
3
@Lazer No, hay exactamente un recorrido para verificar. Te dan un recorrido y registras su duración. Si es menor que , salida , de lo contrario no . x
Juho
"decidir si hay un recorrido", esto definitivamente significa que no se nos ofrece un recorrido. ¿Qué me estoy perdiendo?
Lazer
3
@Lazer No, en el problema se le da un gráfico ponderado y un costo objetivo. El certificado es un recorrido. Para una explicación alternativa, vea la respuesta de Niel. Al igual que en el ejemplo de Wiki en el caso de SUBSET-SUM, no se nos da cero, sino que se nos da un subconjunto particular como un certificado.
Juho
34

El quid es que tienes que considerar el problema de decisión :

Problema de vendedor ambulante (versión de decisión). Dado un gráfico ponderado G y un costo objetivo C , ¿hay un ciclo hamiltoniano en G cuyo peso sea ​​como máximo C ?

Para una instancia 'sí', el certificado es sólo un ciclo de Hamilton, cuyo peso es a lo sumo C . Si pudiera resolver este problema de manera eficiente, podría encontrar el costo de un recorrido mínimo por búsqueda binaria, comenzando con el peso de toda la red como un límite superior.

Niel de Beaudrap
fuente
3

Probablemente esté pensando en el problema de determinar si una solución dada al TSP es la mejor solución. Sin embargo, no existe una solución polinómica conocida para esto, lo que significa que este problema está en NP-hard, pero no necesariamente NP-Complete.

El problema de decisión de TSP en realidad se trata de determinar si el peso de cualquier solución en un gráfico Gtiene el mayor costo C(como se explica mejor en la respuesta de Niel), lo que ciertamente es verificable en el tiempo polinómico.

Casey Kuball
fuente
55
Perdón por la pedantería, pero TSP no es NP-hard porque hay Tours. Por ejemplo, la ordenación está en P aunque hay n ! posibles permutaciones también. Los espacios de búsqueda enormes o de rápido crecimiento no siempre implican dureza. O(n!)n!
Juho
@Juho Es posible verificar que una secuencia esté ordenada, simplemente comprobando que . Sin embargo, para saber que algo es la MEJOR solución para TSP, es necesario saber que el costo es el costo mínimo, lo que inherentemente requiere conocer todos los demás costos. n0<=n1<=...
Casey Kuball
44
No, puede obtener lo óptimo incluso sin calcular la duración de todos los otros recorridos. Y sí, es posible demostrar que este es de hecho el óptimo sin calcular todos los otros recorridos. Por ejemplo, considere branch & bound.
Juho
77
Todo lo que digo es que los grandes espacios de búsqueda no necesariamente significan que el problema sea difícil. Incluso cuando, por ejemplo, no conocemos un algoritmo mejor que la fuerza bruta que enumera todas las posibilidades, no significa que sea el único algoritmo disponible. La programación dinámica es un buen ejemplo incluso aquí: el algoritmo Held-Karp es un algoritmo exacto para TSP que se ejecuta en tiempo . Lo sentimos, esto podría decirse que solo es una trampa, pero solo quería agregar un recordatorio :)O(n22n)
Juho
@Juho buen punto. He actualizado la respuesta para que ya no indique la fuerza bruta como la única opción (solo que no hay soluciones polinómicas).
Casey Kuball
2

Puede demostrar que es óptimo dado un oráculo que resuelve el problema de decisión (ver otras respuestas) en tiempo polinómico al preguntar si existe una solución más corta. Si su objetivo es construir una solución óptima dado el oráculo, proceda de la siguiente manera. Encuentre el peso total mínimo a través de la búsqueda binaria (o si hay pesos de borde no enteros, encuentre un peso total que difiera del mínimo en menos de la diferencia mínima entre dos pesos de borde). Llame a este valor . Para cada borde en el gráfico, elimine el borde y consulte el oráculo para ver si todavía hay una solución de M como máximo . Si es así, deje el borde afuera y continúe. De lo contrario, vuelva a colocar el borde y continúe. Cuando haya procesado todos los bordes, le quedará un ciclo hamiltoniano de peso mínimo.MM

RecursivamenteIronico
fuente