Ayuda pseudocodigo viajante de comercio y problemas de grafos

[chio_maga]

Alguien puede ayudarme?
Tengo que hacer el pseudocódigo de este problema de Computación:

Un grupo de 5 amigos se suben a un taxi.
Le dicen al taxista la dirección de cada uno para que los reparta.
El taxista sabe calcular la distancia entre cada una de esas direcciones.
Escriba un programa que ingresando las distancias entre las direcciones sirva al taxista para calcular el orden en que deben ser repartidos cada uno de los pasajeros si desea hacer el menor recorrido El programa debe estar bien modularizado.

En la materia vimos estructuras repetitivas, estructuras condicionales, ciclos, vectores y matrices.
Ya hice la carga de datos con 6 "for" anidados como me dijo el profesor, tambien hice la validacion de datos.. Pero no se como seguir..
Muchas gracias!

[César Krall]

El problema que indicas se parece mucho a un problema tipo "camino de coste mínimo" que se resuelve con un algoritmo bien conocido: el algoritmo de Dijkstra. También hay otro algoritmo que podría tener cierta similitud: el algoritmo de Prim (o alternativamente el de Kruskal) para determinar árboles de recubrimiento mínimo en grafos.

Aquí tienes una imagen que explica cómo se resuelve el algoritmo de Dijkstra. Puedes considerar que el punto 1 es el punto donde se encuentra el taxi, mientras que los puntos 2, 3, 4, 5 y 6 son los puntos de destino de los viajeros, es decir, los puntos a los que debe llegar el taxista recorriendo la mínima distancia posible. En realidad el algoritmo no está planteado para visitar todos los nodos, sino para ir de un nodo a otro con el coste mínimo (en la imagen el objetivo es ir del nodo 1 al 5 con coste mínimo). Esto podría modificarse para una vez alcanzado el nodo de destino, fijar como nuevo destino un nodo no visitado... y así hasta visitarlos todos.

Si te fijas en la imagen verás la lógica del algoritmo. Los nodos se dividen en dos grupos: por una lado los que ya están en el recorrido (seleccionados) y por otro lado los que todavía no están en el recorrido. Inicialmente el único nodo en el recorrido es el nodo 1. Desde el punto 1 se evalúan los nodos adyacentes que no estén en el recorrido y se elige aquel que se encuentra a una menor distancia. Ese nodo pasa a ser el nodo actual y ya forma parte del conjunto de nodos del recorrido. Seguidamente se repite el proceso, siempre hay que tener en cuenta qué nodos están en el recorrido y cuáles no ya que no puedes volver a tomar un nodo que ya esté en el recorrido.

El algoritmo de Prim (o el de Kruskal) lo que te dice es dado un conjunto de nodos, cuál es el conjunto de aristas o conexiones entre nodos que suman el coste mínimo. En esta imagen se ve:

De todas formas antes de plantear el algoritmo pienso que debe estar claro cuáles son los datos del problema. Tal y como yo lo veo los datos sería las distancias entre los puntos que se ven en la imagen que pongo como archivo adjunto (mira ese archivo), es decir, tendrías 10 datos de distancias. Con esos 10 datos de distancias, tendrías que definir cuáles son los movimientos que debería hacer el taxista para recorrer la menor distancia posible.

Si se confirma que estos son los datos, a partir de ahí puedes empezar a pensar en el algoritmo para solucionarlo.

[chio_maga]

Muchas gracias!

[César Krall]

He vuelto a revisarlo y creo que aunque los problemas anteriores están relacionados el que mejor se ajusta a lo que te piden es otro problema conocido: "El problema del viajante de comercio". El enunciado de este problema es aproximadamente este: Sean N ciudades de un territorio, el objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades y minimice la distancia recorrida por el viajante.

La distancia entre cada ciudad viene dada por la matriz D: N*N, donde d[x,y], representa la distancia que hay entre la ciudad x y la ciudad y.

En tu caso podemos considerar que tienes 6 ciudades (6 puntos, uno que es donde se encuentra el taxi al que podemos denominar punto 0 y 5 puntos que es donde tienes que dejar a los viajeros que podemos denominar punto 1, punto 2, punto 3, punto 4 y punto 5).

Las distancias entre ciudades o puntos se pueden representar en un matriz como esta. Un 0 indica que del punto a sí mismo no hay distancia. Un 999 indica que las dos ciudades no están conectadas directamente por lo que simplemente ponemos una distancia muy grande. Entre el punto 0 y el punto 1 hay una distancia de 140 kms, mientras que entre la ciudad 4 y la 5 hay una distancia de 178 kms.

-	0	1	2	3	4	5
0	0	140	110	150	120	160
1	-	0	190	999	88	999
2	-	-	0	77	999	999
3	-	-	-	0	999	66
4	-	-	-	-	0	178
5	-	-	-	-	-	0

La segunda parte de la matriz no la rellenamos porque es simétrica, es decir, de la ciudad 1 a la 3 hay la misma distancia que de la 3 a la 1.

Ahora nos preguntamos. Partiendo del punto 0, ¿cuántos puntos puedo elegir para visitar (teóricamente)? Cinco puntos. Una vez elegido el primer punto, ¿cuántos puntos puedo elegir para visitar? Cuatro puntos (ya que no puedo volver a ningún punto por el que hubiera pasado previamente). Esto significa que para visitar las dos primeras ciudades o puntos puedo elegir entre 5*4 = 20 posibilidades distintas.

Al final resulta que para visitar los cinco puntos puedo elegir entre 5*4*3*2*1 posibilidades, que son 120 posibilidades, esto se expresa en matemáticas como 5! (5 factorial).

Y esto gracias a que tenemos el punto de origen definido (el taxi). Si tuviéramos que elegir también el punto de partida el número de posibilidades sería 6*5*4*3*2*1 (6 factorial).

Aunque no es una solución eficiente, para resolver el problema tendremos que comprobar el coste de todas las posibles combinaciones de formas de visitar puntos. Es decir, tendremos que evaluar como posibles itienerarios (dado que ya tenemos fijo que partimos del punto 0):

0123450: para este itinerario la distancia a recorrer es d[0,1] + d[1,2] +d[2,3]+d[3,4]+d[4,5]+d[5,0]
0213450
0312350
0412350
0512340
0132450
0142350
0152340
0213450
0231450
0241350
0251340
0312450
...
...
así hasta 120 posibilidades

Entre esas 120 posibilidades, hay que elegir la que suponga una menor suma de distancias.

[chio_maga]

Muchas gracias!.. Será necesario que también ingrese la dirección de cada pasajero? O lo complicará más?

[César Krall]

No le veo ningún problema a que se incluya la dirección de cada pasajero. Aunque eso es un dato que sería relevante en el mundo real, para el algoritmo la dirección no tiene relevancia y por tanto no es necesario, ya que con lo que trabaja el algoritmo es con las distancias, pero si se quiere poner no le veo problema. Bastaría con que definas calle(0) = "Calle Velázquez, 55", calle(1) = "Avenida Libertad, 22", calle(2) = "Calle Albuero, 355", calle(3) = "... " etc. etc.

[chio_maga]

Muchas gracias. Ya he planteado el pseudocodigo para la carga de datos, pero todavía no entiendo como se puede plantear el pseudocodigo para calcular cual sería el menor recorrido. Entendí muy bien como lo explicaste pero no puedo comenzar a plantear esa parte.

[César Krall]

Escribe el pseudocódigo hasta donde hayas llegado para tratar de ayudarte a partir de ahí. Saludos.

[chio_maga]

Bueno, este es el pseudocódigo de la carga de datos.

Procedimiento CARGA_DATOS (A: DISTANCIAS)
Var I, J, K: entero;
Inicio
   Para I ← 1 hasta 6 hacer
     Para J ← 1 hasta 6 hacer
        Si (I=J) o (I<J) entonces
           A[I,J] = 0
          sino
            Si (I>J) entonces
         Imprimir (‘Ingrese la distancia del punto ,’I,’ al punto ,’J);
         Leer (A[I,J])
            Fin_Si;   
      Fin_si;
     Fin_para;
   Fin_para;
Fin_procedimiento.

[César Krall]

En el pseudocódigo que has planteado queda definida la matriz de adyacencia del grafo que representa el problema con la mitad de los datos, ya que la otra mitad es igual y por tanto no hace falta introducirla. Por ejemplo para este grafo:

Voy a ir planteando el problema con la solución que conozco, que es basada en grafos y ramificación y poda, esto es una solución compleja, se supone que se deben tener conocimientos previos.

Por si te sirvieran, aquí algunas referencias de wikipedia:

Sobre el problema en sí: http://es.wikipedia.org/wiki/Problema_del_viajante

Sobre la estrategia algorítmica: http://es.wikipedia.org/wiki/Ramificaci%C3%B3n_y_poda

Con la solución que conozco, partiríamos de la matriz de adyacencia completa, aunque tenga los datos repetidos (se supone que de la introducción de datos se ha encargado un programa o función previa)

El pseudocódigo de carga de datos quedaría así:

Función CARGA_DATOS () : matriz [1..n, 1..n] de enteros
Var grafo: matriz [1..n, 1..n] de enteros
Var i, j: entero;
Inicio
   Para i ← 1 hasta 6 hacer
     Para j ← 1 hasta 6 hacer
         Leer (A[i,j])
     Fin_para;
   Fin_para;
Devolver grafo
Fin_función.

Para el grafo de la imagen anterior (suponiendo que la letra A es 1, la letra B 2, la letra C 3, la letra 4 D) la matriz quedaría así:

(0   20   42   35

 20   0   30   34

 42   30   0   12

 35   34   12   0)

De forma que grafo[1,1] representa la distancia del punto 1 al punto 1, que es cero. grafo [1,2] representa la distancia del punto 1 al punto 2 que es 20, grafo[1,3] representa la distancia del punto 1 al punto 3 que es 42 y así sucesivamente.

El valor -1 significa que entre dos nodos del grafo no hay camino. Por ejemplo en este grafo:

tendríamos que grafo[1,4] = -1

¿Por qué coger el valor -1? Pues no hay un motivo concreto, también podríamos coger 0 ó coger -22 ó -99, simplemente es un valor que permita distinguir.

Para empezar a plantear el problema harían falta estructuras de datos auxiliares que permitan plantear el algoritmo. En esta solución usaríamos:

tipo Tnodo = registro
    ruta = Tvector //Sirve para almacenar la solución parcial
    asignados: TvectorB //vector de booleanos que indica los nodos del grafo que ya están incluidos en un camino que se está probando
    k: entero //índice de número de elemento fijado en la ruta para este nodo
    costeT: entero //Coste acumulado
    estOpt: entero //Estimación optimista de mejor coste que se puede obtener a partir de la ruta
finRegistro

Supuesto el grafo que tiene 6 nodos anterior y que la ruta que estamos probando es 1, 2, 4. Los elementos del tipo registro serían:

ruta = [1, 2, 4, - , -, -]
asignados = [1, 1, 0, 0, 0, 1]
k: 3
costeT: 7+15 = 22
estOpt: un valor seguro se obtiene multiplicando el número de aristas que faltan por el peso mínimo de una arista en el grafo. Para cerrar un ciclo hacen falta tantas aristas como vértices, en este caso 6. Tenemos definidias 2 aristas (de 1 a 2 y de 2 a 4).
Nos faltan 4 aristas para completar el recorrido, así que viendo cuál es la arista de peso mínimo en el grafo la estimación optimista sería 4*2 = 8

Nos hace falta una función para calcular la arista de peso mínimo en el grafo. Intenta plantearla, no sé si me estoy enrollando mucho.

[chio_maga]

En la materia no hemos estudiado los registros, nos han pedido que lo resolvamos con lo que hemos aprendido, que dije anteriormente: estructuras repetitivas y condicionales, ciclos, vectores y matrices

[Alex Rodríguez]

Puedes intentar resolverlo con un algoritmo iterativo que construya todas las posibles combinaciones de caminos que partiendo de un punto visite a todos los demás. Creo que en este caso no es necesario que vuelva al punto inicial porque el enunciado no dice nada sobre eso, simplemente indica que tiene que repartir a todos los pasajeros.

[chio_maga]

Muchas gracias, pero solo necesito saber como plantear en pseudocodigo los itinerarios que Cesar Krall me habia explicado anteriormente

[César Krall]

Aquí dejo un primer boceto de pseudocódigo, no he tenido tiempo de probarlo pero pienso que se puede adaptar a lo que se pide:

Código: [Seleccionar]

Procedimiento CARGA_DATOS (d: DISTANCIAS)
Var i, j: entero;
Inicio
   Para i ← 1 hasta 6 hacer
     Para j ← 1 hasta 6 hacer
         Imprimir (‘Ingrese la distancia del punto ,’i,’ al punto ,’j);
         Leer (d[i,j])   
      Fin_si;
     Fin_para;
   Fin_para;
Fin_procedimiento.

Procedimiento CALCULA_RUTA_VIAJANTE_COMERCIO (ruta: vector de enteros)
Var i, j, k, m, n, p, MINIMO: entero;
Var incluye(), d(), c(), ruta(): array de entero;

MINIMO = 9999;
Desde i = 1 hast (n-1)!
incluye(i,1) = 1
FinDesde

i = 1

Desde j = 2 hasta 6
Si incluye(i,j) = 0 entonces
incluye(i,j) = 1
c(i) = c(i) + d(1,j)
FinSi

Desde k = 2 hasta 6
Si incluye(i,k) = 0 entonces
incluye(i,k) = 1
c(i) = c(i) + d(j,k)
FinSi

Desde m = 2 hasta 6
Si incluye(i,m) = 0 entonces
incluye(i,m) = 1
c(i) = c(i) + d(k,m)
FinSi

Desde n = 2 hasta 6
Si incluye(i,n) = 0 entonces
incluye(i,n) = 1
c(i) = c(i) + d(m,n)
FinSi

Desde p = 2 hasta 6
Si incluye(i,p) = 0 entonces
incluye(i,p) = 1
c(i) = c(i) + d(n,p)
FinSi

//Sumar coste de regresar al inicio
c(i) = c(i) + d(p, 1)

Si c(i) < MINIMO entonces
ruta(1) = 1
ruta(2) = j
ruta(3) = k
ruta(4) = m
ruta(5) = n
ruta(6) = p
ruta(7) = 1
FinSi
i = i+1

Findesde
Findesde
Findesde
findesde
Findesde
Fin_procedimiento.