Estructuras de Datos - I.T.Informática Gestión

Curso 01/02 - Segunda Práctica

7/10/2002: Añadida sección Solución de la práctica

Atención: Añadida sección Comentarios sobre la práctica

Uno de los problemas más famosos en ciencias de cómputo es el problema del viajante, que consiste en encontrar la ruta óptima (aquella que minimiza la distancia recorrida) para recorrer un conjunto de n ciudades (representadas por puntos en un plano bidimensional) de manera que sólo se pase una vez por cada una ciudad y se regrese al punto de partida (esto es, se recorra un ciclo). Aunque sencillo de enunciar, se cree que éste problema no se puede resolver en un tiempo polinómico, y que no existe una solución mucho mejor que la de enumerar las n! rutas posibles y escoger la óptima.

Sin embargo, es posible (o no) que la siguiente variante del problema, que denominaremos problema restringido del viajante, admita una solución más eficiente. En el problema restringido se exige que las ciudades se presenten ordenadas por la coordenada horizontal (es decir, la primera ciudad es la situada más al oeste y la última la situada más al este) y se añade la siguiente restricción que debe cumplir un ciclo para poder ser una solución del problema:

La ruta solución consta de dos partes, una ruta de ida y una ruta de vuelta:

• En la ruta de ida se va de la primera ciudad a la última, pasando por cero o más ciudades intermedias. Se exige que de una ciudad se pase siempre a otra con mayor coordenada horizontal (situada más al este).
• En la ruta de vuelta se va de última ciudad a la primera, pasando por cero o más ciudades intermedias. Se exige que de una ciudad se pase siempre a otra con menor coordenada horizontal (situada más al oeste).

La ruta solución consistirá en unir la ruta de ida a la ruta de vuelta, obteniendo un ciclo que parte de la primera ciudad y termina en ella. Claramente, una ciudad distinta a la primera o la última debe pertenecer o bien a la ruta de ida o bien a la de vuelta.

Ejemplo: En la figura 1 se muestra un conjunto de puntos correspondientes a las capitales de Castilla y León. El orden de las ciudades sería ZA-SA-LE-VA-AV-P-SG-BU-SO (coordenada horizontal creciente). En las figuras 2 y 3 se muestran dos posibles soluciones del problema restringido, en la figura 2 todas las ciudades entre la primera (ZA) y la última (SO) pertenecen a la ruta de ida, y ninguna a la de vuelta. En la figura 3 se presenta la solución óptima, con un ciclo de 861.8 Km., en la cual las ciudades LE-VA-P-BU pertenecen a la ruta de ida y SG-AV-SA a la de vuelta.

Fig. 1	Fig. 2	Fig. 3

La práctica consistirá en crear un algoritmo que encuentre la ruta óptima del problema restringido del viajante aplicando la estrategia de diseño de algoritmos más conveniente para este problema. La calificación dependerá, entre otras cosas, de la eficiencia del algoritmo obtenido. Se deberá entregar la siguiente documentación:

• Una breve descripción de la estrategia aplicada y de las características y orden de complejidad del algoritmo obtenido. Si no se pudiera evaluar teóricamente la complejidad, efectuar un análisis experimental.
• Un disquete (puede ser el mismo que el de la primera práctica) con un programa en Eiffel, Java o Delphi que implemente el algoritmo anterior (se puede suponer que el número de ciudades siempre será menor que 500).

Comentarios sobre la práctica

Datos de entrada:

• Se sugiere que los programas que resuelvan el problema pidan al usuario el número de puntos y a continuación pidan las coordenadas (x e y) de cada uno de ellos.
• No es necesario ordenar los puntos, se puede suponer que siempre se van a introducir en el orden adecuado (de menor a mayor coordenada x).
• Si fuera necesario se puede suponer que no hay dos puntos con el mismo valor de la coordenada x.
• No es necesario que cada punto lleve asociado un nombre. Al presentar la solución se hace referencia a cada punto por la posición en que se introdujo. En el ejemplo del enunciado Zamora sería el punto 1, Salamanca el 2, etc. La solución óptima ZA-LE-VA-P-BU-SO-SG-AV-SA-ZA se presentaría como:

 
1-3-4-6-8-9-7-5-2-1

Resultados:

• Si existieran varias rutas optimas distintas se puede presentar cualquiera de ellas como solución del problema. Es interesante indicar que, dada una ruta óptima, la ruta que se obtiene haciendo que los puntos de la ruta de ida pertenezcan a la ruta de vuelta y viceversa también es óptima. En el ejemplo anterior, esa otra ruta óptima sería:

 
1-2-5-7-9-8-6-4-3-1

Casos de prueba adicionales:

• Para probar vuestros algoritmos con otros conjuntos de puntos además del que aparece en el enunciado, asignar los puntos (x₁, y₁)...(x_n, y_n) mediante la fórmula:

 
x_i = sin(10007.0 * i),   y_i = sin(15013.0 * i)
Nota: En este caso tras obtener los puntos se deben ordenar por la coordenada horizontal.
Donde sin hace referencia a la función seno (en Eiffel esta función es un método de la clase DOUBLE). A continuación se muestra las longitudes de la ruta óptima para distintos valores de n:


n	distancia
2	4.723922
3	5.308505
5	5.939061
10	7.760661
50	16.700951
100	28.481801
500	44.155602



• Tambien podeis probar con los datos del siguiente fichero de texto, que contiene las posiciones de las capitales de provincia peninsulares. En este caso la ruta óptima es la siguiente: (su longitud es de 7315.949173 km)

Solución de la práctica

Notación

• En lo que sigue se va a suponer que las ciudades se proporcionan ordenadas de menor a mayor coordenada horizontal y que las coordenadas de las n ciudades se encuentran en los vectores x₁..x_n e y₁..y_n.

 
• Se supone definida la función dist(i,j) = raiz((x_i-x_j)²+(y_i-y_j)²), que calcula la distancia entre las ciudades i y j (lo habitual es precalcular esta función en una matriz).

 

Estructura de la solución

• Es vital darse cuenta que es posible indicar una ruta (y por lo tanto una posible solución) con solo decir para cada ciudad si pertenece a la ruta de ida o a la de vuelta. La primera y última ciudad se puede suponer que pertenecen a ambas rutas.

 
• Por lo tanto, para indicar una posible solución, se puede proporcionar el vector s₂..s_n-1, donde s_i=0 significa que la ciudad i pertenece a la ruta de ida y s_i=1 significa que la ciudad i pertenece a la ruta de vuelta.