Ejercicio 4 · Matemática Discreta UAB Juny 2022
Tema: Optimització de rutes: carter xinès, viatjant de comerç i complexitat · Del examen Juny (2022)
Enunciado
Ejercicio 4 (1,0 puntos). Algoritmo de Christofides para el TSP
La siguiente tabla de distancias recoge los costes de las aristas de un grafo completo ponderado con vértices :
· A · B · C · D · E · F
A · 0 · 42 · 29 · 30 · 37 · 39
B · 42 · 0 · 13 · 28 · 21 · 23
C · 29 · 13 · 0 · 37 · 8 · 10
D · 30 · 28 · 37 · 0 · 42 · 27
E · 37 · 21 · 8 · 42 · 0 · 15
F · 39 · 23 · 10 · 27 · 15 · 0
Se sabe que estos pesos satisfacen la desigualdad triangular. Encuentra un ciclo hamiltoniano aplicando el algoritmo de aproximación basado en emparejamiento perfecto de peso mínimo (algoritmo de Christofides), de modo que su coste verifique , donde es el ciclo hamiltoniano óptimo. Indica asimismo cuáles son las cotas o posibles valores del coste óptimo .
Solución
Según los criterios oficiales de corrección
Encuentra un ciclo hamiltoniano H aplicando el algoritmo de aproximación basado en emparejamiento perfecto de peso mínimo (algoritmo de Christofides)
Solución: (A, D, F, C, E, B, A) / (A, B, E, C, F, D, A) / (A, C, E, B, D, F, A)
Coste del ciclo H obtenido
Solución: 138 / 152
Cota inferior del coste óptimo coste(H_0)
Solución: 87 / 92
Cota superior del coste óptimo coste(H_0)
Solución: 138 / 152
Desarrollo y justificación de los pasos
Solución: Aplicación completa del algoritmo de Christofides: árbol recubridor mínimo T (coste 87), vértices de grado impar O={A,B,D,E}, emparejamiento mínimo M={{A,D},{B,E}} (coste 51), circuito euleriano y shortcuts.
La explicación paso a paso, hecha con IA, es Premium. Premium
Resuélvelo aquí mismo: corrección automática, pistas y solución paso a paso.
‹ Pregunta 5 · 2023 · Ejercicio 5 · Juny 2022 ›