Suponiendo que el problema hamiltoniano es NPC, demuestre que: TSP (problema del viajante) es un problema NP-difícil (Métodos computacionales de optimización modernos, editor en jefe Xing Wenxun, P50 pregunta 11)

En primer lugar, HC es un problema de NPC y un problema de búsqueda. Supongamos que utilizando el algoritmo de estrategia codiciosa A(·) se puede resolver HC y obtener un ciclo hamiltoniano.

Utilice el gráfico no dirigido G para construir el gráfico G' de tsp. Los pesos de los bordes que existen en el gráfico G se establecen en 1 y los pesos de los bordes que no existen en el gráfico G se establecen en ).

Un problema TSP obtenido de esta forma se puede resolver utilizando el algoritmo A(·).

Condiciones de reducción de Turing: (1) El problema 1 y el problema 2 son ambos problemas de búsqueda

(2) El algoritmo A (·) que resuelve el problema 1 puede resolver el problema 2

; p>

(3) La complejidad temporal del Algoritmo A (Problema 1) es tiempo polinómico, entonces el Algoritmo A (Problema 2) también es tiempo polinómico

Por lo tanto, HC se puede reducir a tal nivel; Ejemplos de problemas de TSP.

Y debido a que HC es un problema de NPC y Turing puede reducirlo a TSP, TSP es un problema de NP difícil