6.6: Los circuitos hamiltonianos y el problema del vendedor ambulante
- Page ID
- 110627
En la última sección, consideramos optimizar una ruta a pie para un transportista postal. ¿En qué se diferencia esto de los requisitos de un conductor de entrega de paquetes? Si bien el transportista postal necesitaba caminar por cada calle (borde) para entregar el correo, el conductor de entrega de paquetes necesita visitar cada uno de un conjunto de ubicaciones de entrega. En lugar de buscar un circuito que cubra cada borde una vez, el repartidor de paquetes está interesado en un circuito que visita cada vértice una vez.
Un circuito hamiltoniano es un circuito que visita cada vértice una vez sin repeticiones. Al ser un circuito, debe comenzar y terminar en el mismo vértice. Un camino hamiltoniano también visita cada vértice una vez sin repeticiones, pero no tiene que comenzar y terminar en el mismo vértice.
Los circuitos hamiltonianos llevan el nombre de William Rowan Hamilton, quien los estudió en la década de 1800.
Un circuito hamiltoniano se muestra en la gráfica a continuación. Hay varios otros circuitos hamiltonianos posibles en esta gráfica. Observe que el circuito solo tiene que visitar cada vértice una vez; no necesita usar todos los bordes.
Solución
Este circuito podría ser anotado por la secuencia de vértices visitados, comenzando y terminando en el mismo vértice: ABFGCDHMLKJEA. Observe que el mismo circuito podría escribirse en orden inverso, o comenzando y terminando en un vértice diferente.
A diferencia de los circuitos de Euler, no existe un teorema agradable que nos permita determinar instantáneamente si existe o no un circuito hamiltoniano para todas las gráficas. [1]
¿Existe un camino o circuito hamiltoniano en la siguiente gráfica?
Solución
Podemos ver que una vez que viajamos al vértice E no hay manera de salir sin regresar a C, por lo que no hay posibilidad de un circuito hamiltoniano. Si partimos en el vértice E podemos encontrar varios caminos hamiltonianos, como ECDAB y ECABD.
Con los circuitos hamiltonianos, nuestro foco no estará en la existencia, sino en la cuestión de la optimización; dada una gráfica donde los bordes tengan pesos, podemos encontrar el circuito hamiltoniano óptimo; el de menor peso total.
Este problema se llama el problema del vendedor ambulante (TSP) porque la pregunta se puede enmarcar así: Supongamos que un vendedor necesita dar argumentos de venta en cuatro ciudades. Busca las tarifas aéreas entre cada ciudad, y pone los costos en una gráfica. ¿En qué orden debe viajar para visitar cada ciudad una vez y luego regresar a casa con el menor costo?
Para responder a esta pregunta de cómo encontrar el circuito hamiltoniano de menor costo, consideraremos algunos enfoques posibles. La primera opción que podría venir a la mente es simplemente probar todos los diferentes circuitos posibles.
- Listar todos los circuitos hamiltonianos posibles
- Encuentra la longitud de cada circuito agregando los pesos de borde
- Seleccione el circuito con peso total mínimo.
Aplica el algoritmo de fuerza bruta para encontrar el costo mínimo circuito hamiltoniano en la gráfica de abajo.
Solución
Para aplicar el algoritmo de fuerza bruta, enumeramos todos los circuitos hamiltonianos posibles y calculamos su peso:
\ (\ begin {array} {|l|l|}
\ hline\ textbf {Circuito} &\ textbf {Peso}\\\ hline\ texto {ABCDA} & 4+13+8+1 = 26\\ hline\ texto {ABDCA} & 4+9+8+2=23
\\ hline\ text {ACBDA} & 2+13+9+9+9=23\\ hline
\ text {ACBDA} & 2+13+9+9+9=23\\ hline\ text {1=25\
\\ hline
\ end {
matriz}\)
Nota: Estos son los circuitos únicos en esta gráfica. Todos los demás circuitos posibles son el reverso de los enumerados o comienzan en un vértice diferente, pero dan como resultado los mismos pesos.
De esto podemos ver que el segundo circuito, ABDCA, es el circuito óptimo.
El algoritmo de fuerza bruta es óptimo; siempre producirá el circuito hamiltoniano con peso mínimo. ¿Es eficiente? Para responder a esa pregunta, debemos considerar cuántos circuitos hamiltonianos podría tener una gráfica. Para simplificar, veamos la posibilidad en el peor de los casos, donde cada vértice está conectado a cada otro vértice. A esto se le llama una gráfica completa.
Supongamos que teníamos una gráfica completa con cinco vértices como la gráfica de viajes aéreos de arriba. Desde Seattle hay cuatro ciudades que podemos visitar primero. De cada una de esas, hay tres opciones. De cada una de esas ciudades, hay dos posibles ciudades para visitar a continuación. Entonces solo hay una opción para la última ciudad antes de regresar a casa.
Esto se puede mostrar visualmente:
Contando el número de rutas, podemos ver que hay\(4 \cdot 3 \cdot 2 \cdot 1=24\) rutas. Para seis ciudades habría\(5 \cdot 4 \cdot 3 \cdot 2 \cdot 1=120\) rutas.
Para\(n\) los vértices en una gráfica completa, habrá\((n-1) !=(n-1)(n-2)(n-3) \cdots 3 \cdot 2 \cdot 1\) rutas. La mitad de estos son duplicados en orden inverso, por lo que hay circuitos\(\frac{(n-1) !}{2}\) únicos.
El símbolo de exclamación,! , se lee “factorial” y es la taquigrafía del producto mostrado.
¿Cuántos circuitos tendría una gráfica completa con 8 vértices?
Solución
Una gráfica completa con 8 vértices tendría\((8-1) !=7 !=7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1=5040\) posibles circuitos hamiltonianos. La mitad de los circuitos son duplicados de otros circuitos pero en orden inverso, dejando 2520 rutas únicas.
Si bien esto es mucho, no parece irrazonablemente enorme. Pero considere lo que sucede a medida que aumenta el número de ciudades:
\ (\ begin {array} {|l|l|}
\ hline\ textbf {Ciudades} &\ textbf {Circuitos Hamiltonianos Únicos}\\
\ hline ¡9 y 8! /2=20,160\\
\ hline ¡10 y 9! /2=181,440\\
\ hline ¡11 y 10! /2=1,814,400\
\ hline ¡15 y 14! /2=43,589,145,600\
\ hline ¡20 y 19! /2=60,822,550,204,416,000\
\ hline
\ end {array}\)
Como puede ver el número de circuitos está creciendo de manera extremadamente rápida. Si una computadora mirara mil millones de circuitos por segundo, ¡todavía tardaría casi dos años en examinar todos los circuitos posibles con solo 20 ciudades! Ciertamente, la Fuerza Bruta no es un algoritmo eficiente.
Desafortunadamente, nadie ha encontrado todavía un algoritmo eficiente y óptimo para resolver el TSP, y es muy poco probable que alguien alguna vez lo haga. Como no es práctico usar la fuerza bruta para resolver el problema, recurrimos en cambio a algoritmos heurísticos; algoritmos eficientes que dan soluciones aproximadas. En otras palabras, los algoritmos heurísticos son rápidos, pero pueden o no producir el circuito óptimo.
- Seleccione un punto de partida.
- Muévase al vértice no visitado más cercano (el borde con menor peso).
- Repita hasta que el circuito esté completo.
Considera nuestra gráfica anterior, que se muestra a la derecha.
Comenzando en el vértice A, el vecino más cercano es el vértice D con un peso de 1.
De D, el vecino más cercano es C, con un peso de 8.
Desde C, nuestra única opción es pasar al vértice B, el único vértice no visitado, con un costo de 13.
De B volvemos a A con un peso de 4.
Solución
El circuito resultante es ADCBA con un peso total de\(1+8+13+4 = 26\).
¡Terminamos encontrando el peor circuito en la gráfica! ¿Qué pasó? Desafortunadamente, si bien es muy fácil de implementar, el NNA es un algoritmo codicioso, es decir, solo mira la decisión inmediata sin considerar las consecuencias en el futuro. En este caso, siguiendo el borde AD nos obligó a usar el borde muy caro BC más tarde.
Considera de nuevo a nuestro vendedor. Comenzando en Seattle, el vecino más cercano (vuelo más barato) es a Los Ángeles, con un costo de $70. A partir de ahí:
Solución
- Los Ángeles a Chicago: $100
- Chicago a Atlanta: $75
- Atlanta a Dallas: $85
- Dallas a Seattle: $120
Costo total: $450
En este caso, el vecino más cercano sí encontró el circuito óptimo.
Volviendo a nuestro primer ejemplo, ¿cómo podríamos mejorar el resultado? Una opción sería rehacer el algoritmo vecino más cercano con un punto de partida diferente para ver si el resultado cambió. Dado que el vecino más cercano es tan rápido, hacerlo varias veces no es gran cosa.
- Hacer el algoritmo de vecino más cercano comenzando en cada vértice
- Elija el circuito producido con un peso total mínimo
Volveremos a visitar la gráfica del Ejemplo 17.
Comenzando en el vértice A resultó en un circuito con peso 26.
Comenzando en el vértice B, el circuito vecino más cercano es BADCB con un peso de 4+1+8+13 = 26. Este es el mismo circuito que encontramos comenzando en el vértice A. No mejor.
Comenzando en el vértice C, el circuito vecino más cercano es CADBC con un peso de 2+1+9+13 = 25. ¡Mejor!
Comenzando en el vértice D, el circuito vecino más cercano es DACBA. Observe que este es en realidad el mismo circuito que encontramos comenzando en C, recién escrito con un vértice inicial diferente.
Solución
El RNNA pudo producir un circuito ligeramente mejor con un peso de 25, pero aún así no el circuito óptimo en este caso. Observe que a pesar de que encontramos el circuito iniciando en el vértice C, aún podríamos escribir el circuito comenzando en A: ADBCA o ACBDA.
La siguiente tabla muestra el tiempo, en milisegundos, que se tarda en enviar un paquete de datos entre computadoras en una red. Si los datos necesitaban ser enviados en secuencia a cada computadora, entonces la notificación necesitaba regresar a la computadora original, estaríamos resolviendo el TSP. Las computadoras están etiquetadas A-F para mayor comodidad.
\ (\ begin {array} {|l|l|l|l|l|l|l|l|}
\ hline &\ mathrm {A} &\ mathrm {B} &\ mathrm {C} &\ mathrm {D} &\ mathrm {E} &\ mathrm {F}\
\\ hline\ mathrm {A} &\ _ &\ _ & 44 & 34 y 12 y 40 41\\
\ hline\ mathrm {B} & 44 &\ _\ _ & 31 & 43 & 24 & 50\
\ hline\ mathrm {C} & 34 & 31 &\ _\ _ & 20 & 39 & 27\
\ hline\ mathrm {D} & 12 & 43 & 20 &\ _\ _ & 11 & 17\\ hline
\\ mathrm {E} & 40 & 24 & 39 & 11 &\ _\ _ & 42\\
\ hline\ mathrm {F} & 41 & 50 & 27 & 17 & 42 &\ _\ _\
\ hline
\ end {array}\)
a. Encuentra el circuito generado por el NNA comenzando en el vértice B.
b. Encontrar el circuito generado por el RNNA.
- Contestar
-
En cada paso, buscamos la ubicación más cercana que aún no hemos visitado.
De B la computadora más cercana es E con tiempo 24.
De E, la computadora más cercana es D con tiempo 11.
De D el más cercano es A con tiempo 12.
De A lo más cercano es C con el tiempo 34.
Desde C, la única computadora que no hemos visitado es F con tiempo 27
De F, regresamos a B con tiempo 50.
El circuito NNA de B es BEDACFB con tiempo 158 milisegundos.
Si bien ciertamente mejor que el NNA básico, desafortunadamente, el RNNA sigue siendo codicioso y producirá muy malos resultados para algunas gráficas. Como alternativa, nuestro siguiente enfoque dará un paso atrás y mirará el “panorama general” — seleccionará primero los bordes que son más cortos, y luego rellenará los huecos.
1. Seleccione el borde no utilizado más barato en la gráfica.
2. Repita el paso 1, agregando el borde no utilizado más barato al circuito, a menos que:
a. agregar el borde crearía un circuito que no contiene todos los vértices, o
b. agregar el borde daría un grado de vértice 3.
3. Repita hasta que se forme un circuito que contenga todos los vértices.
Usando el gráfico de cuatro vértices de antes, podemos usar el algoritmo Bordes Ordenados.
Solución
El borde más barato es AD, con un costo de 1. Destacamos ese borde para marcarlo seleccionado.
El siguiente borde más corto es AC, con un peso de 2, por lo que destacamos ese borde.
Para el tercer borde, nos gustaría agregar AB, pero eso daría vértice A grado 3, que no está permitido en un circuito hamiltoniano. El siguiente borde más corto es CD, pero ese borde crearía un circuito ACDA que no incluya el vértice B, por lo que rechazamos ese borde. El siguiente borde más corto es BD, por lo que agregamos ese borde a la gráfica.
Después agregamos el último borde para completar el circuito: ACBDA con peso 25.
Observe que el algoritmo no produjo el circuito óptimo en este caso; el circuito óptimo es ACDBA con peso 23.
Si bien el algoritmo de Borde Ordenado supera algunas de las deficiencias de NNA, sigue siendo solo un algoritmo heurístico, y no garantiza el circuito óptimo.
La banda de tu profesor, Derivative Work, está haciendo una gira de bares en Oregón. Las distancias de manejo se muestran a continuación. Planifica una ruta eficiente para que tu profesor visite todas las ciudades y regrese al lugar de partida. Use NNA a partir de Portland y luego use Bordes Ordenados.
\ (\ begin {array} {|c|c|c|c|c|c|c|c|c|c|c|c|}
\ hline & & & & &
& & & & & & & & & &\ texto {Ashland} &\ texto {Astoria} &\ texto {Curva} &\ texto {Corvallis} &\ texto {Newport} & amp;\ text {Portland} &\ texto {Salem} &\ texto {Mar}\\
\ hline\ texto {Ashland} &\ _ & 374 & 200 & 223 & 108 & 178 & 252 & 285 & 240 & 356\
\ hline\ texto {Astoria} & 374 &\ _ & 255 & 166 & 433 & 199 & 135 & 95 & 136 & 17\
\ hline\\ hline\ text {Curva} & 200 & 255 &\ _ & 128 & 277 & 128 & 180 & 160 & 131 & 247
\\ hline\ texto {Corvallis} & 223 & 166 & 128 &\ _ & 430 & 47 & 52 & 84 y 40 & 155\
\ hline\ text {Lago del cráter} & 108 & 433 & 277 & 430 &\ _ & 453 & 478 & 344 & 389 & 423\\
\ hline\ texto {Eugene} & 178 & 199 & 128 & 47 & 453 &\ _ & 91 & 110 & 64 & 181\\
\ hline\ text {Newport} & 252 & 135 & 180 & 52 & 478 & 91 &\ _ & 114 & 83 & 117\\
\ hline\ text {Portland} & 285 & 95 & 160 & 84 & 344 & 110 & 114 &\ _ & 47 & 78\
\ hline\ texto {Salem} & 240 y 136 & 131 & 40 & 389 & 64 & 83 & 47 &\ _ & 118\\
\ hline\ text {Seaside} & 356 & 17 & 247 & 155 & 423 & 181 & 117 & 78 & 118 &\ _\
\ hline
\ end {array}\)
Solución
Al usar NNA con una gran cantidad de ciudades, puede resultarle útil marcar las ciudades mientras son visitadas para evitar visitarlas de nuevo por error. Buscando en fila a Portland, la distancia más pequeña es de 47, a Salem. Siguiendo esa idea, nuestro circuito será:
\(\begin{array} {ll} \text{Portland to Salem} & 47 \\ \text{Salem to Corvallis} & 40 \\ \text{Corvallis to Eugene} & 47 \\ \text{Eugene to Newport} & 91 \\ \text{Newport to Seaside} & 117 \\ \text{Seaside to Astoria} & 17 \\ \text{Astoria to Bend} & 255 \\ \text{Bend to Ashland} & 200 \\ \text{Ashland to Crater Lake} & 108 \\ \text{Crater Lake to Portland} & 344 \\ \text{Total trip length: } & 1266\text{ miles} \end{array} \)
Usando Bordes Ordenados, puede resultarle útil dibujar una gráfica vacía, tal vez dibujando vértices en un patrón circular. Agregar bordes a la gráfica a medida que los selecciona te ayudará a visualizar cualquier circuito o vértice con grado 3.
Empezamos a sumar los bordes más cortos:
\(\begin{array} {ll} \text{Seaside to Astoria} & 17\text{ miles} \\ \text{Corvallis to Salem} & 40\text{ miles} \\ \text{Portland to Salem} & 47\text{ miles} \\ \text{Corvallis to Eugene} & 47\text{ miles} \end{array} \)
El gráfico después de agregar estos bordes se muestra a la derecha. El siguiente borde más corto es de Corvallis a Newport a 52 millas, pero agregar ese borde le daría a Corvallis grado 3.
Continuando, podemos saltarnos cualquier par de borde que contenga Salem o Corvallis, ya que ambos ya tienen grado 2.
\(\begin{array} {ll} \text{Portland to Seaside} & 78\text{ miles} \\ \text{Eugene to Newport} & 91\text{ miles} \\ \text{Portland to Astoria} & \text{(reject – closes circuit)} \\ \text{Ashland to Crater Lk 108 miles} & \end{array} \)
El gráfico después de agregar estos bordes se muestra a la derecha. En este punto, podemos saltarnos cualquier par de borde que contenga Salem, Seaside, Eugene, Portland o Corvallis ya que ya tienen grado 2.
\(\begin{array} {ll} \text{Newport to Astoria} & \text{(reject – closes circuit)} \\ \text{Newport to Bend} & 180\text{ miles} \\ \text{Bend to Ashland} & 200\text{ miles} \end{array} \)
En este punto la única forma de completar el circuito es agregar:
Crater Lk a Astoria 433 millas
El circuito final, escrito para comenzar en Portland, es:
Portland, Salem, Corvallis, Eugene, Newport, Bend, Ashland, Lago del cráter, Astoria, Costa, Portland.
Duración total del viaje: 1241 millas.
Si bien fue mejor que la ruta NNA, ninguno de los algoritmos produjo la ruta óptima. La siguiente ruta puede hacer el recorrido en 1069 millas:
Portland, Astoria, Junto al mar, Newport, Corvallis, Eugene, Ashland, Lago del cráter, curva, Salem, Portland
Encuentra el circuito producido por el algoritmo Bordes Ordenados usando la gráfica a continuación.
- Contestar
-
AB: Agregar, costo 11
BG: Agregar, costo 13
AE: Agregar, costo 14
EF: Agregar, costo 15EC: Skip (grado 3 en E)
FG: Skip (crearía un circuito sin incluir C)
BF, BC, AG, AC: Omitir (causaría que un vértice tenga grado 3)
GC: Agregar, costo 36
CF: Agregar, costo 37, completa el circuito
Circuito final: ABGCFEA
[1] Existen algunos teoremas que se pueden utilizar en circunstancias específicas, como el teorema de Dirac, que dice que un circuito hamiltoniano debe existir en una gráfica con n vértices si cada vértice tiene grado n /2 o mayor.