EL PROBLEMA DEL AGENTE VIAJERO

Este problema se conoce ampliamente como problema del agenter viajero o como el problema de recorrido mínimo. El vendedor quiere reducir al mínimo el costo de viaje total (en tiempo o en distancia) requerido para visitar todas las ciudades de un territorio y volver al punto de partida. Otras aplicaciones incluyen la determinación de rutas para los camiones que recogen la basura o que entregan paquetes.

Formalmente descrito se dice que: Dado un grafo ponderado completo, hallar un ciclo hamiltoniano de peso mínimo, o bien, dado un grafo ponderado completo y un entero k, ¿existe un ciclo hamiltoniano cuyo peso total no sea mayor que k?

La versión tradicional trata el grafo como no dirigido; es decir, los pesos son iguales en ambos sentidos.

Nota: Un ciclo hamiltoniano es el que recorre todos los nodos del grafo sin pasar por un mismo nodo dos veces.

Estrategias.

Se conocen algoritmos para hallar árboles abarcadores mínimos en grafos ponderados no dirigidos (algoritmos de Prim y Kruskal), los cuales tienen variaciones naturales y fáciles para el problema del agente viajero.

El algoritmo de Prim principia en un vértice de inicio arbitrario y "cultiva" un árbol a partir de ese punto. En cada iteración del ciclo principal se escoge una arista que une un vértice del árbol con un vértice del borde, escogiendo la arista de menor costo.

El algoritmo de Kruskal en cambio, toma la arista de menor peso que quede en cualquier parte del grafo, en tanto no forme un ciclo con las aristas que ya se escogieron. El subgrafo formado por las aristas ya escogidas en cualquier punto del algoritmo de Kruskal podría no ser conectado, es un bosque , pero no necesariamente un árbol (antes del final).

Las estrategias correspondientes utilizando estos dos algoritmos para el problema del agente viajero se denominan estrategias del vecino más cercano y del eslabon más corto respectivamente.

Estrategia del vecino más cercano

En el algoritmo de Prim, cuando se selecciona una arista nueva podríamos estar tomando una rama que sale de cualquier vértice del árbol. Aquí estamos construyendo un ciclo, no un árbol, así que siempre tomamos una rama que sale del extremo del camino que hemos construido hasta ese momento. Al final, añadimos una arista que une el vértice con el vértice inicio, para completar el recorrido.

masCercano(V, E, W)

Seleccionar el vértice arbitrario s para iniciar el ciclo C

v = s;

Mientras haya vértices que aún no estén en C:

Seleccionar una arista vw de peso mínimo, donde w no está en C

Añadir la arista vw a C;

v = w;

Añadir la arista vs a C

return C;

Es fácil implementar este algoritmo con un tiempo de peor caso en O(n^2) para procesar un grafo de n vértices.

Estrategia del eslabón más corto

Para el caso de un grafo no dirigido, en cada iteración de su ciclo principal, la estrategia del eslabón más pequeño (al igual que en el algoritmo de Kruskal) toma una arista de peso mínimo de entre todas las aristas restantes en cualquier parte del grafo. Sin embargo la estrategia del eslabón más corto desechará esa arista si no es posible que pueda formar parte de un recorrido junto con las otras aristas que ya se escogieron. El subgrafo formado por las aristas ya escogidas en cualquier punto del algoritmo constituye una colección de caminos simples. No debe haber ciclos (antes del final) ni vértices en los que se incidan más de dos aristas escogidas. El algoritmo termina una vez que ha procesado todas las aristas.

eslabonMasCorto(V, E, W)

R = E; //R es las aristas restantes

C = vacío; //C es las aristas del ciclo

Mientras R no esté vacío:

Quitar la arista más ligera (más corta), vw, de R

Si vw no forma un ciclo con las aristas de C y vw no sería la tercera arista de C que incide en v o w:

Añadir vw a C;

//Continuar con el ciclo

Añadir la arista que conecta los extremos del camino que está en C

return C;

Podría hacerse que el ciclo while termine una vez que se hayan escogido n-1 aristas. Es fácil mantener una cuenta de las aristas seleccionadas que inciden en cada vértice, así que el tiempo de ejecución de la estrategia del eslabón más corto es similar al del algoritmo de Kruskal. ¿Cuál es este tiempo de ejecución?