## 3.5.2 ALGORITMO DE APROXIMACIÓN PARA EL PROBLEMA DEL AGENTE VIAJERO

Dado un grafo G no dirigido con pesos c(u, v) asociados a cada arco (u, v) ∈ E, el vendedor viajero es el problema de encontrar el costo mínimo del Hamiltonian cycle. Este problema es NP-Completo. Denotemos c(A) el costo total de los arcos en el subconjunto A ∈ E. Entonces c(A) = P (u.v)∈A c(u, v). Por desigualdad triangular, se tiene que c(u, v) ≤ c(u, w) + c(w, v).

Aplicando la desigualdad triangular, se puede calcular el mínimo arbol de cobertura (Mínimo Spanning Tree - MST) cuyos pesos sean una cota inferior en el largo del tour del vendedor viajero. Se usa el arbol de cobertura mínimo para crear un tour cuyo costo es no mas que el doble del peso del MST, mientras el costo de la funcion satisfaga la desigualdad triangular.

AproxTSPTour(G) seleccione un vertice r ∈ V[G] para la raíz del vertice determine el MST T para G desde la raíz r (use MST-Prim(G) en el libro) sea L la lista de vertices visitados en un árbol en preorden de T return retorne el ciclo Hamiltoniano H que visita los vertices en el orden L.

Imagen1

Imagen2

###