Algoritmo de Christofides (a mano)
On febrero 1, 2021 by adminEstoy siguiendo este ejemplo de algoritmo: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [ingrese la descripción de la imagen aquí] [1]] [1]
Calculate minimum spanning tree T:
[! [Ingrese la descripción de la imagen aquí] [2]] [2]
Calculate the set of vertices O with odd degree in T
Igual que «el árbol de expansión mínimo T «ya que el grado de todos los vértices es impar.
Form the subgraph of G using only the vertices of O
(como todos eran impares, esto debería darnos el gráfico original) [! [ ingrese la descripción de la imagen aquí] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( No estoy seguro si Hizo esto bien ) [! [ingrese la descripción de la imagen aquí] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [ingrese la descripción de la imagen aquí] [4]] [4]
Esto definitivamente no es correcto.
¿Qué salió mal?
Comentarios
- Nota: Todas las imágenes de la publicación parecen haber desaparecido. ¿Tiene el autor los originales?
Respuesta
De hecho, ha estado en lo correcto todo el tiempo . Sin embargo, aún no ha terminado el algoritmo de Christofides.
El siguiente paso es «Calcular el recorrido de Euler».
En la última imagen , ha obtenido un multigraph cuyos vértices tienen grados pares. Entonces debe tener un camino euleriano. Por ejemplo, seleccionemos la ruta euleriana A -> F -> A -> C -> B -> D -> E -> D -> A.
El último paso es «Eliminar vértices repetidos , dando el algoritmo «salida».
Eliminando la segunda A y la segunda D en la ruta anterior, obtenemos una salida deseada, A -> F -> C -> B -> D -> E -> A . Hecho.
Tenga en cuenta que no es muy significativo aplicar el algoritmo de Christofides en el gráfico dado.
«El algoritmo de Christofides es un algoritmo para encontrar soluciones aproximadas a el problema del vendedor ambulante , en casos en los que las distancias forman un espacio métrico (son simétricas y obedecen la desigualdad del triángulo «. Las distancias dadas no obedecen a la desigualdad del triángulo, ya que d (B, D) + d (D, E) = 1 + 4 < 6 = d (B , E). Además, la distancia (directa) entre A y B no se da, lo que genera dudas sobre si se trata de un problema de viajante.
Comentarios
- Soy nuevo en esto, ¡así que gracias por las notas al margen! Tengo algunas preguntas: 1. ¿Es necesario que cada vértice esté conectado entre sí para que sea un TSP válido? Quiero decir que todavía es posible crear una ruta " TSP " incluso sin esa ruta, así que diría que es válida, pero Me he equivocado antes. 2. ¿Piensas (o sabes) si es posible aumentar los pesos de algunos de los vértices de mi gráfica de tal manera que obedezca a la desigualdad del triángulo ? Creo que los gráficos más desordenados son mejores para representar escenarios de mapas del mundo real, que ' es la razón por la que lo creé tal como está.
- 1. Puede tratarlo como un TSP si asume, por ejemplo, que todas las distancias directas que faltan entre ciudades son suficientemente grandes o simplemente infinitas. De esa manera, esas distancias faltantes no afectarán la solución. Sin embargo, todavía no es un espacio métrico. 2. Para obedecer la desigualdad del triángulo, puede agregar 10 a cada distancia que haya especificado y dejar que todas las distancias faltantes sean 20.
- Esto no es cierto: " En la última imagen , ha obtenido un multigraph cuyos vértices tienen grados pares. ": los vértices E, D, A y F tienen un grado impar.
- " Has obtenido un multigraph ", un gráfico que puede tener varios bordes, es decir, bordes que tienen el mismo nodos finales. Hay dos bordes entre D y E. Hay dos bordes entre A y F.
- También puede consultar el ejemplo en Wikipedia . " Esa no es una ruta euleriana ya que visita un vértice más de una vez en esa ruta ". El camino euleriano consiste en visitar cada borde exactamente una vez. Estás hablando del camino hamiltoniano.
Deja una respuesta